PartialOrder.hh

Go to the documentation of this file.

#ifndef __DIADES__UTILS__PARTIALORDER_HH_
#define __DIADES__UTILS__PARTIALORDER_HH_

#include <set>
#include <diades/graph/Graph.hh>
#include <diades/graph/NodeMap.hh>

namespace Diades
{
  namespace Utils
  {
        using std::set;
        using Diades::Graph::Graph;
        using Diades::Graph::Node;
        using Diades::Graph::NodeMap;
        
        
        
        
        
        template<typename Object,
                         typename Order,
                         typename Equal>
        class PartialOrder
        {
        private:
          Graph _order;
          NodeMap<Object> _map;
          set<Node> _min;
          set<Node> _max;

        public:
          
          class Iterator
          {
          private:
                const PartialOrder & _order;
                set<Node>::const_iterator _it;

                
          public:
                
                Iterator(const PartialOrder & order, set<Node>::const_iterator it):_order(order),_it(it){}

                const Object & operator *() const;

                Iterator & operator ++()
                {
                  ++_it;
                  return *this;
                }


                Iterator  operator ++(int)
                {
                  set<Node>::const_iterator _it2= _it;
                  ++_it;
                  return Iterator(_order,_it);
                }

                
                const Object & operator ->(void) const;
        

                bool operator ==(const Iterator & it) const
                {
                  return ((&_order) == (&it._order)) && (_it == it._it);
                }               

                bool operator !=(const Iterator & it) const
                {
                  return !(*this == it);
                }
          };

          
        public:
          
          PartialOrder():_order(),_map()
          {
                _map.init(_order);
          }

          ~PartialOrder()
          {
          }

          PartialOrder(const PartialOrder & order):_order(order._order){}

          
          bool empty() const
          {
                return _order.empty();
          }


          void insert(const Object & object)
          {
                // BRUTE FORCE
                // @todo change that
                Node newNode = _order.newNode();
                _map[newNode]  = object;
                bool isMinMax = true;
                for (Diades::Graph::NodeIterator nodeIt = _order.nodeBegin();
                         nodeIt != _order.nodeEnd();
                         ++nodeIt)
                  {
                        if(*nodeIt != newNode)
                          {
                                if(Equal(getObject(*nodeIt),object))
                                  {
                                        _order.deleteNode(newNode);
                                        return;
                                  }
                                else
                                  {
                                        if(Order(getObject(*nodeIt),object))
                                          {
                                                isMinMax = false;
                                                _order.newEdge(*nodeIt,newNode);
                                                set<Node>::iterator maxIt = _max.find(*nodeIt);
                                                if(maxIt != _max.end())
                                                  {
                                                        _max.erase(maxIt);
                                                        _max.insert(newNode);
                                                  }
                                          }
                                        else
                                          {
                                                if(Order(object,getObject(*nodeIt)))
                                                  {
                                                        isMinMax = false;
                                                        _order.newEdge(getObject(*nodeIt),object);
                                                        set<Node>::iterator minIt = _min.find(*nodeIt);
                                                        if(minIt != _min.end())
                                                          {
                                                                _min.erase(minIt);
                                                                _min.insert(newNode);
                                                          }
                                                  }
                                          }
                                  }
                          }
                  }
                if(isMinMax)
                  {
                        _min.insert(newNode);
                        _max.insert(newNode);
                  }     
          }


          Iterator minimalBegin() const
          {
                return Iterator(*this,_min.begin());
          }

          Iterator minimalEnd() const
          {
                return Iterator(*this,_min.end());
          }
          

          Iterator maximalBegin() const
          {
                return Iterator(*this,_max.begin());
          }

          Iterator maximalEnd() const
          {
                return Iterator(*this,_max.end());
          }


          const Object & getObject(Node node) const
          {
                return _map[node];
          }


          void erase(const Object & object)
          {
                // BRUTE FORCE
                // @todo change that
                for (Diades::Graph::NodeIterator nodeIt = _order.nodeBegin();
                         nodeIt != _order.nodeEnd();
                         ++nodeIt)
                  {
                        if(Equal(getObject(*nodeIt),object))
                          {
                                _order.deleteNode(*nodeIt);
                                return;
                          }
                  }

          }


          void clear()
          {
                _min.clear();
                _max.clear();
                _order.clear();
                _map.init(_order);
          }
          
        };


        template<typename Object, typename Order, typename Equal>
        const Object & PartialOrder<Object,Order,Equal>::Iterator::operator *() const
        {
          return _order.getObject(*_it);
        }

        template<typename Object,typename Order, typename Equal>
        const Object & PartialOrder<Object,Order,Equal>::Iterator::operator ->(void) const
        {
          return _order.getObject(*_it);
        }
        
  }
  
}






#endif