CrystalSpace

Public API Reference

csPartialOrder< T > Class Template Reference

A generic finite partial order class. More...

#include <csutil/partialorder.h>

List of all members.

Public Member Functions

void Add (const T &node)
 Add a node. If the node is already present, has no effect.
bool AddOrder (const T &node1, const T &node2)
 Add an ordering constraint (node1 precedes node2).
void ClearMark ()
 Clear all "marked" flags.
void ClearMark (const T &node)
 Clear the "marked" flag for a given node.
bool Contains (const T &pre, const T &post)
 Query an edge's presence. Does not check for transitive connectivity.
bool Contains (const T &node)
 Query a node's presence.
 csPartialOrder (const csPartialOrder *other)
 Copy constructor.
 csPartialOrder (const csPartialOrder &other)
 Copy constructor.
 csPartialOrder ()
 Create a partial order graph.
void Delete (const T &node)
 Delete a node and all edges connected to it.
void DeleteOrder (const T &node1, const T &node2)
 Remove an ordering constraint (node1 precedes node2).
const T GetByIndex (size_t i)
 Return a node with a given index (0 through Size()-1).
const T GetEnabled (T fail)
 Return an enabled node.
bool HasEnabled ()
 Return true if any node is enabled.
bool IsEnabled (const T &node)
 Return true if all of the node's (zero or more) predecessors have been marked and the node itself has not.
bool IsMarked (const T &node)
 Query whether a given node is "marked".
void Mark (const T &node)
 Set the "marked" flag for a given node.
size_t Size ()
 Number of nodes in the graph.
void Solve (csList< const T > &result)
 Produce a valid "solution" to the partial order graph, i.e., a sequence of nodes that violates no constraints.

Protected Member Functions

bool CycleTest (const T &node)
bool InternalCycleTest (size_t n)
bool InternalCycleTest (size_t n1, size_t n2)
bool InternalIsEnabled (size_t i)
void SanityCheck ()

Protected Attributes

csHash< size_t, const T > NodeMap
csArray< NodeNodes

Classes

class  Node


Detailed Description

template<class T>
class csPartialOrder< T >

A generic finite partial order class.

A finite partial order is a graph with the following properties:

An insert of an edge which violates the third constraint will fail (return false and have no effect).

There must be a csHashComputer for type T.

Definition at line 52 of file partialorder.h.


Constructor & Destructor Documentation

template<class T>
csPartialOrder< T >::csPartialOrder (  )  [inline]

Create a partial order graph.

Definition at line 78 of file partialorder.h.

template<class T>
csPartialOrder< T >::csPartialOrder ( const csPartialOrder< T > &  other  )  [inline]

Copy constructor.

Definition at line 85 of file partialorder.h.

template<class T>
csPartialOrder< T >::csPartialOrder ( const csPartialOrder< T > *  other  )  [inline]

Copy constructor.

Definition at line 124 of file partialorder.h.


Member Function Documentation

template<class T>
void csPartialOrder< T >::Add ( const T &  node  )  [inline]

Add a node. If the node is already present, has no effect.

Definition at line 131 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::AddOrder ( const T &  node1,
const T &  node2 
) [inline]

Add an ordering constraint (node1 precedes node2).

Edge addition is not idempotent, i.e., if you add an edge three times, it must be removed three times before it will disappear from the graph.

Definition at line 224 of file partialorder.h.

template<class T>
void csPartialOrder< T >::ClearMark (  )  [inline]

Clear all "marked" flags.

Definition at line 357 of file partialorder.h.

template<class T>
void csPartialOrder< T >::ClearMark ( const T &  node  )  [inline]

Clear the "marked" flag for a given node.

Definition at line 346 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::Contains ( const T &  pre,
const T &  post 
) [inline]

Query an edge's presence. Does not check for transitive connectivity.

Definition at line 148 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::Contains ( const T &  node  )  [inline]

Query a node's presence.

Definition at line 142 of file partialorder.h.

template<class T>
void csPartialOrder< T >::Delete ( const T &  node  )  [inline]

Delete a node and all edges connected to it.

Definition at line 165 of file partialorder.h.

template<class T>
void csPartialOrder< T >::DeleteOrder ( const T &  node1,
const T &  node2 
) [inline]

Remove an ordering constraint (node1 precedes node2).

Definition at line 251 of file partialorder.h.

template<class T>
const T csPartialOrder< T >::GetByIndex ( size_t  i  )  [inline]

Return a node with a given index (0 through Size()-1).

Definition at line 270 of file partialorder.h.

template<class T>
const T csPartialOrder< T >::GetEnabled ( fail  )  [inline]

Return an enabled node.

Definition at line 392 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::HasEnabled (  )  [inline]

Return true if any node is enabled.

Definition at line 379 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::IsEnabled ( const T &  node  )  [inline]

Return true if all of the node's (zero or more) predecessors have been marked and the node itself has not.

Definition at line 369 of file partialorder.h.

template<class T>
bool csPartialOrder< T >::IsMarked ( const T &  node  )  [inline]

Query whether a given node is "marked".

Definition at line 335 of file partialorder.h.

template<class T>
void csPartialOrder< T >::Mark ( const T &  node  )  [inline]

Set the "marked" flag for a given node.

This is useful for implementing your own graph iterators.

Definition at line 324 of file partialorder.h.

template<class T>
size_t csPartialOrder< T >::Size (  )  [inline]

Number of nodes in the graph.

Definition at line 264 of file partialorder.h.

template<class T>
void csPartialOrder< T >::Solve ( csList< const T > &  result  )  [inline]

Produce a valid "solution" to the partial order graph, i.e., a sequence of nodes that violates no constraints.

Definition at line 279 of file partialorder.h.


The documentation for this class was generated from the following file:
Generated for Crystal Space by doxygen 1.4.7