Doomsday SDK  2.3
Core engine library and supporting libraries
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Member Functions | List of all members
de::PathTree Class Reference

Data structure for modelling a hierarchical relationship tree of Path + data value pairs. More...

#include <pathtree.h>

+ Inheritance diagram for de::PathTree:

Classes

struct  Impl
 
class  Node
 Base class for all nodes of a PathTree. More...
 
struct  NodeArgs
 Parameters passed to the Node constructor. More...
 
struct  NodeHash
 Leaves and branches are stored in separate hashes. More...
 
class  NotFoundError
 The requested entry could not be found in the hierarchy. More...
 

Public Types

enum  ComparisonFlag {
  NoBranch = 0x1, NoLeaf = 0x2, MatchParent = 0x4, MatchFull = 0x8,
  RelinquishMatching = 0x10
}
 Flags used to alter the behavior of path comparisons. More...
 
enum  Flag { MultiLeaf = 0x1 }
 Flags that affect the properties of the tree. More...
 
typedef StringList FoundPaths
 
typedef QMultiHash< Path::hash_type, Node * > Nodes
 
enum  NodeType { Branch, Leaf }
 Node type identifiers. More...
 
typedef duint32 SegmentId
 Identifier associated with each unique path segment. More...
 

Public Member Functions

 PathTree (Flags flags=0)
 
virtual ~PathTree ()
 
Nodes const & branchNodes () const
 Provides access to the branch nodes for efficent traversals. More...
 
void clear ()
 Destroy the tree's contents, freeing all nodes. More...
 
int count () const
 Total number of unique paths in the hierarchy. Same as size(). More...
 
bool empty () const
 
Node const & find (Path const &path, ComparisonFlags flags) const
 Find a single node in the hierarchy. More...
 
Nodefind (Path const &path, ComparisonFlags flags)
 Find a single node in the hierarchy. More...
 
int findAllPaths (FoundPaths &found, ComparisonFlags flags=0, QChar sep='/') const
 Collate all referenced paths in the hierarchy into a list. More...
 
Flags flags () const
 Returns the flags that affect the properties of the tree. More...
 
bool has (Path const &path, ComparisonFlags flags=0) const
 Determines if a path exists in the tree. More...
 
Nodeinsert (Path const &path)
 Add a new path into the hierarchy. More...
 
bool isEmpty () const
 
Nodes const & leafNodes () const
 Provides access to the leaf nodes for efficent traversals. More...
 
Nodes const & nodes (NodeType type) const
 Provides access to the nodes for efficent traversals. More...
 
bool remove (Path const &path, ComparisonFlags flags=0)
 Removes matching nodes from the tree. More...
 
Node const & rootBranch () const
 
Path::hash_type segmentHash (SegmentId segmentId) const
 
String const & segmentName (SegmentId segmentId) const
 
int size () const
 Total number of unique paths in the hierarchy. More...
 
int traverse (ComparisonFlags flags, Node const *parent, Path::hash_type hashKey, int(*callback)(Node &node, void *parameters), void *parameters=0) const
 Traverse the node hierarchy making a callback for visited node. More...
 
Node const * tryFind (Path const &path, ComparisonFlags flags) const
 
NodetryFind (Path const &path, ComparisonFlags flags)
 
- Public Member Functions inherited from de::Lockable
void lock () const
 Acquire the lock. Blocks until the operation succeeds. More...
 
void unlock () const
 Release the lock. More...
 

Static Public Member Functions

static String const & nodeTypeName (NodeType type)
 

Static Public Attributes

static Path::hash_type const no_hash = Path::hash_range
 Identifier used with the search and iteration algorithms in place of a hash when the user does not wish to narrow the set of considered nodes. More...
 

Protected Member Functions

virtual NodenewNode (NodeArgs const &args)
 Construct a new Node instance. More...
 

Detailed Description

Data structure for modelling a hierarchical relationship tree of Path + data value pairs.

Segment is the term given to a components of a hierarchical path. For example, the path

"c:/somewhere/something"

contains three path segments:

[ 0: "c:", 1: "somewhere", 2: "something" ]

Segments are separated by separator characters. For instance, UNIX file paths use forward slashes as separators.

Internally, segments are "pooled" such that only one instance of a segment is included in the model of the whole tree. Potentially, this significantly reduces the memory overhead which would otherwise be necessary to represent the complete hierarchy as a set of fully composed paths.

