Map.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
*/


# ifndef ALEPH_MAP_H
# define ALEPH_MAP_H
/*
        Aleph implementation of map C++ standard container
*/

# include <stdlib.h>
# include <ahFunction.H>
# include <ahPair.H>
# include <ah_stdc++_utils.H>
# include <tpl_treapRk.H>


namespace Aleph
{

    template <class T1, class T2, class Compare>
struct Compare_For_Map 
{
      bool
  operator () (const Aleph::pair<T1, T2> & __x, 
            const Aleph::pair<T1, T2> & __y) const
  { 
    return Compare () (__x.first, __y.first); 
  }
};

    template <class Key, 
           class Elem, 
           class Compare = Aleph::less<Key>,
           template <class, class> class Tree = Treap_Rk
    >
class map
{
public:

  typedef Aleph::pair<Key, Elem> Pair;

  typedef Pair value_type;

  typedef typename map::value_type & reference;

  typedef const typename map::value_type & const_reference;

  typedef size_t size_type;

  typedef Key key_type;

  typedef Elem mapped_type;

private:

  typedef Tree<Pair, Compare_For_Map<Key, Elem, Compare> > Tree_Type;

  typedef typename Tree_Type::Node Node;

  mutable Tree_Type tree;

  Node * search_in_tree (const Key & k)
  {
    return tree.search (Pair (k) );
  }

public:

  class iterator
  {
  private:

    friend class map<Key, Elem>;
    
    typedef typename Tree_Type::Iterator Iterator;
    
    Iterator itor;
    bool underflow;
    bool overflow;

    void init_flags ()
    {
      if (itor.has_current () )
     underflow = overflow = false;
      else
     underflow = overflow = true;
    }

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

    iterator (Tree_Type & _tree, Node * node) 
      : itor (_tree, node), underflow (false), overflow (false)
    {
      /* empty */
    }

  public:

    typedef typename map::value_type   value_type;

    typedef typename map::size_type    difference_type;

    typedef typename map::value_type * pointer;

    typedef typename map::reference    reference;

    iterator () { /* empty */ }

    iterator (Tree_Type & tree) : itor (tree)
    {
      init_flags ();
    }

    Pair & operator * ()
    {
      return KEY (itor.get_current () );
    }

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

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

      return KEY (itor.get_current () );
    }

    Pair & operator ++ (int)
    {
      Pair & retPair = KEY (itor.get_current () );
      forward ();

      return retPair;
    }

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

      return KEY (itor.get_current () );
    }

    Pair & operator -- (int)
    {
      Pair & retPair = KEY (itor.get_current () );
      backward ();

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

      return KEY (itor.get_current () );
    } 

    Pair & operator -= (const size_type & n)
    {
      itor.reset_to_pos (itor.get_current_position () - n);

      return KEY (itor.get_current () );
    } 

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

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

    bool verify (const map & _map) const
    {
      return itor.verify ( (Tree_Type*) &_map.tree); 
    }

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

  map () { /* empty */ }
 
  map (const map & c) 
  {
    tree.getRoot () = copyRec (c.tree.getRoot () );
  }

      template <typename Itor> 
  map (Itor beg, const Itor & end) 
  {
    while (beg != end)
      tree.insert (new Node (beg++) );
  }

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

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

    destroyRec (tree.getRoot ());

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

    return *this;
  }

  size_t size () const { return COUNT (tree.getRoot () ); }

  bool empty () const 
  {
    return size() == 0;
  }

  bool operator == (const map & c) const
  {
    if (size () != c.size () )
      return false;

    typename Tree_Type::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 ();
    }
    
    I (not itor1.has_current () and not itor2.has_current () );

    return true;
  }

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

  bool operator < (const map & c) const
  {
    typename Tree_Type::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;
      
      // En este caso las claves sons iguales
      itor1.next ();
      itor2.next ();
    }
    
    if (not itor1.has_current ())
      return true;

    return false;
  }

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

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

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

  size_type count (const Key & key)
  {
    if (search_in_tree (key) != NULL)
      return 1;

    return 0;
  } 

  iterator find (const Key & key) 
  { 
    Node * p = search_in_tree (key);

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

    return iterator (tree, p);
  }
  iterator lower_bound (const Key & key)
  {
    Node * p = search_rank_parent (tree.getRoot (), Pair (key));

    return iterator (tree, p);
  }

  iterator upper_bound (const Key & key)
  {
    Node * p = search_rank_parent (tree.getRoot (), Pair (key));

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

    return upper;
  }

  void swap (map & c)
  {
    tree.swap (c.tree);
  }

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

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

    return last;
  }

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

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

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

    if (tree.insert (node) == NULL)
    {
      delete node;
      return iterator (tree, tree.search(key));
    }
  
    return iterator (tree, node);
  }

      template <typename Itor>
  void insert (Itor beg, const Itor & end)
  {
    while (beg != end)
      insert (beg++);
  }

  size_type erase (const Key & key)
  {
    Node * p = tree.remove (key);

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

    return 1;
  }

  void erase (iterator pos)
  {
    erase (KEY (pos.itor.get_current ()).first);
  }

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

    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());
  }
  
private:
  
  struct Proxy
  {
    map  * map_ptr;
    Node * node;
    Key    key;

    Proxy (map * m_ptr, const Key & _key) : map_ptr (m_ptr), key (_key)
    {
      node = map_ptr->search_in_tree (key);
    }

    Proxy & operator = (const Elem & elem)
    {
      if (node == NULL)
        {
       node = new Node (Aleph::make_pair (key, elem));
       map_ptr->tree.insert (node);
     }
      else
        KEY (node).second = elem;

      return *this;
    }

    Proxy & operator = (const Proxy & proxy)
    {
      if (this == &proxy)
     return *this;

      if (proxy.node == NULL)
        throw std::domain_error("key not found");;

      if (map_ptr == proxy.map_ptr and key == proxy.key)
        return *this; // They are the same

      if (node == NULL)
        {
       node = new Node (KEY (proxy.node));
       map_ptr->tree.insert (node);
     } 
      else
        KEY (node).second = KEY (proxy.node).second;

      return *this;
    }

    operator Elem & () const
    {
      if (node == NULL)
        throw std::domain_error ("key not found");;

      return KEY (node).second;
    }    
  };

public:

  const Proxy operator [] (const Key & key) const 
    Exception_Prototypes (std::domain_error)
  {
    return Proxy (this, key);
  }

  Proxy operator [] (const Key & key) 
    Exception_Prototypes (std::domain_error)
  {
    return Proxy (this, key);
  }
};



} // end namespace Aleph


# endif // ALEPH_MAP_H

---