summaryrefslogtreecommitdiffstats
path: root/logic/SeparatorPrefixTree.h
diff options
context:
space:
mode:
authorPetr Mrázek <peterix@gmail.com>2015-04-19 04:19:29 +0200
committerPetr Mrázek <peterix@gmail.com>2015-04-19 16:14:32 +0200
commitc7c81463fd3ab01c9e096f75e7e8ad8b50902a98 (patch)
treeab19d0316cd293bcc05bc6b1b6e937c858814b90 /logic/SeparatorPrefixTree.h
parent6cfac115b1f18b9ff5130b2b9a6d5e2fcf052e6c (diff)
downloadMultiMC-c7c81463fd3ab01c9e096f75e7e8ad8b50902a98.tar
MultiMC-c7c81463fd3ab01c9e096f75e7e8ad8b50902a98.tar.gz
MultiMC-c7c81463fd3ab01c9e096f75e7e8ad8b50902a98.tar.lz
MultiMC-c7c81463fd3ab01c9e096f75e7e8ad8b50902a98.tar.xz
MultiMC-c7c81463fd3ab01c9e096f75e7e8ad8b50902a98.zip
GH-885 export dialog for filtering exported files
Includes implementation of a separator based prefix tree and some related bits
Diffstat (limited to 'logic/SeparatorPrefixTree.h')
-rw-r--r--logic/SeparatorPrefixTree.h298
1 files changed, 298 insertions, 0 deletions
diff --git a/logic/SeparatorPrefixTree.h b/logic/SeparatorPrefixTree.h
new file mode 100644
index 00000000..fd149af0
--- /dev/null
+++ b/logic/SeparatorPrefixTree.h
@@ -0,0 +1,298 @@
+#pragma once
+#include <QString>
+#include <QMap>
+#include <QStringList>
+
+template <char Tseparator>
+class SeparatorPrefixTree
+{
+public:
+ SeparatorPrefixTree(QStringList paths)
+ {
+ insert(paths);
+ }
+
+ SeparatorPrefixTree(bool contained = false)
+ {
+ m_contained = contained;
+ }
+
+ 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));
+ }
+ }
+
+ /// 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));
+ }
+ }
+
+ /// 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));
+ }
+ }
+
+ /// 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 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;
+ }
+
+ /// 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;
+ }
+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;
+ }
+
+private:
+ QMap<QString,SeparatorPrefixTree<Tseparator>> children;
+ bool m_contained = false;
+};