OpenEnroth 73e68f7
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
detail::FileSystemTrie< T > Class Template Reference

#include <FileSystemTrie.h>

Public Types

using Node = FileSystemTrieNode< T >
 

Public Member Functions

 FileSystemTrie ()
 
Node * root ()
 
const Node * root () const
 
Node * find (Node *base, FileSystemPathView relativePath)
 
Node * find (FileSystemPathView path)
 
const Node * find (const Node *base, FileSystemPathView relativePath) const
 
const Node * find (FileSystemPathView path) const
 
Node * walk (Node *base, FileSystemPathView relativePath, FileSystemPathView *tail=nullptr)
 
Node * walk (FileSystemPathView path, FileSystemPathView *tail=nullptr)
 
const Node * walk (const Node *base, FileSystemPathView relativePath, FileSystemPathView *tail=nullptr) const
 
const Node * walk (FileSystemPathView path, FileSystemPathView *tail=nullptr) const
 
bool erase (Node *base, FileSystemPathView relativePath={})
 
bool erase (FileSystemPathView path)
 
void chop (Node *base, FileSystemPathView relativePath={})
 
void chop (FileSystemPathView path)
 
Node * insertOrAssign (Node *base, FileSystemPathView relativePath, T value)
 
Node * insertOrAssign (FileSystemPathView path, T value)
 
std::unique_ptr< Node > extract (Node *node)
 
Node * insertOrAssign (Node *base, FileSystemPathView relativePath, std::unique_ptr< Node > node)
 
Node * insertOrAssign (FileSystemPathView path, std::unique_ptr< Node > node)
 
void clear ()
 
bool isEmpty () const
 

Private Member Functions

Node * _prune (Node *node)
 
Node * _grow (Node *base, const FileSystemPathView relativePath)
 

Private Attributes

std::unique_ptr< FileSystemTrieNode< T > > _root
 

Detailed Description

template<class T>
class detail::FileSystemTrie< T >

Trie map from FileSystemPath to T.

Each node can contain a value, even if it's not a leaf node. If the user needs a trie that only contains values in the leaf nodes, then it's up to the user to maintain this invariant.

The only invariant maintained by FileSystemTrie is that it automatically drops all nodes that don't lie on a path to a value node. This means, for example, that the following code will leave the trie empty:

FileSystemTrie<bool> trie;
trie.insertOrAssign(FileSystemPath("a/b/c"), true);
trie.erase(FileSystemPath("a/b"));
// trie is now empty, trie.find(FileSystemPath("a")) will return nullptr.
FileSystemPath
Definition: FileSystemPath.h:24
detail::FileSystemTrie
Definition: FileSystemTrie.h:89
detail::FileSystemTrie::insertOrAssign
Node * insertOrAssign(Node *base, FileSystemPathView relativePath, T value)
Definition: FileSystemTrie.h:189
detail::FileSystemTrie::erase
bool erase(Node *base, FileSystemPathView relativePath={})
Definition: FileSystemTrie.h:157

Note that the interface of FileSystemTrie is a bit different from what one would expect a map-like class to offer. We are directly exposing the fact that FileSystemTrie is a tree. For example, erase removes subtrees. A more STL-like interface would expose something like equal_range to get a subtree, and a two-arg erase to drop it, but that's just adding complexity where it's not warranted.

Member Typedef Documentation

◆ Node

template<class T >
using detail::FileSystemTrie< T >::Node = FileSystemTrieNode<T>

Constructor & Destructor Documentation

◆ FileSystemTrie()

template<class T >
detail::FileSystemTrie< T >::FileSystemTrie ( )
inline

Member Function Documentation

◆ _grow()

template<class T >
Node * detail::FileSystemTrie< T >::_grow ( Node *  base,
const FileSystemPathView  relativePath 
)
inlineprivate

◆ _prune()

template<class T >
Node * detail::FileSystemTrie< T >::_prune ( Node *  node)
inlineprivate

◆ chop() [1/2]

template<class T >
void detail::FileSystemTrie< T >::chop ( FileSystemPathView  path)
inline

◆ chop() [2/2]

template<class T >
void detail::FileSystemTrie< T >::chop ( Node *  base,
FileSystemPathView  relativePath = {} 
)
inline

◆ clear()

template<class T >
void detail::FileSystemTrie< T >::clear ( )
inline

◆ erase() [1/2]

template<class T >
bool detail::FileSystemTrie< T >::erase ( FileSystemPathView  path)
inline

◆ erase() [2/2]

template<class T >
bool detail::FileSystemTrie< T >::erase ( Node *  base,
FileSystemPathView  relativePath = {} 
)
inline

◆ extract()

template<class T >
std::unique_ptr< Node > detail::FileSystemTrie< T >::extract ( Node *  node)
inline

◆ find() [1/4]

template<class T >
const Node * detail::FileSystemTrie< T >::find ( const Node *  base,
FileSystemPathView  relativePath 
) const
inline

◆ find() [2/4]

template<class T >
Node * detail::FileSystemTrie< T >::find ( FileSystemPathView  path)
inline

◆ find() [3/4]

template<class T >
const Node * detail::FileSystemTrie< T >::find ( FileSystemPathView  path) const
inline

◆ find() [4/4]

template<class T >
Node * detail::FileSystemTrie< T >::find ( Node *  base,
FileSystemPathView  relativePath 
)
inline

◆ insertOrAssign() [1/4]

template<class T >
Node * detail::FileSystemTrie< T >::insertOrAssign ( FileSystemPathView  path,
std::unique_ptr< Node >  node 
)
inline

◆ insertOrAssign() [2/4]

template<class T >
Node * detail::FileSystemTrie< T >::insertOrAssign ( FileSystemPathView  path,
T  value 
)
inline

◆ insertOrAssign() [3/4]

template<class T >
Node * detail::FileSystemTrie< T >::insertOrAssign ( Node *  base,
FileSystemPathView  relativePath,
std::unique_ptr< Node >  node 
)
inline

◆ insertOrAssign() [4/4]

template<class T >
Node * detail::FileSystemTrie< T >::insertOrAssign ( Node *  base,
FileSystemPathView  relativePath,
T  value 
)
inline

◆ isEmpty()

template<class T >
bool detail::FileSystemTrie< T >::isEmpty ( ) const
inline

◆ root() [1/2]

template<class T >
Node * detail::FileSystemTrie< T >::root ( )
inline

◆ root() [2/2]

template<class T >
const Node * detail::FileSystemTrie< T >::root ( ) const
inline

◆ walk() [1/4]

template<class T >
const Node * detail::FileSystemTrie< T >::walk ( const Node *  base,
FileSystemPathView  relativePath,
FileSystemPathView *  tail = nullptr 
) const
inline

◆ walk() [2/4]

template<class T >
Node * detail::FileSystemTrie< T >::walk ( FileSystemPathView  path,
FileSystemPathView *  tail = nullptr 
)
inline

◆ walk() [3/4]

template<class T >
const Node * detail::FileSystemTrie< T >::walk ( FileSystemPathView  path,
FileSystemPathView *  tail = nullptr 
) const
inline

◆ walk() [4/4]

template<class T >
Node * detail::FileSystemTrie< T >::walk ( Node *  base,
FileSystemPathView  relativePath,
FileSystemPathView *  tail = nullptr 
)
inline

Member Data Documentation

◆ _root

template<class T >
std::unique_ptr<FileSystemTrieNode<T> > detail::FileSystemTrie< T >::_root
private
The documentation for this class was generated from the following files:
Generated by doxygen 1.9.5