Separators are not included in the hierarchy model. Not including the separators allows for optimal dynamic replacement when recomposing the original paths (also reducing the memory overhead for the whole data set). One potential use for this feature when representing file path hierarchies is "ambidextrously" recomposing paths with either forward or backward slashes, irrespective of the separator used at path insertion time.

Thread-safety

The methods of PathTree automatically lock the tree. Access to the data in the nodes is not automatically protected and is the responsibility of the user.

Definition at line 64 of file pathtree.h.

Member Typedef Documentation

◆ FoundPaths

Definition at line 72 of file pathtree.h.

◆ Nodes

typedef QMultiHash<Path::hash_type, Node *> de::PathTree::Nodes

Definition at line 69 of file pathtree.h.

◆ SegmentId

Identifier associated with each unique path segment.

Definition at line 109 of file pathtree.h.

Member Enumeration Documentation

◆ ComparisonFlag

Flags used to alter the behavior of path comparisons.

Enumerator
NoBranch 

Do not consider branches as possible candidates.

NoLeaf 

Do not consider leaves as possible candidates.

MatchParent 

Only consider nodes whose parent matches the provided reference node.

MatchFull 

Whole path must match completely (i.e., path begins from the same root point) otherwise allow partial (i.e., relative) matches.

RelinquishMatching 

Matching node's ownership is relinquished; the node is removed from the tree.

Definition at line 95 of file pathtree.h.

◆ Flag

Flags that affect the properties of the tree.

Enumerator
MultiLeaf 

There can be more than one leaf with a given name.

Definition at line 86 of file pathtree.h.

◆ NodeType

Node type identifiers.

Enumerator
Branch 
Leaf 

Definition at line 112 of file pathtree.h.

Constructor & Destructor Documentation

◆ PathTree()

de::PathTree::PathTree ( Flags  flags = 0)
explicit

Definition at line 227 of file pathtree.cpp.

◆ ~PathTree()

de::PathTree::~PathTree ( )
virtual

Definition at line 232 of file pathtree.cpp.

Member Function Documentation

◆ branchNodes()

Nodes const& de::PathTree::branchNodes ( ) const
inline

Provides access to the branch nodes for efficent traversals.

Returns
Collection of nodes.
See also
PathTreeIterator

Definition at line 396 of file pathtree.h.

◆ clear()

void de::PathTree::clear ( )

Destroy the tree's contents, freeing all nodes.

Definition at line 295 of file pathtree.cpp.

◆ count()

int de::PathTree::count ( ) const
inline

Total number of unique paths in the hierarchy. Same as size().

Definition at line 275 of file pathtree.h.

◆ empty()

bool de::PathTree::empty ( ) const
Returns
true iff there are no paths in the hierarchy. Same as size() == 0

Definition at line 283 of file pathtree.cpp.

◆ find() [1/2]

PathTree::Node const & de::PathTree::find ( Path const &  path,
ComparisonFlags  flags 
) const

Find a single node in the hierarchy.

Parameters
pathRelative or absolute path to be searched for. Note that this path is NOT resolved before searching. This means that any symbolics contained within must also be present in the tree's name hierarchy.
flagsComparison behavior flags.
Returns
Found node.
Exceptions
NotFoundErrorThe referenced node could not be found.

Definition at line 310 of file pathtree.cpp.

◆ find() [2/2]

PathTree::Node & de::PathTree::find ( Path const &  path,
ComparisonFlags  flags 
)

Find a single node in the hierarchy.

Parameters
pathRelative or absolute path to be searched for. Note that this path is NOT resolved before searching. This means that any symbolics contained within must also be present in the tree's name hierarchy.
flagsComparison behavior flags.
Returns
Found node.

Definition at line 329 of file pathtree.cpp.

◆ findAllPaths()

int de::PathTree::findAllPaths ( FoundPaths found,
ComparisonFlags  flags = 0,
QChar  sep = '/' 
) const

Collate all referenced paths in the hierarchy into a list.

Parameters
foundSet of paths that match the result.
flagsComparison behavior flags.
sepSegments in the composed path will be separated with this character. Paths to branches always include a terminating separator.
Returns
Number of paths found.

Definition at line 383 of file pathtree.cpp.

◆ flags()

PathTree::Flags de::PathTree::flags ( ) const

Returns the flags that affect the properties of the tree.

Definition at line 288 of file pathtree.cpp.

◆ has()

bool de::PathTree::has ( Path const &  path,
ComparisonFlags  flags = 0 
) const

