Debian Codegraph @

protolib/include/protoList.h

raw
1 #ifndef _PROTO_LIST
2 #define _PROTO_LIST
3
4 /**
5 * @class ProtoList
6 *
7 * @brief The ProtoList class provides a simple double linked-list
8 * class with a "ProtoList::Item" base class to use for
9 * deriving your own classes you wish to store in a
10 * ProtoList.
11 *
12 * Note the "ProtoQueue" classes provide some more sophisticated
13 * options like items that can be listed in multiple lists and
14 * automated removal from the multiple lists upon deletion, etc
15 */
16
17 #include "protoDefs.h"
18
19 /**
20 * @class ProtoIterable
21 *
22 * @brief The ProtoIterable is a base class used for Protolib
23 * list, tree, queue, etc implementations so that iterators associated
24 * with these data structures are automatically updated upon
25 * Item addition/removal, list deletion, etc
26 *
27 */
28
29 class ProtoIterable
30 {
31 public:
32 virtual ~ProtoIterable();
33 protected:
34 ProtoIterable();
35
36 class Item {};
37
38 class Iterator
39 {
40 public:
41 virtual ~Iterator();
42 enum Action {REMOVE, PREPEND, APPEND, INSERT, EMPTY};
43
44 bool IsValid() const
45 {return (NULL != iterable);}
46
47 protected:
48 Iterator(ProtoIterable& theIterable);
49
50 // Typical list, etc data structure operations
51 virtual void Update(Item* theItem, Action theAction) = 0;
52
53 friend class ProtoIterable;
54
55 ProtoIterable* iterable;
56
57 private:
58 Iterator* ilist_prev;
59 Iterator* ilist_next;
60 }; // end class ProtoIterable::Iterator
61
62 // Derived classes should call this method upon list, etc modification
63 // actions (i.e. REMOVE, PREPEND, APPEND, INSERT). The associated
64 // iterators' "Update()" methods will be invoked accordingly.
65 void UpdateIterators(Item* theItem, Iterator::Action theAction) const;
66
67 private:
68 friend class Iterator;
69 void AddIterator(Iterator& iterator);
70 void RemoveIterator(Iterator& iterator);
71
72 Iterator* iterator_list_head;
73
74 }; // end class ProtoIterable
75
76 /**
77 * @class ProtoList
78 *
79 * @brief The ProtoList is a basic (doubly) linked list implementation. It derives
80 * from the ProtoIterable class so that associated ProtoList::Iterators are tracked
81 * and updated upon Item addition/removal, list deletion, etc
82 *
83 */
84
85 class ProtoList : private ProtoIterable
86 {
87 public:
88 ProtoList();
89 ~ProtoList();
90
91 class Item;
92 void Prepend(Item& item);
93 void Append(Item& item);
94
95 // This inserts "theItem" _before_ the "nextItem"
96 void Insert(Item& theItem, Item& nextItem);
97
98 // This inserts "theItem" _before_ the "nextItem"
99 void InsertAfter(Item& theItem, Item& prevItem);
100
101 void Remove(Item& item);
102
103 void Empty(); // empties list without deleting items
104
105 void Destroy(); // deletes contents
106
107 bool IsEmpty() const
108 {return (NULL == head);}
109
110 Item* GetHead() const
111 {return head;}
112 Item* GetTail() const
113 {return tail;}
114
115 Item* RemoveHead();
116 Item* RemoveTail();
117
118 class Iterator;
119 friend class Iterator;
120 class ItemPool;
121 /**
122 * @class ProtoList::Item
123 *
124 * @brief Base class to use for deriving your own classes you wish to store in a
125 * ProtoList.
126 */
127 class Item : public ProtoIterable::Item
128 {
129 public:
130 virtual ~Item();
131
132 const Item* GetNext() const
133 {return plist_next;}
134 const Item* GetPrev() const
135 {return plist_prev;}
136
137 protected:
138 Item();
139
140 private:
141 Item* plist_prev;
142 Item* plist_next;
143
144 friend class ProtoList;
145 friend class Iterator;
146 friend class ItemPool;
147 }; // end class ProtoList::Item()
148 /**
149 * @class ProtoList::Iterator
150 *
151 * @brief ProtoList::Item iterator.
152 */
153 class Iterator : private ProtoIterable::Iterator
154 {
155 friend class ProtoList;
156 public:
157 Iterator(ProtoList& theList, bool reverse = false);
158 ~Iterator();
159
160 bool IsValid() const
161 {return ProtoIterable::Iterator::IsValid();}
162
163 void Reset(bool reverse = false);
164 Item* GetNextItem();
165 Item* PeekNextItem() const
166 {return item;}
167 Item* GetPrevItem();
168 Item* PeekPrevItem() const;
169
170 bool SetCursor(Item* cursor)
171 {
172 item = cursor;
173 return true; // note list membership not validated
174 }
175 Item* GetCursor() const
176 {return item;}
177
178 void Reverse();
179 bool IsReversed() const
180 {return reversed;}
181
182 private:
183 // Required override for ProtoIterable to make sure any
184 // iterators associated with a list are updated upon
185 // Item addition or removal.
186 void Update(ProtoIterable::Item* theItem, Action theAction);
187
188 Item* item;
189 bool reversed;
190
191 }; // end class ProtoList::Iterator
192
193 class ItemPool
194 {
195 friend class ProtoList;
196 public:
197 ItemPool();
198 ~ItemPool();
199
200 bool IsEmpty() const
201 {return (NULL == head);}
202
203 Item* Get();
204 void Put(Item& item);
205
206 void Destroy();
207
208 private:
209 Item* head;
210 }; // end class ProtoList::ItemPool
211
212 // Transfers list contents directly to pool
213 // using existing linking
214 void EmptyToPool(ItemPool& pool);
215
216 // Generally, a ProtoList::Iterator should be
217 // used instead of these
218 Item* GetNextItem(Item& item)
219 {return item.plist_next;}
220 Item* GetPrevItem(Item& item)
221 {return item.plist_prev;}
222
223 private:
224 Item* head;
225 Item* tail;
226
227 }; // end class ProtoList
228
229 /**
230 * @class ProtoListTemplate
231 *
232 * @brief The ProtoListTemplate definition lets you create new list variants that
233 * are type checked at compile time, etc.
234 *
235 * Note the "ITEM_TYPE" _must_
236 * be a class that is derived from "ProtoList::Item"
237 * A simple example is provided in the comments.
238 */
239 template <class ITEM_TYPE>
240 class ProtoListTemplate : public ProtoList
241 {
242 public:
243 ProtoListTemplate() {}
244 virtual ~ProtoListTemplate() {}
245
246 ITEM_TYPE* GetHead() const
247 {return static_cast<ITEM_TYPE*>(ProtoList::GetHead());}
248 ITEM_TYPE* GetTail() const
249 {return static_cast<ITEM_TYPE*>(ProtoList::GetTail());}
250 ITEM_TYPE* RemoveHead()
251 {return static_cast<ITEM_TYPE*>(ProtoList::RemoveHead());}
252 ITEM_TYPE* RemoveTail()
253 {return static_cast<ITEM_TYPE*>(ProtoList::RemoveTail());}
254
255 class Iterator : public ProtoList::Iterator
256 {
257 public:
258 Iterator(ProtoListTemplate& theList, bool reverse = false)
259 : ProtoList::Iterator(theList, reverse) {}
260 ~Iterator() {}
261
262 void Reset(bool reverse = false)
263 {ProtoList::Iterator::Reset(reverse);}
264 ITEM_TYPE* GetNextItem()
265 {return static_cast<ITEM_TYPE*>(ProtoList::Iterator::GetNextItem());}
266 ITEM_TYPE* PeekNextItem() const
267 {return static_cast<ITEM_TYPE*>(ProtoList::Iterator::PeekNextItem());}
268 ITEM_TYPE* GetPrevItem()
269 {return static_cast<ITEM_TYPE*>(ProtoList::Iterator::GetPrevItem());}
270 ITEM_TYPE* PeekPrevItem() const
271 {return static_cast<ITEM_TYPE*>(ProtoList::Iterator::PeekPrevItem());}
272
273 }; // end class ProtoListTemplate::Iterator
274
275 class ItemPool : public ProtoList::ItemPool
276 {
277 public:
278 ItemPool() {}
279 ~ItemPool() {}
280
281 void Put(ITEM_TYPE& item)
282 {ProtoList::ItemPool::Put(item);}
283
284 ITEM_TYPE* Get()
285 {return static_cast<ITEM_TYPE*>(ProtoList::ItemPool::Get());}
286 }; // end class ProtoListTemplate::ItemPool
287
288 }; // end ProtoListTemplate
289
290 /******
291 * An example of how to use the ProtoListTemplate with
292 * your own type derived *from ProtoList::Item".
293 *
294 * Note that "ProtoList" itself may be used directly to do the same
295 * thing, but using the template will save you some "static_casts", etc
296 * for item retrieval, list iteration, etc and may have some other
297 * benefits.
298
299
300 class MyItem : public ProtoList::Item
301 {
302 public:
303 MyItem(int v) : value(v) {}
304 int GetValue() const {return value;}
305 private:
306 int value;
307 };
308
309 class MyItemList : public ProtoListTemplate<MyItem> {};
310
311 MyItemList itemList;
312 MyItem item1(1), item2(2);
313
314 itemList.Append(item1);
315 itemList.Append(item2);
316
317 MyItem* headItem = itemList.GetHead();
318
319 ...
320
321 ************************************/
322
323 /**
324 * @class ProtoStack
325 *
326 * @brief The ProtoStack class is like the ProtoList and similarly provides a
327 * ProtoStackTemplate that can be used for deriving easier-to-
328 * use variants for custom items sub-classed from the ProtoStack::Item.
329 *
330 * The ProtoStack is a singly linked-list with Push() and Pop() methods
331 * but does keep track of both the list head and tail and so can be
332 * optionally "appended" and used as a FIFO. Additionally, an iterator
333 * is provided to explore the list from head to tail.
334 *
335 * TBD - implement as derivation from ProtoIterable ...
336 */
337 class ProtoStack
338 {
339 public:
340 ProtoStack();
341 ~ProtoStack();
342
343 class Item;
344
345 // These methods manipulate the ProtoStack as a "stack"
346 void Push(Item& item); // prepend item to list head
347 Item* Pop(); // removes/returns list head
348 Item* Peek() const
349 {return head;}
350
351 // These methods manipulate the ProtoStack as a "FIFO"
352 void Put(Item& item); // append item to list tail
353 Item* Get() // remove/returns list head
354 {return Pop();}
355
356 bool IsEmpty() const
357 {return (NULL == head);}
358 Item* GetHead() const
359 {return head;}
360 Item* GetTail() const
361 {return tail;}
362 void Destroy();
363
364 class Iterator;
365 friend class Iterator;
366 /**
367 * @class ProtoStack::Item
368 *
369 * @brief Base class to use for deriving your own classes you wish to store in a
370 * ProtoStack.
371 */
372 class Item
373 {
374 public:
375 virtual ~Item();
376
377 protected:
378 Item();
379
380 private:
381 Item* pstack_next;
382
383 friend class ProtoStack;
384 friend class Iterator;
385 }; // end class ProtoStack::Item()
386 /**
387 * @class ProtoStack::Iterator
388 *
389 * @brief ProtoStack::Item Iterator
390 */
391 class Iterator
392 {
393 public:
394 Iterator(const ProtoStack& theStack);
395 ~Iterator();
396
397 void Reset()
398 {next = stack.head;}
399
400 Item* GetNextItem();
401 Item* PeekNextItem() const
402 {return next;}
403
404 private:
405 const ProtoStack& stack;
406 Item* next;
407 }; // end class ProtoStack::Iterator
408
409 private:
410 Item* head;
411 Item* tail;
412
413 }; // end class ProtoStack
414
415 /**
416 * @class ProtoStackTemplate
417 *
418 * @brief The ProtoStackTemplate definition lets you create new list variants that
419 * are type checked at compile time, etc. Note the "ITEM_TYPE" _must_
420 * be a class that is derived from "ProtoStack::Item"
421 *
422 * A simple example is provided in the comments.
423 */
424 template <class ITEM_TYPE>
425 class ProtoStackTemplate : public ProtoStack
426 {
427 public:
428 ProtoStackTemplate() {}
429 virtual ~ProtoStackTemplate() {}
430
431 void Push(ITEM_TYPE& item)
432 {ProtoStack::Push(item);}
433 ITEM_TYPE* Pop()
434 {return static_cast<ITEM_TYPE*>(ProtoStack::Pop());}
435 ITEM_TYPE* Peek()
436 {return static_cast<ITEM_TYPE*>(ProtoStack::Peek());}
437 ITEM_TYPE* Get()
438 {return static_cast<ITEM_TYPE*>(ProtoStack::Get());}
439 ITEM_TYPE* GetHead() const
440 {return static_cast<ITEM_TYPE*>(ProtoStack::GetHead());}
441 ITEM_TYPE* GetTail() const
442 {return static_cast<ITEM_TYPE*>(ProtoStack::GetTail());}
443
444 class Iterator : public ProtoStack::Iterator
445 {
446 public:
447 Iterator(const ProtoStackTemplate& theList, bool reverse = false)
448 : ProtoStack::Iterator(theList) {}
449 ~Iterator() {}
450
451 void Reset()
452 {ProtoStack::Iterator::Reset();}
453 ITEM_TYPE* GetNextItem()
454 {return static_cast<ITEM_TYPE*>(ProtoStack::Iterator::GetNextItem());}
455 ITEM_TYPE* PeekNextItem() const
456 {return static_cast<ITEM_TYPE*>(ProtoStack::Iterator::PeekNextItem());}
457
458 }; // end class ProtoStackTemplate::Iterator
459
460 }; // end ProtoStackTemplate
461
462 #endif // _PROTO_LIST