1 #ifndef __STL_MODEL_H__
2 #define __STL_MODEL_H__
6 typedef unsigned int uint;
12 _Tp getVal() {return val;}
13 mllnode<_Tp> * getNext() {return next;}
14 mllnode<_Tp> * getPrev() {return prev;}
23 friend class ModelList;
26 template<typename _Tp>
30 ModelList() : head(NULL),
31 tail(NULL), _size(0) {
34 void push_front(_Tp val) {
35 mllnode<_Tp> * tmp = new mllnode<_Tp>();
47 void push_back(_Tp val) {
48 mllnode<_Tp> * tmp = new mllnode<_Tp>();
54 else tail->next = tmp;
60 mllnode<_Tp> *tmp = head;
68 mllnode<_Tp> *tmp = tail;
77 mllnode<_Tp> *tmp=head->next;
85 void insertAfter(mllnode<_Tp> * node, _Tp val) {
86 mllnode<_Tp> *tmp = new mllnode<_Tp>();
89 tmp->next = node->next;
91 if (tmp->next == NULL) {
94 tmp->next->prev = tmp;
99 void insertBefore(mllnode<_Tp> * node, _Tp val) {
100 mllnode<_Tp> *tmp = new mllnode<_Tp>();
103 tmp->prev = node->prev;
105 if (tmp->prev == NULL) {
108 tmp->prev->next = tmp;
113 mllnode<_Tp> * erase(mllnode<_Tp> * node) {
117 node->prev->next = node->next;
123 tail->next->prev = node->prev;
125 mllnode<_Tp> *next = node->next;
131 mllnode<_Tp> * begin() {
135 mllnode<_Tp> * end() {
162 template<typename _Tp>
165 _Tp getVal() {return val;}
166 sllnode<_Tp> * getNext() {return next;}
167 sllnode<_Tp> * getPrev() {return prev;}
175 friend class SnapList;
178 template<typename _Tp>
182 SnapList() : head(NULL),
183 tail(NULL), _size(0) {
186 void push_front(_Tp val) {
187 sllnode<_Tp> * tmp = new sllnode<_Tp>();
199 void push_back(_Tp val) {
200 sllnode<_Tp> * tmp = new sllnode<_Tp>();
206 else tail->next = tmp;
212 sllnode<_Tp> *tmp = head;
220 sllnode<_Tp> *tmp = tail;
228 while(head != NULL) {
229 sllnode<_Tp> *tmp=head->next;
237 void insertAfter(sllnode<_Tp> * node, _Tp val) {
238 sllnode<_Tp> *tmp = new sllnode<_Tp>();
241 tmp->next = node->next;
243 if (tmp->next == NULL) {
246 tmp->next->prev = tmp;
251 void insertBefore(sllnode<_Tp> * node, _Tp val) {
252 sllnode<_Tp> *tmp = new sllnode<_Tp>();
255 tmp->prev = node->prev;
257 if (tmp->prev == NULL) {
260 tmp->prev->next = tmp;
265 sllnode<_Tp> * erase(sllnode<_Tp> * node) {
269 node->prev->next = node->next;
275 tail->next->prev = node->prev;
278 sllnode<_Tp> *next = node->next;
284 sllnode<_Tp> * begin() {
288 sllnode<_Tp> * end() {
314 #define VECTOR_DEFCAP 8
317 template<typename type>
320 ModelVector(uint _capacity = VECTOR_DEFCAP) :
323 array((type *) model_malloc(sizeof(type) * _capacity)) {
326 ModelVector(uint _capacity, type *_array) :
329 array((type *) model_malloc(sizeof(type) * _capacity)) {
330 memcpy(array, _array, capacity * sizeof(type));
337 return array[size - 1];
340 void resize(uint psize) {
341 if (psize <= _size) {
344 } else if (psize > capacity) {
345 array = (type *)model_realloc(array, (psize << 1) * sizeof(type));
346 capacity = psize << 1;
348 bzero(&array[_size], (psize - _size) * sizeof(type));
352 void push_back(type item) {
353 if (_size >= capacity) {
354 uint newcap = capacity << 1;
355 array = (type *)model_realloc(array, newcap * sizeof(type));
358 array[_size++] = item;
361 type operator[](uint index) const {
365 type & operator[](uint index) {
373 type & at(uint index) const {
377 void setExpand(uint index, type item) {
383 void set(uint index, type item) {
387 void insertAt(uint index, type item) {
389 for (uint i = _size - 1;i > index;i--) {
395 void removeAt(uint index) {
396 for (uint i = index;(i + 1) < _size;i++) {
402 inline uint size() const {
422 template<typename type>
425 SnapVector(uint _capacity = VECTOR_DEFCAP) :
428 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
431 SnapVector(uint _capacity, type *_array) :
434 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
435 memcpy(array, _array, capacity * sizeof(type));
442 return array[_size - 1];
445 void resize(uint psize) {
446 if (psize <= _size) {
449 } else if (psize > capacity) {
450 array = (type *)snapshot_realloc(array, (psize <<1 )* sizeof(type));
451 capacity = psize << 1;
453 bzero(&array[_size], (psize - _size) * sizeof(type));
457 void push_back(type item) {
458 if (_size >= capacity) {
459 uint newcap = capacity << 1;
460 array = (type *)snapshot_realloc(array, newcap * sizeof(type));
463 array[_size++] = item;
466 type & operator[](uint index) {
470 type operator[](uint index) const {
478 type & at(uint index) const {
482 void setExpand(uint index, type item) {
488 void set(uint index, type item) {
492 void insertAt(uint index, type item) {
494 for (uint i = _size - 1;i > index;i--) {
500 void removeAt(uint index) {
501 for (uint i = index;(i + 1) < _size;i++) {
507 inline uint size() const {
512 snapshot_free(array);
526 #endif /* __STL_MODEL_H__ */