1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
/*
* rtlist.h
*
* Copyright (c) 2000-2004 by Florian Fischer (florianfischer@gmx.de)
* and Martin Trautmann (martintrautmann@gmx.de)
*
* This file may be distributed and/or modified under the terms of the
* GNU General Public License version 2 as published by the Free Software
* Foundation.
*
* This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
* WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*
*/
/** \file
* Contains the class template <tt>List</tt>, a double-linked list collection.
* @see List
*/
#ifndef __LRT_LIST__
#define __LRT_LIST__
#include "rtiterator.h"
#include "rtdefs.h"
namespace lrt{
/** A double-linked list collection.
* As opposed to <tt>Vector</tt>s, elements can be inserted and removed very quickly
* into lists, and sequential access to elements (forwards and backwards) is quick, too.
* (The class Iterator is used for this.)
* However, random access to elements is quite slow.
*/
template<class T> class List
{
public:
class Node
{
public:
inline Node* getNext() const { return next; }
inline Node* getPrev() const { return prev; }
inline T& accessElement() { return element; }
inline const T& accessElement() const { return element; }
private:
Node( const T &element ) : element(element), next(0), prev(0) {}
~Node() {}
inline void setNext( Node* nn) { next = nn; }
inline void setPrev( Node* nn) { prev = nn; }
friend class List<T>;
T element;
Node *next;
Node *prev;
};
/** Concrete implementation of an iterator on lists.
* This class is for use by List itself only. Use Iterator instead. */
class IteratorImpl : public lrt::IIteratorImpl<T>
{
public:
virtual ~IteratorImpl() {}
// reimplementing just the virtual functions...
virtual void goToNext() { if(element != 0) element = element->getNext(); }
virtual void goToPrev() { if(element != 0) element = element->getPrev(); }
virtual bool equals(const IIteratorImpl<T> *it) const
{
const IteratorImpl* i = LRT_DYNAMIC_CAST(const IteratorImpl*)(it);
if(!i) return false;
return (element == i->element);
}
virtual bool hasNext() const { if(!element) return false; return (element->getNext() != 0); }
virtual bool hasPrev() const { if(!element) return false; return (element->getPrev() != 0); }
virtual bool hasElement() const { return (element != 0); }
virtual T& get() { return element->accessElement(); }
virtual const T& get() const { return element->accessElement(); }
virtual bool canModify() { return canMod; }
virtual void remove() { if(!element) return; Node* el = element; element = list->remove(el); }
private:
friend class List<T>;
virtual IIteratorImpl<T>* clone() const { return new IteratorImpl(list, element, canMod); }
// el=0 means no element
IteratorImpl(List<T>* const l, Node* el, bool cm) : list(l), element(el), canMod(cm) {}
List<T>* const list;
Node *element;
bool canMod;
};
/** Creates an empty list. */
List();
/** Creates a new list which contains a copy of all entries of the given list. */
List(const List<T> &);
/** Clears the list, then copies all the entries from the given list over to this one. */
List<T> &operator=(const List<T> &);
/** Destroys the list and all of its elements. */
~List();
/** Append an element to the list.
* @param elem The element to append (it will be copied).
* @return A reference to the appended element. */
T& append( const T& elem );
/** Prepend an element to the list.
* @param elem The element to prepend (it will be copied).
* @return A reference to the prepended element. */
T& prepend( const T& elem );
/** Insert an element before the given position.
* @param pos The position after the new element. If the iterator points to nothing,
* the new element is simply appended to the list.
* @param elem The element to insert (it will be copied).
* @return A reference to the inserted element. */
T& insertBefore( Iterator<T> &pos, const T& elem ); // inserts before
/** Insert an element after the given position.
* @param pos The position before the new element. If the iterator points to nothing,
* the new element is simply appended to the list.
* @param elem The element to insert (it will be copied).
* @return A reference to the inserted element. */
T& insertAfter ( Iterator<T> &pos, const T& elem ); // inserts after
/** Remove an element from the list.
* Moves the iterator to the next element of the list. */
inline void remove( Iterator<T> &pos );
/** Remove an element from the list.
* Returns a pointer to the next element of the list. */
Node* remove(Node* element);
/** Remove all elements from the list, and destroy them. */
void clear();
/** Returns the current element count of the list. */
inline int length() const;
/** Returns the current element count of the list. */
inline int getSize() const;
inline Node* first();
inline const Node* first() const;
inline Node* last();
inline const Node* last() const;
/** Returns an unmodifyable iterator to the first element of the list.
* If the list is empty, the iterator points to nothing; you can use
* Iterator::hasElement() to check this. */
inline Iterator<T> begin() const;
/** Returns an unmodifyable iterator to the last element of the list.
* If the list is empty, the iterator points to nothing; you can use
* Iterator::hasElement() to check this. */
inline Iterator<T> end() const;
/** Returns an modifyable iterator to the first element of the list.
* If the list is empty, the iterator points to nothing; you can use
* Iterator::hasElement() to check this. */
inline Iterator<T> begin();
/** Returns an modifyable iterator to the last element of the list.
* If the list is empty, the iterator points to nothing; you can use
* Iterator::hasElement() to check this. */
inline Iterator<T> end();
private:
friend class IteratorImpl; // my iterator
int len;
Node *_begin, *_end;
};
// MSVC++ Bug Workaround
//#ifndef __LRT_TPTR_DEFINED
//#define __LRT_TPTR_DEFINED
//LRT_DEFINE_PTR(T)
//#endif
/** Removes the given node from the list,
* deletes it and advances the pointer to the next node.
* @param list The list to remove the node from.
* @param n A list node.
*/
template<class T> void deleteNode(List<T>& list, typename List<T>::Node*& n);
} // namespace
#include "rtlist.templ.cpp"
#endif
|
