summaryrefslogtreecommitdiffstats
path: root/api/logic/SeparatorPrefixTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'api/logic/SeparatorPrefixTree.h')
-rw-r--r--api/logic/SeparatorPrefixTree.h544
1 files changed, 272 insertions, 272 deletions
diff --git a/api/logic/SeparatorPrefixTree.h b/api/logic/SeparatorPrefixTree.h
index fd149af0..7a841cb7 100644
--- a/api/logic/SeparatorPrefixTree.h
+++ b/api/logic/SeparatorPrefixTree.h
@@ -7,292 +7,292 @@ template <char Tseparator>
class SeparatorPrefixTree
{
public:
- SeparatorPrefixTree(QStringList paths)
- {
- insert(paths);
- }
+ SeparatorPrefixTree(QStringList paths)
+ {
+ insert(paths);
+ }
- SeparatorPrefixTree(bool contained = false)
- {
- m_contained = contained;
- }
+ SeparatorPrefixTree(bool contained = false)
+ {
+ m_contained = contained;
+ }
- void insert(QStringList paths)
- {
- for(auto &path: paths)
- {
- insert(path);
- }
- }
+ void insert(QStringList paths)
+ {
+ for(auto &path: paths)
+ {
+ insert(path);
+ }
+ }
- /// insert an exact path into the tree
- SeparatorPrefixTree & insert(QString path)
- {
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- children[path] = SeparatorPrefixTree(true);
- return children[path];
- }
- else
- {
- auto prefix = path.left(sepIndex);
- if(!children.contains(prefix))
- {
- children[prefix] = SeparatorPrefixTree(false);
- }
- return children[prefix].insert(path.mid(sepIndex + 1));
- }
- }
+ /// insert an exact path into the tree
+ SeparatorPrefixTree & insert(QString path)
+ {
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ children[path] = SeparatorPrefixTree(true);
+ return children[path];
+ }
+ else
+ {
+ auto prefix = path.left(sepIndex);
+ if(!children.contains(prefix))
+ {
+ children[prefix] = SeparatorPrefixTree(false);
+ }
+ return children[prefix].insert(path.mid(sepIndex + 1));
+ }
+ }
- /// is the path fully contained in the tree?
- bool contains(QString path) const
- {
- auto node = find(path);
- return node != nullptr;
- }
+ /// is the path fully contained in the tree?
+ bool contains(QString path) const
+ {
+ auto node = find(path);
+ return node != nullptr;
+ }
- /// does the tree cover a path? That means the prefix of the path is contained in the tree
- bool covers(QString path) const
- {
- // if we found some valid node, it's good enough. the tree covers the path
- if(m_contained)
- {
- return true;
- }
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- auto found = children.find(path);
- if(found == children.end())
- {
- return false;
- }
- return (*found).covers(QString());
- }
- else
- {
- auto prefix = path.left(sepIndex);
- auto found = children.find(prefix);
- if(found == children.end())
- {
- return false;
- }
- return (*found).covers(path.mid(sepIndex + 1));
- }
- }
+ /// does the tree cover a path? That means the prefix of the path is contained in the tree
+ bool covers(QString path) const
+ {
+ // if we found some valid node, it's good enough. the tree covers the path
+ if(m_contained)
+ {
+ return true;
+ }
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ auto found = children.find(path);
+ if(found == children.end())
+ {
+ return false;
+ }
+ return (*found).covers(QString());
+ }
+ else
+ {
+ auto prefix = path.left(sepIndex);
+ auto found = children.find(prefix);
+ if(found == children.end())
+ {
+ return false;
+ }
+ return (*found).covers(path.mid(sepIndex + 1));
+ }
+ }
- /// return the contained path that covers the path specified
- QString cover(QString path) const
- {
- // if we found some valid node, it's good enough. the tree covers the path
- if(m_contained)
- {
- return QString("");
- }
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- auto found = children.find(path);
- if(found == children.end())
- {
- return QString();
- }
- auto nested = (*found).cover(QString());
- if(nested.isNull())
- {
- return nested;
- }
- if(nested.isEmpty())
- return path;
- return path + Tseparator + nested;
- }
- else
- {
- auto prefix = path.left(sepIndex);
- auto found = children.find(prefix);
- if(found == children.end())
- {
- return QString();
- }
- auto nested = (*found).cover(path.mid(sepIndex + 1));
- if(nested.isNull())
- {
- return nested;
- }
- if(nested.isEmpty())
- return prefix;
- return prefix + Tseparator + nested;
- }
- }
+ /// return the contained path that covers the path specified
+ QString cover(QString path) const
+ {
+ // if we found some valid node, it's good enough. the tree covers the path
+ if(m_contained)
+ {
+ return QString("");
+ }
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ auto found = children.find(path);
+ if(found == children.end())
+ {
+ return QString();
+ }
+ auto nested = (*found).cover(QString());
+ if(nested.isNull())
+ {
+ return nested;
+ }
+ if(nested.isEmpty())
+ return path;
+ return path + Tseparator + nested;
+ }
+ else
+ {
+ auto prefix = path.left(sepIndex);
+ auto found = children.find(prefix);
+ if(found == children.end())
+ {
+ return QString();
+ }
+ auto nested = (*found).cover(path.mid(sepIndex + 1));
+ if(nested.isNull())
+ {
+ return nested;
+ }
+ if(nested.isEmpty())
+ return prefix;
+ return prefix + Tseparator + nested;
+ }
+ }
- /// Does the path-specified node exist in the tree? It does not have to be contained.
- bool exists(QString path) const
- {
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- auto found = children.find(path);
- if(found == children.end())
- {
- return false;
- }
- return true;
- }
- else
- {
- auto prefix = path.left(sepIndex);
- auto found = children.find(prefix);
- if(found == children.end())
- {
- return false;
- }
- return (*found).exists(path.mid(sepIndex + 1));
- }
- }
+ /// Does the path-specified node exist in the tree? It does not have to be contained.
+ bool exists(QString path) const
+ {
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ auto found = children.find(path);
+ if(found == children.end())
+ {
+ return false;
+ }
+ return true;
+ }
+ else
+ {
+ auto prefix = path.left(sepIndex);
+ auto found = children.find(prefix);
+ if(found == children.end())
+ {
+ return false;
+ }
+ return (*found).exists(path.mid(sepIndex + 1));
+ }
+ }
- /// find a node in the tree by name
- const SeparatorPrefixTree * find(QString path) const
- {
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- auto found = children.find(path);
- if(found == children.end())
- {
- return nullptr;
- }
- return &(*found);
- }
- else
- {
- auto prefix = path.left(sepIndex);
- auto found = children.find(prefix);
- if(found == children.end())
- {
- return nullptr;
- }
- return (*found).find(path.mid(sepIndex + 1));
- }
- }
+ /// find a node in the tree by name
+ const SeparatorPrefixTree * find(QString path) const
+ {
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ auto found = children.find(path);
+ if(found == children.end())
+ {
+ return nullptr;
+ }
+ return &(*found);
+ }
+ else
+ {
+ auto prefix = path.left(sepIndex);
+ auto found = children.find(prefix);
+ if(found == children.end())
+ {
+ return nullptr;
+ }
+ return (*found).find(path.mid(sepIndex + 1));
+ }
+ }
- /// is this a leaf node?
- bool leaf() const
- {
- return children.isEmpty();
- }
+ /// is this a leaf node?
+ bool leaf() const
+ {
+ return children.isEmpty();
+ }
- /// is this node actually contained in the tree, or is it purely structural?
- bool contained() const
- {
- return m_contained;
- }
+ /// is this node actually contained in the tree, or is it purely structural?
+ bool contained() const
+ {
+ return m_contained;
+ }
- /// Remove a path from the tree
- bool remove(QString path)
- {
- return removeInternal(path) != Failed;
- }
+ /// Remove a path from the tree
+ bool remove(QString path)
+ {
+ return removeInternal(path) != Failed;
+ }
- /// Clear all children of this node tree node
- void clear()
- {
- children.clear();
- }
+ /// Clear all children of this node tree node
+ void clear()
+ {
+ children.clear();
+ }
- QStringList toStringList() const
- {
- QStringList collected;
- // collecting these is more expensive.
- auto iter = children.begin();
- while(iter != children.end())
- {
- QStringList list = iter.value().toStringList();
- for(int i = 0; i < list.size(); i++)
- {
- list[i] = iter.key() + Tseparator + list[i];
- }
- collected.append(list);
- if((*iter).m_contained)
- {
- collected.append(iter.key());
- }
- iter++;
- }
- return collected;
- }
+ QStringList toStringList() const
+ {
+ QStringList collected;
+ // collecting these is more expensive.
+ auto iter = children.begin();
+ while(iter != children.end())
+ {
+ QStringList list = iter.value().toStringList();
+ for(int i = 0; i < list.size(); i++)
+ {
+ list[i] = iter.key() + Tseparator + list[i];
+ }
+ collected.append(list);
+ if((*iter).m_contained)
+ {
+ collected.append(iter.key());
+ }
+ iter++;
+ }
+ return collected;
+ }
private:
- enum Removal
- {
- Failed,
- Succeeded,
- HasChildren
- };
- Removal removeInternal(QString path = QString())
- {
- if(path.isEmpty())
- {
- if(!m_contained)
- {
- // remove all children - we are removing a prefix
- clear();
- return Succeeded;
- }
- m_contained = false;
- if(children.size())
- {
- return HasChildren;
- }
- return Succeeded;
- }
- Removal remStatus = Failed;
- QString childToRemove;
- auto sepIndex = path.indexOf(Tseparator);
- if(sepIndex == -1)
- {
- childToRemove = path;
- auto found = children.find(childToRemove);
- if(found == children.end())
- {
- return Failed;
- }
- remStatus = (*found).removeInternal();
- }
- else
- {
- childToRemove = path.left(sepIndex);
- auto found = children.find(childToRemove);
- if(found == children.end())
- {
- return Failed;
- }
- remStatus = (*found).removeInternal(path.mid(sepIndex + 1));
- }
- switch (remStatus)
- {
- case Failed:
- case HasChildren:
- {
- return remStatus;
- }
- case Succeeded:
- {
- children.remove(childToRemove);
- if(m_contained)
- {
- return HasChildren;
- }
- if(children.size())
- {
- return HasChildren;
- }
- return Succeeded;
- }
- }
- return Failed;
- }
+ enum Removal
+ {
+ Failed,
+ Succeeded,
+ HasChildren
+ };
+ Removal removeInternal(QString path = QString())
+ {
+ if(path.isEmpty())
+ {
+ if(!m_contained)
+ {
+ // remove all children - we are removing a prefix
+ clear();
+ return Succeeded;
+ }
+ m_contained = false;
+ if(children.size())
+ {
+ return HasChildren;
+ }
+ return Succeeded;
+ }
+ Removal remStatus = Failed;
+ QString childToRemove;
+ auto sepIndex = path.indexOf(Tseparator);
+ if(sepIndex == -1)
+ {
+ childToRemove = path;
+ auto found = children.find(childToRemove);
+ if(found == children.end())
+ {
+ return Failed;
+ }
+ remStatus = (*found).removeInternal();
+ }
+ else
+ {
+ childToRemove = path.left(sepIndex);
+ auto found = children.find(childToRemove);
+ if(found == children.end())
+ {
+ return Failed;
+ }
+ remStatus = (*found).removeInternal(path.mid(sepIndex + 1));
+ }
+ switch (remStatus)
+ {
+ case Failed:
+ case HasChildren:
+ {
+ return remStatus;
+ }
+ case Succeeded:
+ {
+ children.remove(childToRemove);
+ if(m_contained)
+ {
+ return HasChildren;
+ }
+ if(children.size())
+ {
+ return HasChildren;
+ }
+ return Succeeded;
+ }
+ }
+ return Failed;
+ }
private:
- QMap<QString,SeparatorPrefixTree<Tseparator>> children;
- bool m_contained = false;
+ QMap<QString,SeparatorPrefixTree<Tseparator>> children;
+ bool m_contained = false;
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-29 15:25:14 +0000