---

more/gen/partial_ordering.h

Go to the documentation of this file.

//  more/partial_ordering.h -- container representing a partial ordering
//  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: partial_ordering.h,v 1.2 2002/08/24 13:50:58 petter_urkedal Exp $


#ifndef MORE_GEN_PARTIAL_ORDERING_H
#define MORE_GEN_PARTIAL_ORDERING_H

//#define MORE_CHECK_ALLOCATIONS 1
#include <more/diag/debug.h>
#include <more/gen/utility.h>
#include <more/gen/iterator.h>
#include <set>


namespace more {
namespace gen {
///\if bits
namespace bits_po {
///\endif

  //
  // -- partial_ordering_base --
  //

  /** \class partial_ordering_base partial_ordering.h \
   **        more/gen/partial_ordering.h
   **
   ** Helper class. */
  struct partial_ordering_base : noncopyable/*XXX todo*/
  {
    private:
      typedef unsigned int algo_serial_type;
    public:
      struct element_base;

      struct node_base : noncopyable
      {
          node_base(partial_ordering_base const* context_)
              : algo_serial(0), context(context_) {}
          std::set<node_base*> m_sups;
          std::set<node_base*> m_infs;
          algo_serial_type mutable algo_serial;

          union algo_cache_type
          {
              bool as_bool;
              int as_int;
              void* as_ptr;
          } algo_cache;

          algo_cache_type& cache() { return algo_cache; }
          bool is_cached() { return algo_serial == context->algo_serial; }
          void set_cached() { algo_serial = context->algo_serial; }

          partial_ordering_base const* context; // need algo_serial

          typedef std::set<node_base*>::iterator sup_iterator;
          typedef std::set<node_base*>::iterator inf_iterator;
      };

      struct element_base
      {
        protected:
          element_base()
              : ptr(0) {}
          element_base(node_base* p)
              : ptr(p) {}
          element_base(element_base const& eb)
              : ptr(eb.ptr) {}
          element_base& operator=(element_base const& eb) {
              ptr = eb.ptr;
              return *this;
          }
        public:
          bool operator==(element_base const& rhs) const {
              return ptr == rhs.ptr;
          }
          bool operator!=(element_base const& rhs) const {
              return ptr != rhs.ptr;
          }
          bool operator<(element_base const& rhs) const {
              return ptr < rhs.ptr;
          }
          //@{
          /** not stabilized yet */
          void clear_cache() const { ptr->context->clear_cache(); }
          void set_cached() const { ptr->set_cached(); }
          bool is_cached() const { return ptr->is_cached(); }
          node_base::algo_cache_type& cache() const { return ptr->cache(); }
          friend void check_range(element_base const& eb0,
                                  element_base const& eb1) {
              if (eb0.ptr->context != eb1.ptr->context)
                  throw std::logic_error("more::partial_ordering::element: "
                                         "Elements do not form a valid range.");
          }
          //@}
        protected:
          mutable node_base* ptr;
          friend class partial_ordering_base;
      };

      partial_ordering_base(node_base* inf, node_base* sup)
          : m_min(inf), m_max(sup), algo_serial(0)
      {
          inf->m_sups.insert(sup);
          sup->m_infs.insert(inf);
      }

      virtual ~partial_ordering_base() {}

      void insert_impl(node_base*);
      void unlink_impl(node_base*);
      static bool preceq_impl(node_base*, node_base*);

    private:
      static bool preceq_impl_x(node_base*, node_base*);

    public:
      static bool eq_impl(node_base* x, node_base* y) { return x == y; }
      void constrain_prec_impl(node_base* x, node_base* y);
      template<typename OutputIterator>
        static bool
        copy_range_impl(node_base* x, node_base* y, OutputIterator it)
        {
            assert(x->context == y->context);
            x->context->clear_cache();
            return copy_range_impl_x(x, y, it);
        }
    private:
      template<typename OutputIterator>
        static bool
        copy_range_impl_x(node_base*, node_base*, OutputIterator);
    public:
      template<typename OutputIterator>
        static void
        copy_supremums_impl(node_base* x, OutputIterator it_out)
        {
            assert(x != 0);
            std::copy(x->m_sups.begin(), x->m_sups.end(), it_out);
        }

