sat-solver/Vec.h
00001 /*******************************************************************************************[Vec.h]
00002 MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
00003 
00004 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
00005 associated documentation files (the "Software"), to deal in the Software without restriction,
00006 including without limitation the rights to use, copy, modify, merge, publish, distribute,
00007 sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
00008 furnished to do so, subject to the following conditions:
00009 
00010 The above copyright notice and this permission notice shall be included in all copies or
00011 substantial portions of the Software.
00012 
00013 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
00014 NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00015 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
00016 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
00017 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00018 **************************************************************************************************/
00019 
00020 #ifndef Vec_h
00021 #define Vec_h
00022 
00023 #include <cstdlib>
00024 #include <cassert>
00025 #include <new>
00026 
00027 //=================================================================================================
00028 // Automatically resizable arrays
00029 //
00030 // NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
00031 
00032 template<class T>
00033 class vec {
00034     T*  data;
00035     int sz;
00036     int cap;
00037 
00038     void     init(int size, const T& pad);
00039     void     grow(int min_cap);
00040 
00041     // Don't allow copying (error prone):
00042     vec<T>&  operator = (vec<T>& other) { assert(0); return *this; }
00043              vec        (vec<T>& other) { assert(0); }
00044 
00045     static inline int imin(int x, int y) {
00046         int mask = (x-y) >> (sizeof(int)*8-1);
00047         return (x&mask) + (y&(~mask)); }
00048 
00049     static inline int imax(int x, int y) {
00050         int mask = (y-x) >> (sizeof(int)*8-1);
00051         return (x&mask) + (y&(~mask)); }
00052 
00053 public:
00054     // Types:
00055     typedef int Key;
00056     typedef T   Datum;
00057 
00058     // Constructors:
00059     vec(void)                   : data(NULL) , sz(0)   , cap(0)    {}
00060     vec(int size)               : data(NULL) , sz(0)   , cap(0)    { growTo(size); }
00061     vec(int size, const T& pad) : data(NULL) , sz(0)   , cap(0)    { growTo(size, pad); }
00062     vec(T* array, int size)     : data(array), sz(size), cap(size) { }      // (takes ownership of array -- will be deallocated with 'free()')
00063    ~vec(void)                                                      { clear(true); }
00064 
00065     // Ownership of underlying array:
00066     T*       release  (void)           { T* ret = data; data = NULL; sz = 0; cap = 0; return ret; }
00067     operator T*       (void)           { return data; }     // (unsafe but convenient)
00068     operator const T* (void) const     { return data; }
00069 
00070     // Size operations:
00071     int      size   (void) const       { return sz; }
00072     void     shrink (int nelems)       { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); }
00073     void     shrink_(int nelems)       { assert(nelems <= sz); sz -= nelems; }
00074     void     pop    (void)             { sz--, data[sz].~T(); }
00075     void     growTo (int size);
00076     void     growTo (int size, const T& pad);
00077     void     clear  (bool dealloc = false);
00078     void     capacity (int size) { grow(size); }
00079 
00080     // Stack interface:
00081 #if 1
00082     void     push  (void)              { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(); sz++; }
00083     //void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(elem); sz++; }
00084     void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } data[sz++] = elem; }
00085     void     push_ (const T& elem)     { assert(sz < cap); data[sz++] = elem; }
00086 #else
00087     void     push  (void)              { if (sz == cap) grow(sz+1); new (&data[sz]) T()    ; sz++; }
00088     void     push  (const T& elem)     { if (sz == cap) grow(sz+1); new (&data[sz]) T(elem); sz++; }
00089 #endif
00090 
00091     const T& last  (void) const        { return data[sz-1]; }
00092     T&       last  (void)              { return data[sz-1]; }
00093 
00094     // Vector interface:
00095     const T& operator [] (int index) const  { return data[index]; }
00096     T&       operator [] (int index)        { return data[index]; }
00097 
00098 
00099     // Duplicatation (preferred instead):
00100     void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) new (&copy[i]) T(data[i]); }
00101     void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = NULL; sz = 0; cap = 0; }
00102 };
00103 
00104 template<class T>
00105 void vec<T>::grow(int min_cap) {
00106     if (min_cap <= cap) return;
00107     if (cap == 0) cap = (min_cap >= 2) ? min_cap : 2;
00108     else          do cap = (cap*3+1) >> 1; while (cap < min_cap);
00109     data = (T*)realloc(data, cap * sizeof(T)); }
00110 
00111 template<class T>
00112 void vec<T>::growTo(int size, const T& pad) {
00113     if (sz >= size) return;
00114     grow(size);
00115     for (int i = sz; i < size; i++) new (&data[i]) T(pad);
00116     sz = size; }
00117 
00118 template<class T>
00119 void vec<T>::growTo(int size) {
00120     if (sz >= size) return;
00121     grow(size);
00122     for (int i = sz; i < size; i++) new (&data[i]) T();
00123     sz = size; }
00124 
00125 template<class T>
00126 void vec<T>::clear(bool dealloc) {
00127     if (data != NULL){
00128         for (int i = 0; i < sz; i++) data[i].~T();
00129         sz = 0;
00130         if (dealloc) free(data), data = NULL, cap = 0; } }
00131 
00132 
00133 #endif