Debian Codegraph @

protolib/src/common/protoGraph.cpp

raw
1 /**
2 * @file protoGraph.cpp
3 *
4 * @brief
5 */
6 #include "protoGraph.h"
7 #include "protoDebug.h"
8 #include "manetGraph.h" // for debug
9
10 ProtoGraph::VerticeQueue::VerticeQueue()
11 {
12 }
13
14 ProtoGraph::VerticeQueue::~VerticeQueue()
15 {
16 // Note the original plan was to call the Empty()
17 // method here so that when a VerticeQueue is deleted
18 // it removes any queued Vertices so they aren't left
19 // with a bad pointer. But, you can't call virtual methods
20 // from a destructor in C++. So, the derived classes
21 // MUST call Empty() in their destructors!
22 }
23
24 /**
25 * This should be called whenever a "VerticeQueue" enqueues (inserts) a "Vertice"
26 */
27 void ProtoGraph::VerticeQueue::Associate(Vertice& vertice, QueueState& queueState)
28 {
29 queueState.Associate(vertice, *this);
30 vertice.Reference(queueState);
31 } // end ProtoGraph::VerticeQueue::Associate()
32
33 /**
34 * This should be called whenever a "VerticeQueue" dequeues (removes) a "Vertice"
35 */
36 void ProtoGraph::VerticeQueue::Disassociate(Vertice& vertice, QueueState& queueState)
37 {
38 vertice.Dereference(queueState);
39 queueState.Disassociate();
40 } // end ProtoGraph::VerticeQueue::Disassociate()
41
42 ProtoGraph::Vertice::Vertice()
43 : adjacency_queue(*this)
44 {
45 }
46
47 /**
48 * Make sure no queues still refer to us by
49 * removing ourself from any queues that do)
50 *
51 * @note If were in an "AdjacencyQueue" the call to
52 * VerticeQueue::Remove() will _delete_ the associated
53 * "Edge" since we don't provide a pointer to
54 * "EdgeFactory" here. ("Edges" that aren't dynamically
55 * allocated would cause a problem here!)
56 */
57 ProtoGraph::Vertice::~Vertice()
58 {
59 // If the call to Cleanup() causes some sort of core dump,
60 // it is likely the case that the derived VerticeQueue depends
61 // upon some extension of the base Vertice class for its data
62 // organization. So, derived Vertice types SHOULD/MUST call
63 // Cleanup() themselves so the Cleanup() call doesn't do
64 // anything harmful. In fact, perhaps it would be better to
65 // not call Cleanup() here and require programmers that create
66 // derived Vertice subclasses to call Cleanup(). The way to force
67 // this may be to make the Cleanup() a pure virtual function in
68 // the base class so that subclasses must implement it? There is still
69 // some leftover safety issue here where further derivations are performed ...
70 // Anyway the result here is that a virtual function may end up indirectly
71 // called from this destructor which can have bad behavior
72 Cleanup();
73 }
74
75 void ProtoGraph::Vertice::Cleanup()
76 {
77 while (!queue_state_tree.IsEmpty())
78 {
79 VerticeQueue::QueueState::Entry*entry = static_cast<VerticeQueue::QueueState::Entry*>(queue_state_tree.GetRoot());
80 VerticeQueue* q = entry->GetQueueState().GetQueue();
81 ASSERT(NULL != q);
82 q->Remove(*this);
83 }
84 } // end ProtoGraph::Vertice::Cleanup()
85
86 /**
87 * Default NULL key / keysize implementation for ProtoGraph::Vertice
88 */
89 const char* ProtoGraph::Vertice::GetVerticeKey() const
90 {
91 return NULL;
92 } // end ProtoGraph::Vertice::GetVerticeKey()
93
94 unsigned int ProtoGraph::Vertice::GetVerticeKeysize() const
95 {
96 return 0;
97 } // end ProtoGraph::Vertice::GetVerticeKeysize()
98
99 ProtoTree::Endian ProtoGraph::Vertice::GetVerticeKeyEndian() const
100 {
101 return ProtoTree::ENDIAN_BIG;
102
103 } // end ProtoGraph::Vertice::GetVerticeKeyEndian()
104
105 bool ProtoGraph::Vertice::GetVerticeKeySigned() const
106 {
107 return false;
108 } // end ProtoGraph::Vertice::GetVerticeKeySigned()
109
110 bool ProtoGraph::Vertice::GetVerticeKeyComplement2() const
111 {
112 return true;
113 } // end ProtoGraph::Vertice::GetVerticeKeyComplement2()
114
115 ProtoGraph::VerticeQueue::QueueState::QueueState()
116 : vertice(NULL), queue(NULL), entry(*this)
117 {
118 }
119
120 ProtoGraph::VerticeQueue::QueueState::~QueueState()
121 {
122 Cleanup();
123 }
124
125 void ProtoGraph::VerticeQueue::QueueState::Cleanup()
126 {
127 if (NULL != vertice)
128 {
129 ASSERT(NULL != queue);
130 queue->Remove(*vertice);
131 }
132 } // end ProtoGraph::VerticeQueue::QueueState::Cleanup()
133
134 ProtoGraph::VerticeQueue::QueueStatePool::QueueStatePool()
135 {
136 }
137
138 ProtoGraph::VerticeQueue::QueueStatePool::~QueueStatePool()
139 {
140 Destroy();
141 }
142
143 void ProtoGraph::VerticeQueue::QueueStatePool::Destroy()
144 {
145 while (!IsEmpty())
146 {
147 QueueState* theState = Get();
148 delete theState;
149 }
150 } // end ProtoGraph::VerticeQueue::QueueStatePool::Destroy()
151
152 ProtoGraph::VerticeQueue::QueueState::Entry::Entry(QueueState& theState)
153 : queue_state(theState)
154 {
155 }
156
157
158 ProtoGraph::Vertice::SimpleList::Item::Item()
159 : prev(NULL), next(NULL)
160 {
161 }
162
163 ProtoGraph::Vertice::SimpleList::Item::~Item()
164 {
165 // Removes from "queue" if it is non-NULL
166 Cleanup();
167 }
168
169 ProtoGraph::Vertice::SimpleList::SimpleList(ItemPool* itemPool)
170 : head(NULL), tail(NULL), item_pool(itemPool)
171 {
172 }
173
174 ProtoGraph::Vertice::SimpleList::~SimpleList()
175 {
176 Empty();
177 }
178
179 bool ProtoGraph::Vertice::SimpleList::Prepend(Vertice& vertice)
180 {
181 Item* item = GetNewItem();
182 if (NULL == item)
183 {
184 PLOG(PL_ERROR, "ProtoGraph::Vertice::SimpleList::Prepend() NewItem() error: %s\n", GetErrorString());
185 return false;
186 }
187 Associate(vertice, *item);
188 PrependItem(*item);
189 return true;
190 } // end ProtoGraph::Vertice::SimpleList::Prepend()
191
192 bool ProtoGraph::Vertice::SimpleList::Append(Vertice& vertice)
193 {
194 Item* item = GetNewItem();
195 if (NULL == item)
196 {
197 PLOG(PL_ERROR, "ProtoGraph::Vertice::SimpleList::Append() NewItem() error: %s\n", GetErrorString());
198 return false;
199 }
200 Associate(vertice, *item);
201 AppendItem(*item);
202 return true;
203 } // end ProtoGraph::Vertice::SimpleList::Append()
204
205 void ProtoGraph::Vertice::SimpleList::Remove(Vertice& vertice)
206 {
207 // 1) Retrieve "Item*" from "vertice" queue state
208 Item* item = static_cast<Item*>(vertice.GetQueueState(*this));
209 // 2) Remove "item" from our linked list
210 ASSERT(NULL != item);
211 RemoveItem(*item);
212 Disassociate(vertice, *item);
213 // 3) Return "item" to pool
214 if (NULL != item_pool)
215 item_pool->Put(*item);
216 else
217 delete item;
218 } // end ProtoGraph::Vertice::SimpleList::Remove()
219
220 ProtoGraph::Vertice* ProtoGraph::Vertice::SimpleList::RemoveHead()
221 {
222 if (NULL != head)
223 {
224 Item* item = head;
225 Vertice* vertice = item->GetVertice();
226 ASSERT(NULL != vertice);
227 RemoveItem(*item);
228 Disassociate(*vertice, *item);
229 if (NULL != item_pool)
230 item_pool->Put(*item);
231 else
232 delete item;
233 return vertice;
234 }
235 else
236 {
237 return NULL;
238 }
239 } // end ProtoGraph::Vertice::SimpleList::RemoveHead()
240
241 void ProtoGraph::Vertice::SimpleList::Empty()
242 {
243 while (!IsEmpty()) RemoveHead();
244 } // end ProtoGraph::Vertice::SimpleList::Empty()
245
246 void ProtoGraph::Vertice::SimpleList::PrependItem(Item& item)
247 {
248 item.Prepend(NULL);
249 if (NULL == head)
250 tail = &item;
251 else
252 head->Prepend(&item);
253 item.Append(head);
254 head = &item;
255 } // end ProtoGraph::Vertice::SimpleList::PrependItem()
256
257 void ProtoGraph::Vertice::SimpleList::AppendItem(Item& item)
258 {
259 item.Prepend(tail);
260 if (NULL == tail)
261 head = &item;
262 else
263 tail->Append(&item);
264 item.Append(NULL);
265 tail = &item;
266 } // end ProtoGraph::Vertice::SimpleList::AppendItem()
267
268 void ProtoGraph::Vertice::SimpleList::RemoveItem(Item& item)
269 {
270 Item* prevItem = item.GetPrev();
271 Item* nextItem = item.GetNext();
272 if (NULL != prevItem)
273 prevItem->Append(nextItem);
274 else
275 head = nextItem;
276 if (NULL != nextItem)
277 nextItem->Prepend(prevItem);
278 else
279 tail = prevItem;
280 } // end ProtoGraph::Vertice::SimpleList::RemoveItem()
281
282
283 ProtoGraph::Vertice::SimpleList::Iterator::Iterator(const Vertice::SimpleList& theList, bool reverse)
284 : list(theList), next_item(reverse ? theList.tail : theList.head), forward(!reverse)
285 {
286 }
287
288 ProtoGraph::Vertice::SimpleList::Iterator::~Iterator()
289 {
290 }
291
292 void ProtoGraph::Vertice::SimpleList::Iterator::Reset()
293 {
294 next_item = forward ? list.head : list.tail;
295 } // end ProtoGraph::Vertice::SimpleList::Iterator::Reset()
296
297 ProtoGraph::Vertice* ProtoGraph::Vertice::SimpleList::Iterator::GetNextVertice()
298 {
299 Item* item = next_item;
300 next_item = item ? (forward ? item->GetNext() : item->GetPrev()) : NULL;
301 return item ? item->GetVertice() : NULL;
302 } // end ProtoGraph::Vertice::SimpleList::Iterator::GetNextVertice()
303
304
305 ProtoGraph::Vertice::SimpleList::ItemPool::ItemPool()
306 {
307 }
308
309 ProtoGraph::Vertice::SimpleList::ItemPool::~ItemPool()
310 {
311 Destroy();
312 }
313
314 ProtoGraph::Vertice::SimpleList::Item* ProtoGraph::Vertice::SimpleList::ItemPool::GetItem()
315 {
316 if (IsEmpty())
317 {
318 Item* item = new Item();
319 if (NULL == item)
320 {
321 PLOG(PL_ERROR, "ProtoGraph::Vertice::SimpleList::ItemPool::GetItem() new Item error: %s\n",
322 GetErrorString());
323 return NULL;
324 }
325 else
326 {
327 return item;
328 }
329 }
330 else
331 {
332 return static_cast<Item*>(VerticeQueue::QueueStatePool::Get());
333 }
334 } // end ProtoGraph::Vertice::SimpleList::ItemPool::GetItem()
335
336 ProtoGraph::Vertice::SortedList::SortedList(ItemPool* itemPool)
337 : item_pool(itemPool)
338 {
339 }
340
341 ProtoGraph::Vertice::SortedList::~SortedList()
342 {
343 // Note that Empty() here invokes the Item's
344 // virtual methods GetKey(), etc ...
345 Empty();
346 }
347
348 bool ProtoGraph::Vertice::SortedList::Insert(Vertice& vertice)
349 {
350 Item* item = GetNewItem();
351 if (NULL == item)
352 {
353 DMSG(0, "ProtoGraph::Vertice::SortedList::Insert() GetNewItem() error: %s\n", GetErrorString());
354 return false;
355 }
356 Associate(vertice, *item);
357 InsertItem(*item);
358 return true;
359 } // end ProtoGraph::Vertice::SortedList::Insert()
360
361 bool ProtoGraph::Vertice::SortedList::Append(Vertice& vertice)
362 {
363 Item* item = GetNewItem();
364 if (NULL == item)
365 {
366 DMSG(0, "ProtoGraph::Vertice::SortedList::Append() GetNewItem() error: %s\n", GetErrorString());
367 return false;
368 }
369 Associate(vertice, *item);
370 AppendItem(*item);
371 return true;
372 } // end ProtoGraph::Vertice::SortedList::Append()
373
374 void ProtoGraph::Vertice::SortedList::Remove(Vertice& vertice)
375 {
376 // 1) Retrieve "Item*" from "vertice" queue state
377 Item* item = static_cast<Item*>(vertice.GetQueueState(*this));
378 // 2) Remove "item" from our ProtoSortedTree
379 ASSERT(NULL != item);
380 RemoveItem(*item);
381 Disassociate(vertice, *item);
382 // 3) Return "item" to pool
383 if (NULL != item_pool)
384 item_pool->Put(*item);
385 else
386 delete item;
387 } // end ProtoGraph::Vertice::SortedList::Remove()
388
389 ProtoGraph::Vertice* ProtoGraph::Vertice::SortedList::RemoveHead()
390 {
391 Item* headItem = static_cast<Item*>(sorted_item_tree.GetHead());
392 if (NULL != headItem)
393 {
394 Vertice* vertice = headItem->GetVertice();
395 ASSERT(NULL != vertice);
396 sorted_item_tree.Remove(*headItem);
397 Disassociate(*vertice, *headItem);
398 // 3) Return "item" to pool
399 if (NULL != item_pool)
400 item_pool->Put(*headItem);
401 else
402 delete headItem;
403 return vertice;
404 }
405 else
406 {
407 return NULL;
408 }
409 } // end ProtoGraph::Vertice::SortedList::RemoveHead()
410
411 void ProtoGraph::Vertice::SortedList::Empty()
412 {
413 while (!IsEmpty()) RemoveHead();
414 } // end ProtoGraph::Vertice::SortedList::Empty()
415
416 ProtoGraph::Vertice::SortedList::Item::Item()
417 {
418 }
419
420 ProtoGraph::Vertice::SortedList::Item::~Item()
421 {
422 Cleanup();
423 }
424
425 // required (and optional) overrides for ProtoSortedTree::Item
426 const char* ProtoGraph::Vertice::SortedList::Item::GetKey() const
427 {
428 ASSERT(NULL != GetVertice());
429 return GetVertice()->GetVerticeKey();
430 } // end ProtoGraph::Vertice::SortedList::Item::GetKey()
431
432 unsigned int ProtoGraph::Vertice::SortedList::Item::GetKeysize() const
433 {
434 ASSERT(NULL != GetVertice());
435 return GetVertice()->GetVerticeKeysize();
436 } // end ProtoGraph::Vertice::SortedList::Item::GetKeysize()
437
438 ProtoTree::Endian ProtoGraph::Vertice::SortedList::Item::GetEndian() const
439 {
440 ASSERT(NULL != GetVertice());
441 return GetVertice()->GetVerticeKeyEndian();
442 } // end ProtoGraph::Vertice::SortedList::Item::GetEndian()
443
444 bool ProtoGraph::Vertice::SortedList::Item::UseSignBit() const
445 {
446 ASSERT(NULL != GetVertice());
447 return GetVertice()->GetVerticeKeySigned();
448 } // end ProtoGraph::Vertice::SortedList::Item::UseSignBit()
449
450 bool ProtoGraph::Vertice::SortedList::Item::UseComplement2() const
451 {
452 ASSERT(NULL != GetVertice());
453 return GetVertice()->GetVerticeKeyComplement2();
454 } // end ProtoGraph::Vertice::SortedList::Item::UseComplement2()
455
456
457
458 ProtoGraph::Vertice::SortedList::ItemPool::ItemPool()
459 {
460 }
461
462 ProtoGraph::Vertice::SortedList::ItemPool::~ItemPool()
463 {
464 }
465
466 ProtoGraph::Vertice::SortedList::Item* ProtoGraph::Vertice::SortedList::ItemPool::GetItem()
467 {
468 if (IsEmpty())
469 {
470 Item* item = new Item();
471 if (NULL == item)
472 {
473 PLOG(PL_ERROR, "ProtoGraph::Vertice::SortedList::ItemPool::GetItem() new Item error: %s\n",
474 GetErrorString());
475 return NULL;
476 }
477 else
478 {
479 return item;
480 }
481 }
482 else
483 {
484 return static_cast<Item*>(VerticeQueue::QueueStatePool::Get());
485 }
486 } // end ProtoGraph::Vertice::SortedList::ItemPool::GetItem()
487
488 ProtoGraph::Vertice::SortedList::Iterator::Iterator(SortedList& theList)
489 : ProtoSortedTree::Iterator(theList.sorted_item_tree)
490 {
491 }
492
493 ProtoGraph::Vertice::SortedList::Iterator::~Iterator()
494 {
495 }
496
497
498 // begin "class ProtoGraph::AdjacencyQueue" implementation
499 ProtoGraph::AdjacencyQueue::AdjacencyQueue(Vertice& srcVertice)
500 : src_vertice(srcVertice), adjacency_count(0)
501 {
502 }
503
504 ProtoGraph::AdjacencyQueue::~AdjacencyQueue()
505 {
506 Empty();
507 }
508
509 void ProtoGraph::AdjacencyQueue::Empty()
510 {
511 Edge* edge;
512 while (NULL != (edge = static_cast<Edge*>(adjacency_tree.GetRoot())))
513 {
514 Vertice* dst = edge->GetDst();
515 ASSERT(NULL != dst);
516 Disconnect(*dst);
517 }
518 } // end ProtoGraph::AdjacencyQueue::Empty()
519
520 void ProtoGraph::AdjacencyQueue::Connect(Vertice& dstVertice, Edge& edge)
521 {
522 if (static_cast<VerticeQueue*>(this) != edge.GetQueue())
523 {
524 Associate(dstVertice, edge);
525 adjacency_tree.Insert(edge);
526 dstVertice.AddConnector(edge);
527 adjacency_count++;
528 edge.OnConnect();
529 }
530 else
531 {
532 PLOG(PL_WARN, "ProtoGraph::AdjacencyQueue::Connect() warning: edge already in adjacency queue\n");
533 }
534 } // end ProtoGraph::AdjacencyQueue::Connect()
535
536 void ProtoGraph::AdjacencyQueue::Reconnect(Vertice& dstVertice, Edge& edge)
537 {
538 if (static_cast<VerticeQueue*>(this) != edge.GetQueue())
539 {
540 Associate(dstVertice, edge);
541 adjacency_tree.Insert(edge);
542 dstVertice.AddConnector(edge);
543 adjacency_count++;
544 }
545 else
546 {
547 PLOG(PL_WARN, "ProtoGraph::AdjacencyQueue::Reconnect() warning: edge already in adjacency queue\n");
548 }
549 } // end ProtoGraph::AdjacencyQueue::Reconnect()
550
551 /**
552 * Remove all edges to "dstVertice"
553 */
554 void ProtoGraph::AdjacencyQueue::Disconnect(Vertice& dstVertice,
555 EdgePool* edgePool)
556 {
557 Edge* edge;
558 while (NULL != (edge = static_cast<Edge*>(dstVertice.GetQueueState(*this))))
559 {
560 edge->OnDisconnect();
561 RemoveEdge(dstVertice, *edge, edgePool);
562 }
563 } // end ProtoGraph::AdjacencyQueue::Disconnect()
564
565 void ProtoGraph::AdjacencyQueue::RemoveEdge(Vertice& dstVertice,
566 Edge& edge,
567 EdgePool* edgePool)
568 {
569 if (static_cast<VerticeQueue*>(this) == edge.GetQueue())
570 {
571 SuspendEdge(dstVertice, edge);
572 if (NULL != edgePool){
573 edgePool->Put(edge);
574 }
575 else{
576 delete &edge;
577 }
578 }
579 else
580 {
581 PLOG(PL_WARN, "ProtoGraph::AdjacencyQueue::RemoveEdge() warning: edge not in queue\n");
582 }
583 } // end ProtoGraph::AdjacencyQueue::RemoveEdge()
584
585 void ProtoGraph::AdjacencyQueue::SuspendEdge(Vertice& dstVertice,
586 Edge& edge)
587 {
588 if (static_cast<VerticeQueue*>(this) == edge.GetQueue())
589 {
590 dstVertice.RemoveConnector(edge);
591 adjacency_tree.Remove(edge);
592 Disassociate(dstVertice, edge);
593 adjacency_count--;
594 }
595 else
596 {
597 PLOG(PL_WARN, "ProtoGraph::AdjacencyQueue::SuspendEdge() warning: edge not in queue\n");
598 }
599 } // end ProtoGraph::AdjacencyQueue::SuspendEdge()
600
601
602 void ProtoGraph::AdjacencyQueue::AddConnector(Edge& edge)
603 {
604 connector_tree.Insert(edge.AccessTracker());
605 } // end ProtoGraph::AdjacencyQueue::AddConnector()
606
607 void ProtoGraph::AdjacencyQueue::RemoveConnector(Edge& edge)
608 {
609 connector_tree.Remove(edge.AccessTracker());
610 } // end ProtoGraph::AdjacencyQueue::RemoveConnector()
611
612 ProtoGraph::AdjacencyIterator::AdjacencyIterator(Vertice & vertice)
613 : adj_iterator(vertice.adjacency_queue.adjacency_tree),
614 con_iterator(vertice.adjacency_queue.connector_tree)
615 {
616 }
617
618 ProtoGraph::AdjacencyIterator::~AdjacencyIterator()
619 {
620 }
621
622 ProtoGraph::Vertice* ProtoGraph::AdjacencyIterator::GetNextAdjacency()
623 {
624 Edge* edge = static_cast<Edge*>(adj_iterator.GetNextItem());
625 return ((NULL != edge) ? edge->GetDst() : NULL);
626 } // end ProtoGraph::AdjacencyIterator::GetNextAdjacency()
627
628 ProtoGraph::Vertice* ProtoGraph::AdjacencyIterator::GetNextConnector()
629 {
630 Edge::Tracker* edgeTracker = static_cast<Edge::Tracker*>(con_iterator.GetNextItem());
631 return ((NULL != edgeTracker) ? edgeTracker->GetEdge().GetSrc() : NULL);
632 } // end ProtoGraph::AdjacencyIterator::GetNextConnector()
633
634 ProtoGraph::Edge::Tracker::Tracker(const Edge& theEdge)
635 : edge(theEdge)
636 {
637 }
638
639 ProtoGraph::Edge::Edge()
640 : tracker(*this)
641 {
642 }
643
644 ProtoGraph::Edge::~Edge()
645 {
646 }
647
648 void ProtoGraph::Edge::OnConnect()
649 {
650 }
651
652 void ProtoGraph::Edge::OnDisconnect()
653 {
654 }
655
656 const char* ProtoGraph::Edge::GetKey() const
657 {
658 return NULL;
659 } // end ProtoGraph::Edge::GetKey()
660
661 unsigned int ProtoGraph::Edge::GetKeysize() const
662 {
663 return 0;
664 } // end ProtoGraph::Edge::GetKeysize()
665
666
667 ProtoTree::Endian ProtoGraph::Edge::GetEndian() const
668 {
669 return ProtoSortedTree::Item::GetEndian();
670 } // end ProtoGraph::Edge::GetEndian()
671
672 bool ProtoGraph::Edge::UseSignBit() const
673 {
674 return ProtoSortedTree::Item::UseSignBit();
675 } // end ProtoGraph::Edge::UseSignBit()
676
677 bool ProtoGraph::Edge::UseComplement2() const
678 {
679 return ProtoSortedTree::Item::UseComplement2();
680 } // end ProtoGraph::Edge::UseComplement2()
681
682
683 ProtoGraph::Vertice* ProtoGraph::Edge::GetSrc() const
684 {
685 // TBD - should we do a dynamic_cast to validate that the
686 // "queue" the edge is held in is actually an "AdjacencyQueue" ???
687 AdjacencyQueue* adjQueue = static_cast<AdjacencyQueue*>(QueueState::GetQueue());
688 if (NULL != adjQueue)
689 return &(adjQueue->GetSrc());
690 else
691 return NULL;
692 } // end ProtoGraph::Edge::GetSrc()
693
694 ProtoGraph::EdgePool::EdgePool()
695 {
696 }
697
698 ProtoGraph::EdgePool::~EdgePool()
699 {
700 Destroy();
701 }
702
703 // begin "class ProtoGraph::SimpleTraversal" implementation
704 ProtoGraph::SimpleTraversal::SimpleTraversal(const ProtoGraph& theGraph,
705 Vertice& startVertice,
706 bool depthFirst)
707 : graph(theGraph), start_vertice(startVertice), depth_first(depthFirst),
708 queue_pending(&item_pool), queue_visited(&item_pool)
709 {
710 Reset();
711 }
712
713 ProtoGraph::SimpleTraversal::~SimpleTraversal()
714 {
715 queue_visited.Empty();
716 queue_pending.Empty();
717 item_pool.Destroy();
718 }
719
720 bool ProtoGraph::SimpleTraversal::Reset()
721 {
722 current_level = 0;
723 trans_vertice = NULL;
724 queue_visited.Empty();
725 queue_pending.Empty();
726 if (!queue_pending.Append(start_vertice))
727 {
728 PLOG(PL_ERROR, "ProtoGraph::SimpleTraversal::Reset() error: couldn't enqueue start_vertice\n");
729 return false;
730 }
731 return true;
732 } // end ProtoGraph::SimpleTraversal::Reset()
733
734
735 ProtoGraph::Vertice* ProtoGraph::SimpleTraversal::GetNextVertice(unsigned int* level)
736 {
737 Vertice* currentVertice = queue_pending.GetHead();
738 if (NULL != currentVertice)
739 {
740 queue_pending.TransferVertice(*currentVertice, queue_visited);
741 AdjacencyIterator it(*currentVertice);
742 Edge* nextEdge;
743 Vertice* transAdjacency = NULL;
744 while (NULL != (nextEdge = it.GetNextAdjacencyEdge()))
745 {
746 Vertice* nextVertice = nextEdge->GetDst();
747 ASSERT(NULL != nextVertice);
748 if (!nextVertice->IsInQueue(queue_visited) &&
749 !nextVertice->IsInQueue(queue_pending))
750 {
751 if (!AllowEdge(*currentVertice, *nextEdge)) continue;
752 if (depth_first)
753 {
754 queue_pending.Prepend(*nextVertice);
755 // (TBD) implement level tracking for Depth-first search
756 }
757 else
758 {
759 queue_pending.Append(*nextVertice);
760 if (NULL == transAdjacency)
761 transAdjacency = nextVertice;
762 }
763 }
764 }
765 if (NULL == trans_vertice)
766 {
767 trans_vertice = transAdjacency;
768 }
769 else if (trans_vertice == currentVertice)
770 {
771 current_level++;
772 trans_vertice = transAdjacency;
773 }
774 if (NULL != level) *level = current_level;
775 }
776 return currentVertice;
777 } // end ProtoGraph::SimpleTraversal::GetNextVertice()
778
779 // begin "class ProtoGraph" implementation
780 ProtoGraph::ProtoGraph()
781 : vertice_list(&vertice_list_item_pool)
782 {
783 }
784
785 ProtoGraph::~ProtoGraph()
786 {
787 Empty();
788 vertice_list_item_pool.Destroy();
789 edge_pool.Destroy();
790 }
791
792 ProtoGraph::Edge* ProtoGraph::GetEdge()
793 {
794 Edge* edge = edge_pool.GetEdge();
795 if (NULL == edge) edge = CreateEdge();
796 if (NULL == edge)
797 {
798 PLOG(PL_ERROR, "ProtoGraph::GetEdge() error: unable to allocate Edge\n");
799 return NULL;
800 }
801 return edge;
802 } // end ProtoGraph::GetEdge()
803
804 /**
805 * Iterate over "vertice_list", disconnecting any
806 * adjacencies and then remove each vertice
807 */
808 void ProtoGraph::Empty()
809 {
810 // Note the removed edges are pooled and the
811 // vertices removed are _not_ deleted
812 while (!vertice_list.IsEmpty())
813 {
814 Vertice* v = vertice_list.GetHead();
815 AdjacencyIterator it(*v);
816 Vertice* a;
817 // (TBD) This could be optimized a little more using it.GetNextEdge() instead ???
818 while (NULL != (a = it.GetNextAdjacency()))
819 v->Disconnect(*a, &edge_pool);
820 vertice_list.Remove(*v);
821 }
822 } // end ProtoGraph::Empty()
823
824 bool ProtoGraph::InsertVertice(Vertice& vertice)
825 {
826 if (vertice.IsInQueue(vertice_list))
827 {
828 PLOG(PL_ERROR, "ProtoGraph::InsertVertice() error: vertice already in graph!\n");
829 return false;
830 }
831 else
832 {
833 return vertice_list.Insert(vertice);
834 }
835 } // end ProtoGraph::InsertVertice()
836
837 void ProtoGraph::RemoveVertice(Vertice& vertice)
838 {
839 // 1) Remove all edges to/from this vertice
840 AdjacencyIterator it(vertice);
841 Vertice* next;
842 // a) Remove all edges from this vertice to any "adjacent" vertices
843 while (NULL != (next = it.GetNextAdjacency()))
844 {
845 Disconnect(vertice, *next);
846 }
847 // b) Remove all edges from any "connector" vertices to this vertice
848 while (NULL != (next = it.GetNextConnector()))
849 Disconnect(*next, vertice);
850
851 // 2) Remove "vertice" from the graph "vertice_list"
852 vertice_list.Remove(vertice);
853 } // end ProtoGraph::RemoveVertice()
854
855 /**
856 * Get an "Edge" from our "edge_pool" or create one and
857 * then add the dst/edge to the src's "adjacency_queue"
858 */
859 ProtoGraph::Edge* ProtoGraph::Connect(Vertice& src, Vertice& dst)
860 {
861 ASSERT(src.IsInQueue(vertice_list) && dst.IsInQueue(vertice_list));
862 // 1) Fetch an "Edge" from our "edge_pool" or create one
863 Edge* edge = GetEdge();
864 if (NULL == edge)
865 {
866 PLOG(PL_ERROR, "ProtoGraph::Connect() error: CreateEdge() error: %s\n", GetErrorString());
867 return NULL;
868 }
869 // 2) Add the dst/edge to the src's "adjacency_queue"
870 src.Connect(dst, *edge);
871 return edge;
872 } // end ProtoGraph::Connect()
873
874 /**
875 * Call Reconnect for the source and dst using the provided edge.
876 */
877 void ProtoGraph::Reconnect(Vertice& src, Vertice& dst,Edge& edge)
878 {
879 ASSERT(src.IsInQueue(vertice_list) && dst.IsInQueue(vertice_list));
880 src.Reconnect(dst,edge);
881 return;
882 }
883 /**
884 * Remove "dst" from src.adjacency_queue and return all
885 * edges to "edge_pool"
886 */
887 void ProtoGraph::Disconnect(Vertice& src, Vertice& dst, bool duplex)
888 {
889 // Remove "dst" from src.adjacency_queue and return all edges to "edge_pool"
890 src.Disconnect(dst, &edge_pool);
891 if (duplex) dst.Disconnect(src, &edge_pool);
892 } // end ProtoGraph::Disconnect()
893
894 ProtoGraph::VerticeIterator::VerticeIterator(ProtoGraph& theGraph)
895 : Vertice::SortedList::Iterator(theGraph.vertice_list)
896 {
897 }
898
899 ProtoGraph::VerticeIterator::~VerticeIterator()
900 {
901 }