Determines if a path exists in the tree.

Parameters
pathPath to look for.
flagsSearch behavior.
Returns
true, if the node exists; otherwise false.

Definition at line 302 of file pathtree.cpp.

◆ insert()

PathTree::Node & de::PathTree::insert ( Path const &  path)

Add a new path into the hierarchy.

Duplicates are automatically pruned. Separators in the path are completely ignored.

Parameters
pathNew path to be added to the tree. Note that this path is NOT resolved before insertion, so any symbolics contained within will also be present in the name hierarchy.
Returns
Tail node for the inserted path. For example, given the path "c:/somewhere/something" this is the node for the path segment "something".

Definition at line 239 of file pathtree.cpp.

◆ isEmpty()

bool de::PathTree::isEmpty ( ) const
inline

Definition at line 266 of file pathtree.h.

◆ leafNodes()

Nodes const& de::PathTree::leafNodes ( ) const
inline

Provides access to the leaf nodes for efficent traversals.

Returns
Collection of nodes.
See also
PathTreeIterator

Definition at line 387 of file pathtree.h.

◆ newNode()

PathTree::Node * de::PathTree::newNode ( NodeArgs const &  args)
protectedvirtual

Construct a new Node instance.

Derived classes can override this to construct specialized nodes.

Parameters
argsParameters for initializing the node.
Returns
New node. Caller gets ownership.

Reimplemented in de::PathTreeT< Type >.

Definition at line 360 of file pathtree.cpp.

◆ nodes()

PathTree::Nodes const & de::PathTree::nodes ( NodeType  type) const

Provides access to the nodes for efficent traversals.

Parameters
typeType of nodes to return: Leaf or Branch.
Returns
Collection of nodes.
See also
PathTreeIterator

Definition at line 365 of file pathtree.cpp.

◆ nodeTypeName()

String const & de::PathTree::nodeTypeName ( NodeType  type)
static
Returns
Print-ready name for node type.

Definition at line 267 of file pathtree.cpp.

◆ remove()

bool de::PathTree::remove ( Path const &  path,
ComparisonFlags  flags = 0 
)

Removes matching nodes from the tree.

Parameters
pathPath to remove.
flagsSearch behavior.
Returns
true, if one or more nodes were removed; otherwise, false.

Definition at line 252 of file pathtree.cpp.

◆ rootBranch()

PathTree::Node const & de::PathTree::rootBranch ( ) const

Definition at line 355 of file pathtree.cpp.

◆ segmentHash()

Path::hash_type de::PathTree::segmentHash ( SegmentId  segmentId) const
Returns
Hash associated with segmentId.

Definition at line 348 of file pathtree.cpp.

◆ segmentName()

String const & de::PathTree::segmentName ( SegmentId  segmentId) const
Returns
The path segment associated with segmentId.

Definition at line 341 of file pathtree.cpp.

◆ size()

int de::PathTree::size ( ) const

Total number of unique paths in the hierarchy.

Definition at line 276 of file pathtree.cpp.

◆ traverse()

int de::PathTree::traverse ( ComparisonFlags  flags,
Node const *  parent,
Path::hash_type  hashKey,
int(*)(Node &node, void *parameters)  callback,
void *  parameters = 0 
) const

Traverse the node hierarchy making a callback for visited node.

Traversal ends when all selected nodes have been visited or a callback returns a non-zero value.

Parameters
flagsPath comparison flags.
parentUsed in combination with ComparisonFlag::MatchParent to limit the traversal to only the child nodes of this node.
hashKeyIf not PathTree::no_hash only consider nodes whose hashed name matches this.
callbackCallback function ptr.
parametersPassed to the callback.
Returns
0 iff iteration completed wholly.

Definition at line 449 of file pathtree.cpp.

◆ tryFind() [1/2]

PathTree::Node const * de::PathTree::tryFind ( Path const &  path,
ComparisonFlags  flags 
) const

Definition at line 323 of file pathtree.cpp.

◆ tryFind() [2/2]

PathTree::Node * de::PathTree::tryFind ( Path const &  path,
ComparisonFlags  flags 
)

Definition at line 335 of file pathtree.cpp.

Member Data Documentation

◆ no_hash

Path::hash_type const de::PathTree::no_hash = Path::hash_range
static

Identifier used with the search and iteration algorithms in place of a hash when the user does not wish to narrow the set of considered nodes.

Definition at line 126 of file pathtree.h.


The documentation for this class was generated from the following files: