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