//====================================================================== // Copyright (C) 2002 Daniel Heck // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 2 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License along // with this program; if not, write to the Free Software Foundation, Inc., // 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA. //====================================================================== #ifndef PX_DICT_HH #define PX_DICT_HH #include "error.hh" #include #include namespace px { extern unsigned hash(const std::string &key); template class Dict { // // Types // public: typedef std::pair value_type; typedef std::string key_type; typedef int size_type; private: struct Entry { Entry(const std::string &k, const T &v) : pair(k,v) {} value_type pair; Entry *next; }; template class Iter { public: typedef U value_type; typedef ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; typedef value_type &reference; typedef value_type *pointer; Iter() : dict(0), idx(0), cur(0) {} Iter(const Dict *d, size_type i, Entry *c) : dict(d),idx(i),cur(c) {} Iter(const Dict *d) :dict(d) { for (idx=0; idxnbuckets; ++idx) if ((cur=dict->hashtab[idx]) != 0) return; dict = 0; // End idx=0; } bool operator==(const Iter &i) { return dict==i.dict && idx==i.idx && cur==i.cur; } bool operator!=(const Iter &i) { return !this->operator==(i); } reference operator*() {return cur->pair;} pointer operator->() {return &cur->pair;} Iter &operator++() { if ((cur=cur->next) == 0) { for (++idx; idxnbuckets; ++idx) if ((cur=dict->hashtab[idx]) != 0) return *this; dict = 0; cur=0; idx=0; } return *this; } Iter &operator++(int) { Iter tmp=*this; ++*this; return tmp; } private: const Dict *dict; size_type idx; Entry *cur; }; // // Iterator access // public: typedef Iter iterator; typedef Iter const_iterator; friend class iterator; friend class const_iterator; iterator begin() { return iterator(this); } iterator end() { return iterator(); } const_iterator begin() const { return const_iterator(this); } const_iterator end() const { return const_iterator(); } // // Construction / destruction // Dict(size_type table_size = 257) : nentries(0), nbuckets (table_size), hashtab (new Entry*[nbuckets]) { for (size_type i=0; i &d) : nentries(d.nentries) , nbuckets(d.nbuckets) , hashtab(new Entry*[nbuckets]) { for (size_type i=0; i &d); public: ~Dict() { clear(); delete [] hashtab; } size_type size() const { return nentries; } // // Lookup of keys // iterator find (const std::string &key) { unsigned h = hash(key) % nbuckets; for (Entry *e = hashtab[h]; e != 0; e=e->next) if (e->pair.first == key) return iterator(this, h, e); return end(); } const_iterator find (const std::string &key) const { unsigned h = hash(key) % nbuckets; for (Entry *e = hashtab[h]; e != 0; e=e->next) if (e->pair.first == key) return const_iterator(this, h, e); return end(); } T &lookup(const std::string &key) { Entry *e = find_entry(key); // if (!e) throw XInvalidKey(); return e->pair.second; } T &operator[] (const std::string &key) { return lookup(key); } const T& lookup(const std::string &key) const { Entry *e = find_entry(key); if (!e) throw XInvalidKey(); return e->pair.second; } const T& operator[] (const std::string &key) const { return lookup(key); } // // Insertion of new elements. // void insert(const std::string &key, const T &val) { unsigned h = hash(key) % nbuckets; Entry *e = new Entry(key, val); e->next = hashtab[h]; hashtab[h] = e; nentries += 1; } // // Removal of all or specific elements // void clear() { for (int i=0; inext; delete cur; } hashtab[i] = 0; } nentries = 0; } void remove(const std::string &key) { unsigned h = hash(key) % nbuckets; Entry *e = hashtab[h]; Entry **eptr = &hashtab[h]; while (e != 0) { if (e->pair.first == key) { *eptr = e->next; // Modify pointer referring to e delete e; nentries -= 1; break; } e = e->next; eptr = &e->next; } } bool has_key(const std::string &key) { return find_entry(key) != 0; } private: Entry *find_entry(const std::string &key) { unsigned h = hash(key) % nbuckets; for (Entry *e = hashtab[h]; e != 0; e=e->next) if (e->pair.first == key) return e; return 0; } size_type nentries; // Number of entries size_type nbuckets; // Number of buckets in `hashtab' Entry **hashtab; }; } #endif