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