source: CMT/HEAD/source/cmt_map.h @ 662

//-----------------------------------------------------------
// Copyright Christian Arnault LAL-Orsay CNRS
// arnault@lal.in2p3.fr
// See the complete license in cmt_license.txt "http://www.cecill.info". 
//-----------------------------------------------------------

#ifndef __cmt_map_h__
#define __cmt_map_h__

#include "cmt_std.h"
#include "cmt_string.h"
#include "cmt_vector.h"

#include <stdlib.h>

/**
 *    class cmt_node
 *
 *   Implements a binary tree of T* keyed by the class K
 *
 *   The class K must have the < and > operators.
 *
 *   This is the basic constituent for the cmt_map class.
 */
template <class K, class T> class cmt_node
{
public:

  /**
   * Required constructor.
   * Provides the key and the value.
   */
  cmt_node (const K& key, T& t) : 
    m_left (0),
    m_key (key),
    m_t (&t),
    m_right (0)
  {
  }

  /**
   *  Destructor
   */
  ~cmt_node ()
  {
    clear ();
  }

  /**
   *   Recursive clear operation. 
   *   Will delete sub-nodes
   */
  void clear ()
  {
    if (m_left == 0) return;

    delete m_left;
    m_left = 0;

    m_t = 0;

    if (m_right == 0) return;

    delete m_right;
    m_right = 0;
  }

  /**
   *  Add an item.
   */
  void add (const K& key, T& t)
  {
    if (key < m_key)
      { 
        if (m_left == 0)
          {
            m_left = new cmt_node (key, t);
          }
        else
          {
            m_left->add (key, t);
          }
      }
    else if (key > m_key)
      { 
        if (m_right == 0)
          {
            m_right = new cmt_node (key, t);
          }
        else
          {
            m_right->add (key, t);
          }
      }
    else
      {
        m_t = &t;
      }
  }

  /**
   *   Finds whether the tree starting from this node 
   *   contains this key
   */
  bool has (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (false);
        else return (m_left->has (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (false);
        else return (m_right->has (key));
      }
    else
      {
        return (true);
      }
  }

  /**
   *   Finds in the tree starting from this node 
   *   the value associated with this key
   *   Return 0 if not found
   */
  T* find (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (0);
        else return (m_left->find (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (0);
        else return (m_right->find (key));
      }
    else
      {
        return (m_t);
      }
  }

  /**
   *   Finds in the tree starting from this node 
   *   the node holding the value associated with this key
   *   Return 0 if not found
   */
  const cmt_node* find_node (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (0);
        else return (m_left->find_node (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (0);
        else return (m_right->find_node (key));
      }
    else
      {
        return (this);
      }
  }

protected:
  cmt_node<K,T>* m_left;
  K m_key;
  T* m_t;
  cmt_node<K,T>* m_right;
};


template <class K, class T> class cmt_vnode
{
public:

  /**
   * Required constructor.
   * Provides the key and the value.
   */
  cmt_vnode (const K& key, T& t) : 
    m_left (0),
    m_key (key),
    m_t (t),
    m_right (0)
  {
  }

  /**
   *  Destructor
   */
  ~cmt_vnode ()
  {
    clear ();
  }

  /**
   *   Recursive clear operation. 
   *   Will delete sub-nodes
   */
  void clear ()
  {
    if (m_left == 0) return;

    delete m_left;
    m_left = 0;

    if (m_right == 0) return;

    delete m_right;
    m_right = 0;
  }

  /**
   *  Add an item.
   */
  void add (const K& key, T& t)
  {
    if (key < m_key)
      { 
        if (m_left == 0)
          {
            m_left = new cmt_vnode (key, t);
          }
        else
          {
            m_left->add (key, t);
          }
      }
    else if (key > m_key)
      { 
        if (m_right == 0)
          {
            m_right = new cmt_vnode (key, t);
          }
        else
          {
            m_right->add (key, t);
          }
      }
    else
      {
        m_t = t;
      }
  }

  /**
   *   Finds whether the tree starting from this node 
   *   contains this key
   */
  bool has (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (false);
        else return (m_left->has (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (false);
        else return (m_right->has (key));
      }
    else
      {
        return (true);
      }
  }

  /**
   *   Finds in the tree starting from this node 
   *   the value associated with this key
   *   Return 0 if not found
   */
  T* find (const K& key)
    //  const T* find (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (0);
        else return (m_left->find (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (0);
        else return (m_right->find (key));
      }
    else
      {
        return (&m_t);
      }
  }

  /**
   *   Finds in the tree starting from this node 
   *   the node holding the value associated with this key
   *   Return 0 if not found
   */
  const cmt_vnode* find_node (const K& key) const
  {
    if (key < m_key)
      { 
        if (m_left == 0) return (0);
        else return (m_left->find_node (key));
      }
    else if (key > m_key)
      { 
        if (m_right == 0) return (0);
        else return (m_right->find_node (key));
      }
    else
      {
        return (this);
      }
  }

protected:
  cmt_vnode<K,T>* m_left;
  K m_key;
  T m_t;
  cmt_vnode<K,T>* m_right;
};


/**
 *   Public interface for maps.
 *   It is implemented by one top cmt_node.
 *
 *   At creation the map is empty. 
 */
template <class K, class T> class cmt_map
{
public:

  /**
   *  Constructor
   */
  cmt_map () : m_top (0)
  {
  }

  /**
   *  Destructor
   */
  ~cmt_map ()
  {
    clear ();
  }

  /**
   * clear: erase everything from this map
   */
  void clear ()
  {
    if (m_top != 0)
      {
        delete m_top;
        m_top = 0;
      }
  }

  /**
   *  Add an entry.
   *
   *  Existing entries with the same key will be overridden
   */
  void add (const K& key, T& t)
  {
    if (m_top == 0)
      {
        m_top = new cmt_node<K, T> (key, t);
      }
    else
      {
        m_top->add (key, t);
      }
  }

  void add (const K& key, T* t)
  {
    if (m_top == 0)
      {
        m_top = new cmt_node<K, T> (key, *t);
      }
    else
      {
        m_top->add (key, *t);
      }
  }

  /**
   *   Finds whether there is a node holding that key
   */
  bool has (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->has (key));
      }
    else
      {
        return (false);
      }
  }

  /**
   *   Finds the value associated with that key.
   *   Returns 0 if not found
   */
  T* find (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->find (key));
      }
    else
      {
        return (0);
      }
  }

  /**
   *   Finds the node containing the value associated with that key.
   *   Returns 0 if not found
   */
  const cmt_node<K, T>* find_node (const K& key) const
  {
    if (m_top == 0) return (0);

    return (m_top->find_node (key));
  }

private:
  cmt_node<K, T>* m_top;
};

