-////////////////////////////////////////////////////////////////////////////////
-
-// Author: Andy Rushton
-// Copyright: (c) Southampton University 1999-2004
-// (c) Andy Rushton 2004-2009
-// License: BSD License, see ../docs/license.html
-
-////////////////////////////////////////////////////////////////////////////////
-#include <iomanip>
-
-namespace stlplus
-{
-
- ////////////////////////////////////////////////////////////////////////////////
- // the element stored in the hash
-
- template<typename K, typename T, typename H, typename E>
- class hash_element
- {
- public:
- master_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> > m_master;
- std::pair<const K, T> m_value;
- hash_element<K,T,H,E>* m_next;
- unsigned m_hash;
-
- hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) :
- m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash)
- {
- }
-
- hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) :
- m_master(owner,this), m_value(value), m_next(0), m_hash(hash)
- {
- }
-
- ~hash_element(void)
- {
- m_next = 0;
- m_hash = 0;
- }
-
- const hash<K,T,H,E>* owner(void) const
- {
- return m_master.owner();
- }
-
- // generate the bin number from the hash value and the owner's number of bins
- unsigned bin(void) const
- {
- return m_hash % (owner()->m_bins);
- }
- };
-
- ////////////////////////////////////////////////////////////////////////////////
- // iterator
-
- // null constructor
- template<typename K, typename T, class H, class E, typename V>
- hash_iterator<K,T,H,E,V>::hash_iterator(void)
- {
- }
-
- // non-null constructor used from within the hash to construct a valid iterator
- template<typename K, typename T, class H, class E, typename V>
- hash_iterator<K,T,H,E,V>::hash_iterator(hash_element<K,T,H,E>* element) :
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(element->m_master)
- {
- }
-
- // constructor used to create an end iterator
- template<typename K, typename T, class H, class E, typename V>
- hash_iterator<K,T,H,E,V>::hash_iterator(const hash<K,T,H,E>* owner) :
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(owner)
- {
- }
-
- template<typename K, typename T, class H, class E, typename V>
- hash_iterator<K,T,H,E,V>::hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator) :
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(iterator)
- {
- }
-
- // destructor
-
- template<typename K, typename T, class H, class E, typename V>
- hash_iterator<K,T,H,E,V>::~hash_iterator(void)
- {
- }
-
- // mode conversions
-
- template<typename K, typename T, class H, class E, typename V>
- TYPENAME hash_iterator<K,T,H,E,V>::const_iterator hash_iterator<K,T,H,E,V>::constify(void) const
- {
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(*this);
- }
-
- template<typename K, typename T, class H, class E, typename V>
- TYPENAME hash_iterator<K,T,H,E,V>::iterator hash_iterator<K,T,H,E,V>::deconstify(void) const
- {
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(*this);
- }
-
- // increment operator looks for the next element in the table
- // if there isn't one, then this becomes an end() iterator with m_bin = m_bins
- template<typename K, typename T, class H, class E, typename V>
- TYPENAME hash_iterator<K,T,H,E,V>::this_iterator& hash_iterator<K,T,H,E,V>::operator ++ (void)
- throw(null_dereference,end_dereference)
- {
- this->assert_valid();
- if (this->node()->m_next)
- set(this->node()->m_next->m_master);
- else
- {
- // failing that, subsequent hash values are tried until either an element is found or there are no more bins
- // in which case it becomes an end() iterator
- hash_element<K,T,H,E>* element = 0;
- unsigned current_bin = this->node()->bin();
- for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++)
- element = this->owner()->m_values[current_bin];
- if (element)
- set(element->m_master);
- else
- this->set_end();
- }
- return *this;
- }
-
- // post-increment is defined in terms of pre-increment
- template<typename K, typename T, class H, class E, typename V>
- TYPENAME hash_iterator<K,T,H,E,V>::this_iterator hash_iterator<K,T,H,E,V>::operator ++ (int)
- throw(null_dereference,end_dereference)
- {
- hash_iterator<K,T,H,E,V> old(*this);
- ++(*this);
- return old;
- }
-
- // two iterators are equal if they point to the same element
- // both iterators must be non-null and belong to the same table
- template<typename K, typename T, class H, class E, typename V>
- bool hash_iterator<K,T,H,E,V>::operator == (const hash_iterator<K,T,H,E,V>& r) const
- {
- return equal(r);
- }
-
- template<typename K, typename T, class H, class E, typename V>
- bool hash_iterator<K,T,H,E,V>::operator != (const hash_iterator<K,T,H,E,V>& r) const
- {
- return !operator==(r);
- }
-
- template<typename K, typename T, class H, class E, typename V>
- bool hash_iterator<K,T,H,E,V>::operator < (const hash_iterator<K,T,H,E,V>& r) const
- {
- return compare(r) < 0;
- }
-
- // iterator dereferencing is only legal on a non-null iterator
- template<typename K, typename T, class H, class E, typename V>
- V& hash_iterator<K,T,H,E,V>::operator*(void) const
- throw(null_dereference,end_dereference)
- {
- this->assert_valid();
- return this->node()->m_value;
- }
-
- template<typename K, typename T, class H, class E, typename V>
- V* hash_iterator<K,T,H,E,V>::operator->(void) const
- throw(null_dereference,end_dereference)
- {
- return &(operator*());
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // hash
-
- // totally arbitrary initial size used for auto-rehashed tables
- static unsigned hash_default_bins = 127;
-
- // constructor
- // tests whether the user wants auto-rehash
- // sets the rehash point to be a loading of 1.0 by setting it to the number of bins
- // uses the user's size unless this is zero, in which case implement the default
-
- template<typename K, typename T, class H, class E>
- hash<K,T,H,E>::hash(unsigned bins) :
- m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0)
- {
- m_values = new hash_element<K,T,H,E>*[m_bins];
- for (unsigned i = 0; i < m_bins; i++)
- m_values[i] = 0;
- }
-
- template<typename K, typename T, class H, class E>
- hash<K,T,H,E>::~hash(void)
- {
- // delete all the elements
- clear();
- // and delete the data structure
- delete[] m_values;
- m_values = 0;
- }
-
- // as usual, implement the copy constructor i.t.o. the assignment operator
-
- template<typename K, typename T, class H, class E>
- hash<K,T,H,E>::hash(const hash<K,T,H,E>& right) :
- m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0)
- {
- m_values = new hash_element<K,T,H,E>*[right.m_bins];
- // copy the rehash behaviour as well as the size
- for (unsigned i = 0; i < m_bins; i++)
- m_values[i] = 0;
- *this = right;
- }
-
- // assignment operator
- // this is done by copying the elements
- // the source and target hashes can be different sizes
- // the hash is self-copy safe, i.e. it is legal to say x = x;
-
- template<typename K, typename T, class H, class E>
- hash<K,T,H,E>& hash<K,T,H,E>::operator = (const hash<K,T,H,E>& r)
- {
- // make self-copy safe
- if (&r == this) return *this;
- // remove all the existing elements
- clear();
- // copy the elements across - remember that this is rehashing because the two
- // tables can be different sizes so there is no quick way of doing this by
- // copying the lists
- for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = r.begin(); i != r.end(); ++i)
- insert(i->first, i->second);
- return *this;
- }
-
- // number of values in the hash
- template<typename K, typename T, class H, class E>
- bool hash<K,T,H,E>::empty(void) const
- {
- return m_size == 0;
- }
-
- template<typename K, typename T, class H, class E>
- unsigned hash<K,T,H,E>::size(void) const
- {
- return m_size;
- }
-
- // equality
- template<typename K, typename T, class H, class E>
- bool hash<K,T,H,E>::operator == (const hash<K,T,H,E>& right) const
- {
- // this table is the same as the right table if they are the same table!
- if (&right == this) return true;
- // they must be the same size to be equal
- if (m_size != right.m_size) return false;
- // now every key in this must be in right and have the same data
- for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = begin(); i != end(); i++)
- {
- hash_iterator<K,T,H,E,const std::pair<const K,T> > found = right.find(i->first);
- if (found == right.end()) return false;
- if (!(i->second == found->second)) return false;
- }
- return true;
- }
-
- // set up the hash to auto-rehash at a specific size
- // setting the rehash size to 0 forces manual rehashing
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::auto_rehash(void)
- {
- m_rehash = m_bins;
- }
-
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::manual_rehash(void)
- {
- m_rehash = 0;
- }
-
- // the rehash function
- // builds a new hash table and moves the elements (without copying) from the old to the new
- // I store the un-modulused hash value in the element for more efficient rehashing
- // passing 0 to the bins parameter does auto-rehashing
- // passing any other value forces the number of bins
-
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::rehash(unsigned bins)
- {
- // user specified size: just take the user's value
- // auto calculate: if the load is high, increase the size; else do nothing
- unsigned new_bins = bins ? bins : m_bins;
- if (bins == 0 && m_size > 0)
- {
- // these numbers are pretty arbitrary
- // TODO - make them user-customisable?
- float load = loading();
- if (load > 2.0)
- new_bins = (unsigned)(m_bins * load);
- else if (load > 1.0)
- new_bins = m_bins * 2;
- }
- if (new_bins == m_bins) return;
- // set the new rehashing point if auto-rehashing is on
- if (m_rehash) m_rehash = new_bins;
- // move aside the old structure
- hash_element<K,T,H,E>** old_values = m_values;
- unsigned old_bins = m_bins;
- // create a replacement structure
- m_values = new hash_element<K,T,H,E>*[new_bins];
- for (unsigned i = 0; i < new_bins; i++)
- m_values[i] = 0;
- m_bins = new_bins;
- // move all the old elements across, rehashing each one
- for (unsigned j = 0; j < old_bins; j++)
- {
- while(old_values[j])
- {
- // unhook from the old structure
- hash_element<K,T,H,E>* current = old_values[j];
- old_values[j] = current->m_next;
- // rehash using the stored hash value
- unsigned bin = current->bin();
- // hook it into the new structure
- current->m_next = m_values[bin];
- m_values[bin] = current;
- }
- }
- // now delete the old structure
- delete[] old_values;
- }
-
- // the loading is the average number of elements per bin
- // this simplifies to the total elements divided by the number of bins
-
- template<typename K, typename T, class H, class E>
- float hash<K,T,H,E>::loading(void) const
- {
- return (float)m_size / (float)m_bins;
- }
-
- // remove all elements from the table
-
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::erase(void)
- {
- // unhook the list elements and destroy them
- for (unsigned i = 0; i < m_bins; i++)
- {
- hash_element<K,T,H,E>* current = m_values[i];
- while(current)
- {
- hash_element<K,T,H,E>* next = current->m_next;
- delete current;
- current = next;
- }
- m_values[i] = 0;
- }
- m_size = 0;
- }
-
- // test for whether a key is present in the table
-
- template<typename K, typename T, class H, class E>
- bool hash<K,T,H,E>::present(const K& key) const
- {
- return find(key) != end();
- }
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::size_type hash<K,T,H,E>::count(const K& key) const
- {
- return present() ? 1 : 0;
- }
-
- // add a key and data element to the table - defined in terms of the general-purpose pair insert function
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key, const T& data)
- {
- return insert(std::pair<const K,T>(key,data)).first;
- }
-
- // insert a key/data pair into the table
- // this removes any old value with the same key since there is no multihash functionality
-
- template<typename K, typename T, class H, class E>
- std::pair<TYPENAME hash<K,T,H,E>::iterator, bool> hash<K,T,H,E>::insert(const std::pair<const K,T>& value)
- {
- // if auto-rehash is enabled, implement the auto-rehash before inserting the new value
- // the table is rehashed if this insertion makes the loading exceed 1.0
- if (m_rehash && (m_size >= m_rehash)) rehash();
- // calculate the new hash value
- unsigned hash_value_full = H()(value.first);
- unsigned bin = hash_value_full % m_bins;
- bool inserted = true;
- // unhook any previous value with this key
- // this has been inlined from erase(key) so that the hash value is not calculated twice
- hash_element<K,T,H,E>* previous = 0;
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)
- {
- // first check the full stored hash value
- if (current->m_hash != hash_value_full) continue;
-
- // next try the equality operator
- if (!E()(current->m_value.first, value.first)) continue;
-
- // unhook this value and destroy it
- if (previous)
- previous->m_next = current->m_next;
- else
- m_values[bin] = current->m_next;
- delete current;
- m_size--;
-
- // we've overwritten a previous value
- inserted = false;
-
- // assume there can only be one match so we can give up now
- break;
- }
- // now hook in a new list element at the start of the list for this hash value
- hash_element<K,T,H,E>* new_item = new hash_element<K,T,H,E>(this, value, hash_value_full);
- new_item->m_next = m_values[bin];
- m_values[bin] = new_item;
- // increment the size count
- m_size++;
- // construct an iterator from the list node, and return whether inserted
- return std::make_pair(hash_iterator<K,T,H,E,std::pair<const K,T> >(new_item), inserted);
- }
-
- // insert a key with an empty data field ready to be filled in later
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key)
- {
- return insert(key,T());
- }
-
- // remove a key from the table - return true if the key was found and removed, false if it wasn't present
-
- template<typename K, typename T, class H, class E>
- unsigned hash<K,T,H,E>::erase(const K& key)
- {
- unsigned hash_value_full = H()(key);
- unsigned bin = hash_value_full % m_bins;
- // scan the list for an element with this key
- // need to keep a previous pointer because the lists are single-linked
- hash_element<K,T,H,E>* previous = 0;
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)
- {
- // first check the full stored hash value
- if (current->m_hash != hash_value_full) continue;
-
- // next try the equality operator
- if (!E()(current->m_value.first, key)) continue;
-
- // found this key, so unhook the element from the list
- if (previous)
- previous->m_next = current->m_next;
- else
- m_values[bin] = current->m_next;
- // destroy it
- delete current;
- // remember to maintain the size count
- m_size--;
- return 1;
- }
- return 0;
- }
-
- // remove an element from the hash table using an iterator (std::map equivalent)
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::erase(TYPENAME hash<K,T,H,E>::iterator it)
- {
- // work out what the next iterator is in order to return it later
- TYPENAME hash<K,T,H,E>::iterator next(it);
- ++next;
- // we now need to find where this item is - made difficult by the use of
- // single-linked lists which means I have to search through the bin from
- // the top in order to unlink from the list.
- unsigned hash_value_full = it.node()->m_hash;
- unsigned bin = hash_value_full % m_bins;
- // scan the list for this element
- // need to keep a previous pointer because the lists are single-linked
- hash_element<K,T,H,E>* previous = 0;
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)
- {
- // direct test on the address of the element
- if (current != it.node()) continue;
- // found this iterator, so unhook the element from the list
- if (previous)
- previous->m_next = current->m_next;
- else
- m_values[bin] = current->m_next;
- // destroy it
- delete current;
- current = 0;
- // remember to maintain the size count
- m_size--;
- break;
- }
- return next;
- }
-
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::clear(void)
- {
- erase();
- }
-
- // search for a key in the table and return an iterator to it
- // if the search fails, returns an end() iterator
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::find(const K& key) const
- {
- // scan the list for this key's hash value for the element with a matching key
- unsigned hash_value_full = H()(key);
- unsigned bin = hash_value_full % m_bins;
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)
- {
- if (current->m_hash == hash_value_full && E()(current->m_value.first, key))
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(current);
- }
- return end();
- }
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::find(const K& key)
- {
- // scan the list for this key's hash value for the element with a matching key
- unsigned hash_value_full = H()(key);
- unsigned bin = hash_value_full % m_bins;
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)
- {
- if (current->m_hash == hash_value_full && E()(current->m_value.first, key))
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(current);
- }
- return end();
- }
-
- // table lookup by key using the index operator[], returning a reference to the data field, not an iterator
- // this is rather like the std::map's [] operator
- // the difference is that I have a const and non-const version
- // the const version will not create the element if not present already, but the non-const version will
- // the non-const version is compatible with the behaviour of the map
-
- template<typename K, typename T, class H, class E>
- const T& hash<K,T,H,E>::operator[] (const K& key) const throw(std::out_of_range)
- {
- // this const version cannot change the hash, so has to raise an exception if the key is missing
- hash_iterator<K,T,H,E,const std::pair<const K,T> > found = find(key);
- if (found == end())
- throw std::out_of_range("key not found in stlplus::hash::operator[]");
- return found->second;
- }
-
- template<typename K, typename T, class H, class E>
- T& hash<K,T,H,E>::operator[] (const K& key)
- {
- // this non-const version can change the hash, so creates a new element if the key is missing
- hash_iterator<K,T,H,E,std::pair<const K,T> > found = find(key);
- if (found == end())
- found = insert(key);
- return found->second;
- }
-
- // iterators
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::begin(void) const
- {
- // find the first element
- for (unsigned bin = 0; bin < m_bins; bin++)
- if (m_values[bin])
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(m_values[bin]);
- // if the hash is empty, return the end iterator
- return end();
- }
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::begin(void)
- {
- // find the first element
- for (unsigned bin = 0; bin < m_bins; bin++)
- if (m_values[bin])
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(m_values[bin]);
- // if the hash is empty, return the end iterator
- return end();
- }
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::end(void) const
- {
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(this);
- }
-
- template<typename K, typename T, class H, class E>
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::end(void)
- {
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(this);
- }
-
- template<typename K, typename T, class H, class E>
- void hash<K,T,H,E>::debug_report(std::ostream& str) const
- {
- // calculate some stats first
- unsigned occupied = 0;
- unsigned min_in_bin = m_size;
- unsigned max_in_bin = 0;
- for (unsigned i = 0; i < m_bins; i++)
- {
- if (m_values[i]) occupied++;
- unsigned count = 0;
- for (hash_element<K,T,H,E>* item = m_values[i]; item; item = item->m_next) count++;
- if (count > max_in_bin) max_in_bin = count;
- if (count < min_in_bin) min_in_bin = count;
- }
- // now print the table
- str << "------------------------------------------------------------------------" << std::endl;
- str << "| size: " << m_size << std::endl;
- str << "| bins: " << m_bins << std::endl;
- str << "| loading: " << loading() << " ";
- if (m_rehash)
- str << "auto-rehash at " << m_rehash << std::endl;
- else
- str << "manual rehash" << std::endl;
- str << "| occupied: " << occupied
- << std::fixed << " (" << (100.0*(float)occupied/(float)m_bins) << "%)" << std::scientific
- << ", min = " << min_in_bin << ", max = " << max_in_bin << std::endl;
- str << "|-----------------------------------------------------------------------" << std::endl;
- str << "| bin 0 1 2 3 4 5 6 7 8 9" << std::endl;
- str << "| ---------------------------------------------------------------";
- for (unsigned j = 0; j < m_bins; j++)
- {
- if (j % 10 == 0)
- {
- str << std::endl;
- str << "| " << std::setw(6) << std::right << (j/10*10) << std::left << " |";
- }
- unsigned count = 0;
- for (hash_element<K,T,H,E>* item = m_values[j]; item; item = item->m_next) count++;
- if (!count)
- str << " .";
- else
- str << std::setw(6) << std::right << count << std::left;
- }
- str << std::endl;
- str << "------------------------------------------------------------------------" << std::endl;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
-
-} // end namespace stlplus
-
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004 onwards\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include <iomanip>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the element stored in the hash\r
+\r
+ template<typename K, typename T, typename H, typename E>\r
+ class hash_element\r
+ {\r
+ public:\r
+ master_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> > m_master;\r
+ std::pair<const K, T> m_value;\r
+ hash_element<K,T,H,E>* m_next;\r
+ unsigned m_hash;\r
+\r
+ hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) :\r
+ m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash)\r
+ {\r
+ }\r
+\r
+ hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) :\r
+ m_master(owner,this), m_value(value), m_next(0), m_hash(hash)\r
+ {\r
+ }\r
+\r
+ ~hash_element(void)\r
+ {\r
+ m_next = 0;\r
+ m_hash = 0;\r
+ }\r
+\r
+ const hash<K,T,H,E>* owner(void) const\r
+ {\r
+ return m_master.owner();\r
+ }\r
+\r
+ // generate the bin number from the hash value and the owner's number of bins\r
+ unsigned bin(void) const\r
+ {\r
+ return m_hash % (owner()->m_bins);\r
+ }\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // iterator\r
+\r
+ // null constructor\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(void)\r
+ {\r
+ }\r
+\r
+ // non-null constructor used from within the hash to construct a valid iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(hash_element<K,T,H,E>* element) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(element->m_master)\r
+ {\r
+ }\r
+\r
+ // constructor used to create an end iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(const hash<K,T,H,E>* owner) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(owner)\r
+ {\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(iterator)\r
+ {\r
+ }\r
+\r
+ // destructor\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::~hash_iterator(void)\r
+ {\r
+ }\r
+\r
+ // mode conversions\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::const_iterator hash_iterator<K,T,H,E,V>::constify(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(*this);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::iterator hash_iterator<K,T,H,E,V>::deconstify(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(*this);\r
+ }\r
+\r
+ // increment operator looks for the next element in the table\r
+ // if there isn't one, then this becomes an end() iterator with m_bin = m_bins\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::this_iterator& hash_iterator<K,T,H,E,V>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_next)\r
+ set(this->node()->m_next->m_master);\r
+ else\r
+ {\r
+ // failing that, subsequent hash values are tried until either an element is found or there are no more bins\r
+ // in which case it becomes an end() iterator\r
+ hash_element<K,T,H,E>* element = 0;\r
+ unsigned current_bin = this->node()->bin();\r
+ for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++)\r
+ element = this->owner()->m_values[current_bin];\r
+ if (element)\r
+ set(element->m_master);\r
+ else\r
+ this->set_end();\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ // post-increment is defined in terms of pre-increment\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::this_iterator hash_iterator<K,T,H,E,V>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ hash_iterator<K,T,H,E,V> old(*this);\r
+ ++(*this);\r
+ return old;\r
+ }\r
+\r
+ // two iterators are equal if they point to the same element\r
+ // both iterators must be non-null and belong to the same table\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator == (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator != (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator < (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ // iterator dereferencing is only legal on a non-null iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ V& hash_iterator<K,T,H,E,V>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_value;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ V* hash_iterator<K,T,H,E,V>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // hash\r
+\r
+ // totally arbitrary initial size used for auto-rehashed tables\r
+ static unsigned hash_default_bins = 127;\r
+\r
+ // constructor\r
+ // tests whether the user wants auto-rehash\r
+ // sets the rehash point to be a loading of 1.0 by setting it to the number of bins\r
+ // uses the user's size unless this is zero, in which case implement the default\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::hash(unsigned bins) :\r
+ m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0)\r
+ {\r
+ m_values = new hash_element<K,T,H,E>*[m_bins];\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ m_values[i] = 0;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::~hash(void)\r
+ {\r
+ // delete all the elements\r
+ clear();\r
+ // and delete the data structure\r
+ delete[] m_values;\r
+ m_values = 0;\r
+ }\r
+\r
+ // as usual, implement the copy constructor i.t.o. the assignment operator\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::hash(const hash<K,T,H,E>& right) :\r
+ m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0)\r
+ {\r
+ m_values = new hash_element<K,T,H,E>*[right.m_bins];\r
+ // copy the rehash behaviour as well as the size\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ m_values[i] = 0;\r
+ *this = right;\r
+ }\r
+\r
+ // assignment operator\r
+ // this is done by copying the elements\r
+ // the source and target hashes can be different sizes\r
+ // the hash is self-copy safe, i.e. it is legal to say x = x;\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>& hash<K,T,H,E>::operator = (const hash<K,T,H,E>& r)\r
+ {\r
+ // make self-copy safe\r
+ if (&r == this) return *this;\r
+ // remove all the existing elements\r
+ clear();\r
+ // copy the elements across - remember that this is rehashing because the two\r
+ // tables can be different sizes so there is no quick way of doing this by\r
+ // copying the lists\r
+ for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = r.begin(); i != r.end(); ++i)\r
+ insert(i->first, i->second);\r
+ return *this;\r
+ }\r
+\r
+ // number of values in the hash\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::empty(void) const\r
+ {\r
+ return m_size == 0;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ unsigned hash<K,T,H,E>::size(void) const\r
+ {\r
+ return m_size;\r
+ }\r
+\r
+ // equality\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::operator == (const hash<K,T,H,E>& right) const\r
+ {\r
+ // this table is the same as the right table if they are the same table!\r
+ if (&right == this) return true;\r
+ // they must be the same size to be equal\r
+ if (m_size != right.m_size) return false;\r
+ // now every key in this must be in right and have the same data\r
+ for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = begin(); i != end(); i++)\r
+ {\r
+ hash_iterator<K,T,H,E,const std::pair<const K,T> > found = right.find(i->first);\r
+ if (found == right.end()) return false;\r
+ if (!(i->second == found->second)) return false;\r
+ }\r
+ return true;\r
+ }\r
+\r
+ // set up the hash to auto-rehash at a specific size\r
+ // setting the rehash size to 0 forces manual rehashing\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::auto_rehash(void)\r
+ {\r
+ m_rehash = m_bins;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::manual_rehash(void)\r
+ {\r
+ m_rehash = 0;\r
+ }\r
+\r
+ // the rehash function\r
+ // builds a new hash table and moves the elements (without copying) from the old to the new\r
+ // I store the un-modulused hash value in the element for more efficient rehashing\r
+ // passing 0 to the bins parameter does auto-rehashing\r
+ // passing any other value forces the number of bins\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::rehash(unsigned bins)\r
+ {\r
+ // user specified size: just take the user's value\r
+ // auto calculate: if the load is high, increase the size; else do nothing\r
+ unsigned new_bins = bins ? bins : m_bins;\r
+ if (bins == 0 && m_size > 0)\r
+ {\r
+ // these numbers are pretty arbitrary\r
+ // TODO - make them user-customisable?\r
+ float load = loading();\r
+ if (load > 2.0)\r
+ new_bins = (unsigned)(m_bins * load);\r
+ else if (load > 1.0)\r
+ new_bins = m_bins * 2;\r
+ }\r
+ if (new_bins == m_bins) return;\r
+ // set the new rehashing point if auto-rehashing is on\r
+ if (m_rehash) m_rehash = new_bins;\r
+ // move aside the old structure\r
+ hash_element<K,T,H,E>** old_values = m_values;\r
+ unsigned old_bins = m_bins;\r
+ // create a replacement structure\r
+ m_values = new hash_element<K,T,H,E>*[new_bins];\r
+ for (unsigned i = 0; i < new_bins; i++)\r
+ m_values[i] = 0;\r
+ m_bins = new_bins;\r
+ // move all the old elements across, rehashing each one\r
+ for (unsigned j = 0; j < old_bins; j++)\r
+ {\r
+ while(old_values[j])\r
+ {\r
+ // unhook from the old structure\r
+ hash_element<K,T,H,E>* current = old_values[j];\r
+ old_values[j] = current->m_next;\r
+ // rehash using the stored hash value\r
+ unsigned bin = current->bin();\r
+ // hook it into the new structure\r
+ current->m_next = m_values[bin];\r
+ m_values[bin] = current;\r
+ }\r
+ }\r
+ // now delete the old structure\r
+ delete[] old_values;\r
+ }\r
+\r
+ // the loading is the average number of elements per bin\r
+ // this simplifies to the total elements divided by the number of bins\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ float hash<K,T,H,E>::loading(void) const\r
+ {\r
+ return (float)m_size / (float)m_bins;\r
+ }\r
+\r
+ // remove all elements from the table\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::erase(void)\r
+ {\r
+ // unhook the list elements and destroy them\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ {\r
+ hash_element<K,T,H,E>* current = m_values[i];\r
+ while(current)\r
+ {\r
+ hash_element<K,T,H,E>* next = current->m_next;\r
+ delete current;\r
+ current = next;\r
+ }\r
+ m_values[i] = 0;\r
+ }\r
+ m_size = 0;\r
+ }\r
+\r
+ // test for whether a key is present in the table\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::present(const K& key) const\r
+ {\r
+ return find(key) != end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::size_type hash<K,T,H,E>::count(const K& key) const\r
+ {\r
+ return present() ? 1 : 0;\r
+ }\r
+\r
+ // add a key and data element to the table - defined in terms of the general-purpose pair insert function\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key, const T& data)\r
+ {\r
+ return insert(std::pair<const K,T>(key,data)).first;\r
+ }\r
+\r
+ // insert a key/data pair into the table\r
+ // this removes any old value with the same key since there is no multihash functionality\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ std::pair<TYPENAME hash<K,T,H,E>::iterator, bool> hash<K,T,H,E>::insert(const std::pair<const K,T>& value)\r
+ {\r
+ // if auto-rehash is enabled, implement the auto-rehash before inserting the new value\r
+ // the table is rehashed if this insertion makes the loading exceed 1.0\r
+ if (m_rehash && (m_size >= m_rehash)) rehash();\r
+ // calculate the new hash value\r
+ unsigned hash_value_full = H()(value.first);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ bool inserted = true;\r
+ // unhook any previous value with this key\r
+ // this has been inlined from erase(key) so that the hash value is not calculated twice\r
+ hash_element<K,T,H,E>* previous = 0;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+ {\r
+ // first check the full stored hash value\r
+ if (current->m_hash != hash_value_full) continue;\r
+\r
+ // next try the equality operator\r
+ if (!E()(current->m_value.first, value.first)) continue;\r
+\r
+ // unhook this value and destroy it\r
+ if (previous)\r
+ previous->m_next = current->m_next;\r
+ else\r
+ m_values[bin] = current->m_next;\r
+ delete current;\r
+ m_size--;\r
+\r
+ // we've overwritten a previous value\r
+ inserted = false;\r
+\r
+ // assume there can only be one match so we can give up now\r
+ break;\r
+ }\r
+ // now hook in a new list element at the start of the list for this hash value\r
+ hash_element<K,T,H,E>* new_item = new hash_element<K,T,H,E>(this, value, hash_value_full);\r
+ new_item->m_next = m_values[bin];\r
+ m_values[bin] = new_item;\r
+ // increment the size count\r
+ m_size++;\r
+ // construct an iterator from the list node, and return whether inserted\r
+ return std::make_pair(hash_iterator<K,T,H,E,std::pair<const K,T> >(new_item), inserted);\r
+ }\r
+\r
+ // insert a key with an empty data field ready to be filled in later\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key)\r
+ {\r
+ return insert(key,T());\r
+ }\r
+\r
+ // remove a key from the table - return true if the key was found and removed, false if it wasn't present\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ unsigned hash<K,T,H,E>::erase(const K& key)\r
+ {\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ // scan the list for an element with this key\r
+ // need to keep a previous pointer because the lists are single-linked\r
+ hash_element<K,T,H,E>* previous = 0;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+ {\r
+ // first check the full stored hash value\r
+ if (current->m_hash != hash_value_full) continue;\r
+\r
+ // next try the equality operator\r
+ if (!E()(current->m_value.first, key)) continue;\r
+\r
+ // found this key, so unhook the element from the list\r
+ if (previous)\r
+ previous->m_next = current->m_next;\r
+ else\r
+ m_values[bin] = current->m_next;\r
+ // destroy it\r
+ delete current;\r
+ // remember to maintain the size count\r
+ m_size--;\r
+ return 1;\r
+ }\r
+ return 0;\r
+ }\r
+\r
+ // remove an element from the hash table using an iterator (std::map equivalent)\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::erase(TYPENAME hash<K,T,H,E>::iterator it)\r
+ {\r
+ // work out what the next iterator is in order to return it later\r
+ TYPENAME hash<K,T,H,E>::iterator next(it);\r
+ ++next;\r
+ // we now need to find where this item is - made difficult by the use of\r
+ // single-linked lists which means I have to search through the bin from\r
+ // the top in order to unlink from the list.\r
+ unsigned hash_value_full = it.node()->m_hash;\r
+ unsigned bin = hash_value_full % m_bins;\r
+ // scan the list for this element\r
+ // need to keep a previous pointer because the lists are single-linked\r
+ hash_element<K,T,H,E>* previous = 0;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+ {\r
+ // direct test on the address of the element\r
+ if (current != it.node()) continue;\r
+ // found this iterator, so unhook the element from the list\r
+ if (previous)\r
+ previous->m_next = current->m_next;\r
+ else\r
+ m_values[bin] = current->m_next;\r
+ // destroy it\r
+ delete current;\r
+ current = 0;\r
+ // remember to maintain the size count\r
+ m_size--;\r
+ break;\r
+ }\r
+ return next;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::clear(void)\r
+ {\r
+ erase();\r
+ }\r
+\r
+ // search for a key in the table and return an iterator to it\r
+ // if the search fails, returns an end() iterator\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::find(const K& key) const\r
+ {\r
+ // scan the list for this key's hash value for the element with a matching key\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
+ {\r
+ if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(current);\r
+ }\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::find(const K& key)\r
+ {\r
+ // scan the list for this key's hash value for the element with a matching key\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
+ {\r
+ if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(current);\r
+ }\r
+ return end();\r
+ }\r
+\r
+ // table lookup by key using the index operator[], returning a reference to the data field, not an iterator\r
+ // this is rather like the std::map's [] operator\r
+ // the difference is that I have a const and non-const version\r
+ // the const version will not create the element if not present already, but the non-const version will\r
+ // the non-const version is compatible with the behaviour of the map\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ const T& hash<K,T,H,E>::operator[] (const K& key) const throw(std::out_of_range)\r
+ {\r
+ // this const version cannot change the hash, so has to raise an exception if the key is missing\r
+ hash_iterator<K,T,H,E,const std::pair<const K,T> > found = find(key);\r
+ if (found == end())\r
+ throw std::out_of_range("key not found in stlplus::hash::operator[]");\r
+ return found->second;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ T& hash<K,T,H,E>::operator[] (const K& key)\r
+ {\r
+ // this non-const version can change the hash, so creates a new element if the key is missing\r
+ hash_iterator<K,T,H,E,std::pair<const K,T> > found = find(key);\r
+ if (found == end())\r
+ found = insert(key);\r
+ return found->second;\r
+ }\r
+\r
+ // iterators\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::begin(void) const\r
+ {\r
+ // find the first element\r
+ for (unsigned bin = 0; bin < m_bins; bin++)\r
+ if (m_values[bin])\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(m_values[bin]);\r
+ // if the hash is empty, return the end iterator\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::begin(void)\r
+ {\r
+ // find the first element\r
+ for (unsigned bin = 0; bin < m_bins; bin++)\r
+ if (m_values[bin])\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(m_values[bin]);\r
+ // if the hash is empty, return the end iterator\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::end(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(this);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::end(void)\r
+ {\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(this);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::debug_report(std::ostream& str) const\r
+ {\r
+ // calculate some stats first\r
+ unsigned occupied = 0;\r
+ unsigned min_in_bin = m_size;\r
+ unsigned max_in_bin = 0;\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ {\r
+ if (m_values[i]) occupied++;\r
+ unsigned count = 0;\r
+ for (hash_element<K,T,H,E>* item = m_values[i]; item; item = item->m_next) count++;\r
+ if (count > max_in_bin) max_in_bin = count;\r
+ if (count < min_in_bin) min_in_bin = count;\r
+ }\r
+ // now print the table\r
+ str << "------------------------------------------------------------------------" << std::endl;\r
+ str << "| size: " << m_size << std::endl;\r
+ str << "| bins: " << m_bins << std::endl;\r
+ str << "| loading: " << loading() << " ";\r
+ if (m_rehash)\r
+ str << "auto-rehash at " << m_rehash << std::endl;\r
+ else\r
+ str << "manual rehash" << std::endl;\r
+ str << "| occupied: " << occupied \r
+ << std::fixed << " (" << (100.0*(float)occupied/(float)m_bins) << "%)" << std::scientific\r
+ << ", min = " << min_in_bin << ", max = " << max_in_bin << std::endl;\r
+ str << "|-----------------------------------------------------------------------" << std::endl;\r
+ str << "| bin 0 1 2 3 4 5 6 7 8 9" << std::endl;\r
+ str << "| ---------------------------------------------------------------";\r
+ for (unsigned j = 0; j < m_bins; j++)\r
+ {\r
+ if (j % 10 == 0)\r
+ {\r
+ str << std::endl;\r
+ str << "| " << std::setw(6) << std::right << (j/10*10) << std::left << " |";\r
+ }\r
+ unsigned count = 0;\r
+ for (hash_element<K,T,H,E>* item = m_values[j]; item; item = item->m_next) count++;\r
+ if (!count)\r
+ str << " .";\r
+ else\r
+ str << std::setw(6) << std::right << count << std::left;\r
+ }\r
+ str << std::endl;\r
+ str << "------------------------------------------------------------------------" << std::endl;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
projects / chaz / yoink / blobdiff