From 7167ce41b61d2ba2cdb526777a4233eb84a3b66a Mon Sep 17 00:00:00 2001 From: Unit 193 Date: Sat, 6 Dec 2014 17:33:25 -0500 Subject: Imported Upstream version 2.99.6 --- SQLiteStudio3/coreSQLiteStudio/common/bihash.h | 302 +++++++++++++++++++++++++ 1 file changed, 302 insertions(+) create mode 100644 SQLiteStudio3/coreSQLiteStudio/common/bihash.h (limited to 'SQLiteStudio3/coreSQLiteStudio/common/bihash.h') diff --git a/SQLiteStudio3/coreSQLiteStudio/common/bihash.h b/SQLiteStudio3/coreSQLiteStudio/common/bihash.h new file mode 100644 index 0000000..cde93d1 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/common/bihash.h @@ -0,0 +1,302 @@ +#ifndef BIHASH_H +#define BIHASH_H + +#include + +/** + * @brief Bi-directional QHash + * + * Bi-directional hash treats both inserted values as keys to each other. + * Bi-directional hash built on the left and right values concept. + * + * It's not multi-value hash, so when you try to insert existing value to any + * of sides (left or right), it will replace the whole conflicting entry. + * + * It doesn't provide operator[], because returning reference to an object, + * which then can be changed outside would desynchronize internals of this hash + * (internal inverted map could not be synchronized properly according to changes + * to the external reference). + */ +template +class BiHash +{ + public: + /** + * @brief Creates empty hash. + */ + BiHash() {} + + /** + * @brief Creates hash initialized with given values. + * @param list C++11 style initializer list, like: {{x=y}, {a=b}} + */ + BiHash(std::initializer_list> list) + { + hash = QHash(list); + initInverted(); + } + + /** + * @brief Creates bi-hash basing on QHash. + * @param other QHash to copy data from. + * + * If multiple keys in the QHash refer to the same value, + * this is not defined which one of those values will remain, + * but there will definitely be copied only one of them. + */ + BiHash(const QHash & other) + { + unite(other); + } + + /** + * @brief Creates copy of BiHash. + * @param other BiHash to copy. + */ + BiHash(const BiHash & other) : hash(other.hash), inverted(other.inverted) {} + + /** + * @brief Inserts new values to the hash. + * @param left Left value to be inserted. + * @param right Right value to be inserted. + * + * Note that if the \p left is already in left values, then the current entry + * for the left will be replaced with this new one. + * The same applies for the \p right. + * + * If it happens, that both \p left and \p right have already entries in the + * hash, but those are 2 different entries, then the insert operation will + * remove both conflicting records and insert the new one. + */ + void insert(const L& left, const R& right) + { + if (hash.contains(left)) + removeLeft(left); + + if (inverted.contains(right)) + removeRight(right); + + inverted.insert(right, left); + hash.insert(left, right); + } + + /** + * @brief Tests if left values contain given value. + * @param left Value to test. + * @return true if left values containe the \p left value. + */ + bool containsLeft(const L& left) const + { + return hash.contains(left); + } + + /** + * @brief Tests if right values contain given value. + * @param right Value to test. + * @return true if right values containe the \p right value. + */ + bool containsRight(const R& right) const + { + return inverted.contains(right); + } + + /** + * @brief Removes entry with left value equal to given value. + * @param left Value to remove by. + * @return Number of removed entries. + */ + int removeLeft(const L& left) + { + if (!hash.contains(left)) + return 0; + + inverted.remove(hash.value(left)); + hash.remove(left); + + return 1; + } + + /** + * @brief Removes entry with right value equal to given value. + * @param right Value to remove by. + * @return Number of removed entries. + */ + int removeRight(const R& right) + { + if (!inverted.contains(right)) + return 0; + + hash.remove(inverted.value(right)); + inverted.remove(right); + + return 1; + } + + /** + * @brief Pops entry with left value equal to given value. + * @param left Value to pop by. + * @return Right value assigned to given left value. + */ + R takeLeft(const L& left) + { + R right = hash.take(left); + inverted.remove(right); + return right; + } + + /** + * @brief Pops entry with right value equal to given value. + * @param right Value to pop by. + * @return Left value assigned to given right value. + */ + L takeRight(const R& right) + { + R left = inverted.take(right); + hash.remove(left); + return left; + } + + /** + * @brief Copies all entries from other BiHash to this hash. + * @param other BiHash to copy from. + * @return Reference to this hash after values are copied. + * + * Any entries from the \p other hash will overwrite current + * entries in case of conflict (by either left or right value). + */ + BiHash& unite(const BiHash& other) + { + unite(other.hash); + return *this; + } + + /** + * @overload + */ + BiHash& unite(const QHash& other) + { + QHashIterator it(other); + while (it.hasNext()) + insert(it.next().key(), it.value()); + + return *this; + } + + /** + * @brief Finds right value associated with given left value. + * @param left Left value to match. + * @return Right value if found, or default constructed value of right type. + */ + R valueByLeft(const L& left) const + { + return hash.value(left); + } + + /** + * @brief Finds left value associated with given right value. + * @param right Right value to match. + * @return Left value if found, or default constructed value of left type. + */ + L valueByRight(const R& right) const + { + return inverted.value(right); + } + + /** + * @brief Provides all left values. + * @return List of values from left side. + */ + QList leftValues() const + { + return hash.keys(); + } + + /** + * @brief Provides all right values. + * @return List of values from right side. + */ + QList rightValues() const + { + return inverted.keys(); + } + + /** + * @brief Provides java-like iterator for the hash. + * @return Iterator object for this hash. + */ + QHashIterator iterator() const + { + return QHashIterator(hash); + } + + /** + * @brief Removes all entries from the hash. + */ + void clear() + { + hash.clear(); + inverted.clear(); + } + + /** + * @brief Counts all entries in the hash. + * @return Number of entries. + */ + int count() const + { + return hash.count(); + } + + /** + * @brief Tests whether the hash is empty or not. + * @return true if the hash is empty, false otherwise. + */ + bool isEmpty() const + { + return hash.isEmpty(); + } + + /** + * @brief Provides QHash from this BiHash. + * @return QHash with left values as keys. + */ + const QHash& toQHash() const + { + return hash; + } + + /** + * @brief Provides QHash with inverted values (right-to-left) + * @return QHash with right values as keys. + */ + const QHash& toInvertedQHash() const + { + return inverted; + } + + private: + /** + * @brief Fills inverted internal hash basing on values from hash class member. + */ + void initInverted() + { + QHashIterator it(hash); + while (it.hasNext()) + { + it.next(); + inverted[it.value()] = it.key(); + } + } + + /** + * @brief Hash containing left-to-right mapping. + */ + QHash hash; + + /** + * @brief Hash containing right-to-left mapping. + */ + QHash inverted; +}; + +#endif // BIHASH_H -- cgit v1.2.3