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