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