tpl_dynMapTree.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 TPL_DYNMAPTREE_H
# define TPL_DYNMAPTREE_H

# include <tpl_binNodeUtils.H>

using namespace Aleph;

namespace Aleph {

    template <
      template <typename /* Key */, class /* Compare */> class Tree, 
      typename Key, 
      typename Range,
      class Compare = Aleph::less<Key>      
      > 
class DynMapTree
{
  Tree<Key, Compare> tree; 
  size_t             num_nodes; 
  struct Node : public Tree<Key, Compare>::Node 
  {

    friend class DynMapTree<Tree, Key, Range, Compare>;

    Range data;

    Node() { /* Empty */ }

    Node(const Key & _key) : Tree<Key, Compare>::Node(_key) { /* empty */ }

    Range & get_data() { return data; } 
  };
  class Proxy
  {
    DynMapTree & tree;
    const Key  & key;
    Node       * node;

  public:

    Proxy(DynMapTree & _tree, const Key &_key) : tree(_tree), key(_key)
    {
      node = static_cast<Node*>(tree.tree.search(key));
    }

    Proxy & operator = (const Range & data)
    {
      if (node == NULL)
        {
          node = static_cast<Node*>(tree.tree.insert(new Node (key)));

          tree.num_nodes++;
        }

      node->get_data() = data;
      
      return *this;
    }

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

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

      if (&tree == &proxy.tree and key == proxy.key)
        return *this; // se trata del mismo elemento del mapeo

      if (node == NULL)
        {
          node = static_cast<Node*>(tree.tree.insert(new Node (key)));

          tree.num_nodes++;         
        }
      
      node->get_data() = proxy.node->get_data();
      
      return *this;
    }

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

      return node->get_data();
    }    
  };

public:

  const size_t & size() const { return num_nodes; }
  bool is_empty() const { return size() == 0; }
  DynMapTree() : num_nodes(0) { /* empty */ }

  DynMapTree(DynMapTree & src_tree) : num_nodes(src_tree.num_nodes) 
  { 
    Node * src_root = static_cast<Node*>(src_tree.tree.getRoot()); 

    try 
      {


        tree.getRoot() = copyRec(src_root);

      }
    catch (...) // hubo falla 
      {
        num_nodes = 0;
        throw;
      }

  }

  virtual ~DynMapTree() 
  {
    if (num_nodes > 0)
      destroyRec(tree.getRoot());
  }
  DynMapTree & operator = (DynMapTree & src_tree)
  {
    if (this == &src_tree)
      return *this;

    Node * src_root = static_cast<Node*>(src_tree.tree.getRoot());
    Node * old_root = static_cast<Node*>(tree.getRoot());

    tree.getRoot() = copyRec(src_root);
    num_nodes      = src_tree.num_nodes;

    destroyRec(old_root);

    return *this;
  }
  size_t insert(const Key & key, const Range & data)
  {
    Node * node = new Node (key);
    node->data = data;

    if (tree.insert(node) == NULL)
      {
        delete node;
        return num_nodes;
      }

    return ++num_nodes;
  }
  size_t remove(const Key & key)
  {
    Node * node = static_cast<Node*>(tree.remove(key));

    if (node == NULL)
      return num_nodes;

    delete node;

    return --num_nodes;
  }
  void empty()
  {
    num_nodes = 0;
    destroyRec(static_cast<Node*>(tree.getRoot()));
  }
  bool test_key(const Key & key)
  {
    Node * node = static_cast<Node*>(tree.search(key));

    return node != NULL;
  }

  Range * test(const Key & key)
  {
    Node * node = static_cast<Node*>(tree.search(key));

    return node != NULL ? &(node->get_data()) : NULL;
  }
  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);
  }
  size_t internal_path_length() 
  {
    return Aleph::internal_path_length(tree.getRoot()); 
  }

  size_t height() { return computeHeightRec(tree.getRoot()); }
  void for_each_in_preorder(void (*visitFct)(Node*, int, int))
  {
    Node * root = static_cast<Node*>(tree.getRoot());

    preOrderRec(root, visitFct); 
  }

  void for_each_in_inorder(void (*visitFct)(Node*, int, int))
  {
    Node * root = static_cast<Node*>(tree.getRoot());

    inOrderRec(root, visitFct);
  }

  void for_each_in_postorder(void (*visitFct)(Node*, int, int))
  {
    Node * root = static_cast<Node*>(tree.getRoot());

    postOrderRec(root, visitFct);
  } 

  void for_each(void (*visitFct)(Node*, int, int))
  {
    for_each_in_inorder(visitFct);
  }
  typedef Node Node_Type;

  typedef Tree<Key, Compare> Tree_Type;
  const Key & get_key(Node_Type * p)
  {
    return p->get_key();
  }

  Range & get_data(Node_Type * p)
  {
    return p->get_data();
  }
};

} // end namespace Aleph

# include <tpl_binTree.H>
# include <tpl_avl.H>
# include <tpl_rb_tree.H>
# include <tpl_rand_tree.H>
# include <tpl_treap.H>
# include <tpl_splay_tree.H>

namespace Aleph {
    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapBinTree : public DynMapTree<BinTree, Key, Type, Compare>
    { /* Empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapAvlTree : public DynMapTree<Avl_Tree, Key, Type, Compare>
    { /* empty */ };
    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapRbTree : public DynMapTree<Rb_Tree, Key, Type, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapRandTree : public DynMapTree<Rand_Tree, Key, Type, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapTreap : public DynMapTree<Treap, Key, Type, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
class DynMapSplayTree : public DynMapTree<Splay_Tree, Key, Type, Compare>
    { /* empty */ };

} // end namespace Aleph

# endif /* TPL_DYNMAPTREE_H */

---