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