stl-model.h

   1 #ifndef __STL_MODEL_H__
   2 #define __STL_MODEL_H__
   3
   4 #include <list>
   5 #include "mymemory.h"
   6
   7 template<typename _Tp>
   8 class mllnode {
   9  public:
  10   _Tp getVal() {return val;}
  11   mllnode<_Tp> * getNext() {return next;}
  12   mllnode<_Tp> * getPrev() {return prev;}
  13
  14   MEMALLOC;
  15
  16  private:
  17   mllnode<_Tp> * next;
  18   mllnode<_Tp> * prev;
  19   _Tp val;
  20   template<typename T>
  21   friend class ModelList;
  22 };
  23
  24 template<typename _Tp>
  25 class ModelList
  26 {
  27 public:
  28  ModelList() : head(NULL),
  29     tail(NULL) {
  30   }
  31
  32   void push_front(_Tp val) {
  33     mllnode<_Tp> * tmp = new mllnode<_Tp>();
  34     tmp->prev = NULL;
  35     tmp->next = head;
  36     tmp->val = val;
  37     if (head == NULL)
  38       tail = tmp;
  39     else
  40       head->prev = tmp;
  41     head = tmp;
  42   }
  43
  44   void push_back(_Tp val) {
  45     mllnode<_Tp> * tmp = new mllnode<_Tp>();
  46     tmp->prev = tail;
  47     tmp->next = NULL;
  48     tmp->val = val;
  49     if (tail == NULL)
  50       head = tmp;
  51     else tail->next = tmp;
  52     tail = tmp;
  53   }
  54
  55   void insertAfter(mllnode<_Tp> * node, _Tp val) {
  56     mllnode<_Tp> *tmp = new mllnode<_Tp>();
  57     tmp->val = val;
  58     tmp->prev = node;
  59     tmp->next = node->next;
  60     node->next = tmp;
  61     if (tmp->next == NULL) {
  62       tail = tmp;
  63     } else {
  64       tmp->next->prev = tmp;
  65     }
  66   }
  67
  68   void insertBefore(mllnode<_Tp> * node, _Tp val) {
  69     mllnode<_Tp> *tmp = new mllnode<_Tp>();
  70     tmp->val = val;
  71     tmp->next = node;
  72     tmp->prev = node->prev;
  73     node->prev = tmp;
  74     if (tmp->prev == NULL) {
  75       head = tmp;
  76     } else {
  77       tmp->prev->next = tmp;
  78     }
  79   }
  80
  81   mllnode<_Tp> * erase(mllnode<_Tp> * node) {
  82     if (head == node) {
  83       head = node->next;
  84     } else {
  85       node->prev->next = node->next;
  86     }
  87
  88     if (tail == node) {
  89       tail = node->prev;
  90     } else {
  91       tail->next->prev = node->prev;
  92     }
  93     mllnode<_Tp> *next = node->next;
  94     delete node;
  95     return next;
  96   }
  97
  98   mllnode<_Tp> * begin() {
  99     return head;
 100   }
 101
 102   mllnode<_Tp> * end() {
 103     return tail;
 104   }
 105
 106   _Tp front() {
 107     return head->val;
 108   }
 109
 110   _Tp back() {
 111     return tail->val;
 112   }
 113
 114
 115   MEMALLOC;
 116  private:
 117   mllnode<_Tp> *head;
 118   mllnode<_Tp> *tail;
 119 };
 120
 121 template<typename _Tp>
 122 class sllnode {
 123  public:
 124   _Tp getVal() {return val;}
 125   sllnode<_Tp> * getNext() {return next;}
 126   sllnode<_Tp> * getPrev() {return prev;}
 127   SNAPSHOTALLOC;
 128
 129  private:
 130   sllnode<_Tp> * next;
 131   sllnode<_Tp> * prev;
 132   _Tp val;
 133   template<typename T>
 134   friend class SnapList;
 135 };
 136
 137 template<typename _Tp>
 138 class SnapList
 139 {
 140 public:
 141  SnapList() : head(NULL),
 142     tail(NULL) {
 143   }
 144
 145   void push_front(_Tp val) {
 146     sllnode<_Tp> * tmp = new sllnode<_Tp>();
 147     tmp->prev = NULL;
 148     tmp->next = head;
 149     tmp->val = val;
 150     if (head == NULL)
 151       tail = tmp;
 152     else
 153       head->prev = tmp;
 154     head = tmp;
 155   }
 156
 157   void push_back(_Tp val) {
 158     sllnode<_Tp> * tmp = new sllnode<_Tp>();
 159     tmp->prev = tail;
 160     tmp->next = NULL;
 161     tmp->val = val;
 162     if (tail == NULL)
 163       head = tmp;
 164     else tail->next = tmp;
 165     tail = tmp;
 166   }
 167
 168   void insertAfter(sllnode<_Tp> * node, _Tp val) {
 169     sllnode<_Tp> *tmp = new sllnode<_Tp>();
 170     tmp->val = val;
 171     tmp->prev = node;
 172     tmp->next = node->next;
 173     node->next = tmp;
 174     if (tmp->next == NULL) {
 175       tail = tmp;
 176     } else {
 177       tmp->next->prev = tmp;
 178     }
 179   }
 180
 181   void insertBefore(sllnode<_Tp> * node, _Tp val) {
 182     sllnode<_Tp> *tmp = new sllnode<_Tp>();
 183     tmp->val = val;
 184     tmp->next = node;
 185     tmp->prev = node->prev;
 186     node->prev = tmp;
 187     if (tmp->prev == NULL) {
 188       head = tmp;
 189     } else {
 190       tmp->prev->next = tmp;
 191     }
 192   }
 193
 194   sllnode<_Tp> * erase(sllnode<_Tp> * node) {
 195     if (head == node) {
 196       head = node->next;
 197     } else {
 198       node->prev->next = node->next;
 199     }
 200
 201     if (tail == node) {
 202       tail = node->prev;
 203     } else {
 204       tail->next->prev = node->prev;
 205     }
 206
 207     sllnode<_Tp> *next = node->next;
 208     delete node;
 209     return next;
 210   }
 211
 212   sllnode<_Tp> * begin() {
 213     return head;
 214   }
 215
 216   sllnode<_Tp> * end() {
 217     return tail;
 218   }
 219
 220   _Tp front() {
 221     return head->val;
 222   }
 223
 224   _Tp back() {
 225     return tail->val;
 226   }
 227
 228
 229   SNAPSHOTALLOC;
 230  private:
 231   sllnode<_Tp> *head;
 232   sllnode<_Tp> *tail;
 233 };
 234
 235
 236 #define VECTOR_DEFCAP 8
 237
 238 typedef unsigned int uint;
 239
 240 template<typename type>
 241 class ModelVector {
 242 public:
 243         ModelVector(uint _capacity = VECTOR_DEFCAP) :
 244                 _size(0),
 245                 capacity(_capacity),
 246                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 247         }
 248
 249         ModelVector(uint _capacity, type *_array)  :
 250                 _size(_capacity),
 251                 capacity(_capacity),
 252                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 253                 memcpy(array, _array, capacity * sizeof(type));
 254         }
 255         void pop_back() {
 256                 _size--;
 257         }
 258
 259         type back() const {
 260                 return array[size - 1];
 261         }
 262
 263         void resize(uint psize) {
 264                 if (psize <= _size) {
 265                         _size = psize;
 266                         return;
 267                 } else if (psize > capacity) {
 268                         array = (type *)model_realloc(array, (psize << 1) * sizeof(type));
 269                         capacity = psize << 1;
 270                 }
 271                 bzero(&array[_size], (psize - _size) * sizeof(type));
 272                 _size = psize;
 273         }
 274
 275         void push_back(type item) {
 276                 if (_size >= capacity) {
 277                         uint newcap = capacity << 1;
 278                         array = (type *)model_realloc(array, newcap * sizeof(type));
 279                         capacity = newcap;
 280                 }
 281                 array[_size++] = item;
 282         }
 283
 284         type operator[](uint index) const {
 285                 return array[index];
 286         }
 287
 288         type & operator[](uint index) {
 289                 return array[index];
 290         }
 291
 292         bool empty() const {
 293                 return _size == 0;
 294         }
 295
 296         type & at(uint index) const {
 297                 return array[index];
 298         }
 299
 300         void setExpand(uint index, type item) {
 301                 if (index >= _size)
 302                         resize(index + 1);
 303                 set(index, item);
 304         }
 305
 306         void set(uint index, type item) {
 307                 array[index] = item;
 308         }
 309
 310         void insertAt(uint index, type item) {
 311                 resize(_size + 1);
 312                 for (uint i = _size - 1;i > index;i--) {
 313                         set(i, at(i - 1));
 314                 }
 315                 array[index] = item;
 316         }
 317
 318         void removeAt(uint index) {
 319                 for (uint i = index;(i + 1) < _size;i++) {
 320                         set(i, at(i + 1));
 321                 }
 322                 resize(_size - 1);
 323         }
 324
 325         inline uint size() const {
 326                 return _size;
 327         }
 328
 329         ~ModelVector() {
 330                 model_free(array);
 331         }
 332
 333         void clear() {
 334                 _size = 0;
 335         }
 336
 337         MEMALLOC;
 338 private:
 339         uint _size;
 340         uint capacity;
 341         type *array;
 342 };
 343
 344
 345 template<typename type>
 346 class SnapVector {
 347 public:
 348         SnapVector(uint _capacity = VECTOR_DEFCAP) :
 349                 _size(0),
 350                 capacity(_capacity),
 351                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 352         }
 353
 354         SnapVector(uint _capacity, type *_array)  :
 355                 _size(_capacity),
 356                 capacity(_capacity),
 357                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 358                 memcpy(array, _array, capacity * sizeof(type));
 359         }
 360         void pop_back() {
 361                 _size--;
 362         }
 363
 364         type back() const {
 365                 return array[_size - 1];
 366         }
 367
 368         void resize(uint psize) {
 369                 if (psize <= _size) {
 370                         _size = psize;
 371                         return;
 372                 } else if (psize > capacity) {
 373                         array = (type *)snapshot_realloc(array, (psize <<1 )* sizeof(type));
 374                         capacity = psize << 1;
 375                 }
 376                 bzero(&array[_size], (psize - _size) * sizeof(type));
 377                 _size = psize;
 378         }
 379
 380         void push_back(type item) {
 381                 if (_size >= capacity) {
 382                         uint newcap = capacity << 1;
 383                         array = (type *)snapshot_realloc(array, newcap * sizeof(type));
 384                         capacity = newcap;
 385                 }
 386                 array[_size++] = item;
 387         }
 388
 389         type & operator[](uint index) {
 390                 return array[index];
 391         }
 392
 393         type operator[](uint index) const {
 394                 return array[index];
 395         }
 396
 397         bool empty() const {
 398                 return _size == 0;
 399         }
 400
 401         type & at(uint index) const {
 402                 return array[index];
 403         }
 404
 405         void setExpand(uint index, type item) {
 406                 if (index >= _size)
 407                         resize(index + 1);
 408                 set(index, item);
 409         }
 410
 411         void set(uint index, type item) {
 412                 array[index] = item;
 413         }
 414
 415         void insertAt(uint index, type item) {
 416                 resize(_size + 1);
 417                 for (uint i = _size - 1;i > index;i--) {
 418                         set(i, at(i - 1));
 419                 }
 420                 array[index] = item;
 421         }
 422
 423         void removeAt(uint index) {
 424                 for (uint i = index;(i + 1) < _size;i++) {
 425                         set(i, at(i + 1));
 426                 }
 427                 resize(_size - 1);
 428         }
 429
 430         inline uint size() const {
 431                 return _size;
 432         }
 433
 434         ~SnapVector() {
 435                 snapshot_free(array);
 436         }
 437
 438         void clear() {
 439                 _size = 0;
 440         }
 441
 442         SNAPSHOTALLOC;
 443 private:
 444         uint _size;
 445         uint capacity;
 446         type *array;
 447 };
 448
 449 #endif  /* __STL_MODEL_H__ */