1 /*
2 colortail -- output last part of file(s) in color.
3 Copyright (C) 2009 Joakim Andersson <ja@joakimandersson.se>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 */
19
20 #ifndef _List_h_
21 #define _List_h_
22
23 // Based on list.h by Timothy A. Budd
24
25 #include <assert.h>
26 #include "Iterator.h"
27
28
29 template <class T> class Link;
30 template <class T> class ListIterator;
31
32 // class List
33 template <class T> class List
34 {
35 protected:
36 Link<T>* m_first;
37 friend class ListIterator<T>;
38
39 public:
40 // constructors
41 List();
42 List(const List<T> &source);
43 virtual ~List();
44
45 // operations
46 void add(T value);
47 void add_last(T value);
48 virtual void delete_all_values();
49 List* duplicate() const;
50 T first_element() const;
51 virtual int includes(T value) const;
52 int is_empty() const;
53 virtual void remove_first();
54 };
55
56
57 // class Link
58 template <class T> class Link
59 {
60 private:
61 // constructor
62 Link(T link_value, Link* next);
63 Link(const Link&);
64
65 // duplicate
66 Link* duplicate() const;
67
68 // data areas
69 T m_value;
70 Link* m_next;
71
72 // friends
73 friend class List<T>;
74 friend class ListIterator<T>;
75
76 public:
77 // insert a new element following the current value
78 Link<T>* insert(T val);
79 };
80
81
82 // class ListIterator
83 template <class T> class ListIterator : public Iterator<T>
84 {
85 protected:
86 // data areas
87 Link<T>* m_current;
88 Link<T>* m_previous;
89 List<T>& m_the_list;
90
91 public:
92 // constructor
93 ListIterator(List<T>& list);
94 ListIterator(const ListIterator&);
95
96 // iterator protocol
97 virtual int init();
98 virtual T operator ()();
99 virtual int operator !();
100 virtual int operator ++();
101 virtual void operator =(T value);
102
103 // new methods specific to list iterators
104 void remove_current();
105 void add_before(T new_value);
106 void add_after(T new_value);
107 };
108
109 // class List implementation
110
List()111 template <class T> List<T>::List() : m_first(0)
112 {
113 // no further initialization
114 }
115
~List()116 template <class T> List<T>::~List()
117 {
118 // empty all elements from the list
119 delete_all_values();
120 }
121
122
add(T value)123 template <class T> void List<T>::add(T value)
124 {
125 // add a new value to the front of a linked list
126 m_first = new Link<T>(value, m_first);
127 assert(m_first != 0);
128 }
129
add_last(T value)130 template <class T> void List<T>::add_last(T value)
131 {
132 // add a new value to the read of a linked list
133
134 // check if there isn't a first element
135 if (m_first == 0)
136 {
137 // the list is empty
138 // insert first in list
139 m_first = new Link<T>(value, m_first);
140 assert (m_first != 0);
141 }
142 else
143 {
144 // the list contains elements
145 // find the last element
146 Link<T> *tmp = m_first;
147 while (tmp->m_next)
148 {
149 tmp = tmp->m_next;
150 }
151
152 // at last position in list, add the new element after tmp
153 tmp->m_next = new Link<T>(value, 0);
154 assert (tmp->m_next);
155 }
156 }
157
delete_all_values()158 template <class T> void List<T>::delete_all_values()
159 {
160 // clear all items from the list
161 Link<T> *next;
162
163 for (Link<T> *p = m_first ; p != 0 ; p = next)
164 {
165 // delete the element pointed to by p
166 next = p->m_next;
167 p->m_next = 0;
168 delete p;
169 }
170
171 // mark that the list contains no elements
172 m_first = 0;
173 }
174
duplicate()175 template <class T> List<T>* List<T>::duplicate() const
176 {
177 List<T> *newlist = new List<T>;
178 assert (newlist != 0);
179
180 // copy list
181 if (m_first)
182 {
183 newlist->m_first = m_first->duplicate();
184 }
185
186 // return the new list
187 return newlist;
188 }
189
List(const List<T> & source)190 template <class T> List<T>::List(const List<T> &source)
191 {
192 // duplicate elements from source list
193 if (source.is_empty())
194 {
195 m_first = 0;
196 }
197 else
198 {
199 Link<T> *first_link = source.m_first;
200 m_first = first_link->duplicate();
201 }
202 }
203
first_element()204 template <class T> T List<T>::first_element() const
205 {
206 // return first value in list
207 assert (m_first != 0);
208 return m_first->m_value;
209 }
210
includes(T v)211 template <class T> int List<T>::includes(T v) const
212 {
213 // loop to test each element
214 for (Link<T> *p = m_first ; p ; p = p->m_next)
215 {
216 if (v == p->m_value)
217 {
218 return 1;
219 }
220 }
221
222 // not found
223 return 0;
224 }
225
is_empty()226 template <class T> int List<T>::is_empty() const
227 {
228 // test to see if the list is empty
229 // list is empty if the pointer to the first link is null
230 return m_first == 0;
231 }
232
remove_first()233 template <class T> void List<T>::remove_first()
234 {
235 // make sure there is a first element
236 assert (m_first != 0);
237
238 // save pointer to the removed node
239 Link<T> *p = m_first;
240
241 // reassign the m_first node
242 m_first = p->m_next;
243
244 // recover memory used by the first element
245 delete p;
246 }
247
248
249 // class Link implementation
250
insert(T val)251 template <class T> Link<T>* Link<T>::insert(T val)
252 {
253 // insert a new link after the current node
254 m_next = new Link<T>(val, m_next);
255
256 // check that allocation was successful
257 assert (m_next != 0);
258
259 return m_next;
260 }
261
Link(T val,Link<T> * nxt)262 template <class T> Link<T>::Link(T val, Link<T> *nxt)
263 : m_value(val), m_next(nxt)
264 {
265 // create and initialize a new link field
266 }
267
Link(const Link<T> & source)268 template <class T> Link<T>::Link(const Link<T> &source)
269 : m_value(source.m_value), m_next(source.m_next)
270 {
271 }
272
duplicate()273 template <class T> Link<T>* Link<T>::duplicate() const
274 {
275 Link<T> *newlink;
276
277 // if there is a next field. copy remainder of list
278 if (m_next != 0)
279 {
280 newlink = new Link<T>(m_value, m_next->duplicate());
281 }
282 else
283 {
284 newlink = new Link<T>(m_value, 0);
285 }
286
287 return newlink;
288 }
289
290
291 // class ListIterator implementation
292
ListIterator(List<T> & aList)293 template <class T> ListIterator<T>::ListIterator(List<T> &aList)
294 : m_the_list(aList)
295 {
296 // create and initialize a new list
297 init();
298 }
299
ListIterator(const ListIterator<T> & x)300 template <class T> ListIterator<T>::ListIterator(const ListIterator<T> &x)
301 : m_the_list(x.m_the_list)
302 {
303 init();
304 }
305
init()306 template <class T> int ListIterator<T>::init()
307 {
308 // set the iterator to the first element in the list
309 m_previous = 0;
310 m_current = m_the_list.m_first;
311
312 return m_current != 0;
313 }
314
operator()315 template <class T> T ListIterator<T>::operator ()()
316 {
317 // return the value of current element
318
319 // check to see if there is a current element
320 assert (m_current != 0);
321
322 // return value associated woth current element
323 return m_current->m_value;
324 }
325
326 template <class T> int ListIterator<T>::operator !()
327 {
328 // test for termination of the iterator
329 // if current link references a removed value,
330 // update current to point to next position
331 if (m_current == 0)
332 {
333 if (m_previous != 0)
334 {
335 m_current = m_previous->m_next;
336 }
337 }
338
339 // now see if current link is valid
340 return m_current != 0;
341 }
342
343 template <class T> int ListIterator<T>::operator ++()
344 {
345 // move current pointer to next element
346 // special processing if current link is deleted
347
348 if (m_current == 0)
349 {
350 if (m_previous == 0)
351 {
352 m_current = m_the_list.m_first;
353 }
354 else
355 {
356 m_current = m_previous->m_next;
357 }
358 }
359 else
360 {
361 // advance pointer
362 m_previous = m_current;
363 m_current = m_current->m_next;
364 }
365
366 // return true if we have a valid current element
367 return m_current != 0;
368 }
369
370 template <class T> void ListIterator<T>::operator =(T val)
371 {
372 // modify value of current element
373 assert (m_current != 0);
374
375 // modify value of the current link
376 m_current->m_value = val;
377 }
378
remove_current()379 template <class T> void ListIterator<T>::remove_current()
380 {
381 // remove the current element from a list
382 // make sure there is a current element
383 assert (m_current != 0);
384
385 // case 1, removing first element
386 if (m_previous == 0)
387 {
388 m_the_list.m_first = m_current->m_next;
389 }
390
391 // case 2, not removing the first element
392 else
393 {
394 m_previous->m_next = m_current->m_next;
395 }
396
397 // delete current node
398 delete m_current;
399
400 // and set current point to null
401 m_current = 0;
402 }
403
add_before(T val)404 template <class T> void ListIterator<T>::add_before(T val)
405 {
406 // add a new element to list before current value
407 // case 1, not at start
408 if (m_previous)
409 {
410 m_previous = m_previous->insert(val);
411 }
412
413 // case 2, at start of list
414 else
415 {
416 m_the_list.add(val);
417 m_previous = m_the_list.m_first;
418 m_current = m_previous->m_next;
419 }
420 }
421
add_after(T val)422 template <class T> void ListIterator<T>::add_after(T val)
423 {
424 // add a new element to list after current value
425 // case 1, not at start
426 if (m_current != 0)
427 {
428 m_current->insert(val);
429 }
430
431 // case 2, at end of list
432 else if (m_previous != 0)
433 {
434 m_current = m_previous->insert(val);
435 }
436
437 // case 3, start of list
438 else
439 {
440 m_the_list.add(val);
441 }
442 }
443
444 #endif
445
446
447
448
449
450