small/sparse vector fixes

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@304 ec762483-ff6d-05da-a07a-a48fb63a330f

2 files changed, 111 insertions, 34 deletions

diff --git a/decoder/small_vector.h b/decoder/small_vector.h
index e5c314de..ed3e1096 100644
--- a/decoder/small_vector.h
+++ b/decoder/small_vector.h
@@ -1,26 +1,55 @@
 #ifndef _SMALL_VECTOR_H_
+#define _SMALL_VECTOR_H_
+
+/* REQUIRES that T is POD (can be memcpy).  won't work (yet) due to union with SMALL_VECTOR_POD==0 - may be possible to handle movable types that have ctor/dtor, by using  explicit allocation, ctor/dtor calls.  but for now JUST USE THIS FOR no-meaningful ctor/dtor POD types.
+
+   stores small element (<=SV_MAX items) vectors inline.  recommend SV_MAX=sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1.  may not work if SV_MAX==0.
+ */
+
+#define SMALL_VECTOR_POD 1
 
 #include <streambuf>  // std::max - where to get this?
 #include <cstring>
 #include <cassert>
 #include <limits.h>
-
+#include <new>
 //sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1
-template <class T,int SV_MAX=2 >
+
+template <class T,int SV_MAX=2>
 class SmallVector {
-  typedef unsigned short uint16_t;
+//  typedef unsigned short uint16_t;
  public:
   typedef SmallVector<T,SV_MAX> Self;
   SmallVector() : size_(0) {}
 
-  explicit SmallVector(size_t s, int v = 0) : size_(s) {
-    assert(s < 0x80);
+  typedef T const* const_iterator;
+  typedef T* iterator;
+  T *begin() { return size_>SV_MAX?data_.ptr:data_.vals; }
+  T const* begin() const { return const_cast<Self*>(this)->begin(); }
+  T *end() { return begin()+size_; }
+  T const* end() const { return begin()+size_; }
+
+
+  explicit SmallVector(size_t s) : size_(s) {
+    assert(s < 0xA000);
+    if (s <= SV_MAX) {
+      for (int i = 0; i < s; ++i) new(&data_.vals[i]) T();
+    } else {
+      capacity_ = s;
+      size_ = s;
+      data_.ptr = new T[s]; // TODO: replace this with allocator or ::operator new(sizeof(T)*s) everywhere
+      for (int i = 0; i < size_; ++i) new(&data_.ptr[i]) T();
+    }
+  }
+
+  SmallVector(size_t s, T const& v) : size_(s) {
+    assert(s < 0xA000);
     if (s <= SV_MAX) {
       for (int i = 0; i < s; ++i) data_.vals[i] = v;
     } else {
       capacity_ = s;
       size_ = s;
-      data_.ptr = new int[s];
+      data_.ptr = new T[s];
       for (int i = 0; i < size_; ++i) data_.ptr[i] = v;
     }
   }
@@ -30,8 +59,8 @@ class SmallVector {
       for (int i = 0; i < SV_MAX; ++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));
+      data_.ptr = new T[capacity_];
+      std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T));
     }
   }
 
@@ -42,8 +71,8 @@ class SmallVector {
         for (int i = 0; i < SV_MAX; ++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));
