1 /* 2 * alist.h 3 * 4 * Simple double linked list template class. 5 */ 6 7 /* 8 * Copyright (C) 2007 Adam Kropelin 9 * 10 * This program is free software; you can redistribute it and/or 11 * modify it under the terms of version 2 of the GNU General 12 * Public License as published by the Free Software Foundation. 13 * 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * General Public License for more details. 18 * 19 * You should have received a copy of the GNU General Public 20 * License along with this program; if not, write to the Free 21 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 22 * MA 02110-1335, USA. 23 */ 24 25 #ifndef __ALIST_H 26 #define __ALIST_H 27 28 #include <stdlib.h> 29 #include "aiter.h" 30 31 template <class T> class alist 32 { 33 private: 34 35 class node 36 { 37 public: node(const T & elem)38 node(const T& elem) : _next(NULL), _prev(NULL), _elem(elem) {} 39 ~node()40 ~node() { if (_prev) _prev->_next = _next; 41 if (_next) _next->_prev = _prev; } 42 43 operator T&() { return _elem; } 44 T& operator*() { return _elem; } 45 next(node * link)46 void next(node *link) { link->_next = _next; 47 link->_prev = this; 48 if (_next) _next->_prev = link; 49 _next = link; } prev(node * link)50 void prev(node *link) { link->_next = this; 51 link->_prev = _prev; 52 if (_prev) _prev->_next = link; 53 _prev = link; } 54 next()55 node *next() { return _next; } prev()56 node *prev() { return _prev; } 57 58 bool operator==(const node &rhs) const 59 { return _next == rhs._next && _prev == rhs._prev; } 60 61 private: 62 node *_next, *_prev; 63 T _elem; 64 }; 65 66 public: 67 alist()68 alist() : _head(NULL), _tail(NULL), _size(0) {} alist(const alist<T> & rhs)69 alist(const alist<T> &rhs) : _head(NULL), _tail(NULL), _size(0) 70 { append(rhs); } 71 ~alist()72 virtual ~alist() 73 { 74 while (!empty()) remove(begin()); 75 _size = 0; 76 } 77 first()78 T& first() { return *_head; } last()79 T& last() { return *_tail; } 80 empty()81 bool empty() const { return _size <= 0; } size()82 unsigned int size() const { return _size; } 83 append(const T & elem)84 T& append(const T& elem) 85 { 86 node *nd = new node(elem); 87 if (_tail) 88 _tail->next(nd); 89 else 90 _head = nd; 91 _tail = nd; 92 _size++; 93 return *_tail; 94 } 95 prepend(const T & elem)96 T& prepend(const T& elem) 97 { 98 node *nd = new node(elem); 99 if (_head) 100 _head->prev(nd); 101 else 102 _tail = nd; 103 _head = nd; 104 _size++; 105 return *_head; 106 } 107 append(const alist<T> & rhs)108 T& append(const alist<T>& rhs) 109 { 110 if (&rhs != this) 111 { 112 for(const_iterator iter = rhs.begin(); 113 iter != rhs.end(); 114 ++iter) 115 { 116 append(*iter); 117 } 118 } 119 return *_tail; 120 } 121 122 alist<T>& operator+=(const alist<T>& rhs) 123 { 124 append(rhs); 125 return *this; 126 } 127 128 alist<T>& operator=(const alist<T>& rhs) 129 { 130 if (&rhs != this) 131 { 132 clear(); 133 append(rhs); 134 } 135 return *this; 136 } 137 remove_first()138 void remove_first() { if (!empty()) remove(_head); } remove_last()139 void remove_last() { if (!empty()) remove(_tail); } clear()140 void clear() { while (!empty()) remove(_head); } 141 142 class iterator 143 { 144 public: iterator()145 iterator() : _node(NULL) {} iterator(const iterator & rhs)146 iterator(const iterator &rhs) : _node(rhs._node) {} 147 148 iterator &operator++() { _node = _node->next(); return *this; } 149 iterator operator++(int) { iterator tmp(_node); ++(*this); return tmp; } 150 iterator &operator--() { _node = _node->prev(); return *this; } 151 iterator operator--(int) { iterator tmp(_node); --(*this); return tmp; } 152 153 T& operator*() { return *_node; } 154 const T& operator*() const { return *_node; } 155 T* operator->() { return &(**_node); } 156 const T* operator->() const { return &(**_node); } 157 158 bool operator==(const iterator &rhs) const { return _node == rhs._node; } 159 bool operator!=(const iterator &rhs) const { return !(*this == rhs); } 160 161 iterator &operator=(const iterator &rhs) 162 { if (&rhs != this) _node = rhs._node; return *this; } 163 164 private: 165 friend class alist; iterator(node * node)166 iterator(node *node) : _node(node) {} 167 node *_node; 168 }; 169 170 typedef ::const_iterator<iterator, T> const_iterator; 171 begin()172 iterator begin() { return iterator(_head); } end()173 iterator end() { return iterator(NULL); } begin()174 const_iterator begin() const { return iterator(_head); } end()175 const_iterator end() const { return iterator(NULL); } 176 remove(iterator iter)177 iterator remove(iterator iter) { 178 if (iter == _head) _head = iter._node->next(); 179 if (iter == _tail) _tail = iter._node->prev(); 180 iterator newiter(iter._node->next()); 181 delete iter._node; 182 _size--; 183 return newiter; 184 } 185 find(const T & needle)186 iterator find(const T& needle) { 187 iterator iter; 188 for (iter = begin(); iter != end(); ++iter) 189 if (*iter == needle) break; 190 return iter; 191 } 192 find(const T & needle)193 const_iterator find(const T& needle) const { 194 const_iterator iter; 195 for (iter = begin(); iter != end(); ++iter) 196 if (*iter == needle) break; 197 return iter; 198 } 199 front()200 T &front() { return *_head; } front()201 const T &front() const { return *_head; } 202 203 private: 204 205 node *_head, *_tail; 206 unsigned int _size; 207 }; 208 209 #endif 210