| 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 |