Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. #ifndef _LIST_INCLUDED
  2. #define _LIST_INCLUDED
  3. #include <stdlib.h>
  4. namespace std
  5. {
  6.         struct __list_node_base
  7.         {
  8.                 __list_node_base* prev;
  9.                 __list_node_base* next;
  10.         };
  11.         template <class T> struct __list_node : __list_node_base
  12.         {
  13.                 T data;
  14.                 __list_node(const T& d):data(d){}
  15.         };
  16.         template <class T> class list
  17.         {
  18.                 __list_node_base head;  // head.prev = end, head.next = start
  19.                 unsigned _size;
  20.         public:
  21.                 list():_size(0) {head.prev=head.next=&head;}
  22.                 ~list() {clear();}
  23.                 void clear()
  24.                 {
  25.                         __list_node<T>* a =
  26.                                 static_cast<__list_node<T>*>(head.next);
  27.                         while (a!=&head)
  28.                         {
  29.                                 __list_node<T>* b =
  30.                                         static_cast<__list_node<T>*>(a->next);
  31.                                 delete a;
  32.                                 a = b;
  33.                         }
  34.                         head.prev = head.next = &head;
  35.                         _size = 0;
  36.                 }
  37.                 class iterator
  38.                 {
  39.                 public:
  40.                         __list_node_base* cur;
  41.                         friend class list;
  42.                         iterator(){}
  43.                         iterator(__list_node_base*c):cur(c){}
  44.                         iterator(const iterator& it):cur(it.cur){}
  45.                         iterator& operator++()
  46.                         {cur=cur->next;return *this;}
  47.                         iterator operator++(int)
  48.                         {iterator tmp(*this);cur=cur->next;return tmp;}
  49.                         iterator& operator--()
  50.                         {cur=cur->prev;return *this;}
  51.                         iterator operator--(int)
  52.                         {iterator tmp(*this);cur=cur->prev;return tmp;}
  53.                         bool operator!=(const iterator& it)
  54.                         {return cur!=it.cur;}
  55.                         bool operator==(const iterator& it)
  56.                         {return cur==it.cur;}
  57.                         T& operator*()
  58.                         {return static_cast<__list_node<T>*>(cur)->data;}
  59.                         T* operator->() {return &**this;}
  60.                 };
  61.                 class const_iterator
  62.                 {
  63.                         const __list_node_base* cur;
  64.                         friend class list;
  65.                 public:
  66.                         const_iterator(){}
  67.                         const_iterator(const __list_node_base*c):cur(c){}
  68.                         const_iterator(const const_iterator& it):cur(it.cur){}
  69.                         const_iterator(const iterator& it):cur(it.cur){}
  70.                         const_iterator& operator++()
  71.                         {cur=cur->next;return *this;}
  72.                         const_iterator operator++(int)
  73.                         {const_iterator tmp(*this);cur=cur->next;return tmp;}
  74.                         const_iterator& operator--()
  75.                         {cur=cur->prev;return *this;}
  76.                         const_iterator operator--(int)
  77.                         {const_iterator tmp(*this);cur=cur->prev;return tmp;}
  78.                         bool operator!=(const const_iterator& it)
  79.                         {return cur!=it.cur;}
  80.                         bool operator==(const const_iterator& it)
  81.                         {return cur==it.cur;}
  82.                         const T& operator*()
  83.                         {return static_cast<const __list_node<T>*>(cur)->data;}
  84.                         const T* operator->() {return &**this;}
  85.                 };
  86.                 iterator erase(iterator it)
  87.                 {
  88.                         if (it==end()) return it;
  89.                         it.cur->prev->next = it.cur->next;
  90.                         it.cur->next->prev = it.cur->prev;
  91.                         iterator res(it.cur->next);
  92.                         delete static_cast<__list_node<T>*>(it.cur);
  93.                         --_size;
  94.                         return res;
  95.                 }
  96.                 iterator erase(iterator first, iterator last)
  97.                 {
  98.                         while (first!=last)
  99.                                 first=erase(first);
  100.                         return first;
  101.                 }
  102.                 void pop_front(void) {erase(begin());}
  103.                 class reverse_iterator
  104.                 {
  105.                         __list_node_base* cur;
  106.                         friend class list;
  107.                 public:
  108.                         reverse_iterator(){}
  109.                         reverse_iterator(__list_node_base*c):cur(c){}
  110.                         reverse_iterator(const reverse_iterator& it):
  111.                           cur(it.cur){}
  112.                         reverse_iterator& operator++()
  113.                         {cur=cur->prev;return *this;}
  114.                         reverse_iterator operator++(int)
  115.                         {reverse_iterator tmp(*this);
  116.                         cur=cur->prev;return tmp;}
  117.                         bool operator!=(const reverse_iterator& it)
  118.                         {return cur!=it.cur;}
  119.                         bool operator==(const reverse_iterator& it)
  120.                         {return cur==it.cur;}
  121.                         T& operator*()
  122.                         {return static_cast<__list_node<T>*>(cur)->data;}
  123.                 };
  124.                 class const_reverse_iterator
  125.                 {
  126.                         const __list_node_base* cur;
  127.                         friend class list;
  128.                 public:
  129.                         const_reverse_iterator(){}
  130.                         const_reverse_iterator(const __list_node_base*c):cur(c){}
  131.                         const_reverse_iterator(const const_reverse_iterator& it):
  132.                           cur(it.cur){}
  133.                         const_reverse_iterator& operator++()
  134.                         {cur=cur->prev;return *this;}
  135.                         const_reverse_iterator operator++(int)
  136.                         {const_reverse_iterator tmp(*this);
  137.                         cur=cur->prev;return tmp;}
  138.                         bool operator!=(const const_reverse_iterator& it)
  139.                         {return cur!=it.cur;}
  140.                         bool operator==(const const_reverse_iterator& it)
  141.                         {return cur==it.cur;}
  142.                         const T& operator*()
  143.                         {return static_cast<__list_node<T>*>(cur)->data;}
  144.                 };
  145.                 void push_front(const T& x)
  146.                 {
  147.                         __list_node<T>* a = new __list_node<T>(x);
  148.                         a->next = head.next;
  149.                         a->prev = &head;
  150.                         head.next = a;
  151.                         a->next->prev = a;
  152.                         ++_size;
  153.                 }
  154.                 void push_back(const T& x)
  155.                 {
  156.                         __list_node<T>* a = new __list_node<T>(x);
  157.                         a->next = &head;
  158.                         a->prev = head.prev;
  159.                         head.prev = a;
  160.                         a->prev->next = a;
  161.                         ++_size;
  162.                 }
  163.                 iterator begin() {return iterator(head.next);}
  164.                 const_iterator begin() const {return const_iterator(head.next);}
  165.                 iterator end() {return iterator(&head);}
  166.                 const_iterator end() const {return const_iterator(&head);}
  167.                 reverse_iterator rbegin()
  168.                 {return reverse_iterator(head.prev);}
  169.                 reverse_iterator rend() {return reverse_iterator(&head);}
  170.                 void remove(const T& x)
  171.                 {
  172.                         __list_node<T>* a =
  173.                                 static_cast<__list_node<T>*>(head.next);
  174.                         while (a!=&head)
  175.                         {
  176.                                 __list_node<T>* b =
  177.                                         static_cast<__list_node<T>*>(a->next);
  178.                                 if (a->data==x)
  179.                                 {
  180.                                         a->prev->next = a->next;
  181.                                         a->next->prev = a->prev;
  182.                                         delete a;
  183.                                         --_size;
  184.                                 }
  185.                                 a=b;
  186.                         }
  187.                 }
  188.                 unsigned size() const {return _size;}
  189.                 bool empty() const {return _size==0;}
  190.         };
  191. }
  192. #endif
  193.