initial check in

1 files changed, 187 insertions, 0 deletions

diff --git a/src/small_vector.h b/src/small_vector.h
new file mode 100644
index 00000000..800c1df1
--- /dev/null
+++ b/src/small_vector.h
@@ -0,0 +1,187 @@
+#ifndef _SMALL_VECTOR_H_
+
+#include <streambuf>  // std::max - where to get this?
+#include <cstring>
+#include <cassert>
+
+#define __SV_MAX_STATIC 2
+
+class SmallVector {
+
+ public:
+  SmallVector() : size_(0) {}
+
+  explicit SmallVector(size_t s, int v = 0) : size_(s) {
+    assert(s < 0x80);
+    if (s <= __SV_MAX_STATIC) {
+      for (int i = 0; i < s; ++i) data_.vals[i] = v;
+    } else {
+      capacity_ = s;
+      size_ = s;
+      data_.ptr = new int[s];
+      for (int i = 0; i < size_; ++i) data_.ptr[i] = v;
+    }
+  }
+
+  SmallVector(const SmallVector& o) : size_(o.size_) {
+    if (size_ <= __SV_MAX_STATIC) {
+      for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i];
+    } else {
+      capacity_ = size_ = o.size_;
+      data_.ptr = new int[capacity_];
+      std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(int));
+    }
+  }
+
+  const SmallVector& operator=(const SmallVector& o) {
+    if (size_ <= __SV_MAX_STATIC) {
+      if (o.size_ <= __SV_MAX_STATIC) {
+        size_ = o.size_;
+        for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i];
+      } else {
+        capacity_ = size_ = o.size_;
+        data_.ptr = new int[capacity_];
+        std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(int));
+      }
+    } else {
+      if (o.size_ <= __SV_MAX_STATIC) {
+        delete[] data_.ptr;
+        size_ = o.size_;
+        for (int i = 0; i < size_; ++i) data_.vals[i] = o.data_.vals[i];
+      } else {
+        if (capacity_ < o.size_) {
+          delete[] data_.ptr;
+          capacity_ = o.size_;
+          data_.ptr = new int[capacity_];
+        }
+        size_ = o.size_;
+        for (int i = 0; i < size_; ++i)
+          data_.ptr[i] = o.data_.ptr[i];
+      }
+    }
+    return *this;
+  }
+
+  ~SmallVector() {
+    if (size_ <= __SV_MAX_STATIC) return;
+    delete[] data_.ptr;
+  }
+
+  void clear() {
+    if (size_ > __SV_MAX_STATIC) {
+      delete[] data_.ptr;
+    }
+    size_ = 0;
+  }
+
+  bool empty() const { return size_ == 0; }
+  size_t size() const { return size_; }
+
+  inline void ensure_capacity(unsigned char min_size) {
+    assert(min_size > __SV_MAX_STATIC);
+    if (min_size < capacity_) return;
+    unsigned char new_cap = std::max(static_cast<unsigned char>(capacity_ << 1), min_size);
+    int* tmp = new int[new_cap];
+    std::memcpy(tmp, data_.ptr, capacity_ * sizeof(int));
+    delete[] data_.ptr;
+    data_.ptr = tmp;
+    capacity_ = new_cap;
+  }
+
+  inline void copy_vals_to_ptr() {
+    capacity_ = __SV_MAX_STATIC * 2;
+    int* tmp = new int[capacity_];
+    for (int i = 0; i < __SV_MAX_STATIC; ++i) tmp[i] = data_.vals[i];
+    data_.ptr = tmp;
+  }
+
+  inline void push_back(int v) {
+    if (size_ < __SV_MAX_STATIC) {
+      data_.vals[size_] = v;
+      ++size_;
+      return;
+    } else if (size_ == __SV_MAX_STATIC) {
+      copy_vals_to_ptr();
+    } else if (size_ == capacity_) {
+      ensure_capacity(size_ + 1);
+    }
+    data_.ptr[size_] = v;
+    ++size_;
+  }
+
+  int& back() { return this->operator[](size_ - 1); }
+  const int& back() const { return this->operator[](size_ - 1); }
+  int& front() { return this->operator[](0); }
+  const int& front() const { return this->operator[](0); }
+
+  void resize(size_t s, int v = 0) {
+    if (s <= __SV_MAX_STATIC) {
+      if (size_ > __SV_MAX_STATIC) {
+        int tmp[__SV_MAX_STATIC];
+        for (int i = 0; i < s; ++i) tmp[i] = data_.ptr[i];
+        delete[] data_.ptr;
+        for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i];
+        size_ = s;
+        return;
+      }
+      if (s <= size_) {
+        size_ = s;
+        return;
+      } else {
+        for (int i = size_; i < s; ++i)
+          data_.vals[i] = v;
+        size_ = s;
+        return;
+      }
+    } else {
+      if (size_ <= __SV_MAX_STATIC)
+        copy_vals_to_ptr();
+      if (s > capacity_)
+        ensure_capacity(s);
+      if (s > size_) {
+        for (int i = size_; i < s; ++i)
+          data_.ptr[i] = v;
+      }
+      size_ = s;
+    }
+  }
+
+  int& operator[](size_t i) {
+    if (size_ <= __SV_MAX_STATIC) return data_.vals[i];
+    return data_.ptr[i];
+  }
+
+  const int& operator[](size_t i) const {
+    if (size_ <= __SV_MAX_STATIC) return data_.vals[i];
+    return data_.ptr[i];
+  }
+
+  bool operator==(const SmallVector& o) const {
+    if (size_ != o.size_) return false;
+    if (size_ <= __SV_MAX_STATIC) {
+      for (size_t i = 0; i < size_; ++i)
+        if (data_.vals[i] != o.data_.vals[i]) return false;
+      return true;
+    } else {
+      for (size_t i = 0; i < size_; ++i)
+        if (data_.ptr[i] != o.data_.ptr[i]) return false;
+      return true;
+    }
+  }
+
+ private:
+  unsigned char capacity_;  // only defined when size_ >= __SV_MAX_STATIC
+  unsigned char size_;
+  union StorageType {
+    int vals[__SV_MAX_STATIC];
+    int* ptr;
+  };
+  StorageType data_;
+
+};
+
+inline bool operator!=(const SmallVector& a, const SmallVector& b) {
+  return !(a==b);
+}
+
+#endif