template <class K, class T> class cmt_vmap
{
public:

  /**
   *  Constructor
   */
  cmt_vmap () : m_top (0)
  {
  }

  /**
   *  Destructor
   */
  ~cmt_vmap ()
  {
    clear ();
  }

  /**
   * clear: erase everything from this map
   */
  void clear ()
  {
    if (m_top != 0)
      {
        delete m_top;
        m_top = 0;
      }
  }

  /**
   *  Add an entry.
   *
   *  Existing entries with the same key will be overridden
   */
  void add (const K& key, T& t)
  {
    if (m_top == 0)
      {
        m_top = new cmt_vnode<K, T> (key, t);
      }
    else
      {
        m_top->add (key, t);
      }
  }

  /**
   *   Finds whether there is a node holding that key
   */
  bool has (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->has (key));
      }
    else
      {
        return (false);
      }
  }

  /**
   *   Finds the value associated with that key.
   *   Returns 0 if not found
   */
  T* find (const K& key) const
    //  const T* find (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->find (key));
      }
    else
      {
        return (0);
      }
  }

  /**
   *   Finds the node containing the value associated with that key.
   *   Returns 0 if not found
   */
  const cmt_vnode<K, T>* find_node (const K& key) const
  {
    if (m_top == 0) return (0);

    return (m_top->find_node (key));
  }

private:
  cmt_vnode<K, T>* m_top;
};




    /*
  T& operator [] (const K& key)
  {
    T* t = find (key);
    
    if (t == 0)
      {
        static T t;
        
        add (key, t);
        return ((*this)[key]);
      }
    else
      {
        return (*t);
      }
  }
    */


/* ------------------------------------------------------------

   This is a future possible implementation for the remove node function

  void add (cmt_node* other)
  {
    if (other->m_key < m_key)
      {
        if (m_left == 0)
          {
            m_left = other;
          }
        else
          {
            m_left->add (other);
          }
      }
    else if (other->m_key > m_key)
      { 
        if (m_right == 0)
          {
            m_right = other;
          }
        else
          {
            m_right->add (other);
          }
      }
    else
      {
        m_t = other->m_t;
      }
  }

  cmt_node* remove_greatest ()
  {
    if (m_right == 0) return (this);

    cmt_node* result = m_right->remove_greatest ();
    if (result == m_right) m_right = 0;

    return (result);
  }

  cmt_node* remove_node (const K& key)
  {
    if (key < m_key)
      { 
        if (m_left != 0)
          {
            cmt_node* node = m_left->remove_node (key);
            if (node != 0)
              {
                delete m_left;
                m_left = node;
              }
          }

        return (0);
      }
    else if (key > m_key)
      { 
        if (m_right != 0)
          {
            cmt_node* node = m_right->remove_node (key);
            if (node != 0)
              {
                delete m_right;
                m_right = node;
              }
          }

        return (0);
      }
    else
      {
        // This node will be removed.
        // The replacement will be returned.

        if (m_left == 0)
          {
            cmt_node* rep = m_right;
            m_right == 0;
            return (rep);
          }
        else if (m_right == 0)
          {
            cmt_node* rep = m_left;
            m_left == 0;
            return (rep);
          }
        else
          {
            // here both sides are busy

            cmt_node* rep = remove_greatest ();

            rep->add (this);

            return (rep);
          }

        return (this);
      }
  }


  void cmt_map::remove (const K& key)
  {
    if (m_top == 0) return;

    cmt_node<K, T>* node = m_top->remove (key);
    if (node == 0) return;

    if (node == m_top) 
      {
      }
    else
      {
      }
  }



 ------------------------------------------------------------ */

#endif