cs_dictionary.h

c-smile 一个语法类似与JS 又有点像C++的 编译器

/*
*
* cs_dictionary.h
*
* Copyright (c) 2001, 2002
* Andrew Fedoniouk - [e-mail]
* Portions: Serge Kuznetsov -  [e-mail]
*
* See the file "COPYING" for information on usage 
* and redistribution of this file
*
*/
#ifndef __cs_dictionary_h
#define __cs_dictionary_h

#include "cs_basic.h"
#include "cs_string.h"
#include "cs_array.h"

namespace tool
{
  template <class c_key,class c_element>
  class dictionary
  {
  public:
    dictionary ( size_t hash_size = 36 )
    {
      _hash_size = hash_size;
      _table = new hash_item* [ hash_size ];
      for ( unsigned i = 0; i < hash_size; i++ )
        _table [ i ] = 0;
    }

    virtual  ~dictionary();
    bool     exists ( const c_key& the_key );

    //
    // Add to hash table association of object with specified name.
    //
    c_element&  operator[] ( const c_key &the_key );

    //
    // Search for object with specified name in hash table.
    // If object is not found false is returned.
    //
    bool  find ( const c_key& the_key, c_element& the_element ) const;
    bool  find ( const c_key& the_key, c_element* &the_element_ptr ) const;
    //
    // Remove object with specified name from hash table.
    // If there are several objects with the same name the one last inserted
    // is removed. If such name was not found 'false' is returned.
    //
    bool  remove ( const c_key& the_key );

    void  clear ();

    int
      size () const
    {
      return _array.size ();
    };

    bool
      is_empty () const
    {
      return _array.size () == 0;
    };


    struct dict_item
    {
      c_key      key;
      c_element  element;
    };

  protected:
    struct hash_item
    {
      size_t      _index;
      hash_item*  _next;
      
      hash_item ()
      {
        _next = 0;
      }
      
      hash_item ( size_t the_index, hash_item* the_next )
      {
        _index = the_index;
        _next  = the_next;
      }
    };

    size_t       _hash_size;
    hash_item**  _table;

    array<dict_item>  _array;

  public:
    int  get_index ( const c_key& the_key, bool create );

    array<dict_item>&
      elements ()
    {
      return _array;
    }

    const c_key&      key   ( int i ) const;
    c_element&        value ( int i );
    const c_element&  value ( int i ) const;
  };

  template <class c_key, class c_element>
  inline
    dictionary<c_key, c_element>::~dictionary ()
  {
    clear ();
    delete [] _table;
  }


  template <class c_key, class c_element>
  inline c_element& 
    dictionary<c_key, c_element>::operator[] ( const c_key &the_key )
  {

    int index = get_index ( the_key, true );
    return _array [ index ].element;
  }

  template <class c_key, class c_element>
  inline const c_key&
    dictionary<c_key, c_element>::key ( int i ) const
  {
    return _array [ i ].key;
  }

  template <class c_key, class c_element>
  inline c_element&
    dictionary<c_key, c_element>::value ( int i )
  {
    return _array [ i ].element;
  }

  template <class c_key, class c_element>
  inline const
    c_element& dictionary<c_key, c_element>::value ( int i ) const
  {
    return _array [ i ].element;
  }

  template <class c_key, class c_element>
  inline bool
    dictionary<c_key, c_element>::find ( const c_key& the_key, c_element& the_element ) const
  {
    int index = const_cast<dictionary<c_key, c_element>*>
                ( this )->get_index ( the_key, false );

    if ( index < 0 )
      return false;

    the_element = _array [ index ].element;
    return true;
  }

  template <class c_key, class c_element>
  inline bool
    dictionary<c_key, c_element>::find ( const c_key& the_key,
                                        c_element* &the_element_ptr ) const
  {
    int index = const_cast<dictionary<c_key, c_element>*>
                ( this )->get_index ( the_key, false );

    if ( index < 0 )
      return false;

    the_element_ptr = const_cast<c_element*> ( &_array [ index ].element );
    return true;
  }

  template <class c_key, class c_element>
  inline int
    dictionary<c_key, c_element>::get_index ( const c_key& the_key,
                                              bool create )
  {
    size_t h = hash<c_key> ( the_key ) % _hash_size;
    for ( hash_item* ip = _table [ h ];
          ip != NULL;
          ip = ip->_next )
      if ( _array [ ip->_index ].key == the_key )
        return ip->_index;

    if ( create )
    {
      size_t ni = _array.size ();
      _array.size ( int ( ni + 1 ) );
      _table [ h ] = new hash_item ( ni, _table [ h ] );
      _array [ ni ].key = the_key;
      return ni;
    }
    return -1;
  }


  template <class c_key, class c_element>
  inline bool
    dictionary<c_key, c_element>::exists ( const c_key& the_key )
  {
    return ( get_index ( the_key, false ) >= 0 );
  }


  template <class c_key, class c_element>
  inline void
    dictionary<c_key,c_element>::clear ()
  {
    for ( int i = _hash_size; --i >= 0; )
    {
      hash_item* ip = _table [ i ];
      while ( ip != NULL )
      {
        hash_item* _next = ip->_next;
        delete ip;
        ip = _next;
      }
      _table [ i ] = 0;
    }
    _array.clear ();
  }

  template <class c_key, class c_element>
  inline bool
    dictionary<c_key, c_element>::remove ( const c_key& the_key )
  {
    size_t h = hash<c_key> ( the_key ) % _hash_size;
    hash_item* curr = _table [ h ], *prev = 0;
    while ( curr != NULL )
    {
      if ( _array [ curr->_index ].key == the_key )
      {
        if ( prev == 0 )
          _table [ h ] = curr->_next;
        else
          prev->_next = curr->_next;
        _array.remove ( curr->_index );
        delete curr;
        return true;
      }
      prev = curr;
      curr = curr->_next;
    }
    return false;
  }

};

#endif