FixedSizeSet.h

Go to the documentation of this file.

//
//  FixedSizeSet.h
//  hog2 glut
//
//  Created by Nathan Sturtevant on 7/27/16.
//  Copyright © 2016 University of Denver. All rights reserved.
//
 
#ifndef FixedSizeSet_h
#define FixedSizeSet_h
 
#include <string.h>
#include <functional>
#include <cstddef>
template<typename T>
class fssIterator;
 
template <typename T, class Hash = std::hash<T>>
class FixedSizeSet {
private:
        struct field {
                T item;
                field *next;
                bool valid;
        };
public:
        FixedSizeSet(size_t capacity);
        ~FixedSizeSet();
        void resize(size_t capacity);
        void swap(FixedSizeSet<T, Hash> &s);
        void clear();
        size_t size() { return currentMemoryEntry/*-removed*/; }
        typedef fssIterator<field> iterator;
        
        iterator begin(){return iterator(&memory[0]);}
        iterator end() const {return iterator(&memory[currentMemoryEntry]);}
        iterator find(const T &item) const
        {
                size_t hash = h(item);
                for (field* f = hashTable[hash%hashTableSize]; f; f = f->next)
                {
                        if (f->item == item && f->valid)
                                return iterator(f);
                }
                return end();
        }
        void erase(iterator &i);
        void insert(const T &item);
        void PrintStats();
private:
        field **hashTable;
        field *memory;
        size_t currentMemoryEntry;
        size_t capacity;
        size_t hashTableSize;
        size_t removed;
        Hash h;
};
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::swap(FixedSizeSet<T, Hash> &s)
{
        field **a, *b;
        size_t c, d, e, f;
        a = hashTable;
        b = memory;
        c = currentMemoryEntry;
        d = capacity;
        e = hashTableSize;
        f = removed;
        *this = s;
        s.hashTable = a;
        s.memory = b;
        s.currentMemoryEntry = c;
        s.capacity = d;
        s.hashTableSize = e;
        s.removed = f;
}
 
 
template <typename T, class Hash>
FixedSizeSet<T, Hash>::FixedSizeSet(size_t capacity)
{
        hashTableSize = (2*capacity)|1;//capacity*2+3;
        hashTable = new field*[hashTableSize];
        memory = new field[capacity];
        memset(memory, 0x0, capacity*sizeof(field));
        memset(hashTable, 0x0, hashTableSize*sizeof(field*));
        currentMemoryEntry = 0;
        this->capacity = capacity;
        removed = 0;
}
 
template <typename T, class Hash>
FixedSizeSet<T, Hash>::~FixedSizeSet()
{
        delete [] hashTable;
        delete [] memory;
        memory = 0;
        hashTable = 0;
        currentMemoryEntry = 0;
        capacity = 0;
        removed = 0;
}
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::resize(size_t capacity)
{
//      if (capacity <= this->capacity)
//      {
//              currentMemoryEntry = 0;
//              removed = 0;
//              memset(hashTable, 0x0, hashTableSize*sizeof(field*));
//              memset(memory, 0x0, capacity*sizeof(field));
//      }
//      else {
        this->capacity = capacity;
        delete [] hashTable;
        delete [] memory;
        hashTableSize = (2*capacity)|1;//capacity*2+3;
        hashTable = new field*[hashTableSize];
        memory = new field[capacity];
        memset(memory, 0x0, capacity*sizeof(field));
        memset(hashTable, 0x0, hashTableSize*sizeof(field*));
        currentMemoryEntry = 0;
        removed = 0;
//      }
}
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::clear()
{
        currentMemoryEntry = 0;
        removed = 0;
        memset(hashTable, 0x0, capacity*sizeof(field*));
        memset(memory, 0x0, capacity*sizeof(field));
}
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::PrintStats()
{
        std::vector<int> dist;
        for (int x = 0; x < hashTableSize; x++)
        {
                int len = 0;
                for (field* f = hashTable[x]; f; f = f->next)
                {
                        len++;
                }
                if (len >= dist.size())
                        dist.resize(len+1);
                dist[len]++;
        }
        for (int x = 0; x < dist.size(); x++)
                printf("%d : %d\n", x, dist[x]);
}
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::erase(iterator &i)
{
//      if ((*i).valid == true)
//      {
                (*i).valid = false;
//              removed++;
//      }
}
 
template <typename T, class Hash>
void FixedSizeSet<T, Hash>::insert(const T &item)
{
        size_t hash = h(item);
        if (hashTable[hash%hashTableSize] == 0)
        {
                field *f = &memory[currentMemoryEntry];
                currentMemoryEntry++;
                f->item = item;
                f->next = 0;
                f->valid = true;
                hashTable[hash%hashTableSize] = f;
        }
        else {
                for (field* t = hashTable[hash%hashTableSize]; t; t = t->next)
                {
                        if (t->item == item)
                                return;
                        if (t->next == 0)
                        {
                                field *f = &memory[currentMemoryEntry];
                                currentMemoryEntry++;
                                f->item = item;
                                f->next = 0;
                                f->valid = true;
                                t->next = f;
                        }
                }
        }
}
 
 
template<typename T>
class fssIterator : public std::iterator<std::random_access_iterator_tag, T, ptrdiff_t, T*, T&>
{
public:
        fssIterator(T* ptr = nullptr){m_ptr = ptr;}
        fssIterator(const fssIterator<T>& rawIterator) = default;
        ~fssIterator(){}
        
        fssIterator<T>& operator=(const fssIterator<T>& rawIterator) = default;
        fssIterator<T>& operator=(T* ptr){m_ptr = ptr;return (*this);}
        
        operator bool()const
        {
                if(m_ptr)
                        return true;
                else
                        return false;
        }
 
        bool operator==(const fssIterator<T>& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());}
        bool operator!=(const fssIterator<T>& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());}
        fssIterator<T>& operator+=(const ptrdiff_t& movement){m_ptr += movement;return (*this);}
        fssIterator<T>& operator-=(const ptrdiff_t& movement){m_ptr -= movement;return (*this);}
        fssIterator<T>& operator++(){++m_ptr;return (*this);}
        fssIterator<T>& operator--(){--m_ptr;return (*this);}
        fssIterator<T> operator++(int){auto temp(*this);++m_ptr;return temp;}
        fssIterator<T> operator--(int){auto temp(*this);--m_ptr;return temp;}
        fssIterator<T> operator+(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
        fssIterator<T> operator-(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
        
        ptrdiff_t operator-(const fssIterator<T>& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());}
        T& operator*(){return *m_ptr;}
        const T& operator*()const{return *m_ptr;}
        T* operator->(){return m_ptr;}
        T* getPtr()const{return m_ptr;}
        const T* getConstPtr()const{return m_ptr;}
        
protected:
        
        T* m_ptr;
};
//-------------------------------------------------------------------
 
#endif /* FixedSizeSet_h */