      template<typename OutputIterator>
        static void
        copy_infimums_impl(node_base* x, OutputIterator it_out)
        {
            assert(x != 0);
            std::copy(x->m_infs.begin(), x->m_infs.end(), it_out);
        }

    protected:
      void clear_cache() const;
      void check_integrity();
      void check_integrity_from_bottom(node_base*);
      void check_integrity_from_top(node_base*);
      void dump_structure();

      // private:

      node_base* m_min;
      node_base* m_max;
      algo_serial_type mutable algo_serial;
  };


  //
  //  -- partial_ordering --
  //

  /** \class partial_ordering partial_ordering.h more/gen/partial_ordering.h
   **
   ** A container which provides a partially ordering of its elements. */
  template<typename T>
    struct partial_ordering : private partial_ordering_base
    {
        typedef T value_type;
        typedef typename partial_ordering_base::node_base node_base;

      private:
        struct node : node_base {
            explicit node(partial_ordering_base const* context_)
                : node_base(context_) {}
            node(partial_ordering_base const* context_, T const& v)
                : node_base(context_), value(v) {}
            ~node() {}
            T value;
        };

      public:
        struct const_element;
        struct infimum_iterator;
        struct const_infimum_iterator;

        /** an element of the ordering */
        struct element : element_base
        {
            typedef partial_ordering container;
            typedef trivial_iterator_tag iterator_category;
            typedef void difference_type;
            typedef partial_ordering::infimum_iterator infimum_iterator;
            typedef partial_ordering::infimum_iterator supremum_iterator;
            element() {}
            element(node_base* p)
                : element_base(p) {}
            element(element const& e)
                : element_base(e.ptr) {}
            element& operator=(element const& e) {
                element_base::operator=(e);
                return *this;
            }
            typedef T value_type;
            typedef T& reference;
            typedef T* pointer;
            reference operator*() { return static_cast<node*>(ptr)->value; }
            pointer operator->() { return &static_cast<node*>(ptr)->value; }
            T const& operator*() const {
                return static_cast<node const*>(ptr)->value;
            }
            T const* operator->() const {
                return &(**this);
            }
            infimum_iterator infimums_begin();
            infimum_iterator infimums_end();
            supremum_iterator supremums_begin();
            supremum_iterator supremums_end();
          private:
            friend class partial_ordering_base;
            friend class partial_ordering;
            friend class const_element;
        };

        /** an element of the ordering with constant value */
        struct const_element : element_base
        {
            typedef partial_ordering container;
            typedef trivial_iterator_tag iterator_category;
            typedef void difference_type;
            typedef partial_ordering::const_infimum_iterator infimum_iterator;
            typedef partial_ordering::const_infimum_iterator supremum_iterator;
            const_element() {}
            const_element(node_base* p)
                : element_base(p) {}
            const_element(element const& e)
                : element_base(e.ptr) {}
            const_element(const_element const& e)
                : element_base(e.ptr) {}
            const_element& operator=(const_element const& e) {
                element_base::operator=(e);
                return *this;
            }
            typedef T const value_type;
            typedef T const& reference;
            typedef T const* pointer;
            reference operator*() const {
                return static_cast<node const*>(ptr)->value;
            }
            pointer operator->() const {
                return &static_cast<node const*>(ptr)->value;
            }
            infimum_iterator infimums_begin();
            infimum_iterator infimums_end();
            supremum_iterator supremums_begin();
            supremum_iterator supremums_end();
          private:
            friend class partial_ordering_base;
            friend class partial_ordering;
        };

