GH-885 export dialog for filtering exported files

Includes implementation of a separator based prefix tree and some related bits

6 files changed, 408 insertions, 11 deletions

diff --git a/logic/CMakeLists.txt b/logic/CMakeLists.txt
index e3b52ec5..6389159e 100644
--- a/logic/CMakeLists.txt
+++ b/logic/CMakeLists.txt
@@ -17,6 +17,11 @@ SET(LOGIC_SOURCES
 	MMCError.h
 	MMCZip.h
 	MMCZip.cpp
+	MMCStrings.h
+	MMCStrings.cpp
+
+	# Prefix tree where node names are strings between separators
+	SeparatorPrefixTree.h
 
 	# WARNING: globals live here
 	Env.h
diff --git a/logic/MMCStrings.cpp b/logic/MMCStrings.cpp
new file mode 100644
index 00000000..c50d596e
--- /dev/null
+++ b/logic/MMCStrings.cpp
@@ -0,0 +1,76 @@
+#include "MMCStrings.h"
+
+/// TAKEN FROM Qt, because it doesn't expose it intelligently
+static inline QChar getNextChar(const QString &s, int location)
+{
+	return (location < s.length()) ? s.at(location) : QChar();
+}
+
+/// TAKEN FROM Qt, because it doesn't expose it intelligently
+int Strings::naturalCompare(const QString &s1, const QString &s2, Qt::CaseSensitivity cs)
+{
+	for (int l1 = 0, l2 = 0; l1 <= s1.count() && l2 <= s2.count(); ++l1, ++l2)
+	{
+		// skip spaces, tabs and 0's
+		QChar c1 = getNextChar(s1, l1);
+		while (c1.isSpace())
+			c1 = getNextChar(s1, ++l1);
+		QChar c2 = getNextChar(s2, l2);
+		while (c2.isSpace())
+			c2 = getNextChar(s2, ++l2);
+
+		if (c1.isDigit() && c2.isDigit())
+		{
+			while (c1.digitValue() == 0)
+				c1 = getNextChar(s1, ++l1);
+			while (c2.digitValue() == 0)
+				c2 = getNextChar(s2, ++l2);
+
+			int lookAheadLocation1 = l1;
+			int lookAheadLocation2 = l2;
+			int currentReturnValue = 0;
+			// find the last digit, setting currentReturnValue as we go if it isn't equal
+			for (QChar lookAhead1 = c1, lookAhead2 = c2;
+				 (lookAheadLocation1 <= s1.length() && lookAheadLocation2 <= s2.length());
+				 lookAhead1 = getNextChar(s1, ++lookAheadLocation1),
+					   lookAhead2 = getNextChar(s2, ++lookAheadLocation2))
+			{
+				bool is1ADigit = !lookAhead1.isNull() && lookAhead1.isDigit();
+				bool is2ADigit = !lookAhead2.isNull() && lookAhead2.isDigit();
+				if (!is1ADigit && !is2ADigit)
+					break;
+				if (!is1ADigit)
+					return -1;
+				if (!is2ADigit)
+					return 1;
+				if (currentReturnValue == 0)
+				{
+					if (lookAhead1 < lookAhead2)
+					{
+						currentReturnValue = -1;
+					}
+					else if (lookAhead1 > lookAhead2)
+					{
+						currentReturnValue = 1;
+					}
+				}
+			}
+			if (currentReturnValue != 0)
+				return currentReturnValue;
+		}
+		if (cs == Qt::CaseInsensitive)
+		{
+			if (!c1.isLower())
+				c1 = c1.toLower();
+			if (!c2.isLower())
+				c2 = c2.toLower();
+		}
+		int r = QString::localeAwareCompare(c1, c2);
+		if (r < 0)
+			return -1;
+		if (r > 0)
+			return 1;
+	}
+	// The two strings are the same (02 == 2) so fall back to the normal sort
+	return QString::compare(s1, s2, cs);
+}
diff --git a/logic/MMCStrings.h b/logic/MMCStrings.h
new file mode 100644
index 00000000..b2dd3912
--- /dev/null
+++ b/logic/MMCStrings.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include <QString>
+
+namespace Strings
+{
+	int naturalCompare(const QString &s1, const QString &s2, Qt::CaseSensitivity cs);
+}
diff --git a/logic/MMCZip.cpp b/logic/MMCZip.cpp
index e2c6d1f5..75f49ced 100644
--- a/logic/MMCZip.cpp
+++ b/logic/MMCZip.cpp
@@ -89,7 +89,7 @@ bool compressFile(QuaZip *zip, QString fileName, QString fileDest)
 	return true;
 }
 
-bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QString>& added,  QString prefix)
+bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QString>& added,  QString prefix, const SeparatorPrefixTree <'/'> * blacklist)
 {
 	if (!zip) return false;
 	if (zip->getMode()!=QuaZip::mdCreate && zip->getMode()!=QuaZip::mdAppend && zip->getMode()!=QuaZip::mdAdd)
@@ -106,13 +106,17 @@ bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QStr
 	QDir origDirectory(origDir);
 	if (dir != origDir)
 	{
-		QuaZipFile dirZipFile(zip);
-		auto dirPrefix = PathCombine(prefix, origDirectory.relativeFilePath(dir)) + "/";
-		if (!dirZipFile.open(QIODevice::WriteOnly, QuaZipNewInfo(dirPrefix, dir), 0, 0, 0))
+		QString internalDirName = origDirectory.relativeFilePath(dir);
+		if(!blacklist || !blacklist->covers(internalDirName))
 		{
-			return false;
+			QuaZipFile dirZipFile(zip);
+			auto dirPrefix = PathCombine(prefix, origDirectory.relativeFilePath(dir)) + "/";
+			if (!dirZipFile.open(QIODevice::WriteOnly, QuaZipNewInfo(dirPrefix, dir), 0, 0, 0))
+			{
+				return false;
+			}
+			dirZipFile.close();
 		}
-		dirZipFile.close();
 	}
 
 	QFileInfoList files = directory.entryInfoList(QDir::AllDirs | QDir::NoDotAndDotDot | QDir::Hidden);
@@ -122,7 +126,7 @@ bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QStr
 		{
 			continue;
 		}
-		if(!compressSubDir(zip,file.absoluteFilePath(),origDir, added, prefix))
+		if(!compressSubDir(zip,file.absoluteFilePath(),origDir, added, prefix, blacklist))
 		{
 			return false;
 		}
@@ -142,6 +146,10 @@ bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QStr
 		}
 
 		QString filename = origDirectory.relativeFilePath(file.absoluteFilePath());
+		if(blacklist && blacklist->covers(filename))
+		{
+			continue;
+		}
 		if(prefix.size())
 		{
 			filename = PathCombine(prefix, filename);
@@ -305,7 +313,7 @@ bool MMCZip::metaInfFilter(QString key)
 	return true;
 }
 
-bool MMCZip::compressDir(QString zipFile, QString dir, QString prefix)
+bool MMCZip::compressDir(QString zipFile, QString dir, QString prefix, const SeparatorPrefixTree <'/'> * blacklist)
 {
 	QuaZip zip(zipFile);
 	QDir().mkpath(QFileInfo(zipFile).absolutePath());
@@ -316,7 +324,7 @@ bool MMCZip::compressDir(QString zipFile, QString dir, QString prefix)
 	}
 
 	QSet<QString> added;
-	if (!compressSubDir(&zip, dir, dir, added, prefix))
+	if (!compressSubDir(&zip, dir, dir, added, prefix, blacklist))
 	{
 		QFile::remove(zipFile);
 		return false;
diff --git a/logic/MMCZip.h b/logic/MMCZip.h
index e1f2ba3a..0107d7a6 100644
--- a/logic/MMCZip.h
+++ b/logic/MMCZip.h
@@ -4,6 +4,7 @@
 #include <QFileInfo>
 #include <QSet>
 #include "minecraft/Mod.h"
+#include "SeparatorPrefixTree.h"
 #include <functional>
 
 class QuaZip;
@@ -18,7 +19,8 @@ namespace MMCZip
 	 * \param recursive Whether to pack sub-directories as well or only files.
 	 * \return true if success, false otherwise.
      */
-	bool compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet<QString>& added, QString prefix = QString());
+	bool compressSubDir(QuaZip *zip, QString dir, QString origDir, QSet<QString> &added,
+					QString prefix = QString(), const SeparatorPrefixTree <'/'> * blacklist = nullptr);
 
 	/**
 	 * Compress a whole directory.
@@ -27,7 +29,7 @@ namespace MMCZip
 	 * \param recursive Whether to pack the subdirectories as well, or just regular files.
 	 * \return true if success, false otherwise.
 	 */
-	bool compressDir(QString zipFile, QString dir, QString prefix = QString());
+	bool compressDir(QString zipFile, QString dir, QString prefix = QString(), const SeparatorPrefixTree <'/'> * blacklist = nullptr);
 
 	/// filter function for @mergeZipFiles - passthrough
 	bool noFilter(QString key);
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;
+};