1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef doubly_linked_list_h
26 #define doubly_linked_list_h
28 ///////////////////////////////////////////////////////////////////////////
30 ///////////////////////////////////////////////////////////////////////////
32 #include <AD/generic/generic.h> // Generic definitions
34 template <class T
> class LinkedListIter
;
39 friend class LinkedListIter
<T
>;
42 T element
; Node
* last
, * next
;
43 Node (const T
& e
, Node
* prev
, Node
* succ
)
44 : element(e
), last(prev
), next(succ
) {}
47 Node
* front
; // pointer to the beginning
48 Node
* back
; // pointer to the end
49 int size
; // length of list
51 LinkedList(const LinkedList
&); // No copy constructor
52 LinkedList
& operator = (const LinkedList
&); // No assignment
55 class Unimplemented
{};
57 LinkedList() : front(0), back(0), size(0) {}
60 int length() const { return size
; }
61 Bool
is_empty() const { return size
== 0; }
62 T
& head() const { return front
->element
; }
63 T
& tail() const { return back
->element
; }
64 LinkedListIter
<T
> headPos() const { return LinkedListIter
<T
>(front
); }
65 LinkedListIter
<T
> tailPos() const { return LinkedListIter
<T
>(back
); }
67 LinkedList
& insert_before (const T
& e
, LinkedListIter
<T
>& i
);
68 LinkedList
& insert_after (const T
& e
, LinkedListIter
<T
>& i
);
69 LinkedList
& delete_before (LinkedListIter
<T
>& i
);
70 LinkedList
& delete_after (LinkedListIter
<T
>& i
);
72 LinkedList
& insert_head (const T
& e
);
73 LinkedList
& insert_tail (const T
& e
);
74 LinkedList
& delete_head ();
75 LinkedList
& delete_tail ();
77 LinkedList
& operator += (const T
& e
) { return insert_tail(e
); }
81 class LinkedListIter
{
82 friend class LinkedList
<T
>;
83 typename LinkedList
<T
>::Node
* cursor
;
84 LinkedListIter(typename LinkedList
<T
>::Node
* c
) : cursor(c
) {}
86 LinkedListIter() : cursor(0) {}
87 LinkedListIter(LinkedList
<T
>& list
) : cursor(list
.front
) {}
90 void operator = (LinkedList
<T
>& list
) { cursor
= list
.front
; }
91 void operator = (LinkedListIter
& i
) { cursor
= i
.cursor
; }
93 operator typename LinkedList
<T
>::Node
* () const { return cursor
; }
95 void operator ++ (int) { cursor
= cursor
->next
; }
96 void operator ++ () { cursor
= cursor
->next
; }
97 void operator -- (int) { cursor
= cursor
->last
; }
98 void operator -- () { cursor
= cursor
->last
; }
99 T
& operator () () const { return cursor
->element
; }
103 ///////////////////////////////////////////////////////////////////////////
104 // Implementation of the template methods
105 ///////////////////////////////////////////////////////////////////////////
108 LinkedList
<T
>::~LinkedList()
109 { Node
* current
, * succ
;
110 for (current
= front
; current
; current
= succ
) {
111 succ
= current
->next
;
117 inline LinkedList
<T
>& LinkedList
<T
>::insert_head(const T
& e
)
118 { Node
* n
= new Node(e
,0,front
);
119 if (front
) front
->last
= n
;
127 inline LinkedList
<T
>& LinkedList
<T
>::insert_tail(const T
& e
)
128 { Node
* n
= new Node(e
,back
,0);
129 if (back
) back
->next
= n
;
137 inline LinkedList
<T
>& LinkedList
<T
>::delete_head()
138 { Node
* garbage
= front
;
139 if (front
== back
) front
= back
= 0;
140 else { front
= front
->next
; front
->last
= 0; }
147 inline LinkedList
<T
>& LinkedList
<T
>::delete_tail()
148 { Node
* garbage
= back
;
149 if (front
== back
) front
= back
= 0;
150 else { back
= back
->last
; back
->next
= 0; }
157 LinkedList
<T
>& LinkedList
<T
>::insert_before
158 (const T
& e
, LinkedListIter
<T
>& i
)
159 { Node
* n
= new Node(e
,i
.cursor
->last
,i
.cursor
);
160 i
.cursor
->last
->next
= n
;
167 LinkedList
<T
>& LinkedList
<T
>::insert_after
168 (const T
& e
, LinkedListIter
<T
>& i
)
169 { Node
* n
= new Node(e
,i
.cursor
,i
.cursor
->next
);
170 i
.cursor
->next
->last
= n
;
177 LinkedList
<T
>& LinkedList
<T
>::delete_before(LinkedListIter
<T
>& i
)
184 LinkedList
<T
>& LinkedList
<T
>::delete_after(LinkedListIter
<T
>& i
)