      private:
        // a proxy used in infimum_iterator to emulate const_element
        // needed for operator->, and may accelerate operator*.
        struct const_proxy0
        {
            const_proxy0() {}
            explicit const_proxy0(node_base::inf_iterator it) : it_sub(it) {}
            typedef T const value_type;
            typedef T const& reference;
            typedef T const* pointer;
            reference operator*() const {
                return static_cast<node const*>(*it_sub)->value;
            }
            pointer operator->() const { return &(operator*()); }
            operator const_element() { return *it_sub; }
            bool operator==(const_element const& rhs) const {
                return const_element(*it_sub) == rhs;
            }
            bool operator!=(const_element const& rhs) const {
                return const_element(*it_sub) != rhs;
            }
            friend bool
            operator==(const_element const& x, const_proxy0 const& y) {
                return y == x;
            }
            friend bool
            operator!=(const_element const& x, const_proxy0 const& y) {
                return y != x;
            }

          protected:
            node_base::inf_iterator it_sub;
        };

        struct proxy0
        {
            proxy0() {}
            explicit proxy0(node_base::inf_iterator it) : it_sub(it) {}
            typedef T value_type;
            typedef T& reference;
            typedef T* pointer;
            reference operator*() const {
                return static_cast<node*>(*it_sub)->value;
            }
            pointer operator->() const { return &(operator*()); }
            operator element() { return *it_sub; }
            bool operator==(element const& rhs) const {
                return const_element(*it_sub) == rhs;
            }
            bool operator!=(element const& rhs) const {
                return const_element(*it_sub) != rhs;
            }
            friend bool
            operator==(element const& x, proxy0 const& y) {
                return y == x;
            }
            friend bool
            operator!=(element const& x, proxy0 const& y) {
                return y != x;
            }

          protected:
            node_base::inf_iterator it_sub;
        };

      public:
        /** A bidirectional iterator used by infimum_range. The \c
         * operator* (and operator->) returns a proxy which must be
         * cast if passed to a templated argument. */
        struct infimum_iterator
            : private proxy0
        {
            typedef std::bidirectional_iterator_tag iterator_category;
            typedef element value_type;
            typedef value_type& reference;
            typedef value_type* pointer;
            typedef std::ptrdiff_t difference_type;
            infimum_iterator() {}
            infimum_iterator(node_base::inf_iterator it) : proxy0(it) {}

            proxy0& operator*() { return *this; }
            proxy0* operator->() { return this; }

            infimum_iterator& operator++() { ++it_sub; return *this; }
            infimum_iterator& operator--() { --it_sub; return *this; }
            infimum_iterator operator++(int) {
                infimum_iterator tmp = *this;
                ++*this;
                return tmp;
            }
            infimum_iterator operator--(int) {
                infimum_iterator tmp = *this;
                --*this;
                return *this;
            }
            bool operator==(infimum_iterator const& rhs) const {
                return it_sub == rhs.it_sub;
            }
            bool operator!=(infimum_iterator const& rhs) const {
                return it_sub != rhs.it_sub;
            }
        };

        /** A bidirectional iterator used by infimum_range. See \c
         * infimum_iterator. */
        struct const_infimum_iterator
            : private const_proxy0
        {
            typedef std::bidirectional_iterator_tag iterator_category;
            typedef const_element value_type;
            typedef value_type& reference;
            typedef value_type* pointer;
            typedef std::ptrdiff_t difference_type;

            const_infimum_iterator() {}
            const_infimum_iterator(node_base::inf_iterator it)
                : const_proxy0(it) {}
            const_infimum_iterator(infimum_iterator const& it)
                : const_proxy0(it.it_sub) {}

            const_proxy0& operator*() { return *this; }
            const_proxy0* operator->() { return this; }

            const_infimum_iterator& operator++() { ++it_sub; return *this; }
            const_infimum_iterator& operator--() { --it_sub; return *this; }
            const_infimum_iterator operator++(int) {
                const_infimum_iterator tmp = *this;
                ++*this;
                return tmp;
            }
            const_infimum_iterator operator--(int) {
                const_infimum_iterator tmp = *this;
                --*this;
                return *this;
            }
            bool operator==(const_infimum_iterator const& rhs) const {
                return it_sub == rhs.it_sub;
            }
            bool operator!=(const_infimum_iterator const& rhs) const {
                return it_sub != rhs.it_sub;
            }
        };

