| 1 |
#ifndef _PROTO_GRAPH |
| 2 |
#define _PROTO_GRAPH |
| 3 |
|
| 4 |
#include "protoTree.h" |
| 5 |
#include "protoDebug.h" |
| 6 |
#include "protoDefs.h" |
| 7 |
|
| 8 |
// TBD - this could be re-implemented using ProtoQueue classes |
| 9 |
// for VerticeQueue, etc. |
| 10 |
|
| 11 |
/** |
| 12 |
* @class ProtoGraph |
| 13 |
* |
| 14 |
* @brief Base class for managing graph data structures. |
| 15 |
*/ |
| 16 |
class ProtoGraph |
| 17 |
{ |
| 18 |
public: |
| 19 |
ProtoGraph(); |
| 20 |
virtual ~ProtoGraph(); |
| 21 |
|
| 22 |
/** |
| 23 |
* @class Vertice |
| 24 |
* |
| 25 |
* @brief A basic ProtoGraph element, the "vertice" |
| 26 |
*/ |
| 27 |
class Vertice; |
| 28 |
/** |
| 29 |
* @class Edge |
| 30 |
* |
| 31 |
* @brief A basic ProtoGraph element, the "edge" |
| 32 |
*/ |
| 33 |
class Edge; |
| 34 |
|
| 35 |
// (TBD) We should probably give the ProtoGraph |
| 36 |
// a "VerticeFactory" and require vertices be |
| 37 |
// managed _under_ the graph (no Insert/Remove) since |
| 38 |
// our Vertice class only has one AdjacencyQueue |
| 39 |
// member. Otherwise we would need to give the Vertice |
| 40 |
// a "GraphList" with each GraphList::Item having |
| 41 |
// the "AdjacencyQueue" for that corresponding graph? |
| 42 |
|
| 43 |
bool InsertVertice(Vertice& vertice); |
| 44 |
|
| 45 |
void RemoveVertice(Vertice& vertice); // associated links are removed with vertice |
| 46 |
|
| 47 |
Vertice* FindVertice(const char* key, unsigned int keysize) const |
| 48 |
{return vertice_list.FindVertice(key, keysize);} |
| 49 |
|
| 50 |
bool IsInGraph(const Vertice& vertice) const |
| 51 |
{return (vertice.IsInQueue(vertice_list));} |
| 52 |
|
| 53 |
|
| 54 |
// "Connect()" creates a directed edge from "src" to "dst" |
| 55 |
Edge* Connect(Vertice& src, Vertice& dst); |
| 56 |
|
| 57 |
void Reconnect(Vertice& src, Vertice& dst, Edge& edge); |
| 58 |
|
| 59 |
void Disconnect(Vertice& src, Vertice& dst, bool duplex = false); |
| 60 |
|
| 61 |
bool IsEmpty() const |
| 62 |
{return vertice_list.IsEmpty();} |
| 63 |
|
| 64 |
// Disconnect and remove any inserted vertices |
| 65 |
// (does not delete the vertices) |
| 66 |
void Empty(); |
| 67 |
|
| 68 |
|
| 69 |
/** |
| 70 |
* @class ProtoGraph::AdjacencyIterator |
| 71 |
*/ |
| 72 |
class AdjacencyIterator |
| 73 |
{ |
| 74 |
public: |
| 75 |
AdjacencyIterator(Vertice& vertice); |
| 76 |
virtual ~AdjacencyIterator(); |
| 77 |
|
| 78 |
// TBD - provide some iteration options here. For example, |
| 79 |
// iterate conjointly over "adjacencies" and "connectors" |
| 80 |
|
| 81 |
// @brief Returns next vertice _to_ which there is connection |
| 82 |
Vertice* GetNextAdjacency(); |
| 83 |
|
| 84 |
// @brief Returns next edge _to_ which there is connection |
| 85 |
Edge* GetNextAdjacencyEdge() |
| 86 |
{return static_cast<Edge*>(adj_iterator.GetNextItem());} |
| 87 |
|
| 88 |
// @brief Returns next vertice _from_ which there is connection |
| 89 |
// (note can use Vertice::GetEdgeTo(vertice) to get that edge if desired) |
| 90 |
Vertice* GetNextConnector(); |
| 91 |
|
| 92 |
void Reset() |
| 93 |
{ |
| 94 |
adj_iterator.Reset(); |
| 95 |
con_iterator.Reset(); |
| 96 |
} |
| 97 |
|
| 98 |
private: |
| 99 |
ProtoSortedTree::Iterator adj_iterator; |
| 100 |
ProtoSortedTree::Iterator con_iterator; |
| 101 |
|
| 102 |
}; // end class ProtoGraph::Vertice::AdjacencyIterator |
| 103 |
|
| 104 |
/** |
| 105 |
* @class VerticeQueue |
| 106 |
* |
| 107 |
* @brief Base class for Queues that wish to contain Vertices. Note that |
| 108 |
* the VerticeQueue does _not_ itself implement any form of list or tree, etc |
| 109 |
* but instead leaves the specific form of data structure to derived |
| 110 |
* subclasses so that VerticeQueues may be implemented in different ways. The |
| 111 |
* VerticeQueue really just provides a base means for Vertices to keep track |
| 112 |
* of which lists they are in and the pure virtual VerticeQueue::Remove() method |
| 113 |
* is where a Vertice should get disassociated from the given VerticeQueue derivative |
| 114 |
*/ |
| 115 |
|
| 116 |
class VerticeQueue |
| 117 |
{ |
| 118 |
public: |
| 119 |
virtual ~VerticeQueue(); |
| 120 |
|
| 121 |
virtual void Remove(Vertice& vertice) = 0; |
| 122 |
|
| 123 |
virtual void Empty() = 0; // MUST remove all items from queue |
| 124 |
|
| 125 |
bool Contains(const Vertice& vertice) |
| 126 |
{return (NULL != vertice.GetQueueState(*this));} |
| 127 |
|
| 128 |
class QueueStatePool; |
| 129 |
/** |
| 130 |
* @class QueueState |
| 131 |
* |
| 132 |
* @brief The "ProtoGraph::VerticeQueue::QueueState" |
| 133 |
* class is a base class that enables |
| 134 |
* the "Vertice" class to keep track of the |
| 135 |
* VerticeQueues to which it belongs. Additionally, |
| 136 |
* those VerticeQueue subclasses can extend |
| 137 |
* the VerticeQueue::QueueState class to contain |
| 138 |
* additional state that is associated with the |
| 139 |
* given vertice in the context of that VerticeQueue |
| 140 |
*/ |
| 141 |
class QueueState |
| 142 |
{ |
| 143 |
friend class VerticeQueue; |
| 144 |
friend class Vertice; |
| 145 |
friend class QueueStatePool; |
| 146 |
|
| 147 |
public: |
| 148 |
virtual ~QueueState(); |
| 149 |
|
| 150 |
Vertice* GetVertice() const |
| 151 |
{return vertice;} |
| 152 |
VerticeQueue* GetQueue() const |
| 153 |
{return queue;} |
| 154 |
|
| 155 |
protected: |
| 156 |
QueueState(); |
| 157 |
|
| 158 |
// IMPORTANT: Any derived QueueState classes MUST call |
| 159 |
// cleanup in their destructor to avoid possible indirect |
| 160 |
// calls to virtual functions in the ~QueueState() destructor |
| 161 |
void Cleanup(); |
| 162 |
|
| 163 |
void Associate(Vertice& theVertice, VerticeQueue& theQueue) |
| 164 |
{ |
| 165 |
vertice = &theVertice; |
| 166 |
queue = &theQueue; |
| 167 |
} |
| 168 |
void Disassociate() |
| 169 |
{ |
| 170 |
vertice = NULL; |
| 171 |
queue = NULL; |
| 172 |
} |
| 173 |
|
| 174 |
void SetQueue(VerticeQueue& theQueue) |
| 175 |
{queue = &theQueue;} |
| 176 |
|
| 177 |
/** |
| 178 |
* @class Entry |
| 179 |
* |
| 180 |
* @brief Container used by Vertices to keep |
| 181 |
* their lists of VerticeQueueState |
| 182 |
*/ |
| 183 |
class Entry : public ProtoTree::Item |
| 184 |
{ |
| 185 |
public: |
| 186 |
Entry(QueueState& queueState); |
| 187 |
QueueState& GetQueueState() const |
| 188 |
{return queue_state;} |
| 189 |
|
| 190 |
const char* GetKey() const |
| 191 |
{return ((const char*)queue_state.GetQueueHandle());} |
| 192 |
unsigned int GetKeysize() const |
| 193 |
{return (sizeof(VerticeQueue*) << 3);} |
| 194 |
|
| 195 |
private: |
| 196 |
QueueState& queue_state; // "parent" VerticeQueueState |
| 197 |
}; // end class ProtoGraph::Vertice::Queue::QueueState::Entry |
| 198 |
|
| 199 |
Entry& AccessEntry() {return entry;} |
| 200 |
|
| 201 |
const VerticeQueue** GetQueueHandle() const |
| 202 |
{return ((const VerticeQueue**)&queue);} |
| 203 |
|
| 204 |
private: |
| 205 |
Vertice* vertice; |
| 206 |
VerticeQueue* queue; // "parent" VerticeQueue |
| 207 |
Entry entry; |
| 208 |
|
| 209 |
}; // end class ProtoGraph::VerticeQueue::QueueState |
| 210 |
/** |
| 211 |
* @class ProtoGraph::VerticeQueue::QueueStatePool |
| 212 |
* |
| 213 |
* @brief QueueState repository. Note that a QueueStatePool |
| 214 |
* should ony be used to cache a single (i.e. homogeneous) type |
| 215 |
* of QueueState (i.e. QueueState subclass) otherwise one |
| 216 |
* may not "Get()" what one expects from the pool! |
| 217 |
*/ |
| 218 |
class QueueStatePool : public ProtoTree::ItemPool |
| 219 |
{ |
| 220 |
public: |
| 221 |
QueueStatePool(); |
| 222 |
virtual ~QueueStatePool(); |
| 223 |
|
| 224 |
void Destroy(); |
| 225 |
|
| 226 |
QueueState* Get() |
| 227 |
{ |
| 228 |
QueueState::Entry* entry = static_cast<QueueState::Entry*>(ProtoTree::ItemPool::Get()); |
| 229 |
return ((NULL != entry) ? &(entry->GetQueueState()) : NULL); |
| 230 |
} |
| 231 |
|
| 232 |
void Put(QueueState& theState) |
| 233 |
{ProtoTree::ItemPool::Put(theState.AccessEntry());} |
| 234 |
|
| 235 |
}; // end class ProtoGraph::VerticeQueue::QueueStatePool |
| 236 |
|
| 237 |
protected: |
| 238 |
VerticeQueue(); |
| 239 |
|
| 240 |
void TransferQueueState(QueueState& queueState, VerticeQueue& dstQueue) |
| 241 |
{ |
| 242 |
Vertice* vertice = queueState.GetVertice(); |
| 243 |
ASSERT(NULL != vertice); |
| 244 |
vertice->Dereference(queueState); |
| 245 |
queueState.SetQueue(dstQueue); |
| 246 |
vertice->Reference(queueState); |
| 247 |
} |
| 248 |
|
| 249 |
QueueState* GetQueueState(const Vertice& vertice) const |
| 250 |
{return vertice.GetQueueState(*this);} |
| 251 |
|
| 252 |
void Associate(Vertice& vertice, QueueState& queueState); |
| 253 |
void Disassociate(Vertice& vertice, QueueState& queueState); |
| 254 |
|
| 255 |
}; // end class VerticeQueue |
| 256 |
|
| 257 |
|
| 258 |
class EdgePool; |
| 259 |
/** |
| 260 |
* @class AdjacencyQueue |
| 261 |
* |
| 262 |
* @brief List of Vertices adjacent, sorted by Edge "key" |
| 263 |
* (i.e. instead of Vertice "key" as in case of SortedList) |
| 264 |
*/ |
| 265 |
class AdjacencyQueue : public VerticeQueue |
| 266 |
{ |
| 267 |
friend class Vertice; |
| 268 |
friend class Edge; |
| 269 |
friend class AdjacencyIterator; |
| 270 |
|
| 271 |
protected: |
| 272 |
AdjacencyQueue(Vertice& srcVertice); |
| 273 |
virtual ~AdjacencyQueue(); |
| 274 |
|
| 275 |
// Connect to "dstVertice" with "edge" |
| 276 |
void Connect(Vertice& dstVertice, |
| 277 |
Edge& edge); |
| 278 |
// Same as connect but doesn't call OnConnect |
| 279 |
void Reconnect(Vertice& dstVertice, |
| 280 |
Edge& edge); |
| 281 |
|
| 282 |
// Remove all edges to "dstVertice" |
| 283 |
void Disconnect(Vertice& dstVertice, |
| 284 |
EdgePool* edgePool = NULL); |
| 285 |
|
| 286 |
// Remove a specific edge (and pool or delete it) |
| 287 |
void RemoveEdge(Vertice& dstVertice, |
| 288 |
Edge& edge, |
| 289 |
EdgePool* edgePool = NULL); |
| 290 |
|
| 291 |
// Remove a specific edge (but don't delete it) |
| 292 |
void SuspendEdge(Vertice& dstVertice, |
| 293 |
Edge& edge); |
| 294 |
|
| 295 |
Vertice& GetSrc() const |
| 296 |
{return src_vertice;} |
| 297 |
|
| 298 |
// Note this count currently only reflects edges _to_ other Vertices |
| 299 |
unsigned int GetCount() const |
| 300 |
{return adjacency_count;} |
| 301 |
|
| 302 |
// Methods used to manage connector_tree |
| 303 |
// TBD - keep a "connector_count" ??? |
| 304 |
void AddConnector(Edge& edge); |
| 305 |
void RemoveConnector(Edge& edge); |
| 306 |
|
| 307 |
private: |
| 308 |
void Remove(Vertice& dstVertice) |
| 309 |
{Disconnect(dstVertice, NULL);} |
| 310 |
|
| 311 |
void Empty(); |
| 312 |
|
| 313 |
Vertice& src_vertice; |
| 314 |
ProtoSortedTree adjacency_tree; // list of dst vertices I am connected _to_ |
| 315 |
unsigned int adjacency_count; |
| 316 |
ProtoSortedTree connector_tree; // sorted list edges connected _to_ me |
| 317 |
|
| 318 |
}; // end class ProtoGraph::AdjacencyQueue |
| 319 |
|
| 320 |
|
| 321 |
/** |
| 322 |
* @class ProtoGraph::Edge |
| 323 |
* |
| 324 |
* @brief The ProtoGraph::Edge inherits from "VerticeQueue::QueueState" so |
| 325 |
* for the Edge's src Vertice "adjacency_queue" that derives from VerticeQueue. |
| 326 |
* It inherits from ProtoSortedTree::Item since the AdjacencyQueue is implemented |
| 327 |
* as a ProtoSortedTree (sorted on the Edge key). Finally, the Edge contains |
| 328 |
* a "tracker" member that is used by the Edge's dst Vertice to "track" which |
| 329 |
* edges are pointing towards that given Vertice. A "connector_list" is an element |
| 330 |
* of the Vertice "adjacency_queue" |
| 331 |
* |
| 332 |
*/ |
| 333 |
class Edge : public VerticeQueue::QueueState, public ProtoSortedTree::Item |
| 334 |
{ |
| 335 |
friend class AdjacencyQueue; |
| 336 |
friend class AdjacencyIterator; |
| 337 |
|
| 338 |
public: |
| 339 |
Edge(); |
| 340 |
|
| 341 |
virtual ~Edge(); |
| 342 |
|
| 343 |
virtual void OnConnect(); |
| 344 |
virtual void OnDisconnect(); |
| 345 |
|
| 346 |
Vertice* GetDst() const |
| 347 |
{return GetVertice();} |
| 348 |
|
| 349 |
Vertice* GetSrc() const; |
| 350 |
|
| 351 |
// Subclasses should override these to provide |
| 352 |
// a sorting criteria (if desired) for the |
| 353 |
// "AdjacencyQueue" defined above |
| 354 |
virtual const char* GetKey() const; |
| 355 |
virtual unsigned int GetKeysize() const; |
| 356 |
virtual ProtoTree::Endian GetEndian() const; |
| 357 |
virtual bool UseSignBit() const; |
| 358 |
virtual bool UseComplement2() const; |
| 359 |
|
| 360 |
private: |
| 361 |
class Tracker : public ProtoSortedTree::Item |
| 362 |
{ |
| 363 |
public: |
| 364 |
Tracker(const Edge& edge); |
| 365 |
|
| 366 |
const Edge& GetEdge() const |
| 367 |
{return edge;} |
| 368 |
|
| 369 |
private: |
| 370 |
virtual const char* GetKey() const |
| 371 |
{return edge.GetKey();} |
| 372 |
virtual unsigned int GetKeysize() const |
| 373 |
{return edge.GetKeysize();} |
| 374 |
virtual ProtoTree::Endian GetEndian() const |
| 375 |
{return edge.GetEndian();} |
| 376 |
virtual bool UseSignBit() const |
| 377 |
{return edge.UseSignBit();} |
| 378 |
virtual bool UseComplement2() const |
| 379 |
{return edge.UseComplement2();} |
| 380 |
|
| 381 |
const Edge& edge; |
| 382 |
|
| 383 |
}; // end class ProtoGraph::Edge::Tracker |
| 384 |
|
| 385 |
// Only the AdjacencyQueue should invoke this method. |
| 386 |
Tracker& AccessTracker() |
| 387 |
{return tracker;} |
| 388 |
|
| 389 |
Tracker tracker; // used by dst vertices to "track" edges _from_ src vertices |
| 390 |
// (Whenever an Edge is added to a src vertice "adjacency_queue", |
| 391 |
// the Edge::tracker is added to the dst vertice |
| 392 |
// "adjacency_queue::connector_tree" |
| 393 |
|
| 394 |
}; // end class ProtoGraph::Edge |
| 395 |
|
| 396 |
class EdgePool : public VerticeQueue::QueueStatePool |
| 397 |
{ |
| 398 |
public: |
| 399 |
EdgePool(); |
| 400 |
virtual ~EdgePool(); |
| 401 |
|
| 402 |
Edge* GetEdge() |
| 403 |
{return static_cast<Edge*>(VerticeQueue::QueueStatePool::Get());} |
| 404 |
|
| 405 |
void PutEdge(Edge& edge) |
| 406 |
{VerticeQueue::QueueStatePool::Put(edge);} |
| 407 |
|
| 408 |
}; // end class ProtoGraph::EdgePool |
| 409 |
|
| 410 |
|
| 411 |
/** |
| 412 |
* @class Vertice |
| 413 |
* |
| 414 |
*/ |
| 415 |
class Vertice |
| 416 |
{ |
| 417 |
friend class ProtoGraph; |
| 418 |
friend class VerticeQueue; |
| 419 |
|
| 420 |
public: |
| 421 |
virtual ~Vertice(); |
| 422 |
|
| 423 |
// Subclasses _may_ want to override these methods |
| 424 |
// (These are used for default sorting of |
| 425 |
// of the Vertice::SortedList if used) |
| 426 |
// _BUT_ if these are overridden, the derived |
| 427 |
// class destructor _MUST_ call Vertice::Cleanup() so |
| 428 |
// that these _are_ not indirectly called in the Vertice |
| 429 |
// destructor!!! |
| 430 |
virtual const char* GetVerticeKey() const = 0; |
| 431 |
virtual unsigned int GetVerticeKeysize() const = 0; |
| 432 |
virtual ProtoTree::Endian GetVerticeKeyEndian() const; |
| 433 |
virtual bool GetVerticeKeySigned() const; |
| 434 |
virtual bool GetVerticeKeyComplement2() const; |
| 435 |
|
| 436 |
void Cleanup(); // see comment immediately above |
| 437 |
|
| 438 |
bool IsInQueue(const VerticeQueue& queue) const |
| 439 |
{return (NULL != GetQueueState(queue));} |
| 440 |
|
| 441 |
// This tests for "this" _to_ "dst" connection (unidirectional check) |
| 442 |
bool HasEdgeTo(const Vertice& dst) const |
| 443 |
{return dst.IsInQueue(adjacency_queue);} |
| 444 |
|
| 445 |
Edge* GetEdgeTo(const Vertice& dst) const |
| 446 |
{return static_cast<Edge*>(dst.GetQueueState(adjacency_queue));} |
| 447 |
|
| 448 |
unsigned int GetAdjacencyCount() const |
| 449 |
{return adjacency_queue.GetCount();} |
| 450 |
|
| 451 |
/** |
| 452 |
* @class ProtoGraph::Vertice::SimpleList |
| 453 |
* |
| 454 |
* @brief Simple unsorted, doubly linked-list class used for |
| 455 |
* traversals and other purposes |
| 456 |
*/ |
| 457 |
class SimpleList : public VerticeQueue |
| 458 |
{ |
| 459 |
public: |
| 460 |
class ItemPool; |
| 461 |
|
| 462 |
SimpleList(SimpleList::ItemPool* itemPool = NULL); |
| 463 |
virtual ~SimpleList(); |
| 464 |
|
| 465 |
// required override |
| 466 |
virtual void Remove(Vertice& vertice); |
| 467 |
|
| 468 |
bool Prepend(Vertice& vertice); |
| 469 |
bool Append(Vertice& vertice); |
| 470 |
|
| 471 |
bool IsEmpty() const |
| 472 |
{return (NULL == head);} |
| 473 |
|
| 474 |
// Note "Empty()" does not delete Vertices, but does |
| 475 |
// delete or pool the queue state "Items" |
| 476 |
void Empty(); |
| 477 |
|
| 478 |
Vertice* GetHead() const |
| 479 |
{return ((NULL != head) ? head->GetVertice() : NULL);} |
| 480 |
|
| 481 |
Vertice* RemoveHead(); |
| 482 |
|
| 483 |
class Iterator; |
| 484 |
|
| 485 |
/** |
| 486 |
* @class ProtoGraph::Vertice::SimpleList::Item |
| 487 |
* |
| 488 |
*/ |
| 489 |
class Item : public QueueState |
| 490 |
{ |
| 491 |
friend class SimpleList; |
| 492 |
friend class ItemPool; |
| 493 |
friend class Iterator; |
| 494 |
|
| 495 |
public: |
| 496 |
Item(); |
| 497 |
virtual ~Item(); |
| 498 |
|
| 499 |
protected: |
| 500 |
void Prepend(Item* theItem) |
| 501 |
{prev = theItem;} |
| 502 |
void Append(Item* theItem) |
| 503 |
{next = theItem;} |
| 504 |
|
| 505 |
Item* GetPrev() const |
| 506 |
{return prev;} |
| 507 |
Item* GetNext() const |
| 508 |
{return next;} |
| 509 |
|
| 510 |
private: |
| 511 |
Item* prev; |
| 512 |
Item* next; |
| 513 |
}; // end class ProtoGraph::Vertice::SimpleList::Item |
| 514 |
|
| 515 |
// Move vertice from this SimpleList to another |
| 516 |
void TransferVertice(Vertice& vertice, SimpleList& dstSimpleList) |
| 517 |
{ |
| 518 |
Item* item = static_cast<Item*>(vertice.GetQueueState(*this)); |
| 519 |
ASSERT(NULL != item); |
| 520 |
TransferItem(*item, dstSimpleList); |
| 521 |
} |
| 522 |
|
| 523 |
void TransferItem(Item& item, SimpleList& dstSimpleList) |
| 524 |
{ |
| 525 |
Vertice* vertice = item.GetVertice(); |
| 526 |
ASSERT(NULL != vertice); |
| 527 |
RemoveItem(item); |
| 528 |
TransferQueueState(item, dstSimpleList); |
| 529 |
dstSimpleList.AppendItem(item); |
| 530 |
} |
| 531 |
|
| 532 |
/** |
| 533 |
* @class ProtoGraph::Vertice::SimpleList::ItemPool |
| 534 |
* |
| 535 |
* @brief Container class for Items |
| 536 |
*/ |
| 537 |
class ItemPool : public VerticeQueue::QueueStatePool |
| 538 |
{ |
| 539 |
public: |
| 540 |
ItemPool(); |
| 541 |
virtual ~ItemPool(); |
| 542 |
|
| 543 |
Item* GetItem(); |
| 544 |
|
| 545 |
void PutItem(Item& item) |
| 546 |
{VerticeQueue::QueueStatePool::Put(item);} |
| 547 |
|
| 548 |
}; // end class ProtoGraph::Vertice::SimpleList::ItemPool |
| 549 |
|
| 550 |
/** |
| 551 |
* @class ProtoGraph::Vertice::SimpleList::Iterator |
| 552 |
*/ |
| 553 |
class Iterator |
| 554 |
{ |
| 555 |
public: |
| 556 |
Iterator(const SimpleList& theSimpleList, bool reverse = false); |
| 557 |
virtual ~Iterator(); |
| 558 |
|
| 559 |
void Reset(); |
| 560 |
Vertice* GetNextVertice(); |
| 561 |
|
| 562 |
private: |
| 563 |
const SimpleList& list; |
| 564 |
Item* next_item; |
| 565 |
bool forward; |
| 566 |
|
| 567 |
}; // end class ProtoGraph::Vertice::SimpleList::Iterator |
| 568 |
friend class Iterator; |
| 569 |
|
| 570 |
protected: |
| 571 |
Item* GetNewItem() |
| 572 |
{return ((NULL != item_pool) ? item_pool->GetItem() : new Item);} |
| 573 |
void AppendItem(Item& item); |
| 574 |
void PrependItem(Item& item); |
| 575 |
void RemoveItem(Item& item); |
| 576 |
|
| 577 |
Item* head; |
| 578 |
Item* tail; |
| 579 |
ItemPool* item_pool; |
| 580 |
|
| 581 |
}; // end class ProtoGraph::Vertice::SimpleList() |
| 582 |
|
| 583 |
|
| 584 |
/** |
| 585 |
* @class SortedList |
| 586 |
* |
| 587 |
* @brief This maintains a list of Vertices, |
| 588 |
* sorted by their "key", whatever that happens to be ... |
| 589 |
*/ |
| 590 |
class SortedList : public VerticeQueue |
| 591 |
{ |
| 592 |
public: |
| 593 |
class ItemPool; |
| 594 |
|
| 595 |
SortedList(ItemPool* itemPool = NULL); |
| 596 |
virtual ~SortedList(); |
| 597 |
|
| 598 |
// required override |
| 599 |
virtual void Remove(Vertice& vertice); |
| 600 |
|
| 601 |
bool Insert(Vertice& vertice); |
| 602 |
|
| 603 |
Vertice* FindVertice(const char* key, unsigned int keysize) const |
| 604 |
{ |
| 605 |
Item* item = static_cast<Item*>(sorted_item_tree.Find(key, keysize)); |
| 606 |
return (NULL != item) ? item->GetVertice() : NULL; |
| 607 |
} |
| 608 |
|
| 609 |
Vertice* GetHead() const |
| 610 |
{ |
| 611 |
Item* headItem = static_cast<Item*>(sorted_item_tree.GetHead()); |
| 612 |
return ((NULL != headItem) ? headItem->GetVertice() : NULL); |
| 613 |
} |
| 614 |
|
| 615 |
Vertice* RemoveHead(); |
| 616 |
|
| 617 |
// Only use when you don't want the list sorted! |
| 618 |
// (you should probably use simple list instead) |
| 619 |
bool Append(Vertice& vertice); |
| 620 |
|
| 621 |
bool IsEmpty() const |
| 622 |
{return sorted_item_tree.IsEmpty();} |
| 623 |
|
| 624 |
void Empty(); |
| 625 |
|
| 626 |
/** |
| 627 |
* @class ProtoGraph::Vertice::SortedList::Item |
| 628 |
* |
| 629 |
* @brief "Item" is our QueueState subclass |
| 630 |
* "container" for vertices in the list |
| 631 |
*/ |
| 632 |
class Item : public VerticeQueue::QueueState, public ProtoSortedTree::Item |
| 633 |
{ |
| 634 |
public: |
| 635 |
Item(); |
| 636 |
virtual ~Item(); |
| 637 |
|
| 638 |
// required (and optional) overrides for ProtoSortedTree::Item |
| 639 |
// (these default implementations use Vertice::GetVerticeKey(), etc) |
| 640 |
virtual const char* GetKey() const; |
| 641 |
virtual unsigned int GetKeysize() const; |
| 642 |
virtual ProtoTree::Endian GetEndian() const; |
| 643 |
virtual bool UseSignBit() const; |
| 644 |
virtual bool UseComplement2() const; |
| 645 |
}; // end class ProtoGraph::Vertice::SortedList::Item |
| 646 |
|
| 647 |
// Move vertice from this SortedList to another |
| 648 |
void TransferVertice(Vertice& vertice, SortedList& dstList) |
| 649 |
{ |
| 650 |
Item* item = static_cast<Item*>(vertice.GetQueueState(*this)); |
| 651 |
ASSERT(NULL != item); |
| 652 |
TransferItem(*item, dstList); |
| 653 |
} |
| 654 |
|
| 655 |
void TransferItem(Item& item, SortedList& dstList) |
| 656 |
{ |
| 657 |
Vertice* vertice = item.GetVertice(); |
| 658 |
ASSERT(NULL != vertice); |
| 659 |
RemoveItem(item); |
| 660 |
TransferQueueState(item, dstList); |
| 661 |
dstList.InsertItem(item); |
| 662 |
} |
| 663 |
|
| 664 |
/** |
| 665 |
* @class ProtoGraph::Vertice::SortedList::ItemPool |
| 666 |
* |
| 667 |
*/ |
| 668 |
class ItemPool : public VerticeQueue::QueueStatePool |
| 669 |
{ |
| 670 |
public: |
| 671 |
ItemPool(); |
| 672 |
virtual ~ItemPool(); |
| 673 |
|
| 674 |
Item* GetItem(); |
| 675 |
|
| 676 |
void PutItem(Item& item) |
| 677 |
{VerticeQueue::QueueStatePool::Put(item);} |
| 678 |
|
| 679 |
}; // end class ProtoGraph::Vertice::SortedList::ItemPool |
| 680 |
|
| 681 |
/** |
| 682 |
* @class ProtoGraph::Vertice::SortedList::Iterator |
| 683 |
*/ |
| 684 |
class Iterator : public ProtoSortedTree::Iterator |
| 685 |
{ |
| 686 |
public: |
| 687 |
Iterator(SortedList& theList); |
| 688 |
virtual ~Iterator(); |
| 689 |
|
| 690 |
Item* GetNextItem() |
| 691 |
{return static_cast<Item*>(ProtoSortedTree::Iterator::GetNextItem());} |
| 692 |
|
| 693 |
Vertice* GetNextVertice() |
| 694 |
{ |
| 695 |
Item* nextItem = GetNextItem(); |
| 696 |
return ((NULL != nextItem) ? nextItem->GetVertice() : NULL); |
| 697 |
} |
| 698 |
}; // end class ProtoGraph::Vertice::SortedList::Iterator |
| 699 |
friend class Iterator; |
| 700 |
|
| 701 |
protected: |
| 702 |
Item* GetNewItem() |
| 703 |
{return ((NULL != item_pool) ? item_pool->GetItem() : new Item);} |
| 704 |
void InsertItem(Item& item) |
| 705 |
{ |
| 706 |
ASSERT(0 != item.GetKeysize()); |
| 707 |
sorted_item_tree.Insert(item); |
| 708 |
} |
| 709 |
void RemoveItem(Item& item) |
| 710 |
{sorted_item_tree.Remove(item);} |
| 711 |
void AppendItem(Item& item) |
| 712 |
{sorted_item_tree.Append(item);} |
| 713 |
|
| 714 |
ProtoSortedTree sorted_item_tree; |
| 715 |
ItemPool* item_pool; |
| 716 |
|
| 717 |
}; // end class ProtoGraph::Vertice::SortedList |
| 718 |
|
| 719 |
friend class AdjacencyQueue; |
| 720 |
friend class AdjacencyIterator; |
| 721 |
|
| 722 |
protected: |
| 723 |
Vertice(); |
| 724 |
|
| 725 |
// These are used by the friend class ProtoGraph. We keep these |
| 726 |
// protected since the ProtoGraph instance in which the connections |
| 727 |
// are made (or removed) maintains the pools of Edge and Connector |
| 728 |
// instances and public access to these methods could result |
| 729 |
// in mismanagement of the pooled items. I.e., the |
| 730 |
// "ProtoGraph::Connect()", "ProtoGraph::Disconnect()", etc |
| 731 |
// methods MUST be used instead of using these directly. |
| 732 |
|
| 733 |
// Note here the "edge" is the connection from src->dst while |
| 734 |
// the "connector" allows dst vertices to know who is connected |
| 735 |
// to them. |
| 736 |
void Connect(Vertice& dst, Edge& edge) |
| 737 |
{adjacency_queue.Connect(dst, edge);} |
| 738 |
|
| 739 |
void Reconnect(Vertice& dst, Edge& edge) |
| 740 |
{adjacency_queue.Reconnect(dst, edge);} |
| 741 |
|
| 742 |
void Disconnect(Vertice& dst, EdgePool* edgePool = NULL) |
| 743 |
{adjacency_queue.Disconnect(dst, edgePool);} |
| 744 |
|
| 745 |
void RemoveEdge(Vertice& dst, Edge& edge, EdgePool* edgePool = NULL) |
| 746 |
{adjacency_queue.RemoveEdge(dst, edge, edgePool);} |
| 747 |
|
| 748 |
void SuspendEdge(Vertice& dst, Edge& edge) |
| 749 |
{adjacency_queue.SuspendEdge(dst, edge);} |
| 750 |
|
| 751 |
private: |
| 752 |
// These are called by a connected src Vertice::adjacency_queue |
| 753 |
// so a dst Vertice can know of connections _to_ itself |
| 754 |
void AddConnector(Edge& edge) |
| 755 |
{adjacency_queue.AddConnector(edge);} |
| 756 |
void RemoveConnector(Edge& edge) |
| 757 |
{adjacency_queue.RemoveConnector(edge);} |
| 758 |
|
| 759 |
VerticeQueue::QueueState* GetQueueState(const VerticeQueue& queue) const |
| 760 |
{ |
| 761 |
const VerticeQueue* ptr = &queue; |
| 762 |
VerticeQueue::QueueState::Entry* entry = |
| 763 |
static_cast<VerticeQueue::QueueState::Entry*>(queue_state_tree.Find((const char*)&ptr, sizeof(VerticeQueue*) << 3)); |
| 764 |
return ((NULL != entry) ? &entry->GetQueueState() : NULL); |
| 765 |
} |
| 766 |
void Reference(VerticeQueue::QueueState& queueState) |
| 767 |
{queue_state_tree.Insert(queueState.AccessEntry());} |
| 768 |
void Dereference(VerticeQueue::QueueState& queueState) |
| 769 |
{ |
| 770 |
ASSERT(this == queueState.GetVertice()); |
| 771 |
queue_state_tree.Remove(queueState.AccessEntry()); |
| 772 |
} |
| 773 |
|
| 774 |
// Queue of adjacent vertices |
| 775 |
// (uses "Edge" for queue state) |
| 776 |
AdjacencyQueue adjacency_queue; |
| 777 |
|
| 778 |
// These members are for use by traversals and |
| 779 |
// other queue manipulations as needed |
| 780 |
ProtoTree queue_state_tree; |
| 781 |
|
| 782 |
}; // end class ProtoGraph::Vertice |
| 783 |
|
| 784 |
/** |
| 785 |
* @class ProtoGraph::VerticeIterator |
| 786 |
*/ |
| 787 |
class VerticeIterator : public Vertice::SortedList::Iterator |
| 788 |
{ |
| 789 |
public: |
| 790 |
VerticeIterator(ProtoGraph& theGraph); |
| 791 |
virtual ~VerticeIterator(); |
| 792 |
|
| 793 |
// Note: Inherits the following |
| 794 |
// void Reset(); |
| 795 |
// Vertice* GetNextVertice(); |
| 796 |
|
| 797 |
}; // end class ProtoGraph::VerticeIterator |
| 798 |
friend class VerticeIterator; |
| 799 |
|
| 800 |
/** |
| 801 |
* @class ProtoGraph::SimpleTraversal |
| 802 |
* |
| 803 |
* @brief (TBD) We may want to make a separate "Traversal" base class |
| 804 |
* that SimpleTraversal (and others) derive from so that a |
| 805 |
* ProtoGraph can inform associated Traversals if the |
| 806 |
* graph state changes ??? |
| 807 |
*/ |
| 808 |
class SimpleTraversal |
| 809 |
{ |
| 810 |
public: |
| 811 |
SimpleTraversal(const ProtoGraph& theGraph, |
| 812 |
Vertice& startVertice, |
| 813 |
bool depthFirst = false); |
| 814 |
virtual ~SimpleTraversal(); |
| 815 |
bool Reset(); |
| 816 |
Vertice* GetNextVertice(unsigned int* level = NULL); |
| 817 |
|
| 818 |
// Override this method to filter which edges are included in traversal |
| 819 |
// (return "false" to disallow specific edges) |
| 820 |
// (Note that "edge->GetDst()" can be used to get the dst vertice) |
| 821 |
virtual bool AllowEdge(const Vertice& srcVertice, const Edge& edge) |
| 822 |
{return true;} |
| 823 |
|
| 824 |
protected: |
| 825 |
// Members |
| 826 |
const ProtoGraph& graph; |
| 827 |
Vertice& start_vertice; |
| 828 |
bool depth_first; // false == breadth-first search |
| 829 |
unsigned int current_level; |
| 830 |
Vertice* trans_vertice; // level transition marker |
| 831 |
Vertice::SimpleList queue_pending; |
| 832 |
Vertice::SimpleList queue_visited; |
| 833 |
|
| 834 |
Vertice::SimpleList::ItemPool item_pool; |
| 835 |
|
| 836 |
}; // end class ProtoGraph::SimpleTraversal |
| 837 |
|
| 838 |
protected: |
| 839 |
// Subclasses may wish to override this if |
| 840 |
// they use different Edge subclass variants |
| 841 |
virtual Edge* CreateEdge() const |
| 842 |
{return new Edge;} |
| 843 |
// "GetEdge()" tries to get an edge from edge_pool else calls "CreateEdge()" |
| 844 |
Edge* GetEdge(); |
| 845 |
void PutEdge(Edge& edge) |
| 846 |
{edge_pool.Put(edge);} |
| 847 |
|
| 848 |
// These let ProtoGraph subclasses control Connect() a little more specifically if desired |
| 849 |
void Connect(Vertice& src, Vertice& dst, Edge& edge) |
| 850 |
{src.Connect(dst, edge);} |
| 851 |
|
| 852 |
void RemoveEdge(Vertice& src, Vertice& dst, Edge& edge) |
| 853 |
{src.RemoveEdge(dst, edge, &edge_pool);} |
| 854 |
|
| 855 |
void SuspendEdge(Vertice& src, Vertice& dst, Edge& edge) |
| 856 |
{src.SuspendEdge(dst, edge);} |
| 857 |
|
| 858 |
// Member variables |
| 859 |
Vertice::SortedList vertice_list; |
| 860 |
|
| 861 |
// Pools of vertice items and edges |
| 862 |
Vertice::SortedList::ItemPool vertice_list_item_pool; |
| 863 |
EdgePool edge_pool; |
| 864 |
|
| 865 |
}; // end class ProtoGraph |
| 866 |
|
| 867 |
#endif // _PROTO_GRAPH |