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