Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // HashSet.hpp
- //
- // ICS 46 Spring 2015
- // Project #3: Set the Controls for the Heart of the Sun
- //
- // A HashSet is an implementation of a Set that is a separately-chained
- // hash table, implemented as a dynamically-allocated array of linked
- // lists. At any given time, the HashSet has a "size" indicating
- // how many elements are stored within it, along with a "capacity"
- // indicating the size of the array.
- //
- // As elements are added to the HashSet and the proportion of the HashSet's
- // size to its capacity exceeds 0.8 (i.e., there are more than 80% as many
- // elements as there are array cells), the HashSet should be resized so
- // that it is twice as large as it was before.
- //
- // You are not permitted to use the containers in the C++ Standard Library
- // (such as std::vector, std::list, or std::array). Instead, you'll need
- // to use a dynamically-allocated array and your own linked list
- // implementation; the linked list doesn't have to be its own class,
- // though you can do that, if you'd like.
- #ifndef HASHSET_HPP
- #define HASHSET_HPP
- #include <functional>
- #include "Set.hpp"
- template <typename T>
- class HashSet : public Set<T>
- {
- public:
- // The default capacity of the HashSet before anything has been
- // added to it.
- static constexpr unsigned int DEFAULT_CAPACITY = 10;
- // A HashFunction
- typedef std::function<unsigned int(const T&)> HashFunction;
- public:
- // Initializes a HashSet to be empty, so that it will use the given
- // hash function whenever it needs to hash an element.
- HashSet(HashFunction hashFunction);
- // Cleans up the HashSet so that it leaks no memory.
- virtual ~HashSet();
- // Initializes a new HashSet to be a copy of an existing one.
- HashSet(const HashSet& s);
- // Assigns an existing HashSet into another.
- HashSet& operator=(const HashSet& s);
- // isImplemented() should be modified to return true if you've
- // decided to implement a HashSet, false otherwise.
- virtual bool isImplemented() const;
- // add() adds an element to the set. If the element is already in the set,
- // this function has no effect. This function triggers a resizing of the
- // array when the ratio of size to capacity would exceed 0.8. In the case
- // where the array is resized, this function runs in linear time (with
- // respect to the number of elements, assuming a good hash function);
- // otherwise, it runs in constant time (again, assuming a good hash
- // function).
- virtual void add(const T& element);
- // contains() returns true if the given element is already in the set,
- // false otherwise. This function runs in constant time (with respect
- // to the number of elements, assuming a good hash function).
- virtual bool contains(const T& element) const;
- // size() returns the number of elements in the set.
- virtual unsigned int size() const;
- struct elementLink{
- T item;
- T name;
- elementLink* next;
- };
- private:
- HashFunction hashFunction;
- //lam
- unsigned int currentCap;
- elementLink** storage; //array that stores pointer to elementLink
- void resize(); //resize storage
- };
- template <typename T>
- int HashSet<T>::counter = 0;
- template <typename T>
- HashSet<T>::HashSet(HashFunction hashFunction)
- : hashFunction{hashFunction}
- {
- //lam
- currentCap = DEFAULT_CAPACITY;
- storage = new elementLink*[currentCap];
- }
- template <typename T>
- HashSet<T>::~HashSet()
- {
- delete hashTable[];
- }
- template <typename T>
- HashSet<T>::HashSet(const HashSet& s)
- : hashFunction{s.hashFunction}
- {
- }
- template <typename T>
- HashSet<T>& HashSet<T>::operator=(const HashSet& s)
- {
- if (this != &s)
- {
- hashFunction = s.hashFunction;
- }
- return *this;
- }
- template <typename T>
- bool HashSet<T>::isImplemented() const
- {
- return false;
- }
- template <typename T>
- void HashSet<T>::add(const T& element)
- {
- //lam
- unsigned int hashResult = hashFunction(element);
- if(storage[hashResult] != NULL) //something is there already
- {
- if(contains(element)) //the same one
- {
- return; //nothing happen
- }
- else //not the same
- {
- resize();
- unsigned int index = hashResult;
- while(storage[index]->next != NULL) //keep looking until find an empty cell, empty cell being storage[index]->next
- {
- index++;
- index = index%currentCap; //will loop back to 0 if index = currentCap
- }
- storage[(index+1)%currentCap] = &element; //put element into empty cell
- storage[index]->next = &element; //adjust previous cell's next pointer to correctly point at newly added element, maybe not needed
- element->next = storage[(index+2)%currentCap; //newly added element's next pointer points to next cell
- }
- }
- else //nothing there, add like normal
- {
- resize();
- storage[hashResult] = &element;
- element.next = storage[(hashResult+1)%currentCap];
- if(storage[(hashResult-1)%currentCap] != NULL) //if previous node exists then change its next pointer accordingly
- storage[(hashResult-1)%currentCap]->next = &element;
- }
- }
- template <typename T>
- bool HashSet<T>::contains(const T& element) const
- {
- //lam
- unsigned int hashResult = hashFunction(element);
- if(storage[hashResult] != NULL) //something is there already
- {
- if(storage[hashResult]->item == element.item && storage[hashResult]->name == element.name) //the same one
- {
- return true;
- }
- else
- {
- unsigned int index = (hashResult+1)%currentCap;
- while(storage[index] != NULL)
- {
- if(storage[index]->item == element.item && storage[index]->name == element.name)
- return true;
- else
- {
- index++;
- index = index%currentCap;
- }
- }
- return false;
- }
- }
- else
- {
- return false;
- }
- }
- template <typename T>
- unsigned int HashSet<T>::size() const
- {
- unsigned int count = 0;
- int i = 0;
- while(i < currentCap)
- {
- if(storage[i] != NULL) count++;
- i++;
- }
- return count;
- }
- //lam
- template <typename T>
- void HashSet<T>::resize()
- {
- currentCap = currentCap*2;
- elementLink** newStorage;
- newStorage = new elementLink*[currentCap];
- int i = 0;
- while(i < currentCap/2)
- {
- newStorage[i] = storage[i];
- i++;
- }
- delete[] storage;
- storage = newStorage;
- }
- #endif // HASHSET_HPP
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement