cmt_map.h

Go to the documentation of this file.

//-----------------------------------------------------------
// Copyright Christian Arnault LAL-Orsay CNRS
// 
// 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 

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

  cmt_node (const K& key, T& t) : 
    m_left (0),
    m_key (key),
    m_t (&t),
    m_right (0)
  {
  }

  ~cmt_node ()
  {
    clear ();
  }

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

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

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

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

  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* m_left;
  K m_key;
  T* m_t;
  cmt_node* m_right;
};


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

  cmt_vnode (const K& key, T& t) : 
    m_left (0),
    m_key (key),
    m_t (t),
    m_right (0)
  {
  }

  ~cmt_vnode ()
  {
    clear ();
  }

  void clear ()
  {
    if (m_left == 0) return;

    delete m_left;
    m_left = 0;

    if (m_right == 0) return;

    delete m_right;
    m_right = 0;
  }

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

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

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

  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* m_left;
  K m_key;
  T m_t;
  cmt_vnode* m_right;
};


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

  cmt_map () : m_top (0)
  {
  }

  ~cmt_map ()
  {
    clear ();
  }

  void clear ()
  {
    if (m_top != 0)
      {
        delete m_top;
        m_top = 0;
      }
  }

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

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

  bool has (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->has (key));
      }
    else
      {
        return (false);
      }
  }

  T* find (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->find (key));
      }
    else
      {
        return (0);
      }
  }

  const cmt_node* find_node (const K& key) const
  {
    if (m_top == 0) return (0);

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

private:
  cmt_node* m_top;
};

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

  cmt_vmap () : m_top (0)
  {
  }

  ~cmt_vmap ()
  {
    clear ();
  }

  void clear ()
  {
    if (m_top != 0)
      {
        delete m_top;
        m_top = 0;
      }
  }

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

  bool has (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->has (key));
      }
    else
      {
        return (false);
      }
  }

  const T* find (const K& key) const
  {
    if (m_top != 0)
      {
        return (m_top->find (key));
      }
    else
      {
        return (0);
      }
  }

  const cmt_vnode* find_node (const K& key) const
  {
    if (m_top == 0) return (0);

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

private:
  cmt_vnode* 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* node = m_top->remove (key);
    if (node == 0) return;

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



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

#endif

---