stl-model.h

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