        /** A bidirectional iterator used by supremum_range. */
        typedef infimum_iterator supremum_iterator;

        /** A bidirectional iterator used by supremum_range. */
        typedef const_infimum_iterator const_supremum_iterator;

        /** construct a partial ordering with only infimun and
         * supremum elements. */
        partial_ordering()
            : partial_ordering_base(MORE_NEW(node, this),
                                    MORE_NEW(node, this)) {}

        /** contruct a deep copy. */
        partial_ordering(partial_ordering const& po)
            : partial_ordering_base(MORE_NEW(node, this),
                                    MORE_NEW(node, this))
        {
            insert(po.min(), po.max());
            *min() = *po.min();
            *max() = *po.max();
        }

        /** assign a deep copy. */
        partial_ordering&
        operator=(partial_ordering const& po)
        {
            clear();
            insert(po.min(), po.max());
            *min() = *po.min();
            *max() = *po.max();
            return *this;
        }

        /** compare container structure and valued using
         * value_type::operator==. */
//      bool operator==(partial_ordering const& rhs) const {
//          clear_cache();
//          return compare_caching() == 0;
//      }
//      bool operator!=(partial_ordering const& rhs) const {
//          return !(*this == rhs);
//      }

        /** destructs the partial ordering. All elements created from
         * the ordering will be invalidated. */
        virtual ~partial_ordering()
        {
            clear();
            MORE_DELETE(node, static_cast<node*>(m_min));
            MORE_DELETE(node, static_cast<node*>(m_max));
        }

        /** Not for production code. */
        void debug_dump() { dump_structure(); }

        /** clear a partial ordering. All elements of the ordering are
         * invalidated. */
        void clear();

        /** returns true iff \f$e_0\sqsubseteq e_1\f$ is implied by
         * the given constraints. */
        static bool preceq(element e0, element e1)
        {
            return preceq_impl(e0.ptr, e1.ptr);
        }

        /** returns true iff \f$e_0=e_1\f$ is implied by the given
         * contraits. Equivalent to <tt>prec(e0, e1) && preceq(e1,
         * e0)</tt> */
        static bool eq(element e0, element e1)
        {
            return eq_impl(e0.ptr, e1.ptr);
        }

        /** imposes the constraint \f$e_0\sqsubseteq e_1\f$. */
        bool constrain_prec(element e0, element e1)
        {
            if (prec(e0, e1))
                return true;
            else if (preceq(e1, e0))
                return false;
            else {
                constrain_prec_impl(e0.ptr, e1.ptr);
                return true;
            }
        }

      private:
        static node_base* copy_caching(node_base*, node_base*, node_base*);
//      static int compare_caching(node_base*, node_base*, node_base*);

      public:
        /** create a new element with the given value. */
        element insert(T const& value)
        {
            node* ptr = MORE_NEW(node, this, value);
            insert_impl(ptr);
            return ptr;
        }

        /** create a new default constructed element. */
        element insert()
        {
            node* ptr = MORE_NEW(node, this);
            insert_impl(ptr);
            return ptr;
        }

        /** insert a range of values. Equivalent to <tt>insert(e_min,
         * e_max, min(), max())</tt>. */
        void insert(const_element e_min, const_element e_max)
        {
            insert(e_min, e_max, min(), max());
        }

