summaryrefslogtreecommitdiffstats
path: root/logic/SeparatorPrefixTree.h
diff options
context:
space:
mode:
authorPetr Mrázek <peterix@gmail.com>2016-04-10 04:29:29 +0200
committerPetr Mrázek <peterix@gmail.com>2016-04-30 23:59:23 +0200
commit47e37635f50c09b4f9a9ee7699e3120bab3e4088 (patch)
tree061c2f675fb7e244ebe4b54ef206bfbd615c91f8 /logic/SeparatorPrefixTree.h
parentfcd4a482f759cd58ee319a51082d0146b7e426e2 (diff)
downloadMultiMC-47e37635f50c09b4f9a9ee7699e3120bab3e4088.tar
MultiMC-47e37635f50c09b4f9a9ee7699e3120bab3e4088.tar.gz
MultiMC-47e37635f50c09b4f9a9ee7699e3120bab3e4088.tar.lz
MultiMC-47e37635f50c09b4f9a9ee7699e3120bab3e4088.tar.xz
MultiMC-47e37635f50c09b4f9a9ee7699e3120bab3e4088.zip
NOISSUE split GUI stuff from logic library
Diffstat (limited to 'logic/SeparatorPrefixTree.h')
-rw-r--r--logic/SeparatorPrefixTree.h298
1 files changed, 0 insertions, 298 deletions
diff --git a/logic/SeparatorPrefixTree.h b/logic/SeparatorPrefixTree.h
deleted file mode 100644
index fd149af0..00000000
--- a/logic/SeparatorPrefixTree.h
+++ /dev/null
@@ -1,298 +0,0 @@
-#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;
-};