00001 #ifndef DICTIONARY_HXX_
00002 # define DICTIONARY_HXX_
00003
00004 namespace dictionary
00005 {
00006 template<typename Content>
00007 DictionaryNode<Content>::DictionaryNode() : _content(NULL)
00008 {
00009 }
00010
00011 template<typename Content>
00012 Dictionary<Content>::Dictionary()
00013 {
00014 }
00015
00016 template<typename Content>
00017 Dictionary<Content>::~Dictionary()
00018 {
00019 clear();
00020 }
00021
00022 template<typename Content>
00023 void Dictionary<Content>::clear()
00024 {
00025 for (std::map<int, DictionaryNode<Content> *>::iterator it = _root._sub_nodes.begin();
00026 it != _root._sub_nodes.end();
00027 it++)
00028 {
00029 clear_rec(*it->second);
00030 }
00031 }
00032
00033 template<typename Content>
00034 void Dictionary<Content>::put_word(const std::string &s, Content *c)
00035 {
00036 _current_node = &_root;
00037 _current_iterator = s.begin();
00038 _end_iterator = s.end();
00039 if (_current_iterator == _end_iterator)
00040 return;
00041
00042 put_word_rec();
00043
00044 _current_node->_content = c;
00045 }
00046
00047 template<typename Content>
00048 Content *Dictionary<Content>::find(const std::string &s)
00049 {
00050 _current_node = &_root;
00051 _depth = 0;
00052 _current_iterator = s.begin();
00053 _end_iterator = s.end();
00054
00055 find_rec();
00056
00057 if (_current_node->_content == NULL || _depth != s.size())
00058 return NULL;
00059 return _current_node->_content;
00060 }
00061
00062 template<typename Content>
00063 Content *Dictionary<Content>::find_shortest(const std::string &s, std::string *res)
00064 {
00065 _current_node = &_root;
00066 _depth = 0;
00067 _current_iterator = s.begin();
00068 _end_iterator = s.end();
00069
00070 find_shortest_rec();
00071
00072 if (_current_node->_content == NULL)
00073 return NULL;
00074
00075 if (res != NULL)
00076 *res = std::string(s.begin(), s.begin() + _depth);
00077
00078 return _current_node->_content;
00079 }
00080
00081 template<typename Content>
00082 Content *Dictionary<Content>::find_longest(const std::string &s, std::string *res)
00083 {
00084 _best_node = NULL;
00085 _current_node = &_root;
00086 _depth = 0;
00087 _current_iterator = s.begin();
00088 _end_iterator = s.end();
00089
00090 find_longest_rec();
00091
00092 if (_best_node == NULL || _best_node->_content == NULL)
00093 return NULL;
00094
00095 if (res != NULL)
00096 *res = std::string(s.begin(), s.begin() + _best_depth);
00097
00098 return _best_node->_content;
00099 }
00100
00101 template<typename Content>
00102 void Dictionary<Content>::put_word_rec()
00103 {
00104 std::map<int, DictionaryNode<Content> *>::iterator it =
00105 _current_node->_sub_nodes.find(*_current_iterator);
00106 if (it == _current_node->_sub_nodes.end())
00107 _current_node = _current_node->_sub_nodes[*_current_iterator] = new DictionaryNode<Content>();
00108 else
00109 _current_node = it->second;
00110 _current_iterator++;
00111
00112 if (_current_iterator == _end_iterator)
00113 return;
00114 put_word_rec();
00115 }
00116
00117 template<typename Content>
00118 void Dictionary<Content>::find_rec()
00119 {
00120 if (_current_iterator == _end_iterator)
00121 return;
00122
00123 std::map<int, DictionaryNode<Content> *>::iterator it =
00124 _current_node->_sub_nodes.find(*_current_iterator);
00125 if (it != _current_node->_sub_nodes.end())
00126 {
00127 _depth++;
00128 _current_node = it->second;
00129 _current_iterator++;
00130 find_rec();
00131 }
00132 }
00133
00134 template<typename Content>
00135 void Dictionary<Content>::find_shortest_rec()
00136 {
00137 if (_current_node->_content != NULL)
00138 return;
00139 if (_current_iterator == _end_iterator)
00140 return;
00141
00142 std::map<int, DictionaryNode<Content> *>::iterator it =
00143 _current_node->_sub_nodes.find(*_current_iterator);
00144 if (it != _current_node->_sub_nodes.end())
00145 {
00146 _depth++;
00147 _current_node = it->second;
00148 _current_iterator++;
00149 find_shortest_rec();
00150 }
00151 }
00152
00153 template<typename Content>
00154 void Dictionary<Content>::find_longest_rec()
00155 {
00156 if (_current_node->_content != NULL)
00157 {
00158 _best_node = _current_node;
00159 _best_depth = _depth;
00160 }
00161 if (_current_iterator == _end_iterator)
00162 return;
00163
00164 std::map<int, DictionaryNode<Content> *>::iterator it =
00165 _current_node->_sub_nodes.find(*_current_iterator);
00166 if (it != _current_node->_sub_nodes.end())
00167 {
00168 _depth++;
00169 _current_node = it->second;
00170 _current_iterator++;
00171 find_longest_rec();
00172 }
00173 }
00174
00175 template<typename Content>
00176 void Dictionary<Content>::clear_rec(DictionaryNode<Content> &node)
00177 {
00178 for (std::map<int, DictionaryNode<Content> *>::iterator it = node._sub_nodes.begin();
00179 it != node._sub_nodes.end();
00180 it++)
00181 {
00182 clear_rec(*it->second);
00183 }
00184 delete &node;
00185 }
00186 }
00187
00188 #endif
