Back to index

texmacs  1.0.7.15
hashtree.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashtree
00004 * DESCRIPTION: A tree class that stores a node's children in a hashmap instead
00005 *              of a list. Can be used to implement a dictionary that maps
00006 *              strings to strings efficiently.
00007 * COPYRIGHT  : (C) 2002  Felix Breuer
00008 *******************************************************************************
00009 * This software falls under the GNU general public license version 3 or later.
00010 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00011 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00012 ******************************************************************************/
00013 
00014 #ifndef HASHTREE_C
00015 #define HASHTREE_C
00016 #include "hashtree.hpp"
00017 
00018 /******************************************************************************
00019 * Methods normally provided by
00020 * CONCRETE_TEMPLATE_2_CODE(hashtree,class,K,class,V);
00021 ******************************************************************************/
00022 
00023 template<class K,class V> inline 
00024 hashtree<K,V>::hashtree(const hashtree<K,V>& x): rep(x.rep) {
00025   if (this->rep!=NULL) INC_COUNT (this->rep);
00026 }
00027 
00028 template<class K,class V> inline 
00029 hashtree<K,V>::~hashtree() {
00030   if (this->rep!=NULL) DEC_COUNT (this->rep);
00031 }
00032 
00033 template<class K,class V> inline hashtree<K,V>&
00034 hashtree<K,V>::operator= (hashtree<K,V> x) {
00035   if (this->rep!=NULL) DEC_COUNT (this->rep); 
00036   this->rep = x.rep;
00037   if (x.rep!=NULL) INC_COUNT (x.rep);
00038   return *this;
00039 }
00040 
00041 /******************************************************************************
00042 * Methods of hashtree_rep<K,V>
00043 ******************************************************************************/
00044 
00045 template<class K, class V> inline bool
00046 hashtree_rep<K,V>::contains (K key) {
00047   return children->contains(key);
00048 }
00049 
00050 template<class K, class V> void 
00051 hashtree_rep<K,V>::add_child (K key, hashtree<K,V>& child) {
00052   child.realize();                   // make sure the child has a rep!
00053   children (key) = child;
00054 }
00055 
00056 template<class K, class V> void 
00057 hashtree_rep<K,V>::add_new_child (K key) {
00058   hashtree<K,V> child;
00059   add_child (key, child);
00060 }
00061 
00062 template<class K, class V> void 
00063 hashtree_rep<K,V>::set_label (V val) {
00064   label = val;
00065 }
00066 
00067 template<class K, class V> V 
00068 hashtree_rep<K,V>::get_label () {
00069   return label;
00070 }
00071 
00072 /******************************************************************************
00073 * Method to ensure that hashtree is non null
00074 ******************************************************************************/
00075 
00076 template<class K, class V> inline void
00077 hashtree<K,V>::realize() {
00078   if (rep == NULL) {
00079     rep = tm_new<hashtree_rep<K,V> > ();
00080     INC_COUNT(rep);
00081   }
00082 }
00083   
00084 /******************************************************************************
00085 * Overloaded operators
00086 ******************************************************************************/
00087   
00088 template<class K, class V> inline hashtree_rep<K,V>* 
00089 hashtree<K,V>::operator-> (void) {
00090   // always make sure there is a rep!
00091   realize ();
00092   return rep;
00093 }
00094 
00095 template<class K, class V> inline hashtree<K,V> 
00096 hashtree<K,V>::operator[] (K key) {
00097   if (*this->contains (key)) return *this->children (key);
00098   else FAILED ("read-access to non-existent node requested");
00099 }
00100   
00101 template<class K, class V> inline hashtree<K,V> 
00102 hashtree<K,V>::operator() (K key) {
00103   realize ();
00104   if (!(*this)->contains (key)) (*this)->add_new_child (key);
00105   return (*this)->children (key);
00106 }
00107 
00108 /******************************************************************************
00109 * Functions
00110 ******************************************************************************/
00111 
00112 template<class K, class V> inline bool
00113 is_nil (hashtree<K,V> ht) {
00114   return ht.rep == NULL;
00115 }
00116 
00117 template<class K, class V> inline int
00118 N (hashtree<K,V> ht) {
00119   return N(ht->children);
00120 }
00121 
00122 #endif // HASHTREE_C