Multiset.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 multiset C++ standard container
*/

# ifndef AH_MULTISET_H
# define AH_MULTISET_H

# include <memory>
# include <ah_stdc++_utils.H>
# include <tpl_dnode.H>
# include <tpl_treapRk.H>

namespace Aleph
{

    template <class T, 
           class Compare = Aleph::less<T>,
           template <class, class> class Tree = Treap_Rk_Vtl
           >
class multiset
{
public:

  typedef T value_type;

  typedef typename multiset::value_type & reference;

  typedef const typename multiset::value_type & const_reference;

  typedef size_t size_type;

  typedef T key_type;

private:

  typedef Tree<T, Compare> Tree_Type;

  mutable Tree_Type tree;

  mutable size_t num_elem;

      // Definición de nodo que manejerá el árbol
  struct Node : public Tree<T, Compare>::Node
  {
    mutable Dlink key_list;   // lista de claves repetidas
    mutable size_t num_elem;  // número de elementos repetidos.

    Node () : num_elem (0) { /* empty */ }

    Node (const T & k) : Tree_Type::Node (k), num_elem (0) { /* empty */ }

    void copy_list (Dlink & l)
    {
      for (typename Dnode<T>::Iterator it (&l); it.has_current (); it.next ())
     {
       Dnode<T> * node = new Dnode<T> (it.get_current ()->get_data ());
       key_list.append(node);
       ++num_elem;
     }
    }

    Node * operator = (const Node & node)
    {
      if (this == &node)
     return *this;

      *static_cast<typename Tree_Type::Node*> (this) = node;
      num_elem = 0;

      key_list.remove_all_and_delete();
      copy_list(&node.key_list);
    }

    Node (const Node & p) : Tree_Type::Node (p), num_elem (0)
    {
      copy_list(p.key_list);
    }

    ~Node ()
    {
      key_list.remove_all_and_delete();
    }
  };

public:  

  class iterator
  {
  private:

    friend class multiset<T, Compare, Tree>;
    
    typedef typename Tree_Type::Iterator Iterator;
    
    mutable multiset * multiset_ptr;

    Iterator tree_itor;

    typename Dnode<T>::Iterator list_itor;

    bool overflow;

    bool underflow;

        /* Coloca list_itor en un nodo de la lista en tree_itor */
    void set_list_itor_in_node (Dnode<T> * list_node)
    {
      Node * node = static_cast<Node*> (tree_itor.get_current ());

      list_itor = typename Dnode<T>::Iterator (&node->key_list, list_node);
    }

    iterator (multiset * mset_ptr, 
           Node *     curr_tree_node,
           Dlink &    key_list,
           Dnode<T> * curr_list_node) 
      : multiset_ptr (mset_ptr),
     tree_itor (mset_ptr->tree, curr_tree_node), 
     list_itor (&key_list, curr_list_node),
     overflow (false), underflow (false)
    {
      I (curr_list_node->get_data () == curr_tree_node->get_key ());
      I (multiset_ptr->tree.search (KEY (curr_tree_node)) != NULL);
      I (&curr_tree_node->key_list == &key_list);
    }

    iterator (multiset * mset_ptr, Node * curr_tree_node)
      : multiset_ptr (mset_ptr),
     tree_itor (mset_ptr->tree, curr_tree_node), 
     list_itor (&curr_tree_node->key_list), 
     overflow (false), underflow (false)
    {
      I (mset_ptr->tree.search (KEY (curr_tree_node)) != NULL);
    }

    void default_init ()
    {
      if (tree_itor.has_current ())
     {
       list_itor.reset
         (&static_cast<Node*> (tree_itor.get_current ())->key_list);

       underflow = overflow = false;
     }
      else
     underflow = overflow = true;
    }

    iterator (const multiset & ms)
      :  multiset_ptr (const_cast<multiset*> (&ms)), tree_itor (ms.tree)
    {
      default_init ();
    }

    bool has_current () const 
    {
      return tree_itor.has_current () and list_itor.has_current (); 
    }

    T & get_current () { return list_itor.get_current ()->get_data (); }

  public:

    typedef typename multiset<T>::value_type      value_type;

    typedef typename multiset<T>::size_type       difference_type;

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

    typedef typename multiset<T>::reference       reference;

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

    iterator (multiset * mset_ptr)
      : multiset_ptr (mset_ptr), tree_itor (multiset_ptr->tree) 
    {
      default_init ();
    }

    iterator () 
    {
      underflow = overflow = true;
    }

    T & operator * ()
    {
      return get_current ();
    }

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

  private:

    void goto_begin ()
    {
      tree_itor.reset_first ();
      
      if (tree_itor.has_current ())
     {
       list_itor.reset
         (& static_cast<Node*> (tree_itor.get_current ())->key_list);

       underflow = false;
     }
      else
     underflow = true;
    }