+        data_.ptr = new T[capacity_];
+        std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T));
       }
     } else {
       if (o.size_ <= SV_MAX) {
@@ -54,7 +83,7 @@ class SmallVector {
         if (capacity_ < o.size_) {
           delete[] data_.ptr;
           capacity_ = o.size_;
-          data_.ptr = new int[capacity_];
+          data_.ptr = new T[capacity_];
         }
         size_ = o.size_;
         for (int i = 0; i < size_; ++i)
@@ -65,8 +94,13 @@ class SmallVector {
   }
 
   ~SmallVector() {
-    if (size_ <= SV_MAX) return;
-    delete[] data_.ptr;
+    if (size_ <= SV_MAX) {
+      // skip if pod?  yes, we required pod anyway.  no need to destruct
+#if !SMALL_VECTOR_POD
+      for (int i=0;i<size_;++i) data_.vals[i].~T();
+#endif
+    } else
+      delete[] data_.ptr;
   }
 
   void clear() {
@@ -83,21 +117,31 @@ class SmallVector {
     assert(min_size > SV_MAX);
     if (min_size < capacity_) return;
     uint16_t new_cap = std::max(static_cast<uint16_t>(capacity_ << 1), min_size);
-    int* tmp = new int[new_cap];
-    std::memcpy(tmp, data_.ptr, capacity_ * sizeof(int));
+    T* tmp = new T[new_cap];
+    std::memcpy(tmp, data_.ptr, capacity_ * sizeof(T));
     delete[] data_.ptr;
     data_.ptr = tmp;
     capacity_ = new_cap;
   }
 
+private:
   inline void copy_vals_to_ptr() {
     capacity_ = SV_MAX * 2;
-    int* tmp = new int[capacity_];
+    T* tmp = new T[capacity_];
     for (int i = 0; i < SV_MAX; ++i) tmp[i] = data_.vals[i];
     data_.ptr = tmp;
   }
+  inline void ptr_to_small() {
+    assert(size_<=SV_MAX);
+    int *tmp=data_.ptr;
+    for (int i=0;i<size_;++i)
+      data_.vals[i]=tmp[i];
+    delete[] tmp;
+  }
+
+public:
 
-  inline void push_back(int v) {
+  inline void push_back(T const& v) {
     if (size_ < SV_MAX) {
       data_.vals[size_] = v;
       ++size_;
@@ -111,18 +155,40 @@ class SmallVector {
     ++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); }
+  T& back() { return this->operator[](size_ - 1); }
+  const T& back() const { return this->operator[](size_ - 1); }
+  T& front() { return this->operator[](0); }
+  const T& front() const { return this->operator[](0); }
+
+  void pop_back() {
+    assert(size_>0);
+    --size_;
+    if (size_==SV_MAX)
+      ptr_to_small();
+  }
+
+
+  void compact() {
+    compact(size_);
+  }
+
+  // size must be <= size_ - TODO: test
+  void compact(uint16_t size) {
+    assert(size<=size_);
+    if (size_>SV_MAX) {
+      size_=size;
+      if (size<=SV_MAX)
+        ptr_to_small();
+    } else
+      size_=size;
+  }
 
   void resize(size_t s, int v = 0) {
     if (s <= SV_MAX) {
       if (size_ > SV_MAX) {
-        int tmp[SV_MAX];
-        for (int i = 0; i < s; ++i) tmp[i] = data_.ptr[i];
-        delete[] data_.ptr;
+        T *tmp=data_.ptr;
         for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i];
+        delete[] tmp;
         size_ = s;
         return;
       }
@@ -148,12 +214,12 @@ class SmallVector {
     }
   }
 
-  int& operator[](size_t i) {
+  T& operator[](size_t i) {
     if (size_ <= SV_MAX) return data_.vals[i];
     return data_.ptr[i];
   }
 
-  const int& operator[](size_t i) const {
+  const T& operator[](size_t i) const {
     if (size_ <= SV_MAX) return data_.vals[i];
     return data_.ptr[i];
   }
@@ -177,12 +243,12 @@ class SmallVector {
 
  private:
   union StorageType {
-    int vals[SV_MAX];
-    int* ptr;
+    T vals[SV_MAX];
+    T* ptr;
   };
   StorageType data_;
   uint16_t size_;
-  uint16_t capacity_;  // only defined when size_ >= __SV_MAX_STATIC
+  uint16_t capacity_;  // only defined when size_ > __SV_MAX_STATIC
 };
 
 typedef SmallVector<int,2> SmallVectorInt;
diff --git a/decoder/sparse_vector.h b/decoder/sparse_vector.h
index 43880014..f41bedf5 100644
--- a/decoder/sparse_vector.h
+++ b/decoder/sparse_vector.h
@@ -11,6 +11,7 @@
 #include <valarray>
 
 #include "fdict.h"
+#include "small_vector.h"
 
 template <class T>
 inline T & extend_vector(std::vector<T> &v,int i) {
@@ -310,10 +311,20 @@ private:
 // doesn't support fast indexing directly
 template <class T>
 class SparseVectorList {
-  typedef std::vector<const int,T> ListType;
-  typedef typename ListType::value_type pair_type;
-  typedef typename ListType::const_iterator const_iterator;
+  typedef typename std::pair<int,T> Pair;
+  typedef SmallVector<Pair,1> List;
+  typedef typename List::const_iterator const_iterator;
   SparseVectorList() {  }
+  template <class I>
+  SparseVectorList(I i,I const& end) {
+    const T z=T(0);
+    int c=0;
+    for (;i<end;++i,++c) {
+      if (*i!=z)
+        p.push_back(pair_type(c,*i));
+    }
+    p.compact();
+  }
   explicit SparseVectorList(std::vector<T> const& v) {
     const T z=T(0);
     for (unsigned i=0;i<v.size();++i) {
@@ -321,10 +332,10 @@ class SparseVectorList {
       if (t!=z)
         p.push_back(pair_type(i,t));
     }
-    p.resize(p.size());
+    p.compact();
   }
 private:
-  ListType p;
+  List p;
 };