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