---

more/gen/link.h

Go to the documentation of this file.

//  Copyright (C) 2001--2002  Petter Urkedal
//
//  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: link.h,v 1.2 2002/08/24 13:55:15 petter_urkedal Exp $


#ifndef MORE_GEN_LINK_H
#define MORE_GEN_LINK_H

#include <iterator>
#include <cstdlib>


namespace more {
namespace gen {

  using std::size_t;

  template<typename T> class link;

  /** \class linked link.h more/gen/link.h
   **
   ** A class for linking objects together. This allows you for
   ** instance to link objects on the stack into a (unordered)
   ** list. */
  struct linked
  {
      /** construct a link which is a member of gr. gr may be eigher a
       * linked object or a link<T>. */
      explicit linked(linked& gr)
      {
          m_next = &gr;
          m_prev = gr.m_prev;
          gr.m_prev = this;
          m_prev->m_next = this;
      }

      /** construct a node to be later linked in with the link member
       * function. */
      linked() { m_prev = m_next = this; }

      /** unlink and destruct. */
      ~linked() { unlink(); }

      /** link in a node which as constructed by the default constructor. */
      void link_to(linked& gr)
      {
          unlink();
          m_next = &gr;
          m_prev = gr.m_prev;
          gr.m_prev = this;
          m_prev->m_next = this;
      }

      /** join with another link. */
      void join(linked& x)
      {
          linked* tmp = m_next;
          m_next = x.m_next;
          m_next->m_prev = this;
          x.m_next = tmp;
          tmp->m_prev = &x;
      }

      /** Join ln so that the next node becomes ln. */
      void join_after(linked* ln)
      {
          ln->m_prev->m_next = m_next;
          m_next->m_prev = ln->m_prev;
          m_next = ln;
          ln->m_prev = this;
      }

      /** Join ln so that the previous node becomes ln. */
      void join_before(linked* ln)
      {
          ln->m_next->m_prev = m_prev;
          m_prev->m_next = ln->m_next;
          m_prev = ln;
          ln->m_next = this;
      }

      /** unlink. */
      void unlink()
      {
          m_next->m_prev = m_prev;
          m_prev->m_next = m_next;
          m_prev = m_next = this;
      }

      bool is_linked() { return m_prev != this; }

      /** swap the possitions of the linked objects, possibly between
       * different rings. */
      friend void swap(linked& x, linked& y) {
          linked* tmp;
          tmp = x.m_prev; x.m_prev = y.m_prev; y.m_prev = tmp;
          tmp = x.m_next; x.m_next = y.m_next; y.m_next = tmp;
//        std::swap(x.m_prev, y.m_prev);
//        std::swap(x.m_next, y.m_next);
      }

    private:
      linked* m_prev;
      linked* m_next;

      template<typename T> friend class link;
  };

  /** \class link link.h more/gen/link.h
   **
   ** A container of linked objects. */
  template<typename T = linked>
    struct link : public linked
    {
        typedef size_t size_type;
        typedef T value_type;
        typedef T& reference;
        typedef T const& const_reference;
        typedef T* pointer;
        typedef T const* const_pointer;

        /** Constructs an empty container. */
        link() {}

        class const_iterator;

        /** A bidirectional iterator over \c T. */
        struct iterator
            : std::iterator<std::bidirectional_iterator_tag, T>
        {
            iterator() {}
            iterator(iterator const& it) : ln(it.ln) {}
            iterator(linked* ln_) : ln(ln_) {}
            iterator& operator=(iterator const& it)
            {
                ln = it.ln; return *this;
            }

            bool operator==(iterator const& rhs) const { return ln == rhs.ln; }
            bool operator!=(iterator const& rhs) const { return ln != rhs.ln; }

            iterator& operator++() { ln = next(ln); return *this; }
            iterator& operator--() { ln = prev(ln); return *this; }
            iterator operator++(int)
            {
                iterator tmp = *this;
                ++*this;
                return tmp;
            }
            iterator operator--(int)
            {
                iterator tmp = *this;
                --*this;
                return tmp;
            }

            T& operator*() { return *static_cast<T*>(ln); }
            T* operator->() { return static_cast<T*>(ln); }

          private:
            linked* ln;
            friend class const_iterator;
        };

        /** A constant valued bidirectional iterator over \c T. */
        struct const_iterator
            : std::iterator<std::bidirectional_iterator_tag, const T>
        {
            const_iterator() {}
            const_iterator(const_iterator const& it) : ln(it.ln) {}
            const_iterator(iterator const& it) : ln(it.ln) {}
            const_iterator(const linked* ln_) : ln(ln_) {}
            const_iterator& operator=(const_iterator const& it)
            {
                ln = it.ln; return *this;
            }

            bool operator==(const_iterator const& rhs) const
            {
                return ln == rhs.ln;
            }
            bool operator!=(const_iterator const& rhs) const
            {
                return ln != rhs.ln;
            }

            const_iterator& operator++() { ln = next(ln); return *this; }
            const_iterator& operator--() { ln = prev(ln); return *this; }
            const_iterator operator++(int)
            {
                const_iterator tmp = *this;
                ++*this;
                return tmp;
            }
            const_iterator operator--(int)
            {
                const_iterator tmp = *this;
                --*this;
                return tmp;
            }

            T const& operator*() { return *static_cast<T const*>(ln); }
            T const* operator->() { return static_cast<T const*>(ln); }

          private:
            const linked* ln;
        };

        typedef std::reverse_iterator<iterator> reverse_iterator;
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

        /** Start of the range of linked objects. */
        iterator        begin() { return iterator(m_next); }
        /** Past the end of the range of linked objects. */
        iterator        end() { return iterator(this); }

        reverse_iterator rbegin() { return reverse_iterator(end()); }
        reverse_iterator rend() { return reverse_iterator(begin()); }

        const_iterator  begin() const { return const_iterator(m_next); }
        const_iterator  end() const { return const_iterator(this); }

        const_reverse_iterator rbegin() const
        {
            return const_reverse_iterator(end());
        }
        const_reverse_iterator rend() const
        {
            return const_reverse_iterator(begin());
        }

        bool            empty() const { return m_next == this; }

        /** Join ln so that it becomes the first node. */
        void            join_front(linked* ln) { join_after(ln); }
        /** Join ln so that it becomes the last node. */
        void            join_back(linked* ln) { join_before(ln); }

        reference       front() { return static_cast<reference>(*m_next); }
        reference       back()  { return static_cast<reference>(*m_prev); }

        const_reference front() const
        {
            return static_cast<const_reference>(*m_next);
        }
        const_reference back()  const
        {
            return static_cast<const_reference>(*m_prev);
        }

      private:
        // Friendship with linked is not inherited to iterator.
        static linked* next(linked* ln) { return ln->m_next; }
        static linked* prev(linked* ln) { return ln->m_prev; }
        static linked const* next(linked const* ln) { return ln->m_next; }
        static linked const* prev(linked const* ln) { return ln->m_prev; }

        friend class iterator;
        friend class const_iterator;
        friend class linked;
    };

}} // more::gen

#endif

---