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() {
158 template<typename _Tp>
161 _Tp getVal() {return val;}
162 sllnode<_Tp> * getNext() {return next;}
163 sllnode<_Tp> * getPrev() {return prev;}
171 friend class SnapList;
174 template<typename _Tp>
178 SnapList() : head(NULL),
179 tail(NULL), _size(0) {
182 void push_front(_Tp val) {
183 sllnode<_Tp> * tmp = new sllnode<_Tp>();
195 void push_back(_Tp val) {
196 sllnode<_Tp> * tmp = new sllnode<_Tp>();
202 else tail->next = tmp;
208 sllnode<_Tp> *tmp = head;
216 sllnode<_Tp> *tmp = tail;
224 while(head != NULL) {
225 sllnode<_Tp> *tmp=head->next;
233 void insertAfter(sllnode<_Tp> * node, _Tp val) {
234 sllnode<_Tp> *tmp = new sllnode<_Tp>();
237 tmp->next = node->next;
239 if (tmp->next == NULL) {
242 tmp->next->prev = tmp;
247 void insertBefore(sllnode<_Tp> * node, _Tp val) {
248 sllnode<_Tp> *tmp = new sllnode<_Tp>();
251 tmp->prev = node->prev;
253 if (tmp->prev == NULL) {
256 tmp->prev->next = tmp;
261 sllnode<_Tp> * erase(sllnode<_Tp> * node) {
265 node->prev->next = node->next;
271 tail->next->prev = node->prev;
274 sllnode<_Tp> *next = node->next;
280 sllnode<_Tp> * begin() {
284 sllnode<_Tp> * end() {
307 #define VECTOR_DEFCAP 8
310 template<typename type>
313 ModelVector(uint _capacity = VECTOR_DEFCAP) :
316 array((type *) model_malloc(sizeof(type) * _capacity)) {
319 ModelVector(uint _capacity, type *_array) :
322 array((type *) model_malloc(sizeof(type) * _capacity)) {
323 memcpy(array, _array, capacity * sizeof(type));
330 return array[size - 1];
333 void resize(uint psize) {
334 if (psize <= _size) {
337 } else if (psize > capacity) {
338 array = (type *)model_realloc(array, (psize << 1) * sizeof(type));
339 capacity = psize << 1;
341 bzero(&array[_size], (psize - _size) * sizeof(type));
345 void push_back(type item) {
346 if (_size >= capacity) {
347 uint newcap = capacity << 1;
348 array = (type *)model_realloc(array, newcap * sizeof(type));
351 array[_size++] = item;
354 type operator[](uint index) const {
358 type & operator[](uint index) {
366 type & at(uint index) const {
370 void setExpand(uint index, type item) {
376 void set(uint index, type item) {
380 void insertAt(uint index, type item) {
382 for (uint i = _size - 1;i > index;i--) {
388 void removeAt(uint index) {
389 for (uint i = index;(i + 1) < _size;i++) {
395 inline uint size() const {
415 template<typename type>
418 SnapVector(uint _capacity = VECTOR_DEFCAP) :
421 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
424 SnapVector(uint _capacity, type *_array) :
427 array((type *) snapshot_malloc(sizeof(type) * _capacity)) {
428 memcpy(array, _array, capacity * sizeof(type));
435 return array[_size - 1];
438 void resize(uint psize) {
439 if (psize <= _size) {
442 } else if (psize > capacity) {
443 array = (type *)snapshot_realloc(array, (psize <<1 )* sizeof(type));
444 capacity = psize << 1;
446 bzero(&array[_size], (psize - _size) * sizeof(type));
450 void push_back(type item) {
451 if (_size >= capacity) {
452 uint newcap = capacity << 1;
453 array = (type *)snapshot_realloc(array, newcap * sizeof(type));
456 array[_size++] = item;
459 type & operator[](uint index) {
463 type operator[](uint index) const {
471 type & at(uint index) const {
475 void setExpand(uint index, type item) {
481 void set(uint index, type item) {
485 void insertAt(uint index, type item) {
487 for (uint i = _size - 1;i > index;i--) {
493 void removeAt(uint index) {
494 for (uint i = index;(i + 1) < _size;i++) {
500 inline uint size() const {
505 snapshot_free(array);
519 #endif /* __STL_MODEL_H__ */