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

Node &	find (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...

Node &	insert (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

Node *	tryFind (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 Node *	newNode (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

typedef StringList de::PathTree::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

typedef duint32 de::PathTree::SegmentId

Identifier associated with each unique path segment.

Definition at line 109 of file pathtree.h.

Member Enumeration Documentation

◆ ComparisonFlag

enum de::PathTree::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

enum de::PathTree::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

enum de::PathTree::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

path	Relative 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.
flags	Comparison behavior flags.

Returns: Found node.

Exceptions

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

path	Relative 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.
flags	Comparison 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

found	Set of paths that match the result.
flags	Comparison behavior flags.
sep	Segments 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

path	Path to look for.
flags	Search 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

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

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

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

path	Path to remove.
flags	Search 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

flags	Path comparison flags.
parent	Used in combination with ComparisonFlag::MatchParent to limit the traversal to only the child nodes of this node.
hashKey	If not `PathTree::no_hash` only consider nodes whose hashed name matches this.
callback	Callback function ptr.
parameters	Passed 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:

sdk/libcore/include/de/data/pathtree.h
sdk/libcore/src/data/pathtree.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ FoundPaths

◆ Nodes

◆ SegmentId

Member Enumeration Documentation

◆ ComparisonFlag

◆ Flag

◆ NodeType

Constructor & Destructor Documentation

◆ PathTree()

◆ ~PathTree()

Member Function Documentation

◆ branchNodes()

◆ clear()

◆ count()

◆ empty()

◆ find() [1/2]

◆ find() [2/2]

◆ findAllPaths()

◆ flags()

◆ has()

◆ insert()

◆ isEmpty()

◆ leafNodes()

◆ newNode()

◆ nodes()

◆ nodeTypeName()

◆ remove()

◆ rootBranch()

◆ segmentHash()

◆ segmentName()

◆ size()

◆ traverse()

◆ tryFind() [1/2]

◆ tryFind() [2/2]

Member Data Documentation

◆ no_hash