Back to index

texmacs  1.0.7.15
hashtree.hpp
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_H
00015 #define HASHTREE_H
00016 #include "hashmap.hpp"
00017 #include "hashmap.cpp"
00018  
00019 template<class K, class V> class hashtree;
00020 template<class K, class V> int N (hashtree<K,V> tree);
00021 template<class K, class V> bool is_nil (hashtree<K,V> tree);
00022  
00023 template<class K, class V> class hashtree_rep: concrete_struct {
00024   hashmap<K,hashtree<K,V> > children;
00025 public:
00026   V label;
00027 
00028   inline hashtree_rep(): children(hashtree<K,V> (false)), label() {}
00029   inline hashtree_rep(V val): children(hashtree<K,V> ()), label(val) {}
00030   
00031   inline bool contains (K key);
00032   void add_child (K key, hashtree<K,V>& child);
00033   void add_new_child (K key);
00034   void set_label (V val);
00035   V get_label ();
00036   
00037   friend class hashtree<K,V>;  
00038 #ifdef OS_WIN32
00039   friend int N (hashtree<K,V> tree);
00040 #else
00041   friend int N<K,V>(hashtree<K,V> tree);
00042 #endif
00043 };
00044 
00045 /******************************************************************************
00046 * The class hashtree is a tree-class with the special property that
00047 * a node stores its children not in a list or in an array but in a hashmap
00048 * so as to make child-lookup efficient (for broad trees). Each edge of
00049 * the tree has a label and these labels are used as keys for the hashmap.
00050 * The nodes of the may have a value associated with them. 
00051 *
00052 * This data structure is suitable for storing dictionaries which map
00053 * strings of keys to some value in the following fashion:
00054 * Consider this englisch->german dictionary:
00055 *
00056 *   he -> er
00057 *   head -> Kopf
00058 *   heaven -> Himmel
00059 *   hell -> H?lle
00060 *   hello -> hallo
00061 *
00062 * which is represented by the following tree.
00063 *  
00064 *   []--h--[]--e--[er]--a--[]--d--[Kopf]
00065 *                  |       |
00066 *                  |       v
00067 *                  l       |
00068 *                  |       +--e--[]--n--[Himmel]
00069 *                  |
00070 *                  +--l--[H?lle]--o--[hallo]
00071 *
00072 * However, using hashmaps to store the children of a node is problematic
00073 * in TeXmacs. A Hashmap contains a *copy* of a default value.
00074 * If now a hashtree (node) contains a hasmap which in turn
00075 * contains *at least one* hashtree, the instantiation of a single
00076 * hashtree leads to an infinite recursion. I chose to solve this problem
00077 * by allowing hashtree which do not have a hashtree_rep (the equivalent
00078 * of NULL pointers so to speak). These NULL nodes are created by passing
00079 * a boolean value to the hashtree constructor. One cannot accidentally
00080 * obtain a NULL element by e.g. accessing a child (see below).
00081 *
00082 * In general, I tried to imitate the TeXmacs-way of memory management
00083 * as closely as possibly, however the workaround is not that pretty.
00084 * As more elegant way might be to modify the hashmap class so that
00085 * a hashmap contains only a pointer to a function that returns
00086 * a default value instead of a instance of a value-element.
00087 * But I didn't want to modify core TeXmacs code.
00088 ******************************************************************************/
00089   
00090 template<class K, class V> class hashtree {
00091   //CONCRETE_TEMPLATE_2(hashtree,K,V);
00092   hashtree_rep<K,V>* rep;
00093 
00094   // this constructor always returns a NULL element
00095   inline hashtree (bool): rep (NULL) {}
00096   
00097   // ensures that this hashtree has a rep
00098   void realize();
00099 
00100 public:
00101   inline hashtree (const hashtree<K,V>&);
00102   inline ~hashtree ();
00103   inline hashtree<K,V>& operator= (hashtree<K,V> x);
00104     
00105   // default constructor returns a non-NULL node, which does not have a value
00106   inline hashtree (): rep (tm_new<hashtree_rep<K,V> > ()) {}
00107   
00108   // returns a non-NULL node, that has value
00109   inline hashtree (V val): rep (tm_new<hashtree_rep<K,V> > (val)) {}
00110   
00111   // returns this node's value
00112   inline hashtree_rep<K,V>* operator-> (void);
00113   
00114   // returns this node's child with the label "key". If the node doesn't
00115   // have such a child, an error is raised.
00116   inline hashtree<K,V> operator() (K key);   // read only access
00117   
00118   // returns this node's child with the label "key". If the node doesn't
00119   // have such a child, a non-NULL node is created, added to this node's 
00120   // children with the appropriate label and returned. 
00121   // Thus, this method may change the in-memory representation of a tree
00122   // but it does not change the dictionary the tree represents.  
00123   inline hashtree<K,V> operator[] (K key);   // rw access
00124 
00125   friend class hashtree_rep<K,V>;
00126 #ifdef OS_WIN32
00127   friend bool is_nil (hashtree<K,V> ht);
00128   friend int N (hashtree<K,V> ht);
00129 #else
00130   friend bool is_nil<K,V> (hashtree<K,V> ht);
00131   friend int N<K,V>(hashtree<K,V> ht);
00132 #endif
00133 };
00134 
00135 #include "hashtree.cpp"
00136 
00137 #endif // HASHTREE_H