    void goto_last ()
    {
      tree_itor.reset_last ();
      
      if (tree_itor.has_current ())
     {
       list_itor.reset
         (& static_cast<Node*> (tree_itor.get_current ())->key_list);
       list_itor.reset_last ();
       overflow = false;
     }
      else
     overflow = true;
    }

    void goto_end ()
    {
      tree_itor.reset_last ();
      
      if (tree_itor.has_current ())
     {
       list_itor.reset 
         (& static_cast<Node*> (tree_itor.get_current ())->key_list);

       list_itor.prev ();
       tree_itor.next ();
       underflow = false;
     }
      else
     underflow = true;

      overflow = true;
    }

    void forward ()
    {
      if (underflow)
     {
       goto_begin ();
       return;
     }

      list_itor.next (); // Avanza elementos repetidos

      if (not list_itor.has_current ()) 
     { 
       tree_itor.next (); 

       if (tree_itor.has_current ())
         {
           Dlink * list = 
          &static_cast<Node*> (tree_itor.get_current ())->key_list;
           list_itor.reset (list);
         }
       else
         overflow = true;
     }
    }

    void backward ()
    {
      if (overflow)
     {
       goto_last ();
       return;
     }

      list_itor.prev ();

      if (not list_itor.has_current ())
     {
       tree_itor.prev ();

       if (tree_itor.has_current ())
         {
           Dlink * list = 
          &static_cast<Node*> (tree_itor.get_current ())->key_list;
           list_itor.reset (list);
           list_itor.reset_last ();
         }
       else
         underflow = true;
     }
    }

    void del ()
    {
      Dnode<T> * list_node = list_itor.del ();
      Node * tree_node = static_cast<Node*> (tree_itor.get_current ());
            
      delete list_node;

      --tree_node->num_elem;

      --multiset_ptr->num_elem;

      if (tree_node->num_elem == 0)
     {
       tree_itor.del ();
       delete tree_node;

       if (tree_itor.has_current ())
         {
           Dlink * list = 
          &static_cast<Node*> (tree_itor.get_current ())->key_list;
           list_itor.reset (list);
         }
       else
         overflow = true;
     }
    }

  public:

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

      return get_current ();
    }

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

      forward ();

      return return_value;
    }

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

      return get_current ();
    }

    T & operator -- (int)
    {
      T & return_value = get_current ();

      backward ();

      return return_value;
    }
    
    /* TODO: Estas funciones pueden optimizarse para que avancen por
       contadores de nodos */  

    T & operator += (size_type n)
    {
      for (int i = 0; i < n; ++i)
        forward ();

      return get_current ();
    } 

    T & operator -= (size_type n)
    {
      for (int i = 0; i < n; ++i)
        backward ();
      
      return get_current ();
    } 

    bool operator == (const iterator & itor) const
    {
      if (overflow == itor.overflow and underflow == itor.underflow)
     return true;

      return tree_itor == itor.tree_itor and list_itor == itor.list_itor; 
    }

    bool operator != (const iterator & itor) const
    {
      return not (*this == itor);
    }

    bool verify (const multiset & _multiset) const
    {
      return tree_itor.verify ( (Tree_Type*)& (_multiset.tree));
    }

    bool verify (const iterator & it) const
    {
      return tree_itor.verify (it.tree_itor);
    }
  }; // class iterator;

  typedef typename multiset::iterator const_iterator;

  typedef typename multiset::iterator reverse_iterator;
  
  typedef typename multiset::iterator const_reverse_iterator;

  multiset () : num_elem (0) { /* empty */  }

private:

  void copy (const multiset & c)
  {
    Node * tree_node = copyRec<Node> (static_cast<Node*> (c.tree.getRoot ()));

    tree.getRoot () = tree_node;
  }

