---

more/gen/unifying_partial_ordering.h

Go to the documentation of this file.

//  more/unifying_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: unifying_partial_ordering.h,v 1.2 2002/08/24 13:50:58 petter_urkedal Exp $


#ifndef MORE_GEN_UNIFYING_PARTIAL_ORDERING_H
#define MORE_GEN_UNIFYING_PARTIAL_ORDERING_H

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


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

  //
  // -- unifying_partial_ordering_base --
  //

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

      struct node_base : noncopyable
      {
          node_base(unifying_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; }

          link<element_base> users;
          unifying_partial_ordering_base const* context; // need algo_serial

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

      typedef link<element_base>::iterator user_iterator;

      struct element_base : linked
      {
        protected:
          element_base()
              : ptr(0) {}
          element_base(node_base* p)
              : linked(p->users), ptr(p) {}
          element_base(element_base const& eb)
              : linked(eb.ptr->users), ptr(eb.ptr) {}
          element_base& operator=(element_base const& eb) {
              unlink();
              ptr = eb.ptr;
              link_to(ptr->users);
              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(); }
          //@}
        protected:
          mutable node_base* ptr;
          friend class unifying_partial_ordering_base;
      };

      unifying_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 ~unifying_partial_ordering_base() {}

      void insert_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_preceq_impl(node_base* x, node_base* y);
      void constrain_eq_impl(std::set<node_base*> const& S,
                          node_base* new_node);
      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*, OutputIterator);
      template<typename OutputIterator>
        static void
        copy_infimums_impl(node_base*, OutputIterator);

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

  template<typename T>
    struct unify_if_equal
        : std::binary_function< T&, T, bool >
    {
        bool operator()(T& x, T const& y) {
            if (x == y)
                return true;
            else
                return false;
        }
    };

  template<typename T>
    struct unify_none
        : std::binary_function< T&, T, bool >
    {
        bool operator()(T& x, T const& y)
        {
            return false;
        }
    };

  template<typename T>
    struct unify_to_first
        : std::binary_function< T&, T, bool >
    {
        bool operator()(T& x, T const& y)
        {
            return true;
        }
    };



  //
  //  -- unifying_partial_ordering --
  //

  /** \class unifying_partial_ordering unifying_partial_ordering.h \
   **        more/gen/unifying_partial_ordering.h
   **
   ** A container which provides a partial ordering of its elements. */
  template<typename T, typename Unify = unify_if_equal<T> >
    struct unifying_partial_ordering : private unifying_partial_ordering_base
    {
        typedef T value_type;
        typedef Unify unify_function;

      private:
        struct node : node_base
        {
            explicit node(unifying_partial_ordering_base const* context_)
                : node_base(context_) {}
            node(unifying_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 unifying_partial_ordering container;
            typedef trivial_iterator_tag iterator_category;
            typedef void difference_type;
            typedef unifying_partial_ordering::infimum_iterator infimum_iterator;
            typedef unifying_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; }

            infimum_iterator infimums_begin();
            infimum_iterator infimums_end();

            supremum_iterator supremums_begin();
            supremum_iterator supremums_end();

          private:
            friend class unifying_partial_ordering_base;
            friend class unifying_partial_ordering;
            friend class const_element;
        };

        /** an element of the ordering with constant value */
        struct const_element : element_base
        {
            typedef unifying_partial_ordering container;
            typedef trivial_iterator_tag iterator_category;
            typedef void difference_type;
            typedef unifying_partial_ordering::const_infimum_iterator
                    infimum_iterator;
            typedef unifying_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 unifying_partial_ordering_base;
            friend class unifying_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; }
          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; }
          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. */
        unifying_partial_ordering()
            : unifying_partial_ordering_base(MORE_NEW(node, this),
                                    MORE_NEW(node, this)) {}

        /** construct a partial ordering with the given unify function
         * object. */
        explicit unifying_partial_ordering(unify_function const& fn)
            : unifying_partial_ordering_base(MORE_NEW(node, this),
                                    MORE_NEW(node, this)),
              unify(fn) {}

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

        /** assign a deep copy. */
        unifying_partial_ordering&
        operator=(unifying_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==(unifying_partial_ordering const& rhs) const {
//          clear_cache();
//          return compare_caching() == 0;
//      }
//      bool operator!=(unifying_partial_ordering const& rhs) const {
//          return !(*this == rhs);
//      }

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

        /** 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>preceq(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_preceq(element e0, element e1);

        /** imposes the constraint \f$e_0=e_1\f$. Equivalent to
         * <tt>constrain_preceq(e0, e1), constrain_preceq(e1, e0)</tt>. */
        bool constrain_eq(element e0, element e1);
      private:
        bool constrain_eq(std::set<node_base*> const&);
        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::gen::unifying_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);
            }
        }

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

        template<typename OutputIterator>
          static void copy_range(element, element, OutputIterator);
        template<typename OutputIterator>
          static void copy_range(const_element, const_element,
                                 OutputIterator);
        template<typename OutputIterator>
          static void copy_supremums(element, OutputIterator);
        template<typename OutputIterator>
          static void copy_supremums(const_element, OutputIterator);
        template<typename OutputIterator>
          static void copy_infimums(element, OutputIterator);
        template<typename OutputIterator>
          static void copy_infimums(const_element, OutputIterator);
//      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()));
        }

      private:
        unify_function unify;
    };

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

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

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

  template<typename T, typename Unify>
    inline typename
    unifying_partial_ordering<T, Unify>::const_element::infimum_iterator
    unifying_partial_ordering<T, Unify>::const_element::infimums_begin()
    {
        return ptr->m_infs.begin();
    }
  template<typename T, typename Unify>
    inline typename
    unifying_partial_ordering<T, Unify>::const_element::infimum_iterator
    unifying_partial_ordering<T, Unify>::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_upo::unifying_partial_ordering;
  using bits_upo::unify_to_first;
  using bits_upo::unify_if_equal;
  using bits_upo::unify_none;
///\endif

  // The rest is Koenig lookup.
}} // more::gen

#include <more/bits/unifying_partial_ordering.tcc>

#endif

---