summaryrefslogtreecommitdiffstats
path: root/raul/TableImpl.hpp
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2007-07-26 16:19:58 +0000
committerDavid Robillard <d@drobilla.net>2007-07-26 16:19:58 +0000
commitdfcc6b65f887e3afcb3aa35eb7b15b7d7ffb972e (patch)
treef04e684e9bb14c2ac54687a1b0390338b4cd0d50 /raul/TableImpl.hpp
parent47fb95d6086c2c67086316a25b4c0858783d3c2b (diff)
downloadraul-dfcc6b65f887e3afcb3aa35eb7b15b7d7ffb972e.tar.gz
raul-dfcc6b65f887e3afcb3aa35eb7b15b7d7ffb972e.tar.bz2
raul-dfcc6b65f887e3afcb3aa35eb7b15b7d7ffb972e.zip
Fix various Table bugs (and put some way too slow code in there, but hey, it works).
Use PathTable for models on the client side. Implement renaming on client side. git-svn-id: http://svn.drobilla.net/lad/raul@636 a436a847-0d15-0410-975c-d299462d15a1
Diffstat (limited to 'raul/TableImpl.hpp')
-rw-r--r--raul/TableImpl.hpp138
1 files changed, 92 insertions, 46 deletions
diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp
index 5da9715..7240950 100644
--- a/raul/TableImpl.hpp
+++ b/raul/TableImpl.hpp
@@ -26,6 +26,11 @@
namespace Raul {
+/* This is all a god awful mess.
+ * Whoever decided you shouldn't be able to get an index from an
+ * std::vector::iterator or vice-versa should be shot and pissed on.
+ */
+
#ifndef NDEBUG
template <typename K, typename T>
bool
@@ -86,46 +91,26 @@ Table<K,T>::find(const K& key)
}
-/** Binary search (O(log(end-begin))) */
+/** Find the end of a range using a custom comparator.
+ * Two entries a, b are considered in the range if comp(a, b) returns true.
+ *
+ * Returns an iterator exactly one entry past the end of the range (possibly end()).
+ *
+ * WARNING: The restrictions on \a comparator are very strict: ALL items
+ * considered equal by \a comparator must be stored in the Table consecutively
+ * i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c).
+ *
+ * This is useful for very quickly finding all children of a Path, which
+ * obey the above rule with lexicographical order.
+ */
template <typename K, typename T>
typename Table<K,T>::const_iterator
-Table<K,T>::find_in_range(const K& key, const_iterator start, const_iterator end, bool (*comp)(const K&,const K&)) const
+Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const
{
- if (size() == 0)
- return this->end();
-
- size_t lower = start._index;
- size_t upper = end._index;
-
- if (lower == upper)
- if (comp(key, _entries[lower].first))
- return const_iterator(*this, lower);
- else
- return this->end();
-
- size_t i = lower + ((upper - lower) / 2);
-
- while (upper >= lower) {
-
- const Entry& elem = _entries[i];
-
- if (comp(key, elem.first))
- if (i == size()-1 || !comp(elem.first, _entries[i+1].first))
- return const_iterator(*this, i);
- else if (comp(_entries[lower].first, elem.first))
- lower = i;
-
- if (comp(_entries[lower].first, _entries[upper].first))
- upper = i - 1;
- }
-
- assert(comp(start->first, _entries[lower].first));
- assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
-
- return const_iterator(*this, lower);
+ return ((Table<K, T>*)this)->find_range_end(*((iterator*)&start), comp);
}
-
+
/** Find the end of a range using a custom comparator.
* Two entries a, b are considered in the range if comp(a, b) returns true.
*
@@ -139,8 +124,8 @@ Table<K,T>::find_in_range(const K& key, const_iterator start, const_iterator end
* obey the above rule with lexicographical order.
*/
template <typename K, typename T>
-typename Table<K,T>::const_iterator
-Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const
+typename Table<K,T>::iterator
+Table<K,T>::find_range_end(iterator start, bool (*comp)(const K&,const K&))
{
if (size() == 0)
return this->end();
@@ -152,7 +137,7 @@ Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)
if (lower == upper)
if (comp(key, _entries[lower].first))
- return const_iterator(*this, lower);
+ return iterator(*this, lower+1);
else
return this->end();
@@ -161,6 +146,12 @@ Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)
while (upper > lower) {
i = lower + ((upper - lower) / 2);
+
+ if (upper - lower == 1)
+ if (comp(key, _entries[upper].first) && upper < size())
+ return iterator(*this, upper+1);
+ else if (lower < size())
+ return iterator(*this, lower+1);
const Entry& elem = _entries[i];
@@ -168,7 +159,7 @@ Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)
if (comp(key, elem.first)) {
if (i == size()-1 || !comp(key, _entries[i+1].first))
- return const_iterator(*this, i+1);
+ return iterator(*this, i+1);
else
lower = i;
@@ -183,7 +174,66 @@ Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)
assert(comp(start->first, _entries[lower].first));
assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
- return const_iterator(*this, lower+1);
+ return iterator(*this, lower+1);
+}
+
+
+/** Erase and return a range of entries */
+template <typename K, typename T>
+std::vector<std::pair<K, T> >
+Table<K, T>::yank(iterator start, iterator end)
+{
+ std::vector<std::pair<K, T> > ret(end._index - start._index);
+ for (size_t i=start._index; i < end._index; ++i)
+ ret.at(i - start._index) = _entries[i];
+ erase(start, end);
+ return ret;
+}
+
+
+/** Cram a range of entries back in.
+ * Range MUST follow the same ordering guidelines as find_range_end.
+ * Return type is the same as insert, iterator points to first inserted entry */
+template <typename K, typename T>
+std::pair<typename Table<K,T>::iterator, bool>
+Table<K, T>::cram(const std::vector<std::pair<K, T> >& range)
+{
+ /* FIXME: _way_ too slow */
+
+ const size_t orig_size = size();
+
+ if (range.size() == 0)
+ return std::make_pair(end(), false);
+
+ std::pair<iterator, bool> ret = insert(range.front());
+ if (range.size() == 1)
+ return ret;
+
+ const size_t insert_index = ret.first._index;
+
+ std::vector<Entry> new_entries(orig_size + range.size());
+
+ for (size_t i=0; i <= insert_index; ++i)
+ new_entries.at(i) = _entries.at(i);
+
+ for (size_t i=0; i < size() - insert_index; ++i)
+ new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i);
+
+ for (size_t i=1; i < range.size(); ++i)
+ new_entries.at(insert_index + i) = range.at(i);
+
+ _entries = new_entries;
+
+ /*std::cerr << "********************************\n";
+ for (size_t i=0; i < size(); ++i) {
+ std::cerr << _entries[i].first << std::endl;
+ }
+ std::cerr << "********************************\n";*/
+
+ assert(size() == orig_size + range.size());
+ assert(is_sorted());
+
+ return make_pair(iterator(*this, insert_index), true);
}
@@ -300,9 +350,7 @@ Table<K,T>::erase(iterator i)
_entries.pop_back();
-#ifndef NDEBUG
assert(is_sorted());
-#endif
}
@@ -316,7 +364,7 @@ Table<K,T>::erase(iterator first, iterator last)
const size_t first_index = first._index;
const size_t last_index = last._index;
- erase(first_index, last_index);
+ Table<K,T>::erase_by_index(first_index, last_index);
}
@@ -325,7 +373,7 @@ Table<K,T>::erase(iterator first, iterator last)
*/
template <typename K, typename T>
void
-Table<K,T>::erase(size_t first_index, size_t last_index)
+Table<K,T>::erase_by_index(size_t first_index, size_t last_index)
{
const size_t num_removed = last_index - first_index;
@@ -335,9 +383,7 @@ Table<K,T>::erase(size_t first_index, size_t last_index)
_entries.resize(size() - num_removed);
-#ifndef NDEBUG
assert(is_sorted());
-#endif
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-04-17 15:34:02 +0000