public:
 
  multiset (const multiset & c) : num_elem (c.num_elem)
  {
    copy (c);
  }

      template <typename Itor> 
  multiset (Itor beg, Itor end) : num_elem (0)
  {
    while (beg != end)
      insert (beg++);
  }

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

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

    destroyRec (tree.getRoot());

    copy (c);

    num_elem = c.num_elem;

    return *this;
  }

  size_type size () const { return num_elem; }

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

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

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

    iterator itor1 (*this), itor2 (c);

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

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

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

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

    iterator itor1 (*this), itor2 (c);

    while (itor1.has_current () and itor2.has_current ())
      {
     if (itor1.get_current () < itor2.get_current ())
       return true;
     else if (itor2.get_current () < itor1.get_current ())
       return false; // no son iguales
       
     itor1.forward ();
     itor2.forward ();
      }
    
    if (itor1.has_current ()) /* |*this| >= |c| */
      return false;

    return itor2.has_current ();
  }

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

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

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

  size_type count (const T & value) const
  {
    Node * p = static_cast<Node*> (tree.search (value));

    if (p == NULL)
      return 0;

    return p->num_elem;
  } 

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

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

    iterator itor (*this);

    itor.tree_itor.reset_to_node (node);
    itor.list_itor.reset (&node->key_list);

    return itor;
  }

  iterator lower_bound (const T & value) const
  {
    if (size () == 0)
      throw std::underflow_error ("multiset is empty");

    Node * tree_node = static_cast<Node*> (tree.search (value));

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

    return iterator (this, tree_node);
  }

  iterator upper_bound (const T & value) const
  {
    if (size () == 0)
      throw std::underflow_error ("multiset is empty");

    Node * tree_node = static_cast<Node*> (tree.search (value));

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

    iterator it (this, tree_node);
    it.list_itor.reset_last ();

    return it;
  }

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

  iterator begin () const
  {
    return iterator (*this);
  }

  iterator end () const
  {
    iterator it (*this);

    it.goto_end ();

    return it;
  }

  iterator insert (const T & value) 
  {
    bool node_allocated = false;
    Node * tree_node_ptr = static_cast<Node*> (tree.search (value));

    if (tree_node_ptr == NULL)
      {
     tree_node_ptr = static_cast<Node*>(tree.insert( new Node(value)));
     node_allocated = true;
      }

    I (tree_node_ptr != NULL);

    try
      {
     Dnode<T> * list_node_ptr =  new Dnode<T>(value) ;

     tree_node_ptr->key_list.append(list_node_ptr);

     ++tree_node_ptr->num_elem;

     ++num_elem;

     return iterator(this, tree_node_ptr, 
               tree_node_ptr->key_list, list_node_ptr);
      }
    catch (std::bad_alloc)
      {
     if (node_allocated)
       {
         tree_node_ptr = static_cast<Node*>(tree.remove (value));
     
         I (tree_node_ptr != NULL);

         delete tree_node_ptr;
       }
      
     throw;
      }
  }
    
  iterator insert (iterator pos, const T & value)
  {
    Aleph::verify_container_and_iterator (this, pos);

    auto_ptr< Dnode<T> > list_node(new Dnode<T>(value));
    try
      {
     if (*pos == value) // dispara overflow_error si iterador es invalido
       {     /* en este caso, debe existir un nodo en el arbol, lo que
             evita la busqueda en árbol */
         
         pos.list_itor.get_current()->insert(list_node.get());
         ++static_cast<Node*>(pos.tree_itor.get_current())->num_elem;

         pos.list_itor.set(list_node.release());

         I(KEY(pos.tree_itor.get_current()) == value);
       }
     else
       {
         Node * tree_node = static_cast<Node*>(tree.search(value));

         if (tree_node == NULL)
           tree_node = static_cast<Node*>(tree.insert(new Node(value)));

         tree_node->key_list.append(list_node.release());
         ++tree_node->num_elem;

         pos.tree_itor.reset_to_node (tree_node);
         pos.list_itor.reset (&tree_node->key_list);
       }

     ++num_elem;
      
     return pos;
      }
    catch (std::overflow_error)
      {     /* proveniente de if (*pos == value) */
     return insert (value); 
      }
  }

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

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

  size_type erase (const T & value)
  {
    Node * tree_node = static_cast<Node*> (tree.remove (value));

    if (tree_node == NULL)
      return 0;

    const size_t ret_val = tree_node->num_elem;
     
    delete tree_node;

    num_elem -= ret_val;

    return ret_val;
  }

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

    Dnode<T> * list_node = pos.list_itor.get_current ();
    Node * tree_node = static_cast<Node*> (pos.tree_itor.get_current ());

    I (tree.search (KEY (tree_node)) == tree_node);
    I (KEY (tree_node) == list_node->get_data ());

    list_node->del ();
    delete list_node;

    --tree_node->num_elem;
    --num_elem;

    if (tree_node->num_elem == 0)
      {
     tree.remove (KEY (tree_node));
     delete tree_node;
      }
  }
  
private:

      /* Borra el rango secuencialmente */
  iterator delete_range (iterator beg, const iterator & end)
  {
    while (beg != end)
      beg.del ();

    return beg;
  }

public:

  iterator erase (iterator beg, const iterator & end)
  {
    Aleph::verify_container_and_iterator (*this, beg);
    Aleph::verify_iterators (beg, end);

    return delete_range(beg, end);
  }

  void clear ()
  {
    destroyRec (static_cast<Node *> (tree.getRoot ()));
    num_elem = 0;
  }
};


    template <typename T>
typename iterator_traits<typename multiset<T>::iterator>::difference_type 
distance (typename multiset<T>::iterator it1, 
       typename multiset<T>::iterator it2)
{
  typename iterator_traits<typename multiset<T>::iterator>::difference_type
    counter = 0;

  
  while (it1 != it2)
    {
      ++counter;
      ++it1;
    }

  return counter;
}

} // end namespace Aleph

# endif // AH_MULTISET_H

---