Set.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph 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.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/

/*
     Aleph implementation of set C++ standard container
*/

# ifndef AH_SET_H
# define AH_SET_H

# include <ahPair.H>
# include <ah_stdc++_utils.H>
# include <tpl_treapRk.H>

namespace Aleph
{

    template <class T, 
           class Compare = Aleph::less<T>,
           template <class, class> class Tree = Treap_Rk
           >
class set
{
private:

  Tree<T, Compare> tree;

  typedef typename Tree<T, Compare>::Node Node;

public:

  typedef T value_type;

  typedef typename set::value_type * pointer;

  typedef typename set::value_type & reference;

  typedef const typename set::value_type & const_reference;

  typedef size_t size_type;

  typedef T key_type;

  class iterator
  {
  private:

    friend class set<T, Compare, Tree>;
    
    typedef typename Tree<T, Compare>::Iterator Iterator;
    
    Tree<T, Compare> * tree;
    Iterator  itor;
    bool underflow;
    bool overflow;

    iterator (Tree<T, Compare> & _tree, Node * node) 
      : tree (&_tree), itor (_tree, node), underflow (false), overflow (false)
    {
      /* empty */
    }

    void init_flags ()
    {
      if (tree->size () == 0)
     underflow = overflow = true;
      else
     underflow = overflow = false;
    }

    iterator (Tree<T, Compare> &_tree) : tree (&_tree), itor (_tree)
    {
      init_flags ();
    }

    void goto_begin ()
    {
      itor.reset_first ();
      init_flags ();
    }

    void goto_last ()
    {
      itor.reset_last ();
      init_flags ();
    }

    void goto_end ()
    {
      itor.reset_last ();
      init_flags ();
      itor.next ();
      overflow = true;
    }

    void forward ()
    {
      if (underflow)
     {
       goto_begin ();
       return;
     }
      
      itor.next ();

      if (not itor.has_current () )
     overflow = true;
    }

    void backward ()
    {
      if (overflow)
     {
       goto_last ();
       return;
     }
      
      itor.prev ();

      if (not itor.has_current () )
     underflow = true;
    }

  public:

    typedef typename set<T>::value_type   value_type;

    typedef typename set<T>::size_type       difference_type;

    typedef typename set<T>::value_type *    pointer;

    typedef typename set<T>::reference       reference;

    typedef const typename set<T>::reference const_reference;

    iterator () : tree (NULL), underflow (true), overflow (true) 
    {
      /* empty */ 
    }
    
    T & operator * ()
    {
      return KEY (itor.get_current () );
    }

    T * operator -> ()
    {
      return & KEY (itor.get_current () );
    }

    T & operator ++ ()
    {
      forward ();

      return KEY (itor.get_current() );
    }

    T & operator ++ (int)
    {
      T & return_value = KEY (itor.get_current () );

      forward ();

      return return_value;
    }

    T & operator -- ()
    {
      backward ();

      return KEY (itor.get_current () );
    }

    T & operator -- (int)
    {
      T& return_value = KEY (itor.get_current () );
      backward ();

      return return_value;
    }
    
    T & operator += (const size_type & n)
    {
      itor.reset_to_pos (itor.get_current_position () + n);

      return itor.get_current ()->get_key();
    } 

    T & operator -= (const size_type & n)
    {
      itor.reset_to_pos (itor.get_current_position () - n);
      
      return itor.get_current ()->get_key ();
    } 

    bool operator == (const iterator & _itor) const
    {
      return itor == _itor.itor;
    }

    bool operator != (const iterator & _itor) const
    {
      return not (itor == _itor.itor);
    }

    bool verify (const set & _set) const
    {
      return itor.verify ( (Tree<T, Compare>*) &_set.tree);
    }

    bool verify (const iterator & it) const
    {
      return itor.verify (it.itor);
    }
  };

  set () { /* empty */  }

  set (const set & c) 
  {
    tree.getRoot () = copyRec (c.tree.getRoot () );
  }

      template <typename Itor> 
  set (Itor beg, const Itor & end)
  {
    Aleph::verify_iterators (beg, end);

    while (beg != end)
      tree.insert (new Node (beg++) ) ;
  }

  ~set () 
  { 
    destroyRec (tree.getRoot () );
  }  

  size_type size () { return COUNT (tree.getRoot () ); }

  bool empty () const
  {
    return COUNT (tree.getRoot () ) == 0;
  }

  bool operator == (const set & c) const
  {
    if (this == &c)
      return true;

    if (size () != c.size () )
      return false;

    typename Tree<T, Compare>::Iterator itor1 (tree), itor2 (c.tree);

    while (itor1.has_current () and itor2.has_current () )
      {
     if (KEY (itor1.get_current () ) != KEY (itor2.get_current () ))
       return false;

     itor1.next ();
     itor2.next ();
      }
    
    return true;
  }

