Subject: [Boost-commit] svn:boost r53891 - in sandbox/monotonic: boost/monotonic boost/utility libs/monotonic/test
From: christian.schladetsch_at_[hidden]
Date: 2009-06-14 01:59:22
Author: cschladetsch
Date: 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
New Revision: 53891
URL: http://svn.boost.org/trac/boost/changeset/53891
Log:
completed first rope implementation with iterators
added iter_range
Added:
sandbox/monotonic/boost/utility/
sandbox/monotonic/boost/utility/iter_range.h (contents, props changed)
sandbox/monotonic/libs/monotonic/test/rope.cpp (contents, props changed)
Text files modified:
sandbox/monotonic/boost/monotonic/rope.h | 198 +++++++++++++++++++++++++++++++++++++--
sandbox/monotonic/libs/monotonic/test/main.cpp | 3
sandbox/monotonic/libs/monotonic/test/monotonic.vcproj | 12 ++
3 files changed, 199 insertions(+), 14 deletions(-)
Modified: sandbox/monotonic/boost/monotonic/rope.h
==============================================================================
--- sandbox/monotonic/boost/monotonic/rope.h (original)
+++ sandbox/monotonic/boost/monotonic/rope.h 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
@@ -7,30 +7,108 @@
#include <boost/monotonic/allocator.h>
#include <boost/monotonic/storage_base.h>
+#include <boost/utility/iter_range.h>
+#include <boost/unordered_map.hpp>
namespace boost
{
namespace monotonic
{
/// a set of sequences that are tied together to present a contiguous sequence
- template <class T>
+ ///
+ /// this is to provide a sequence type that is 'between' a list and a vector. it
+ /// has slower access speed than a vector, but faster access speed than a list.
+ ///
+ /// unlike a vector, a rope cannot be resize()d
+ template <class T, size_t ChunkSize = 32>
struct rope
{
+ typedef rope<T,ChunkSize> Rope;
typedef allocator<T> Allocator;
typedef vector<T> Vector;
typedef list<Vector> Strands;
+ typedef const_iter_range<Strands> ConstStrandsIterators;
+ typedef iter_range<Strands> StrandsIterators;
+ typedef const_iter_range<Vector> ConstVectorIterators;
+ typedef iter_range<Vector> VectorIterators;
- struct const_iterator
+ template <class R, class S, class V, class Derived>
+ struct iterator_base //: TODO: add iterator category
{
- rope<T> const *parent;
- Strands::const_iterator strand;
- Vector::const_iterator iter;
-
- const_iterator() : parent(0) { }
- const_iterator(rope<T> const *P) : parent(P) { }
- const_iterator(rope<T> const *P, Strands::const_iterator const &S, Vector::const_iterator const &V)
- : parent(P), strand(S), iter(V) { }
- //const_iterator operator++(int)
+ typedef R Rope;
+ typedef S StrandIterators;
+ typedef V VectorIterators;
+ Rope *parent;
+ StrandIterators strand;
+ VectorIterators vec;
+
+ iterator_base() { }
+ iterator_base(Rope &P) : parent(&P) { }
+ iterator_base(Rope &P, StrandIterators const &S)
+ : parent(&P), strand(S) { }
+ iterator_base(Rope &P, StrandIterators const &S, VectorIterators const &V)
+ : parent(&P), strand(S), vec(V) { }
+ Derived &This()
+ {
+ return static_cast<Derived &>(*this);
+ }
+ Derived &operator++()
+ {
+ if (!++vec)
+ {
+ if (!++strand)
+ {
+ return This();
+ }
+ vec = *strand;
+ }
+ return This();
+ }
+ bool operator==(iterator_base const &B) const
+ {
+ return parent == B.parent && strand == B.strand && vec == B.vec;
+ }
+ bool operator!=(iterator_base const &B) const
+ {
+ return !(*this == B);
+ }
+ };
+ struct iterator : iterator_base<Rope, StrandsIterators, VectorIterators, iterator>
+ {
+ typedef iterator_base<Rope, StrandsIterators, VectorIterators, iterator> Parent;
+ iterator() { }
+ iterator(Rope &P)
+ : Parent(P) { }
+ iterator(Rope &P, StrandsIterators const &S)
+ : Parent(P, S) { }
+ iterator(Rope &P, StrandsIterators const &S, VectorIterators const &V)
+ : Parent(P, S, V) { }
+ T const &operator*() const
+ {
+ return *Parent::vec;
+ }
+ T &operator*()
+ {
+ return *Parent::vec;
+ }
+ };
+ struct const_iterator : iterator_base<Rope const, ConstStrandsIterators, ConstVectorIterators, const_iterator>
+ {
+ typedef iterator_base<Rope const, ConstStrandsIterators, ConstVectorIterators, const_iterator> Parent;
+ const_iterator() { }
+ const_iterator(Rope const &P)
+ : Parent(P) { }
+ const_iterator(iterator const &X)
+ : Parent(*X.parent, X.strand, X.vec)
+ { }
+ const_iterator(Rope const &P, ConstStrandsIterators const &S)
+ : Parent(P, S) { }
+ const_iterator(Rope const &P, ConstStrandsIterators const &S, ConstVectorIterators const &V)
+ : Parent(P, S, V) { }
+ T const &operator*() const
+ {
+ return *Parent::vec;
+ }
};
private:
@@ -40,15 +118,107 @@
public:
rope() { }
rope(Allocator const &A)
- : alloc(A) { }
+ : alloc(A), strands(A) { }
rope(size_t N, T const &X, Allocator const &A)
- : alloc(A)
+ : alloc(A), strands(A)
{
+ //TODO
}
template <class II>
rope(II F, II L, Allocator const &A)
- : alloc(A)
+ : alloc(A), strands(A)
+ {
+ //TODO
+ }
+
+ size_t size() const
+ {
+ size_t len = 0;
+ BOOST_FOREACH(Vector const &vec, strands)
+ {
+ len += vec.size();
+ }
+ return len;
+ }
+ bool empty() const
+ {
+ return strands.empty() || size() == 0;
+ }
+ const_iterator begin() const
+ {
+ if (strands.empty())
+ return const_iterator(*this);
+ return const_iterator(*this, strands, strands.front());
+ }
+ const_iterator end() const
+ {
+ if (strands.empty())
+ return const_iterator(*this);
+ return const_iterator(*this, strands.end(), strands.back().end());
+ }
+ iterator begin()
+ {
+ if (strands.empty())
+ return iterator(*this);
+ return iterator(*this, strands, strands.front());
+ }
+ iterator end()
+ {
+ if (strands.empty())
+ return iterator(*this);
+ return iterator(*this, strands.end(), strands.back().end());
+ }
+ void push_back(T const &X)
+ {
+ bool require_new_vec = strands.empty();
+ require_new_vec = require_new_vec || strands.back().size() == strands.back().capacity();
+ if (require_new_vec)
+ {
+ strands.push_back(Vector(alloc));
+ strands.back().reserve(ChunkSize);
+ }
+ strands.back().push_back(X);
+ }
+
+ T &at(size_t N)
+ {
+ size_t offset = 0;
+ BOOST_FOREACH(Vector &vec, strands)
+ {
+ size_t local = N - offset;
+ if (local < vec.size())
+ {
+ return vec.at(local);
+ }
+ offset += vec.size();
+ if (offset > N)
+ break;
+ }
+ throw std::out_of_range("rope");
+ }
+ T const &at(size_t N) const
+ {
+ size_t offset = 0;
+ BOOST_FOREACH(Vector const &vec, strands)
+ {
+ size_t local = N - offset;
+ if (local < vec.size())
+ {
+ return vec.at(local);
+ }
+ offset += vec.size();
+ if (offset < N)
+ break;
+ }
+ throw std::out_of_range("rope");
+ }
+ T &operator[](size_t N)
+ {
+ return at(N);
+ }
+ T const &operator[](size_t N) const
{
+ return at(N);
}
};
}
Added: sandbox/monotonic/boost/utility/iter_range.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/utility/iter_range.h 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
@@ -0,0 +1,127 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#pragma once
+
+namespace boost
+{
+ namespace iter_range_detail
+ {
+ template <class Iter>
+ struct iter_range : std::pair<Iter, Iter>
+ {
+ typedef std::pair<Iter, Iter> Parent;
+
+ iter_range() { }
+ iter_range(Iter const &A, Iter const &B)
+ : Parent(A,B) { }
+
+ size_t size() const
+ {
+ return std::distance(first, second);
+ }
+ bool empty() const
+ {
+ return first == second;
+ }
+ void advance(size_t N)
+ {
+ std::advance(first, N);
+ }
+ iter_range& operator++()
+ {
+ BOOST_ASSERT(*this);
+ ++first;
+ return *this;
+ }
+ iter_range operator++(int)
+ {
+ BOOST_ASSERT(*this);
+ iter_range tmp(*this);
+ ++*this;
+ return tmp;
+ }
+ iter_range& operator--()
+ {
+ BOOST_ASSERT(*this);
+ --first;
+ return *this;
+ }
+ iter_range operator--(int)
+ {
+ BOOST_ASSERT(*this);
+ iter_range tmp(*this);
+ --*this;
+ return tmp;
+ }
+ operator bool() const
+ {
+ return first != second;
+ }
+ };
+ }
+
+ template <class C>
+ struct iter_range : iter_range_detail::iter_range<typename C::iterator>
+ {
+ typedef C Container;
+ typedef typename Container::iterator iterator;
+ typedef iter_range_detail::iter_range<iterator> Parent;
+ typedef typename boost::iterator_value<iterator>::type Value;
+
+ iter_range() { }
+ iter_range(Container &C)
+ : Parent(C.begin(), C.end()) { }
+ iter_range(iterator A)
+ : Parent(A,A) { }
+ iter_range(iterator A, iterator B)
+ : Parent(A,B) { }
+ typename Value &operator*() const
+ {
+ return *first;
+ }
+ };
+
+ template <class C>
+ struct const_iter_range : iter_range_detail::iter_range<typename C::const_iterator>
+ {
+ typedef C Container;
+ typedef typename Container::const_iterator const_iterator;
+ typedef iter_range_detail::iter_range<const_iterator> Parent;
+ typedef typename boost::iterator_value<const_iterator>::type Value;
+
+ const_iter_range() { }
+ template <class C2>
+ const_iter_range(iter_range<C2> const &R)
+ : Parent(R.first, R.second) { }
+ const_iter_range(Container const &C)
+ : Parent(C.begin(), C.end()) { }
+ const_iter_range(const_iterator A)
+ : Parent(A,A) { }
+ const_iter_range(const_iterator A, const_iterator B)
+ : Parent(A,B) { }
+ typename const Value &operator*() const
+ {
+ return *first;
+ }
+ };
+ template <class C>
+ const_iter_range<C> make_const_range(C &X)
+ {
+ return const_iter_range<C>(X);
+ }
+ template <class C>
+ const_iter_range<C> make_iter_range(C const &X)
+ {
+ return const_iter_range<C>(X);
+ }
+ template <class C>
+ const_iter_range<C> make_iter_range(C &X)
+ {
+ return iter_range<C>(X);
+ }
+}
+
+//EOF
Modified: sandbox/monotonic/libs/monotonic/test/main.cpp
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/main.cpp (original)
+++ sandbox/monotonic/libs/monotonic/test/main.cpp 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
@@ -429,8 +429,11 @@
}
}
+void test_rope();
+
int main()
{
+ test_rope();
test_shared_allocators();
test_alignment();
test_auto_buffer();
Modified: sandbox/monotonic/libs/monotonic/test/monotonic.vcproj
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/monotonic.vcproj (original)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.vcproj 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
@@ -214,6 +214,14 @@
>
</File>
</Filter>
+ <Filter
+ Name="utility"
+ >
+ <File
+ RelativePath="..\..\..\boost\utility\iter_range.h"
+ >
+ </File>
+ </Filter>
</Filter>
<File
RelativePath="..\doc\index.html"
@@ -223,6 +231,10 @@
RelativePath=".\main.cpp"
>
</File>
+ <File
+ RelativePath=".\rope.cpp"
+ >
+ </File>
</Files>
<Globals>
</Globals>
Added: sandbox/monotonic/libs/monotonic/test/rope.cpp
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/test/rope.cpp 2009-06-14 01:59:20 EDT (Sun, 14 Jun 2009)
@@ -0,0 +1,82 @@
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+// the documentation is at https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/doc/index.html
+
+// the sandbox is at https://svn.boost.org/svn/boost/sandbox/monotonic/
+
+#include <boost/monotonic/vector.h>
+#include <boost/monotonic/list.h>
+#include <boost/monotonic/map.h>
+#include <boost/monotonic/set.h>
+
+#include <boost/timer.hpp>
+#include <boost/foreach.hpp>
+#include <iostream>
+
+#include <boost/range.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/array.hpp>
+#include <boost/scoped_ptr.hpp>
+
+#include <boost/monotonic/rope.h>
+
+using namespace boost;
+using namespace std;
+
+void test_iter_range()
+{
+ std::vector<int> v(10);
+ boost::iter_range<std::vector<int> > r(v);
+ boost::const_iter_range<std::vector<int> > c(r);
+}
+void test_rope()
+{
+ monotonic::inline_storage<1000> storage;
+ {
+ typedef monotonic::rope<int, 2> Rope;
+ Rope rope(storage);
+ rope.push_back(0);
+ rope.push_back(1);
+ rope.push_back(2);
+ rope.push_back(3);
+
+ Rope::iterator A = rope.begin(), B = rope.end();
+ for (; A != B; ++A)
+ {
+ *A *= 2;
+ }
+ Rope::const_iterator C = rope.begin(), D = rope.end();
+ for (; C != D; ++C)
+ {
+ cout << *C;
+ }
+
+ //BOOST_FOREACH(int n, rope)
+ //{
+ // cout << n << endl;
+ //}
+
+ //BOOST_FOREACH(int &n, rope)
+ //{
+ // n *= 2;
+ //}
+ //BOOST_FOREACH(int n, rope)
+ //{
+ // cout << n << endl;
+ //}
+
+
+ rope[0] = 0;
+ rope[1] = 1;
+ rope[2] = 2;
+ rope[3] = 3;
+ assert(*rope.begin() == 0);
+ assert(rope.at(0) == 0);
+ assert(rope.at(1) == 1);
+ assert(rope.at(2) == 2);
+ assert(rope.at(3) == 3);
+ }
+}
+
+//EOF