sat-solver/BoxedVec.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 BoxedVec_h
00021 #define BoxedVec_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 bvec {
00034 
00035     static inline int imin(int x, int y) {
00036         int mask = (x-y) >> (sizeof(int)*8-1);
00037         return (x&mask) + (y&(~mask)); }
00038 
00039     static inline int imax(int x, int y) {
00040         int mask = (y-x) >> (sizeof(int)*8-1);
00041         return (x&mask) + (y&(~mask)); }
00042 
00043     struct Vec_t {
00044         int sz;
00045         int cap;
00046         T   data[0];
00047 
00048         static Vec_t* alloc(Vec_t* x, int size){
00049             x = (Vec_t*)realloc((void*)x, sizeof(Vec_t) + sizeof(T)*size);
00050             x->cap = size;
00051             return x;
00052         }
00053         
00054     };
00055 
00056     Vec_t* ref;
00057 
00058     static const int init_size = 2;
00059     static int   nextSize (int current) { return (current * 3 + 1) >> 1; }
00060     static int   fitSize  (int needed)  { int x; for (x = init_size; needed > x; x = nextSize(x)); return x; }
00061 
00062     void fill (int size) {
00063         assert(ref != NULL);
00064         for (T* i = ref->data; i < ref->data + size; i++)
00065             new (i) T();
00066     }
00067 
00068     void fill (int size, const T& pad) {
00069         assert(ref != NULL);
00070         for (T* i = ref->data; i < ref->data + size; i++)
00071             new (i) T(pad);
00072     }
00073 
00074     // Don't allow copying (error prone):
00075     altvec<T>&  operator = (altvec<T>& other) { assert(0); }
00076     altvec (altvec<T>& other)                  { assert(0); }
00077 
00078 public:
00079     void     clear  (bool dealloc = false) { 
00080         if (ref != NULL){
00081             for (int i = 0; i < ref->sz; i++) 
00082                 (*ref).data[i].~T();
00083 
00084             if (dealloc) { 
00085                 free(ref); ref = NULL; 
00086             }else 
00087                 ref->sz = 0;
00088         } 
00089     }
00090 
00091     // Constructors:
00092     altvec(void)                   : ref (NULL) { }
00093     altvec(int size)               : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size);      ref->sz = size; }
00094     altvec(int size, const T& pad) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size, pad); ref->sz = size; }
00095    ~altvec(void) { clear(true); }
00096 
00097     // Ownership of underlying array:
00098     operator T*       (void)           { return ref->data; }     // (unsafe but convenient)
00099     operator const T* (void) const     { return ref->data; }
00100 
00101     // Size operations:
00102     int      size   (void) const       { return ref != NULL ? ref->sz : 0; }
00103 
00104     void     pop    (void)             { assert(ref != NULL && ref->sz > 0); int last = --ref->sz; ref->data[last].~T(); }
00105     void     push   (const T& elem) {
00106         int size = ref != NULL ? ref->sz  : 0;
00107         int cap  = ref != NULL ? ref->cap : 0;
00108         if (size == cap){
00109             cap = cap != 0 ? nextSize(cap) : init_size;
00110             ref = Vec_t::alloc(ref, cap); 
00111         }
00112         //new (&ref->data[size]) T(elem); 
00113         ref->data[size] = elem; 
00114         ref->sz = size+1; 
00115     }
00116 
00117     void     push   () {
00118         int size = ref != NULL ? ref->sz  : 0;
00119         int cap  = ref != NULL ? ref->cap : 0;
00120         if (size == cap){
00121             cap = cap != 0 ? nextSize(cap) : init_size;
00122             ref = Vec_t::alloc(ref, cap); 
00123         }
00124         new (&ref->data[size]) T(); 
00125         ref->sz = size+1; 
00126     }
00127 
00128     void     shrink (int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
00129     void     shrink_(int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
00130     void     growTo (int size)               { while (this->size() < size) push(); }
00131     void     growTo (int size, const T& pad) { while (this->size() < size) push(pad); }
00132     void     capacity (int size)             { growTo(size); }
00133 
00134     const T& last  (void) const              { return ref->data[ref->sz-1]; }
00135     T&       last  (void)                    { return ref->data[ref->sz-1]; }
00136 
00137     // Vector interface:
00138     const T& operator [] (int index) const  { return ref->data[index]; }
00139     T&       operator [] (int index)        { return ref->data[index]; }
00140 
00141     void copyTo(altvec<T>& copy) const { copy.clear(); for (int i = 0; i < size(); i++) copy.push(ref->data[i]); }
00142     void moveTo(altvec<T>& dest) { dest.clear(true); dest.ref = ref; ref = NULL; }
00143 
00144 };
00145 
00146 
00147 #endif