  bool operator != (const set & c) const
  {
    return not (*this == c);
  }

  bool operator < (const set & c) const
  {
    if (this == &c)
      return false;

    typename Tree<T, Compare>::Iterator itor1 (tree), itor2 (c.tree);

    while (itor1.has_current () and itor2.has_current () )
      {
     if (KEY (itor1.get_current ()) < KEY (itor2.get_current ()))
       return true;
     else if (KEY (itor2.get_current ()) < KEY (itor1.get_current () ) )
       return false; // no son iguales

     itor1.next ();
     itor2.next ();
      }
    
    if (itor1.has_current () ) /* |*this| >= |c| */
      return false;

    return itor2.has_current ();
  }

  bool operator > (const set & c) const
  {
    return not (*this == c or *this < c);
  }

  bool operator <= (const set & c) const
  {
    return not (*this > c );
  }

  bool operator >= (const set & c) const
  {
    return not (*this < c);
  }
  
  size_type count (const T & value) 
  {
    if (tree.search (value) == NULL)
      return 0;

    return 1;
  } 

  iterator find (const T & value) 
  { 
    Node * node = tree.search (value);

    if (node == NULL)
      return end();

    iterator itor (tree);

    itor.itor.reset_to_node (node);

    return itor;
  }

  iterator lower_bound (const T & value)
  {
    if (size () == 0)
      return end ();

    Node * p = search_rank_parent (tree.getRoot (), value);

    return iterator (tree, p);
  }

  iterator upper_bound (const T & value)
  {
    if (size () == 0)
      return end ();

    Node * p = search_rank_parent (tree.getRoot (), value);

    iterator upper (tree, p);
    
    if (KEY (p) == value)
      upper.itor.next ();

    return upper;
  }

  set & operator = (const set & c)
  {
    if (*this == &c)
      return *this;

    destroyRec (tree.getRoot () );

    tree.getRoot () = copyRec (c.tree.getRoot () ); 

    return *this;
  }

  void swap (set & c)
  {
    Aleph::swap (tree.getRoot (), c.tree.getRoot () );
  }

  iterator begin () 
  {
    return iterator (tree);
  }

  iterator end ()
  {
    iterator last (tree);
    last.goto_end ();

    return last;
  }

  Aleph::pair<iterator, bool> insert (const T & value)
  {
    Node * node = new Node (value);

    iterator itor (tree);

    if (tree.insert (node) == NULL)
      {
     delete node;
     itor.itor.reset_to_key (value);
     
     return Aleph::pair<iterator, bool> (itor, false);
      }

    itor.itor.reset_to_node (node);

    return Aleph::pair<iterator, bool> (itor, true);
  }
    
  iterator insert (const iterator & /* pos */, const T & value)
  {
    Node * node = new Node (value);

    iterator _itor (tree);

    if (tree.insert (node) == NULL)
      { // clave duplicada
     delete node;
     _itor.itor.reset_to_key (value);
      }
    else
      _itor.itor.reset_to_node (node);   
  
    return _itor;    
  }

      template <typename Itor>
  void insert (Itor beg, const Itor & end)
  {
    Aleph::verify_iterators (beg, end);

    while (beg != end)
    {
      insert (*beg);
      beg++;
    }
  }

  size_type erase (const T & value)
  {
    Node * p = tree.remove (value);

    if (p == NULL)
      return 0;
     
    delete p;

    return 1;
  }

  void erase (iterator pos)
  {
    Aleph::verify_container_and_iterator (*this, pos);

    delete pos.itor.del ();
  }
  
  iterator erase (const iterator & beg, const iterator & end)
  {
    Aleph::verify_container_and_iterator (*this, beg);
    Aleph::verify_iterators (beg, end);

    iterator ret_val = end;

    const size_t pos_beg = beg.itor.get_current_position ();
    const size_t pos_end = end.itor.get_current_position ();

    Node * removed_tree = tree.remove(pos_beg, pos_end - 1);

    destroyRec(removed_tree);

    return ret_val;
  }

  void clear ()
  {
    destroyRec(tree.getRoot());
  }
};


    template <typename T>
typename iterator_traits<typename set<T>::iterator>::difference_type
distance(typename set<T>::iterator it1, typename set<T>::iterator it2)
{
  Aleph::verify_iterators(it1, it2);

  return it2.itor.get_current_position() - it1.itor.get_current_position();
}

}

# endif // AH_SET_H

---