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         sllnode<_Tp> * 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                 return tmp;
 289         }
 290
 291         void insertBefore(sllnode<_Tp> * node, _Tp val) {
 292                 sllnode<_Tp> *tmp = new sllnode<_Tp>();
 293                 tmp->val = val;
 294                 tmp->next = node;
 295                 tmp->prev = node->prev;
 296                 node->prev = tmp;
 297                 if (tmp->prev == NULL) {
 298                         head = tmp;
 299                 } else {
 300                         tmp->prev->next = tmp;
 301                 }
 302                 _size++;
 303         }
 304
 305         sllnode<_Tp> * erase(sllnode<_Tp> * node) {
 306                 if (head == node) {
 307                         head = node->next;
 308                 } else {
 309                         node->prev->next = node->next;
 310                 }
 311
 312                 if (tail == node) {
 313                         tail = node->prev;
 314                 } else {
 315                         node->next->prev = node->prev;
 316                 }
 317
 318                 sllnode<_Tp> *next = node->next;
 319                 delete node;
 320                 _size--;
 321                 return next;
 322         }
 323
 324         sllnode<_Tp> * begin() {
 325                 return head;
 326         }
 327
 328         sllnode<_Tp> * end() {
 329                 return tail;
 330         }
 331
 332         _Tp front() {
 333                 return head->val;
 334         }
 335
 336         _Tp back() {
 337                 return tail->val;
 338         }
 339         uint size() {
 340                 return _size;
 341         }
 342         bool empty() {
 343                 return _size == 0;
 344         }
 345
 346         SNAPSHOTALLOC;
 347 private:
 348         sllnode<_Tp> *head;
 349         sllnode<_Tp> *tail;
 350         uint _size;
 351 };
 352
 353
 354 #define VECTOR_DEFCAP 8
 355
 356
 357 template<typename type>
 358 class ModelVector {
 359 public:
 360         ModelVector(uint _capacity = VECTOR_DEFCAP) :
 361                 _size(0),
 362                 capacity(_capacity),
 363                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 364         }
 365
 366         ModelVector(uint _capacity, type *_array)  :
 367                 _size(_capacity),
 368                 capacity(_capacity),
 369                 array((type *) model_malloc(sizeof(type) * _capacity)) {
 370                 memcpy(array, _array, capacity * sizeof(type));
 371         }
 372         void pop_back() {
 373                 _size--;
 374         }
 375
 376         type back() const {
 377                 return array[_size - 1];
 378         }
 379
 380         void resize(uint psize) {
 381                 if (psize <= _size) {
 382                         _size = psize;
 383                         return;
 384                 } else if (psize > capacity) {
 385                         array = (type *)model_realloc(array, (psize << 1) * sizeof(type));
 386                         capacity = psize << 1;
 387                 }
 388                 bzero(&array[_size], (psize - _size) * sizeof(type));
 389                 _size = psize;
 390         }
 391
 392         void push_back(type item) {
 393                 if (_size >= capacity) {
 394                         uint newcap = capacity << 1;
 395                         array = (type *)model_realloc(array, newcap * sizeof(type));
 396                         capacity = newcap;
 397                 }
 398                 array[_size++] = item;
 399         }
 400
 401         type operator[](int index) const {
 402                 return array[index];
 403         }
 404
 405         type & operator[](int index) {
 406                 return array[index];
 407         }
 408
 409         bool empty() const {
 410                 return _size == 0;
 411         }
 412
 413         type & at(uint index) const {
 414                 return array[index];
 415         }
 416
 417         void setExpand(uint index, type item) {
 418                 if (index >= _size)
 419                         resize(index + 1);
 420                 set(index, item);
 421         }
 422
 423         void set(uint index, type item) {
 424                 array[index] = item;
 425         }
 426
 427         void insertAt(uint index, type item) {
 428                 resize(_size + 1);
 429                 for (uint i = _size - 1;i > index;i--) {
 430                         set(i, at(i - 1));
 431                 }
 432                 array[index] = item;
 433         }
 434
 435         void removeAt(uint index) {
 436                 for (uint i = index;(i + 1) < _size;i++) {
 437                         set(i, at(i + 1));
 438                 }
 439                 resize(_size - 1);
 440         }
 441
 442         inline uint size() const {
 443                 return _size;
 444         }
 445
 446         ~ModelVector() {
 447                 model_free(array);
 448         }
 449
 450         void clear() {
 451                 _size = 0;
 452         }
 453
 454         MEMALLOC;
 455 private:
 456         uint _size;
 457         uint capacity;
 458         type *array;
 459 };
 460
 461
 462 template<typename type>
 463 class SnapVector {
 464 public:
 465         SnapVector(uint _capacity = VECTOR_DEFCAP) :
 466                 _size(0),
 467                 capacity(_capacity),
 468                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 469         }
 470
 471         SnapVector(uint _capacity, type *_array)  :
 472                 _size(_capacity),
 473                 capacity(_capacity),
 474                 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
 475                 memcpy(array, _array, capacity * sizeof(type));
 476         }
 477         void pop_back() {
 478                 _size--;
 479         }
 480
 481         type back() const {
 482                 return array[_size - 1];
 483         }
 484
 485         void resize(uint psize) {
 486                 if (psize <= _size) {
 487                         _size = psize;
 488                         return;
 489                 } else if (psize > capacity) {
 490                         array = (type *)snapshot_realloc(array, (psize <<1 )* sizeof(type));
 491                         capacity = psize << 1;
 492                 }
 493                 bzero(&array[_size], (psize - _size) * sizeof(type));
 494                 _size = psize;
 495         }
 496
 497         void push_back(type item) {
 498                 if (_size >= capacity) {
 499                         uint newcap = capacity << 1;
 500                         array = (type *)snapshot_realloc(array, newcap * sizeof(type));
 501                         capacity = newcap;
 502                 }
 503                 array[_size++] = item;
 504         }
 505
 506         type operator[](int index) const {
 507                 return array[index];
 508         }
 509
 510         type & operator[](int index) {
 511                 return array[index];
 512         }
 513
 514         bool empty() const {
 515                 return _size == 0;
 516         }
 517
 518         type & at(uint index) const {
 519                 return array[index];
 520         }
 521
 522         void setExpand(uint index, type item) {
 523                 if (index >= _size)
 524                         resize(index + 1);
 525                 set(index, item);
 526         }
 527
 528         void set(uint index, type item) {
 529                 array[index] = item;
 530         }
 531
 532         void insertAt(uint index, type item) {
 533                 resize(_size + 1);
 534                 for (uint i = _size - 1;i > index;i--) {
 535                         set(i, at(i - 1));
 536                 }
 537                 array[index] = item;
 538         }
 539
 540         void removeAt(uint index) {
 541                 for (uint i = index;(i + 1) < _size;i++) {
 542                         set(i, at(i + 1));
 543                 }
 544                 resize(_size - 1);
 545         }
 546
 547         inline uint size() const {
 548                 return _size;
 549         }
 550
 551         ~SnapVector() {
 552                 snapshot_free(array);
 553         }
 554
 555         void clear() {
 556                 _size = 0;
 557         }
 558
 559         SNAPSHOTALLOC;
 560 private:
 561         uint _size;
 562         uint capacity;
 563         type *array;
 564 };
 565
 566 #endif  /* __STL_MODEL_H__ */