5 files changed, 134 insertions, 55 deletions

diff --git a/raul/Path.hpp b/raul/Path.hpp
index d8ef751..ba8574e 100644
--- a/raul/Path.hpp
+++ b/raul/Path.hpp
@@ -44,6 +44,9 @@ namespace Raul {
 class Path : public std::basic_string<char> {
 public:
 
+	/** Contrust an uninitialzed path, because the STL is annoying. */
+	Path() : std::basic_string<char>("/") {}
+
 	/** Construct a Path from an std::string.
 	 *
 	 * It is a fatal error to construct a Path from an invalid string,
@@ -114,7 +117,7 @@ public:
 	 * Returned value is always a valid path, with the single exception that
 	 * the last character is "/".
 	 */
-	inline string base() const
+	inline const string base() const
 	{
 		if ((*this) == "/")
 			return *this;
@@ -125,9 +128,9 @@ public:
 	/** Return true if \a child is equal to, or a descendant of \a parent */
 	static bool descendant_comparator(const Path& parent, const Path& child)
 	{
-		return ( child == parent
-				|| (!strncmp(parent.c_str(), child.c_str(), parent.length())
-						&& child[parent.length()] == '/') );
+		return ( child == parent || (child.length() > parent.length() &&
+				(!strncmp(parent.c_str(), child.c_str(), parent.length())
+						&& child[parent.length()] == '/')) );
 	}
 };
 
diff --git a/raul/PathTable.hpp b/raul/PathTable.hpp
index 6754b14..65b7cc8 100644
--- a/raul/PathTable.hpp
+++ b/raul/PathTable.hpp
@@ -31,8 +31,14 @@ public:
 	 * descendants of parent.  The return value is never a descendent of
 	 * parent, and may be end().
 	 */
+	typename Table<Path, T>::iterator find_descendants_end(
+			typename Table<Path, T>::iterator parent)
+	{
+		return find_range_end(parent, &Path::descendant_comparator);
+	}
+	
 	typename Table<Path, T>::const_iterator find_descendants_end(
-			typename Table<Path, T>::const_iterator parent) const
+			typename Table<Path, T>::const_iterator parent) const 
 	{
 		return find_range_end(parent, &Path::descendant_comparator);
 	}
diff --git a/raul/Table.hpp b/raul/Table.hpp
index e4d4fa5..3342bdb 100644
--- a/raul/Table.hpp
+++ b/raul/Table.hpp
@@ -37,6 +37,7 @@ public:
 	
 	void clear() { _entries.clear(); }
 	bool empty() const { return _entries.empty(); }
+	void reserve(size_t n) { _entries.reserve(n); }
 
 	struct const_iterator {
 		const_iterator(const Table<K,T>& t, size_t i) : _table(t), _index(i) {}
@@ -76,14 +77,17 @@ public:
 	void erase(const K& key);
 	void erase(iterator i);
 	void erase(iterator start, iterator end);
-	void erase(size_t start, size_t end);
+	void erase_by_index(size_t start, size_t end);
+	
+	std::vector<std::pair<K, T> > yank(iterator start, iterator end);
+
+	std::pair<iterator, bool> cram(const std::vector<std::pair<K, T> >& range);
 	
 	const_iterator find(const K& key) const;
 	iterator find(const K& key);
 
 	const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const;
-	const_iterator find_in_range(const K& key, const_iterator start, const_iterator end,
-			bool (*comp)(const K&,const K&)) const;
+	iterator find_range_end(iterator left, bool (*comp)(const K&,const K&));
 
 	T& operator[](const K& key);
 
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
 }
 
 
diff --git a/tests/table_test.cpp b/tests/table_test.cpp
index 35bc408..4628474 100644
--- a/tests/table_test.cpp
+++ b/tests/table_test.cpp
@@ -44,7 +44,7 @@ main()
 	Table<int,int>::const_iterator range_begin = t.begin();
 	++range_begin; ++range_begin;
 	
-	Table<int,int>::const_iterator range_end = t.find_range_end(t.begin(), range_comparator);
+	Table<int,int>::iterator range_end = t.find_range_end(t.begin(), range_comparator);
 
 	for (Table<int,int>::const_iterator i = t.begin(); i != range_end; ++i)
 		cout << i->first << " ";
@@ -122,6 +122,26 @@ main()
 		cout << i->first << " ";
 	cout << endl;
 
+	const Path yank_path("/bar");
+	PathTable<char>::iterator quux = pt.find(yank_path);
+	assert(quux != pt.end());
+	PathTable<char>::iterator quux_end = pt.find_descendants_end(quux );
+	assert(quux_end != quux);
+
+	std::vector<std::pair<Path,char> > yanked = pt.yank(quux, quux_end);
+	
+	cout << "Yanked " << yank_path << endl;
+	for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+
+	pt.cram(yanked);
+	
+	cout << "Crammed " << yank_path << endl;
+	for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+
 	/* **** */
 
 	cout << "\nAssuming you built with debugging, if this continues to run "