From: daniel_james_at_[hidden]
Date: 2008-04-30 03:16:52
Author: danieljames
Date: 2008-04-30 03:16:52 EDT (Wed, 30 Apr 2008)
New Revision: 44916
URL: http://svn.boost.org/trac/boost/changeset/44916
Log:
New version of list.hpp
Text files modified:
branches/unordered/trunk/libs/unordered/test/helpers/list.hpp | 377 +++++++++++++++++++++------------------
1 files changed, 202 insertions(+), 175 deletions(-)
Modified: branches/unordered/trunk/libs/unordered/test/helpers/list.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/list.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/list.hpp 2008-04-30 03:16:52 EDT (Wed, 30 Apr 2008)
@@ -11,227 +11,254 @@
#if !defined(UNORDERED_TEST_LIST_HEADER)
#define UNORDERED_TEST_LIST_HEADER
-#include <boost/operators.hpp>
+#include <boost/iterator.hpp>
#include <boost/limits.hpp>
#include <functional>
namespace test
{
+ template <typename T> class list;
+
namespace test_detail
{
+ template <typename T> struct list_node;
+ template <typename T> class list_data;
+ template <typename T> class list_iterator;
+ template <typename T> class list_const_iterator;
+
template <typename T>
- class list_impl
+ struct list_node
{
- public:
- class iterator;
- class const_iterator;
-
- typedef T value_type;
- typedef value_type& reference;
- typedef value_type const& const_reference;
+ T value_;
+ list_node* next_;
+
+ list_node(T const& v) : value_(v), next_(0) {}
+ list_node(T const& v, list_node* n) : value_(v), next_(n) {}
+ };
+ template <typename T>
+ class list_data
+ {
+ public:
+ typedef list_node<T> node;
typedef unsigned int size_type;
- struct node {
- T value_;
- node* next_;
-
- node(T const& v) : value_(v), next_(0) {}
- node(T const& v, node* n) : value_(v), next_(n) {}
- };
-
- class iterator
- : public boost::forward_iterator_helper<
- iterator, value_type,
- int, value_type*, value_type&>
- {
- friend class const_iterator;
- friend class list_impl;
- node* ptr_;
- public:
- iterator() : ptr_(0) {};
- explicit iterator(node* x) : ptr_(x) {}
-
- value_type& operator*() const { return ptr_->value_; }
- iterator& operator++() {
- ptr_ = ptr_->next_; return *this; }
- friend bool operator==(iterator const& x,
- iterator const& y) { return x.ptr_ == y.ptr_; }
- };
-
- class const_iterator
- : public boost::forward_iterator_helper<
- const_iterator, value_type const,
- int, value_type const*, value_type const&>
- {
- friend class list_impl;
- node* ptr_;
- public:
- const_iterator() : ptr_(0) {}
- const_iterator(iterator const& x) : ptr_(x.ptr_) {}
-
- value_type const& operator*() const { return ptr_->value_; }
- const_iterator& operator++() {
- ptr_ = ptr_->next_; return *this; }
- friend bool operator==(const_iterator const& x,
- const_iterator const& y) { return x.ptr_ == y.ptr_; }
- };
-
- protected:
node* first_;
node** last_ptr_;
size_type size_;
- public:
- list_impl() : first_(0), last_ptr_(&first_), size_(0) {}
+ list_data() : first_(0), last_ptr_(&first_), size_(0) {}
- ~list_impl() {
+ ~list_data() {
while(first_) {
node* tmp = first_;
first_ = first_->next_;
delete tmp;
}
}
+ private:
+ list_data(list_data const&);
+ list_data& operator=(list_data const&);
+ };
- iterator begin() { return iterator(first_); }
- iterator end() { return iterator(); }
- const_iterator begin() const { return iterator(first_); }
- const_iterator end() const { return iterator(); }
- const_iterator cbegin() const { return iterator(first_); }
- const_iterator cend() const { return iterator(); }
-
- template <class InputIterator>
- void insert(InputIterator i, InputIterator j) {
- for(; i != j; ++i)
- push_back(*i);
- }
-
- void push_front(value_type const& v) {
- first_ = new node(v, first_);
- if(size_) last_ptr_ = &(*last_ptr_)->next_;
- ++size_;
- }
-
- void push_back(value_type const& v) {
- *last_ptr_ = new node(v);
- last_ptr_ = &(*last_ptr_)->next_;
- ++size_;
- }
-
- void clear() {
- while(first_) {
- node* tmp = first_;
- first_ = first_->next_;
- --size_;
- delete tmp;
- }
- last_ptr_ = &first_;
- }
+ template <typename T>
+ class list_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, T,
+ int, T*, T&>
+ {
+ friend class list_const_iterator<T>;
+ friend class test::list<T>;
+ typedef list_node<T> node;
+ typedef list_const_iterator<T> const_iterator;
- void erase(const_iterator start, const_iterator end) {
- node** ptr = &first_;
+ node* ptr_;
+ public:
+ list_iterator() : ptr_(0) {};
+ explicit list_iterator(node* x) : ptr_(x) {}
- while(*ptr != start.ptr_) {
- ptr = &(*ptr)->next_;
- }
+ T& operator*() const { return ptr_->value_; }
+ T* operator->() const { return &ptr_->value_; }
+ list_iterator& operator++() {
+ ptr_ = ptr_->next_; return *this; }
+ list_iterator& operator++(int) {
+ list_iterator tmp = *this; ptr_ = ptr_->next_; return tmp; }
+ bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+ bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+ };
- while(*ptr != end.ptr_) {
- node* to_delete = *ptr;
- *ptr = (*ptr)->next_;
- --size_;
- delete to_delete;
- }
+ template <typename T>
+ class list_const_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, T,
+ int, T const*, T const&>
+ {
+ friend class list_iterator<T>;
+ friend class test::list<T>;
+ typedef list_node<T> node;
+ typedef list_iterator<T> iterator;
+ typedef list_const_iterator<T> const_iterator;
- if(!*ptr) last_ptr_ = ptr;
- }
+ node* ptr_;
+ public:
+ list_const_iterator() : ptr_(0) {}
+ list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
- bool empty() const {
- return !size_;
- }
+ T const& operator*() const { return ptr_->value_; }
+ T const* operator->() const { return &ptr_->value_; }
+ list_const_iterator& operator++() {
+ ptr_ = ptr_->next_; return *this; }
+ list_const_iterator& operator++(int) {
+ list_const_iterator tmp = *this; ptr_ = ptr_->next_; return tmp; }
+ bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+ bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+ };
+ }
- size_type size() const {
- return size_;
- }
+ template <typename T>
+ class list
+ {
+ typedef test::test_detail::list_data<T> data;
+ typedef test::test_detail::list_node<T> node;
+ data data_;
+ public:
+ typedef T value_type;
+ typedef value_type& reference;
+ typedef value_type const& const_reference;
+ typedef unsigned int size_type;
- void sort() {
- sort(std::less<T>());
- }
+ typedef test::test_detail::list_iterator<T> iterator;
+ typedef test::test_detail::list_const_iterator<T> const_iterator;
- template <typename Less>
- void sort(Less less = Less()) {
- if(!this->empty()) merge_sort(&this->first_,
- (std::numeric_limits<size_type>::max)(), less);
- }
+ list() : data_() {}
- private:
+ list(list const& other) : data_() {
+ insert(other.begin(), other.end());
+ }
- template <typename Less>
- node** merge_sort(node** l, size_type recurse_limit, Less less)
- {
- node** ptr = &(*l)->next_;
- for(size_type count = 0; count < recurse_limit && *ptr; ++count)
- {
- ptr = merge_adjacent_ranges(l, ptr,
- merge_sort(ptr, count, less), less);
- }
- return ptr;
+ template <class InputIterator>
+ list(InputIterator i, InputIterator j) : data_() {
+ insert(i, j);
+ }
+
+ list& operator=(list const& other) {
+ clear();
+ insert(other.begin(), other.end());
+ }
+
+ iterator begin() { return iterator(data_.first_); }
+ iterator end() { return iterator(); }
+ const_iterator begin() const { return iterator(data_.first_); }
+ const_iterator end() const { return iterator(); }
+ const_iterator cbegin() const { return iterator(data_.first_); }
+ const_iterator cend() const { return iterator(); }
+
+ template <class InputIterator>
+ void insert(InputIterator i, InputIterator j) {
+ for(; i != j; ++i)
+ push_back(*i);
+ }
+
+ void push_front(value_type const& v) {
+ data_.first_ = new node(v, data_.first_);
+ if(data_.size_) data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+ ++data_.size_;
+ }
+
+ void push_back(value_type const& v) {
+ *data_.last_ptr_ = new node(v);
+ data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+ ++data_.size_;
+ }
+
+ void clear() {
+ while(data_.first_) {
+ node* tmp = data_.first_;
+ data_.first_ = data_.first_->next_;
+ --data_.size_;
+ delete tmp;
}
-
- template <typename Less>
- node** merge_adjacent_ranges(node** first, node** second,
- node** third, Less less)
- {
- while(first != second) {
- if(less((*second)->value_, (*first)->value_)) {
- swap_adjacent_ranges(first, second, third);
- std::swap(second, third);
- }
- first = &(*first)->next_;
- }
- return third;
+ data_.last_ptr_ = &data_.first_;
+ }
+
+ void erase(const_iterator start, const_iterator end) {
+ node** ptr = &data_.first_;
+
+ while(*ptr != start.ptr_) {
+ ptr = &(*ptr)->next_;
}
-
- void swap_adjacent_ranges(node** first, node** second, node** third)
- {
- node* tmp = *first;
- *first = *second;
- *second = *third;
- *third = tmp;
- if(!*second) this->last_ptr_ = second;
+
+ while(*ptr != end.ptr_) {
+ node* to_delete = *ptr;
+ *ptr = (*ptr)->next_;
+ --data_.size_;
+ delete to_delete;
}
- list_impl(list_impl const&);
- list_impl& operator=(list_impl const&);
- };
- }
+ if(!*ptr) data_.last_ptr_ = ptr;
+ }
- template <typename T>
- class list
- : public test::test_detail::list_impl<T>,
- boost::equality_comparable1<list<T> >
-
- {
- typedef test::test_detail::list_impl<T> base;
- public:
- list() : base() {}
+ bool empty() const {
+ return !data_.size_;
+ }
- list(list const& other) : base() {
- this->insert(other.begin(), other.end());
+ size_type size() const {
+ return data_.size_;
}
- template <class InputIterator>
- list(InputIterator i, InputIterator j) : base() {
- this->insert(i, j);
+ void sort() {
+ sort(std::less<T>());
}
- list& operator=(list const& other) {
- this->clear();
- this->insert(other.begin(), other.end());
+ template <typename Less>
+ void sort(Less less = Less()) {
+ if(!empty()) merge_sort(&data_.first_,
+ (std::numeric_limits<size_type>::max)(), less);
+ }
+
+ bool operator==(list const& y) const {
+ return size() == y.size() &&
+ std::equal(begin(), end(), y.begin());
+ }
+
+ bool operator!=(list const& y) const {
+ return !(*this == y);
}
- friend bool operator==(list const& x, list const& y) {
- return x.size() == y.size() &&
- std::equal(x.begin(), x.end(), y.begin());
+ private:
+ template <typename Less>
+ node** merge_sort(node** l, size_type recurse_limit, Less less)
+ {
+ node** ptr = &(*l)->next_;
+ for(size_type count = 0; count < recurse_limit && *ptr; ++count)
+ {
+ ptr = merge_adjacent_ranges(l, ptr,
+ merge_sort(ptr, count, less), less);
+ }
+ return ptr;
+ }
+
+ template <typename Less>
+ node** merge_adjacent_ranges(node** first, node** second,
+ node** third, Less less)
+ {
+ while(first != second) {
+ if(less((*second)->value_, (*first)->value_)) {
+ swap_adjacent_ranges(first, second, third);
+ std::swap(second, third);
+ }
+ first = &(*first)->next_;
+ }
+ return third;
+ }
+
+ void swap_adjacent_ranges(node** first, node** second, node** third)
+ {
+ node* tmp = *first;
+ *first = *second;
+ *second = *third;
+ *third = tmp;
+ if(!*second) data_.last_ptr_ = second;
}
};
}