        /** insert nodes in (e_min, e_max) into (e_min_dest,
         * e_max_dest). */
        void insert(const_element e_min, const_element e_max,
                    element e_min_dest, element e_max_dest)
        {
            if (e_min == e_max) return;
            if (e_min_dest == e_max_dest)
                throw std::logic_error("more::partial_ordering::insert: "
                                       "Invalid destination range.");
            e_min.clear_cache();
            for (node_base::sup_iterator it = e_min.ptr->m_sups.begin();
                 it != e_min.ptr->m_sups.end(); ++it) {
                node_base* node_new
                    = copy_caching(*it, e_max.ptr, e_max_dest.ptr);
                e_min_dest.ptr->m_sups.insert(node_new);
                node_new->m_infs.insert(e_min_dest.ptr);
            }
        }

        /** erase an element. Unimplemented, does nothing. */
        void erase(element e)
        {
            unlink_impl(e.ptr);
            delete e.ptr;
        }

        /** returns the element which is less than any other
         * element. It is dereferenceable. */
        const_element min() const { return m_min; }

        /** returns the element which is greater than any other
         * element. It is derferenceable. */
        const_element max() const { return m_max; }

        /** returns the element which is less than any other element.
         * It is dereferenceable with an lvalue as the result. */
        element min() { return m_min; }

        /** returns the element which is greater than any other element.
         * It is dereferenceable with an lvalue as the result. */
        element max() { return m_max; }

        //@{
        /** copies to \c it_out the set of elements
         * \f$\{z : x\sqsubseteq z \sqsubseteq y \wedge z \neq y\}\f$. */
        template<typename OutputIterator>
          static void
          copy_range(element e0, element e1, OutputIterator it_out)
          {
              partial_ordering<T>::copy_range_impl(e0.ptr, e1.ptr, it_out);
          }
        template<typename OutputIterator>
          static void
          copy_range(const_element e0, const_element e1,
                     OutputIterator it_out)
          {
              if (0) { *it_out = e0; } // constness check for iterator
              partial_ordering<T>::copy_range_impl(e0.ptr, e1.ptr, it_out);
          }
        //@}

        //@{
        /** copies to \c it_out the set of elements \f$\{z : x\sqsubseteq z
         * \wedge (x\sqsubseteq y\sqsubseteq z\Rightarrow x=y\vee
         * x=z)\}\f$. In contrast to full orderings, there may be more than
         * one element fulfilling this condition. */
        template<typename OutputIterator>
          static void
          copy_supremums(element e, OutputIterator it_out)
          {
              partial_ordering<T>::copy_supremums_impl(e.ptr, it_out);
          }

        template<typename OutputIterator>
          static void
          copy_supremums(const_element e, OutputIterator it_out)
          {
              if (0) { *it_out = e; } // constness check for iterator
              partial_ordering<T>::copy_supremums_impl(e.ptr, it_out);
          }
        //@}
        //@{
        /** copyies to \c it_out the set of elements \f$\{z : z\sqsubseteq
         * x\wedge (z\sqsubseteq y\sqsubseteq x\Rightarrow y=x\vee
         * y=z)\}\f$. */
        template<typename OutputIterator>
          static void
          copy_infimums(element e, OutputIterator it_out)
          {
              partial_ordering<T>::copy_infimums_impl(e.ptr, it_out);
          }
        template<typename OutputIterator>
          static void
          copy_infimums(const_element e, OutputIterator it_out)
          {
              if (0) { *it_out = e; } // constness check for iterator
              partial_ordering<T>::copy_infimums_impl(e.ptr, it_out);
          }
        //@}
//      template<typename PrecEqPredicate, typename OutputIterator>
//        static void copy_infimums(value_type const&, PrecEqPredicate,
//                                  OutputIterator);

        /** Returns a range of the infimums of \c x. Note that the
         * value_type of the iterator is \c const_element, so a double
         * dereference is needed to obtain a \c value_type of this
         * container. */
        static std::pair<const_infimum_iterator, const_infimum_iterator>
        infimum_range(const_element x)
        {
            return std::make_pair(const_infimum_iterator(x.ptr->m_infs.begin()),
                                  const_infimum_iterator(x.ptr->m_infs.end()));
        }

