---

more/gen/ring.h

Go to the documentation of this file.

//  Copyright (C) 2001  Petter Urkedal (petter.urkedal@matfys.lth.se)
//
//  This file is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This file is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: ring.h,v 1.1 2002/05/30 18:01:37 petter_urkedal Exp $


#ifndef MORE_GEN_RING_H
#define MORE_GEN_RING_H

#include <more/gen/memory.h>
#include <stdexcept>
#include <iterator>


namespace more {
namespace gen {

  /** \class ring ring.h more/ring.h
   *
   *  A ring is a collection of object which are bidirectionally
   *  linked into a ring.  That is, a ring is like a list, but with
   *  the last element connected to the first.  One of the nodes is
   *  called the principal node.  This is the only node directly
   *  accessible, and is analogous to both the \c begin() and \c end()
   *  of other containers.
   *
   *  \image html ring_ring.png
   *  \image latex ring_ring.eps
   *  A ring of numbers from 0 to 7.
   *
   *  Note that there is no half-open range of iterators which span
   *  the whole ring.  There are ranges which excludes one element,
   *  and there are pairs of half-open ranges which together span the
   *  ring.
   *
   *  One way to look at it is too see [\c it, \c it) as an ambiguous
   *  range which is empty or spans the whole ring.  Inspired by this
   *  idea you can iterate over all nodes by skipping the first
   *  ``<tt>it != it_past_the_end'' test, as in
   *
   *  \code
   *  if (!r.empty()) {
   *      iterator it = r.principal();
   *      do some_code(it); while (++it != r.principal());
   *  }
   *  \endcode
   */
  template< typename T, typename Alloc = more::gen::allocator<T> >
    struct ring {
        //@{
        /** The standard container types. */
        typedef T value_type;
        typedef Alloc allocator_type;
        typedef typename allocator_type::pointer pointer;
        typedef typename allocator_type::const_pointer const_pointer;
        typedef typename allocator_type::reference reference;
        typedef typename allocator_type::const_reference const_reference;
        typedef typename allocator_type::size_type size_type;
        typedef typename allocator_type::difference_type difference_type;
        //@}

      private:
        struct node {
            node() {}
            node(T const& v) : value(v) {}
            node(node const& x) : value(x.value) {}

            node* prev;
            node* next;
            T value;
        };

        typedef typename allocator_type::template rebind<node>::other
                real_allocator_type;

      public:
        /** A bidirectional iterator. */
        struct iterator
        {
            typedef std::ptrdiff_t difference_type;
            typedef T value_type;
            typedef value_type& reference;
            typedef value_type* pointer;
            typedef std::bidirectional_iterator_tag iterator_category;

            iterator() {}
            iterator(iterator const& it) : x(it.x) {}
            explicit iterator(node* x_) : x(x_) {}
            iterator& operator++() { x = x->next; return *this; }
            iterator operator++(int) {
                iterator tmp = *this;
                ++*this;
                return tmp;
            }
            iterator& operator--() { x = x->prev; return *this; }
            iterator operator--(int) {
                iterator tmp = *this;
                --*this;
                return tmp;
            }
            bool operator==(iterator const& rhs) const {
                return x = rhs.x;
            }
            bool operator!=(iterator const& rhs) const {
                return x != rhs.x;
            }
            iterator& operator=(iterator const& rhs) {
                x = rhs.x;
                return *this;
            }
            reference operator*() { return x->value; }
            pointer operator->() { return &x->value; } // XXX allocator
          private:
            node* x;
            friend class ring;
        };

        /** Yet another bidirectional iterator, but this one's got
         **  const values. */
        struct const_iterator
        {
            typedef std::ptrdiff_t difference_type;
            typedef T const value_type;
            typedef value_type const& reference;
            typedef value_type const* pointer;
            typedef std::bidirectional_iterator_tag iterator_category;

            const_iterator() {}
            const_iterator(const_iterator const& it) : x(it.x) {}
            const_iterator(iterator const& it) : x(it.x) {}
            explicit const_iterator(node const* x_) : x(x_) {}
            const_iterator& operator++() { x = x->next; return *this; }
            const_iterator operator++(int) {
                const_iterator tmp = *this;
                ++*this;
                return tmp;
            }
            const_iterator& operator--() { x = x->prev; return *this; }
            const_iterator operator--(int) {
                const_iterator tmp = *this;
                --*this;
                return tmp;
            }
            bool operator==(const_iterator const& rhs) const {
                return x = rhs.x;
            }
            bool operator!=(const_iterator const& rhs) const {
                return x != rhs.x;
            }
            const_iterator& operator=(const_iterator const& rhs) {
                x = rhs.x;
                return *this;
            }
            reference operator*() { return x->value; }
            pointer operator->() { return &x->value; } // XXX allocator
          private:
            node const* x;
            friend class ring;
        };


        /** Construct an empty continer, which becomes a ring if you
         *  insert an element. */
        ring() : a_node(0), m_size(0) {}

        /** Construct a deep copy of \a x. */
        ring(ring const& r)
            : alloc(r.alloc), a_node(0), m_size(r.m_size) {
            if (r.size()) {
                const_iterator it = r.principal();
                while (--it != r.principal())
                    push_front(*it);
                push_front(*it);
            }
        }

        /** Destruct. */
        ~ring() { clear(); }

        /** Assign a deep copy of \a x. */
        ring& operator=(ring const& x) {
            this->~ring();
            new(this) ring(x);
            return *this;
        }

        /** Number of members of the ring. */
        size_type size() const { return m_size; }

