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   MEMALLOC;
 152  private:
 153   mllnode<_Tp> *head;
 154   mllnode<_Tp> *tail;
 155   uint _size;
 156 };
 157
 158 template<typename _Tp>
 159 class sllnode {
 160  public:
 161   _Tp getVal() {return val;}
 162   sllnode<_Tp> * getNext() {return next;}
 163   sllnode<_Tp> * getPrev() {return prev;}
 164   SNAPSHOTALLOC;
 165
 166  private:
 167   sllnode<_Tp> * next;
 168   sllnode<_Tp> * prev;
 169   _Tp val;
 170   template<typename T>
 171   friend class SnapList;
 172 };
 173
 174 template<typename _Tp>
 175 class SnapList
 176 {
 177 public:
 178  SnapList() : head(NULL),
 179     tail(NULL), _size(0) {
 180   }
 181
 182   void push_front(_Tp val) {
 183     sllnode<_Tp> * tmp = new sllnode<_Tp>();
 184     tmp->prev = NULL;
 185     tmp->next = head;
 186     tmp->val = val;
 187     if (head == NULL)
 188       tail = tmp;
 189     else
 190       head->prev = tmp;
 191     head = tmp;
 192     _size++;
 193   }
 194
 195   void push_back(_Tp val) {
 196     sllnode<_Tp> * tmp = new sllnode<_Tp>();
 197     tmp->prev = tail;
 198     tmp->next = NULL;
 199     tmp->val = val;
 200     if (tail == NULL)
 201       head = tmp;
 202     else tail->next = tmp;
 203     tail = tmp;
 204     _size++;
 205   }
 206
 207   void pop_front() {
 208     sllnode<_Tp> *tmp = head;
 209     head = head->next;
 210     head->prev = NULL;
 211     delete tmp;
 212     _size--;
 213   }
 214
 215   void pop_back() {
 216     sllnode<_Tp> *tmp = tail;
 217     tail = tail->next;
 218     tail->next = NULL;
 219     delete tmp;
 220     _size--;
 221   }
 222
 223   void clear() {
 224     while(head != NULL) {
 225       sllnode<_Tp> *tmp=head->next;
 226       delete head;
 227       head = tmp;
 228     }
 229     tail=NULL;
 230     _size=0;
 231   }
 232
 233   void insertAfter(sllnode<_Tp> * node, _Tp val) {
 234     sllnode<_Tp> *tmp = new sllnode<_Tp>();
 235     tmp->val = val;
 236     tmp->prev = node;
 237     tmp->next = node->next;
 238     node->next = tmp;
 239     if (tmp->next == NULL) {
 240       tail = tmp;
 241     } else {
 242       tmp->next->prev = tmp;
 243     }
 244     _size++;
 245   }
 246
 247   void insertBefore(sllnode<_Tp> * node, _Tp val) {
 248     sllnode<_Tp> *tmp = new sllnode<_Tp>();
 249     tmp->val = val;
 250     tmp->next = node;
 251     tmp->prev = node->prev;
 252     node->prev = tmp;
 253     if (tmp->prev == NULL) {
 254       head = tmp;
 255     } else {
 256       tmp->prev->next = tmp;
 257     }
 258     _size++;
 259   }
 260
 261   sllnode<_Tp> * erase(sllnode<_Tp> * node) {
 262     if (head == node) {
 263       head = node->next;
 264     } else {
 265       node->prev->next = node->next;
 266     }
 267
 268     if (tail == node) {
 269       tail = node->prev;
 270     } else {
 271       tail->next->prev = node->prev;
 272     }
 273
 274     sllnode<_Tp> *next = node->next;
 275     delete node;
 276     _size--;
 277     return next;
 278   }
 279
 280   sllnode<_Tp> * begin() {
 281     return head;
 282   }
 283
 284   sllnode<_Tp> * end() {
 285     return tail;
 286   }
 287
 288   _Tp front() {
 289     return head->val;
 290   }
 291
 292   _Tp back() {
 293     return tail->val;
 294   }
 295   uint size() {
 296     return _size;
 297   }
 298
 299   SNAPSHOTALLOC;
 300  private:
 301   sllnode<_Tp> *head;
 302   sllnode<_Tp> *tail;
 303   uint _size;
 304 };
 305
 306
 307 #define VECTOR_DEFCAP 8
 308
 309
 310 template<typename type>
 311 class ModelVector {
 312 public:
 313         ModelVector(uint _capacity = VECTOR_DEFCAP) :
 314                 _size(0),
 315                 capacity(_capacity),
 316                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 317         }
 318
 319         ModelVector(uint _capacity, type *_array)  :
 320                 _size(_capacity),
 321                 capacity(_capacity),
 322                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 323                 memcpy(array, _array, capacity * sizeof(type));
 324         }
 325         void pop_back() {
 326                 _size--;
 327         }
 328
 329         type back() const {
 330                 return array[size - 1];
 331         }
 332
 333         void resize(uint psize) {
 334                 if (psize <= _size) {
 335                         _size = psize;
 336                         return;
 337                 } else if (psize > capacity) {
 338                         array = (type *)model_realloc(array, (psize << 1) * sizeof(type));
 339                         capacity = psize << 1;
 340                 }
 341                 bzero(&array[_size], (psize - _size) * sizeof(type));
 342                 _size = psize;
 343         }
 344
 345         void push_back(type item) {
 346                 if (_size >= capacity) {
 347                         uint newcap = capacity << 1;
 348                         array = (type *)model_realloc(array, newcap * sizeof(type));
 349                         capacity = newcap;
 350                 }
 351                 array[_size++] = item;
 352         }
 353
 354         type operator[](uint index) const {
 355                 return array[index];
 356         }
 357
 358         type & operator[](uint index) {
 359                 return array[index];
 360         }
 361
 362         bool empty() const {
 363                 return _size == 0;
 364         }
 365
 366         type & at(uint index) const {
 367                 return array[index];
 368         }
 369
 370         void setExpand(uint index, type item) {
 371                 if (index >= _size)
 372                         resize(index + 1);
 373                 set(index, item);
 374         }
 375
 376         void set(uint index, type item) {
 377                 array[index] = item;
 378         }
 379
 380         void insertAt(uint index, type item) {
 381                 resize(_size + 1);
 382                 for (uint i = _size - 1;i > index;i--) {
 383                         set(i, at(i - 1));
 384                 }
 385                 array[index] = item;
 386         }
 387
 388         void removeAt(uint index) {
 389                 for (uint i = index;(i + 1) < _size;i++) {
 390                         set(i, at(i + 1));
 391                 }
 392                 resize(_size - 1);
 393         }
 394
 395         inline uint size() const {
 396                 return _size;
 397         }
 398
 399         ~ModelVector() {
 400                 model_free(array);
 401         }
 402
 403         void clear() {
 404                 _size = 0;
 405         }
 406
 407         MEMALLOC;
 408 private:
 409         uint _size;
 410         uint capacity;
 411         type *array;
 412 };
 413
 414
 415 template<typename type>
 416 class SnapVector {
 417 public:
 418         SnapVector(uint _capacity = VECTOR_DEFCAP) :
 419                 _size(0),
 420                 capacity(_capacity),
 421                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 422         }
 423
 424         SnapVector(uint _capacity, type *_array)  :
 425                 _size(_capacity),
 426                 capacity(_capacity),
 427                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 428                 memcpy(array, _array, capacity * sizeof(type));
 429         }
 430         void pop_back() {
 431                 _size--;
 432         }
 433
 434         type back() const {
 435                 return array[_size - 1];
 436         }
 437
 438         void resize(uint psize) {
 439                 if (psize <= _size) {
 440                         _size = psize;
 441                         return;
 442                 } else if (psize > capacity) {
 443                         array = (type *)snapshot_realloc(array, (psize <<1 )* sizeof(type));
 444                         capacity = psize << 1;
 445                 }
 446                 bzero(&array[_size], (psize - _size) * sizeof(type));
 447                 _size = psize;
 448         }
 449
 450         void push_back(type item) {
 451                 if (_size >= capacity) {
 452                         uint newcap = capacity << 1;
 453                         array = (type *)snapshot_realloc(array, newcap * sizeof(type));
 454                         capacity = newcap;
 455                 }
 456                 array[_size++] = item;
 457         }
 458
 459         type & operator[](uint index) {
 460                 return array[index];
 461         }
 462
 463         type operator[](uint index) const {
 464                 return array[index];
 465         }
 466
 467         bool empty() const {
 468                 return _size == 0;
 469         }
 470
 471         type & at(uint index) const {
 472                 return array[index];
 473         }
 474
 475         void setExpand(uint index, type item) {
 476                 if (index >= _size)
 477                         resize(index + 1);
 478                 set(index, item);
 479         }
 480
 481         void set(uint index, type item) {
 482                 array[index] = item;
 483         }
 484
 485         void insertAt(uint index, type item) {
 486                 resize(_size + 1);
 487                 for (uint i = _size - 1;i > index;i--) {
 488                         set(i, at(i - 1));
 489                 }
 490                 array[index] = item;
 491         }
 492
 493         void removeAt(uint index) {
 494                 for (uint i = index;(i + 1) < _size;i++) {
 495                         set(i, at(i + 1));
 496                 }
 497                 resize(_size - 1);
 498         }
 499
 500         inline uint size() const {
 501                 return _size;
 502         }
 503
 504         ~SnapVector() {
 505                 snapshot_free(array);
 506         }
 507
 508         void clear() {
 509                 _size = 0;
 510         }
 511
 512         SNAPSHOTALLOC;
 513 private:
 514         uint _size;
 515         uint capacity;
 516         type *array;
 517 };
 518
 519 #endif  /* __STL_MODEL_H__ */