        /** Returns a range of the supremums of \c x. See \c
         * infimum_range(const_element)  const. */
        static std::pair<const_supremum_iterator, const_supremum_iterator>
        supremum_range(const_element x)
        {
            return std::make_pair(const_supremum_iterator(x.ptr->m_sups.begin()),
                                  const_supremum_iterator(x.ptr->m_sups.end()));
        }

        /** Returns a range of the infimums of \c x. See \c
         * infimum_range(const_element) const. */
        static std::pair<infimum_iterator, infimum_iterator>
        infimum_range(element x)
        {
            return std::make_pair(infimum_iterator(x.ptr->m_infs.begin()),
                                  infimum_iterator(x.ptr->m_infs.end()));
        }

        /** Returns a range of the supremums of \c x. See \c
         * infimum_range(const_element) const. */
        static std::pair<supremum_iterator, supremum_iterator>
        supremum_range(element x)
        {
            return std::make_pair(supremum_iterator(x.ptr->m_sups.begin()),
                                  supremum_iterator(x.ptr->m_sups.end()));
        }
    };

  template<typename T>
    inline typename partial_ordering<T>::element::supremum_iterator
    partial_ordering<T>::element::supremums_begin()
    {
        return ptr->m_sups.begin();
    }
  template<typename T>
    inline typename partial_ordering<T>::element::supremum_iterator
    partial_ordering<T>::element::supremums_end()
    {
        return ptr->m_sups.end();
    }

  template<typename T>
    inline typename partial_ordering<T>::element::infimum_iterator
    partial_ordering<T>::element::infimums_begin()
    {
        return ptr->m_infs.begin();
    }
  template<typename T>
    inline typename partial_ordering<T>::element::infimum_iterator
    partial_ordering<T>::element::infimums_end()
    {
        return ptr->m_infs.end();
    }

  template<typename T>
    inline typename partial_ordering<T>::const_element::supremum_iterator
    partial_ordering<T>::const_element::supremums_begin()
    {
        return ptr->m_sups.begin();
    }
  template<typename T>
    inline typename partial_ordering<T>::const_element::supremum_iterator
    partial_ordering<T>::const_element::supremums_end()
    {
        return ptr->m_sups.end();
    }

  template<typename T>
    inline typename partial_ordering<T>::const_element::infimum_iterator
    partial_ordering<T>::const_element::infimums_begin()
    {
        return ptr->m_infs.begin();
    }
  template<typename T>
    inline typename partial_ordering<T>::const_element::infimum_iterator
    partial_ordering<T>::const_element::infimums_end()
    {
        return ptr->m_infs.end();
    }

  template<typename Element>
    std::pair< typename Element::supremum_iterator,
               typename Element::supremum_iterator >
    supremums(Element e)
    {
        return std::make_pair(e.supremums_begin(),
                              e.supremums_end());
    }
  template<typename Element>
    std::pair< typename Element::infimum_iterator,
               typename Element::infimum_iterator >
    infimums(Element e)
    {
        return std::make_pair(e.infimums_begin(),
                              e.infimums_end());
    }



  /** returns true if \f$e_0\sqsubseteq e_1\f$. */
  template<typename Element>
    inline bool preceq(Element e0, Element e1)
    {
        typedef typename Element::container container;
        return container::preceq(e0, e1);
    }

  /** returns true if \f$e_0\sqsubset e_1\f$. */
  template<typename Element>
    inline bool prec(Element e0, Element e1)
    {
        return e0 != e1 && preceq(e0, e1);
    }

  /** returns true if \f$e_0\sqsupseteq e_1\f$. */
  template<typename Element>
    inline bool succeq(Element e0, Element e1) { return preceq(e1, e0); }

  /** returns true if \f$e_0\sqsupset e_1\f$. */
  template<typename Element>
    inline bool succ(Element e0, Element e1) { return prec(e1, e0); }

  ///\if bits
}
  using bits_po::partial_ordering;
  ///\endif
  // The rest is Koenig lookup.

}} // more::gen

#include <more/bits/partial_ordering.tcc>

#endif

---