From c7c81463fd3ab01c9e096f75e7e8ad8b50902a98 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Petr=20Mr=C3=A1zek?= Date: Sun, 19 Apr 2015 04:19:29 +0200 Subject: GH-885 export dialog for filtering exported files Includes implementation of a separator based prefix tree and some related bits --- logic/CMakeLists.txt | 5 + logic/MMCStrings.cpp | 76 +++++++++++ logic/MMCStrings.h | 8 ++ logic/MMCZip.cpp | 26 ++-- logic/MMCZip.h | 6 +- logic/SeparatorPrefixTree.h | 298 ++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 408 insertions(+), 11 deletions(-) create mode 100644 logic/MMCStrings.cpp create mode 100644 logic/MMCStrings.h create mode 100644 logic/SeparatorPrefixTree.h (limited to 'logic') 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 + +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& added, QString prefix) +bool MMCZip::compressSubDir(QuaZip* zip, QString dir, QString origDir, QSet& 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, QSetcovers(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, QSetcovers(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 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 #include #include "minecraft/Mod.h" +#include "SeparatorPrefixTree.h" #include 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& added, QString prefix = QString()); + bool compressSubDir(QuaZip *zip, QString dir, QString origDir, QSet &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 +#include +#include + +template +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> children; + bool m_contained = false; +}; -- cgit v1.2.3