        /** Returns true if the container contains no node. */
        bool empty() const { return m_size == 0; }

        /** Returns an iterator to the principal node. */
        iterator principal() {
#ifndef MORE_NDEBUG
            if (!a_node)
                throw std::logic_error(
                    "A ring with no nodes has no valid iterator.");
#endif
            return iterator(a_node);
        }

        /** Returns an iterator to the principal node. */
        const_iterator principal() const {
#ifndef MORE_NDEBUG
            if (!a_node)
                throw std::logic_error(
                    "A ring with no nodes has no valid iterator.");
#endif
            return const_iterator(a_node);
        }

//      reverse_iterator rprincipal() {
// #ifndef MORE_NDEBUG
//          if (!a_node)
//              throw std::logic_error(
//                  "A ring with no nodes has no valid iterator.");
// #endif
//          return reverse_iterator(a_node);
//      }

        /** Erase all nodes in the ring. */
        void clear() {
            m_size = 0;
            node* x = a_node;
            if (x)
                for(;;) {
                    node* y = x->next;
                    alloc.destroy(x);
                    alloc.deallocate(x, 1);
                    if (y == a_node) break;
                    x = y;
                }
        }

        /** Erase the node at \a it.
         *
         *  \return an iterator to the next element if the container
         *  is non-empty after the operation, otherwise an invalid
         *  iterator.
         */
        iterator erase(iterator it) {
            --m_size;
            node* y = it.x->next;
            y->prev = it.x->prev;
            it.x->prev->next = y;
            if (it.x == a_node) {
                if (y == a_node)
                    a_node = 0;
                else
                    a_node = y;
            }
            alloc.destroy(it.x);
            alloc.deallocate(it.x, 1);
            return iterator(y);
        }

        /** Insert \a val in front of \a it. */
        iterator insert(iterator it, value_type const& val) {
            ++m_size;
            node* x = alloc.allocate(1);
            a.construct(x, node(val));
            x->next = it.x;
            x->prev = it.x->prev;
            it.x->prev->next = x;
            it.x->prev = x;
            return iterator(x);
        }

        /** Insert a default constructed object in front of \a it.
         *  \pre The allocator is extended to support default construction.
         */
        iterator insert(iterator it) {
            ++m_size;
            node* x = alloc.allocate(1);
            alloc.construct(x);
            x->next = it.x;
            x->prev = it.x->prev;
            it.x->prev->next = x;
            it.x->prev = x;
            return iterator(x);
        }

        /** Insert \a val in before the principal and make it the new
         *  principal.  If the ring is empty, set the principal to \a
         *  val. */
        void push_front(value_type const& val) {
            ++m_size;
            node* x = alloc.allocate(1);
            alloc.construct(x, node(val));
            if (a_node) {
                x->prev = a_node->prev;
                x->next = a_node;
                x->prev->next = x;
                a_node->prev = x;
            }
            else {
                x->next = x;
                x->prev = x;
            }
            a_node = x;
        }

        /** Insert a default constructed object before the principal
         *  and make it the new principal.
         *  \pre The allocator is extended to support default construction.
         */
        void push_front() {
            ++m_size;
            node* x = alloc.allocate(1);
            alloc.construct(x);
            if (a_node) {
                x->prev = a_node->prev;
                x->next = a_node;
                x->prev->next = x;
                a_node->prev = x;
            }
            else {
                x->next = x;
                x->prev = x;
            }
            a_node = x;
        }

        /** Insert \a val after the principal and make it the new
         *  principal.  If the ring is empty, set the principal to \a
         *  val. */
        void push_back(value_type const& val) {
            ++m_size;
            node* x = alloc.allocate(1);
            alloc.construct(x, node(val));
            if (a_node) {
                x->prev = a_node;
                x->next = a_node->next;
                x->next->prev = x;
                a_node->next = x;
            }
            else {
                x->next = x;
                x->prev = x;
            }
            a_node = x;
        }

        /** Insert a default constructed object after the principal
         *  and make it the new principal.
         *  \pre The allocator is extended to support default construction.
         */
        void push_back() {
            ++m_size;
            node* x = alloc.allocate(1);
            alloc.construct(x);
            if (a_node) {
                x->prev = a_node;
                x->next = a_node->next;
                x->next->prev = x;
                a_node->next = x;
            }
            else {
                x->next = x;
                x->prev = x;
            }
            a_node = x;
        }

        /** Pop the principal node off the ring, and make the node
         *  after it the new principal. */
        void pop_front() { erase(iterator(a_node)); }

        /** Pop the principal node off the ring, and make the node
         *  before it the new principal. */
        void pop_back() {
            erase(iterator(a_node));
            if (a_node) a_node = a_node->prev;
        }

        /** Make the node after the principal node the next
         *  principal. (Counterclockwise is usually taken as the
         *  positive direction of rotation.)
         *  \pre The ring is not empty.
         */
        void rotate_counterclockwise() {
#ifndef MORE_NDEBUG
            if (!a_node)
                throw std::logic_error("No ring to rotate.");
#endif
            a_node = a_node->next;
        }

        /** Make the node before the principal node the next principal.
         *  \pre The ring is not empty.
         */
        void rotate_clockwise() {
#ifndef MORE_NDEBUG
            if (!a_node)
                throw std::logic_error("No ring to rotate.");
#endif
            a_node = a_node->prev;
        }

        /** Return the allocator. */
        allocator_type get_allocator() const { return alloc; }

      private:
        real_allocator_type alloc;
        node* a_node;
        size_type m_size;
    };
}} // more::gen

#endif

---