[Boost-commit] svn:boost r44916 - branches/unordered/trunk/libs/unordered/test/helpers

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;
         }
     };
 }