Teuchos_HashSet.hpp

Go to the documentation of this file.

// @HEADER
// *****************************************************************************
//                    Teuchos: Common Tools Package
//
// Copyright 2004 NTESS and the Teuchos contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER
 
#ifndef TEUCHOS_HASHSET_H
#define TEUCHOS_HASHSET_H
 
#include "Teuchos_ConfigDefs.hpp"
#include "Teuchos_Array.hpp"
#include "Teuchos_HashUtils.hpp"
 
namespace Teuchos
{
  using std::string;
 
 
  template<class Key> class HashSet
    {
    public:
 
      inline HashSet(int capacity=19);
 
      inline bool containsKey(const Key& key) const ;
 
      inline void put(const Key& key);
 
      inline void remove(const Key& key);
 
      inline int size() const {return count_;}
 
      inline Array<Key> arrayify() const ;
 
      inline void arrayify(Array<Key>& keys) const ;
 
      inline std::string toString() const ;
 
    private:
      inline void rehash();
      inline int nextPrime(int newCap) const ;
 
      Array<Array<Key> > data_;
      int count_;
      int capacity_;
      mutable Key mostRecentKey_;
    };
 
 
  template<class Key>
    std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h);
 
  template<class Key> inline
    std::string toString(const HashSet<Key>& h) {return h.toString();}
 
 
  template<class Key> inline
    HashSet<Key>::HashSet(int capacity)
    : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity))
    {
      data_.resize(capacity_);
    }
 
  template<class Key> inline
    bool HashSet<Key>::containsKey(const Key& key) const
    {
      const Array<Key>& candidates
        = data_[hashCode(key) % capacity_];
 
      for (int i=0; i<candidates.length(); i++)
        {
          const Key& c = candidates[i];
          if (c == key)
            {
              return true;
            }
        }
      return false;
    }
 
  template<class Key> inline
    void HashSet<Key>::put(const Key& key)
    {
      int index = hashCode(key) % capacity_;
 
      Array<Key>& local = data_[index];
 
      // check for duplicate key
      for (int i=0; i<local.length(); i++)
        {
          if (local[i] == key)
            {
              return;
            }
        }
 
      // no duplicate key, so increment element count by one.
      count_++;
 
      // check for need to resize.
      if (count_ > capacity_)
        {
          capacity_ = HashUtils::nextPrime(capacity_+1);
          rehash();
          // recaluate index
          index = hashCode(key) % capacity_;
        }
 
      data_[index].append(key);
    }
 
 
 
  template<class Key> inline
    void HashSet<Key>::rehash()
    {
      Array<Array<Key> > tmp(capacity_);
 
      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              int newIndex = hashCode(data_[i][j]) % capacity_;
              tmp[newIndex].append(data_[i][j]);
            }
        }
 
      data_ = tmp;
    }
 
  template<class Key> inline
    Array<Key> HashSet<Key>::arrayify() const
    {
      Array<Key> rtn;
      rtn.reserve(size());
 
      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              rtn.append(data_[i][j]);
            }
        }
 
      return rtn;
    }
 
  template<class Key> inline
    void HashSet<Key>::arrayify(Array<Key>& rtn) const
    {
      rtn.resize(0);
 
      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              rtn.append(data_[i][j]);
            }
        }
    }
 
  template<class Key>  inline
    std::string HashSet<Key>::toString() const
    {
      std::string rtn = "HashSet[";
 
      bool first = true;
 
      for (int i=0; i<data_.length(); i++)
        {
          for (int j=0; j<data_[i].length(); j++)
            {
              if (!first) rtn += ", ";
              first = false;
              rtn += Teuchos::toString(data_[i][j]);
            }
        }
      rtn += "]";
      return rtn;
    }
 
 
  template<class Key> inline
    void HashSet<Key>::remove(const Key& key)
    {
      TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
                         std::runtime_error,
                         "HashSet<Key>::remove: key "
                         << Teuchos::toString(key)
                         << " not found in HashSet"
                         << toString());
 
      count_--;
      int h = hashCode(key) % capacity_;
      Array<Key>& candidates = data_[h];
 
      for (int i=0; i<candidates.length(); i++)
        {
          if (candidates[i] == key)
            {
              candidates.remove(i);
              break;
            }
        }
    }
 
 
 
  template<class Key>  inline
    std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h)
    {
      return os << h.toString();
    }
 
 
}
 
#endif // TEUCHOS_HASHSET_H