diff options
Diffstat (limited to 'FoundationEx/Dictionary.inl')
-rw-r--r-- | FoundationEx/Dictionary.inl | 544 |
1 files changed, 284 insertions, 260 deletions
diff --git a/FoundationEx/Dictionary.inl b/FoundationEx/Dictionary.inl index 98cdd05..1f32b9a 100644 --- a/FoundationEx/Dictionary.inl +++ b/FoundationEx/Dictionary.inl @@ -1,260 +1,284 @@ -/* Project FoundationEx
- Destroyer Studios LLC
- Copyright © 1997-2004. All Rights Reserved.
-
- SUBSYSTEM: FoundationEx
- FILE: Dictionary.inl
- AUTHOR: John DiCamillo
-
-
- OVERVIEW
- ========
- Implementation of the Dictionary class
-*/
-
-#ifndef NDEBUG
-#define DICT_CHECK(a, b) if ((a) == 0) throw b;
-#else
-#define DICT_CHECK(a, b)
-#endif
-
-const int CHAINS = 256;
-
-// +-------------------------------------------------------------------+
-
-template <class T> Dictionary<T>::Dictionary()
- : items(0)
-{ init(); }
-
-template <class T> Dictionary<T>::~Dictionary()
-{ clear(); }
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void Dictionary<T>::init()
-{
- items = 0;
- memset(table, 0, CHAINS*sizeof(PTR));
-}
-
-template <class T>
-void Dictionary<T>::clear()
-{
- for (int i = 0; i < CHAINS; i++) {
- DictionaryCell<T>* link = table[i];
-
- while (link) {
- DictionaryCell<T>* n = link->next;
- delete link;
- link = n;
- }
- }
-
- init();
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-T& Dictionary<T>::operator[](const Text& key)
-{
- int idx = key.hash() % CHAINS;
- DictionaryCell<T>* cell = table[idx];
-
- if (cell == 0) { // empty chain
- items++;
-
-#ifdef MEM_DEBUG
- cell = new(__FILE__,__LINE__) DictionaryCell<T>(key);
-#else
- cell = new DictionaryCell<T>(key);
-#endif
-
- table[idx] = cell;
-
- return cell->value;
- }
- else { // search for key
- while (cell->next && cell->key != key)
- cell = cell->next;
-
- if (cell->key != key) { // not found in chain
- items++;
-
-#ifdef MEM_DEBUG
- cell->next = new(__FILE__,__LINE__) DictionaryCell<T>(key);
-#else
- cell->next = new DictionaryCell<T>(key);
-#endif
-
- return cell->next->value;
- }
- else { // found: return it!
- return cell->value;
- }
- }
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void Dictionary<T>::insert(const Text& key, const T& val)
-{
- T& value = operator[](key);
- value = val;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void Dictionary<T>::remove(const Text& key)
-{
- int idx = key.hash() % CHAINS;
- DictionaryCell<T>* cell = table[idx];
-
- if (cell == 0) { // empty chain
- return;
- }
- else { // search for key
- while (cell->next && cell->key != key)
- cell = cell->next;
-
- if (cell->key != key) { // not found in chain
- return;
- }
- else { // found: remove it!
- if (table[idx] == cell) {
- table[idx] = cell->next;
- delete cell;
- }
- else {
- DictionaryCell<T>* p = table[idx];
- while (p->next != cell)
- p = p->next;
- p->next = cell->next;
- delete cell;
- }
- }
- }
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-int Dictionary<T>::contains(const Text& key) const
-{
- int idx = key.hash() % CHAINS;
- DictionaryCell<T>* cell = table[idx];
-
- if (cell != 0) {
- while (cell->next && cell->key != key)
- cell = cell->next;
-
- if (cell->key == key)
- return 1;
- }
-
- return 0;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-T Dictionary<T>::find(const Text& key, T defval) const
-{
- int idx = key.hash() % CHAINS;
- DictionaryCell<T>* cell = table[idx];
-
- if (cell != 0) {
- while (cell->next && cell->key != key)
- cell = cell->next;
-
- if (cell->key == key)
- return cell->value;
- }
-
- return defval;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T> DictionaryIter<T>::DictionaryIter(Dictionary<T>& d)
- : dict(&d), chain(0), here(0)
-{ }
-
-template <class T> DictionaryIter<T>::~DictionaryIter()
-{ }
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void DictionaryIter<T>::reset()
-{
- chain = 0;
- here = 0;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-Text DictionaryIter<T>::key() const
-{
- return here->key;
-}
-
-template <class T>
-T DictionaryIter<T>::value() const
-{
- return here->value;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-int DictionaryIter<T>::operator++()
-{
- forth();
- int more = chain < CHAINS;
- return more;
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void DictionaryIter<T>::forth()
-{
- if (here) {
- here = here->next;
- if (!here) // off the end of this chain
- chain++;
- }
-
- if (!here) {
- while (!dict->table[chain] && chain < CHAINS)
- chain++;
-
- if (chain < CHAINS)
- here = dict->table[chain];
- else
- here = 0;
- }
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-void DictionaryIter<T>::attach(Dictionary<T>& d)
-{
- dict = &d;
- reset();
-}
-
-// +-------------------------------------------------------------------+
-
-template <class T>
-Dictionary<T>& DictionaryIter<T>::container()
-{
- return *dict;
-}
-
+/* Starshatter OpenSource Distribution + Copyright (c) 1997-2004, Destroyer Studios LLC. + All Rights Reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + * Neither the name "Destroyer Studios" nor the names of its contributors + may be used to endorse or promote products derived from this software + without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + POSSIBILITY OF SUCH DAMAGE. + + SUBSYSTEM: FoundationEx + FILE: Dictionary.inl + AUTHOR: John DiCamillo + + + OVERVIEW + ======== + Implementation of the Dictionary class +*/ + +#ifndef NDEBUG +#define DICT_CHECK(a, b) if ((a) == 0) throw b; +#else +#define DICT_CHECK(a, b) +#endif + +const int CHAINS = 256; + +// +-------------------------------------------------------------------+ + +template <class T> Dictionary<T>::Dictionary() + : items(0) +{ init(); } + +template <class T> Dictionary<T>::~Dictionary() +{ clear(); } + +// +-------------------------------------------------------------------+ + +template <class T> +void Dictionary<T>::init() +{ + items = 0; + memset(table, 0, CHAINS*sizeof(PTR)); +} + +template <class T> +void Dictionary<T>::clear() +{ + for (int i = 0; i < CHAINS; i++) { + DictionaryCell<T>* link = table[i]; + + while (link) { + DictionaryCell<T>* n = link->next; + delete link; + link = n; + } + } + + init(); +} + +// +-------------------------------------------------------------------+ + +template <class T> +T& Dictionary<T>::operator[](const Text& key) +{ + int idx = key.hash() % CHAINS; + DictionaryCell<T>* cell = table[idx]; + + if (cell == 0) { // empty chain + items++; + +#ifdef MEM_DEBUG + cell = new(__FILE__,__LINE__) DictionaryCell<T>(key); +#else + cell = new DictionaryCell<T>(key); +#endif + + table[idx] = cell; + + return cell->value; + } + else { // search for key + while (cell->next && cell->key != key) + cell = cell->next; + + if (cell->key != key) { // not found in chain + items++; + +#ifdef MEM_DEBUG + cell->next = new(__FILE__,__LINE__) DictionaryCell<T>(key); +#else + cell->next = new DictionaryCell<T>(key); +#endif + + return cell->next->value; + } + else { // found: return it! + return cell->value; + } + } +} + +// +-------------------------------------------------------------------+ + +template <class T> +void Dictionary<T>::insert(const Text& key, const T& val) +{ + T& value = operator[](key); + value = val; +} + +// +-------------------------------------------------------------------+ + +template <class T> +void Dictionary<T>::remove(const Text& key) +{ + int idx = key.hash() % CHAINS; + DictionaryCell<T>* cell = table[idx]; + + if (cell == 0) { // empty chain + return; + } + else { // search for key + while (cell->next && cell->key != key) + cell = cell->next; + + if (cell->key != key) { // not found in chain + return; + } + else { // found: remove it! + if (table[idx] == cell) { + table[idx] = cell->next; + delete cell; + } + else { + DictionaryCell<T>* p = table[idx]; + while (p->next != cell) + p = p->next; + p->next = cell->next; + delete cell; + } + } + } +} + +// +-------------------------------------------------------------------+ + +template <class T> +int Dictionary<T>::contains(const Text& key) const +{ + int idx = key.hash() % CHAINS; + DictionaryCell<T>* cell = table[idx]; + + if (cell != 0) { + while (cell->next && cell->key != key) + cell = cell->next; + + if (cell->key == key) + return 1; + } + + return 0; +} + +// +-------------------------------------------------------------------+ + +template <class T> +T Dictionary<T>::find(const Text& key, T defval) const +{ + int idx = key.hash() % CHAINS; + DictionaryCell<T>* cell = table[idx]; + + if (cell != 0) { + while (cell->next && cell->key != key) + cell = cell->next; + + if (cell->key == key) + return cell->value; + } + + return defval; +} + +// +-------------------------------------------------------------------+ + +template <class T> DictionaryIter<T>::DictionaryIter(Dictionary<T>& d) + : dict(&d), chain(0), here(0) +{ } + +template <class T> DictionaryIter<T>::~DictionaryIter() +{ } + +// +-------------------------------------------------------------------+ + +template <class T> +void DictionaryIter<T>::reset() +{ + chain = 0; + here = 0; +} + +// +-------------------------------------------------------------------+ + +template <class T> +Text DictionaryIter<T>::key() const +{ + return here->key; +} + +template <class T> +T DictionaryIter<T>::value() const +{ + return here->value; +} + +// +-------------------------------------------------------------------+ + +template <class T> +int DictionaryIter<T>::operator++() +{ + forth(); + int more = chain < CHAINS; + return more; +} + +// +-------------------------------------------------------------------+ + +template <class T> +void DictionaryIter<T>::forth() +{ + if (here) { + here = here->next; + if (!here) // off the end of this chain + chain++; + } + + if (!here) { + while (!dict->table[chain] && chain < CHAINS) + chain++; + + if (chain < CHAINS) + here = dict->table[chain]; + else + here = 0; + } +} + +// +-------------------------------------------------------------------+ + +template <class T> +void DictionaryIter<T>::attach(Dictionary<T>& d) +{ + dict = &d; + reset(); +} + +// +-------------------------------------------------------------------+ + +template <class T> +Dictionary<T>& DictionaryIter<T>::container() +{ + return *dict; +} + |