double_hashing.cpp

#ifndef DOUBLEHASING_H
#define DOUBLEHASHING_H
#include <iostream>
#include "Container.h"
#include <cmath>

class DoubleHashingEmptyException : public ContainerException
{
  public:
    virtual const char *what() const throw()
    {
        return "DoubleHashing: empty";
    }
};

enum states
{
    occupied,
    freee,
    freeagain
};

template <typename E, size_t N = 7>
class DoubleHashing : public Container<E>
{
    size_t nmax;
    size_t n;
    double maxLoadFac;
    E first;
    E last;
    E recAdd;
    E recRem;
    bool fresh;

    struct Element
    {
        E value;
        states state;
        Element() : state(freee) {}
    };

    Element *values;
    mutable E *arr;

  public:
    unsigned long hashKey(const E &a) const
    {
        return hashValue(a) % nmax;
    }

    DoubleHashing(double mlf = 0.7) : nmax(N), n(0), fresh(true), values(new Element[this->nmax])
    {
        arr = 0;
        maxLoadFac = mlf;
    }

    DoubleHashing(const DoubleHashing &original)
    {
        nmax = original.nmax;
        n = original.n;
        values = original.values;
    }

    virtual ~DoubleHashing()
    {
        delete[] values;
    }

    using Container<E>::add;
    virtual void add(const E e[], size_t len);

    using Container<E>::remove;
    virtual void remove(const E[], size_t s);

    using Container<E>::even;
    virtual E* even() const;

    virtual bool member(const E &e) const;
    virtual size_t size() const
    {
        return n;
    }

    using Container<E>::min;
    virtual E min() const;

    using Container<E>::max;
    virtual E max() const;

    using Container<E>::print;
    virtual std::ostream &print(std::ostream &o) const;

    using Container<E>::apply;
    virtual size_t apply(const Functor<E> &f, Order order = dontcare) const;

    using Container<E>::x;
    virtual size_t x(const E &a, const E &b) const;

    using Container<E>::ndMin;
    virtual E ndMin() const;

    using Container<E>::avg;
    virtual double avg() const;

    bool isPrimeNumber(size_t number)
    {
        if (number < 2)
        {
            return false;
        }

        static const unsigned int primes[] =
            {
                2, 3, 5, 7, 11, 13, 17, 19,
                23, 29, 31, 37, 41, 43, 47, 53,
                59, 61, 67, 71, 73, 79, 83, 89,
                97, 101, 103, 107, 109, 113, 127, 131,
                137, 139, 149, 151, 157, 163, 167, 173,
                179, 181, 191, 193, 197, 199, 211, 223,
                227, 229, 233, 239, 241, 251, 257, 263,
                269, 271, 277, 281, 283, 293, 307, 311};

        for (register int p = 0; p < 63; ++p)
        {
            if (number == primes[p])
            {
                return true;
            }

            else if (number % primes[p] == 0)
            {
                return false;
            }
        }

        unsigned int maxFactor = sqrt(number);
        for (size_t i = 313; i < maxFactor; i += 2)
        {
            if (number % i == 0)
            {
                return false;
            }
        }

        return true;
    }

    unsigned long nextPrimeNumber(size_t number)
    {
        unsigned long next = number + 1, last = number * 2;

        while (next < last)
        {
            if (isPrimeNumber(next) == true)
            {
                return next;
            }

            else
            {
                last++;
            }

            next++;
        }
    }

    void sort() const //selection sort
    {
        register E tmp;

        for (size_t i = 0; i < n; ++i)
        {
            size_t minInd = i;

            for (int j = i + 1; j < n; ++j)
            {
                if (arr[minInd] > arr[j])
                {
                    minInd = j;
                }
            }

            if (minInd != i)
            {
                tmp = arr[minInd];
                arr[minInd] = arr[i];
                arr[i] = tmp;
            }
        }
    }

    void resize()
    {
        Element *tempTab = values;
        size_t n1 = nmax;
        nmax = nextPrimeNumber(nmax); //nmax*2;
        values = new Element[nmax];
        n = 0;

        for (register int i = 0; i < n1; ++i)
        {
            if (tempTab[i].state == occupied)
            {
                add(tempTab[i].value);
            }
        }

        delete[] tempTab;
    }

};



template <typename E, size_t N>
E *DoubleHashing<E, N>::even() const
{
    E *arr = new E;

    int count = 0;
    for (int i = 0; i < nmax; ++i)
    {
        if (values[i].state == occupied && !(values[i].value % 2))
        {
            arr[count++] = values[i].value;
        }
    }

    return arr;
}

template <typename E, size_t N>
void DoubleHashing<E, N>::add(const E e[], size_t len)
{
    for (register short unsigned int i = 0; i < len; ++i)
    {
        register unsigned long a = hashKey(e[i]);

        if (!member(e[i]))
        {
            if (fresh)
            {
                first = e[i];
            }

            values[a].value = e[i];
            values[a].state = occupied;

            ++n;

            last = values[a].value;

            if ((values[a].state == freee) && n == 1)
                first = values[a].value;

            if ((double(n) / double(nmax)) > this->maxLoadFac)
            {
                resize();
            }
        }
    }
}

template <typename E, size_t N>
bool DoubleHashing<E, N>::member(const E &e) const
{
    unsigned long key = hashKey(e);

    short unsigned int tries = 0;

    while (values[key].state != freee)
    {
        if ((values[key].value == e) && (values[key].state == occupied))
        {
            return true;
        }

        else
        {
            key = (key + 1) % nmax;
        }

        ++tries;

        if (tries > nmax * 2)
        {
            break;
        }
    }

    return false;
}

template <typename E, size_t N>
std::ostream &DoubleHashing<E, N>::print(std::ostream &o) const
{

    o << "DoubleHashing [ n=" << n << " nmax=" << nmax << " first=" << first << " values=";

    for (int i = 0; i < nmax; ++i)
    {
        if (values[i].state == occupied)
        {
            o << ' ' << values[i].value;
        }
    }

    o << " ]";
    return o;
}

template <typename E, size_t N>
void DoubleHashing<E, N>::remove(const E e[], size_t len)
{
    for (size_t i = 0; i < len; ++i)
    {
        for (size_t j = 0; j < nmax; ++j)
        {
            if ((values[j].state == occupied && values[j].value == e[i]))
            {
                --n;
                values[j].state = freeagain;

                if (j + 1 < nmax && (values[j + 1]).state == freee)
                {
                    break;
                }
            }
        }
    }
}

template <typename E, size_t N>
E DoubleHashing<E, N>::min() const
{
    if (this->empty())
    {
        throw DoubleHashingEmptyException();
    }

    register Element *smallestOne = 0;

    for (size_t i = 0; i < nmax; ++i)
    {

        if (values[i].state == occupied)
        {
            if (smallestOne)
            {
                if ((smallestOne->value > values[i].value))
                    smallestOne = (values + i);
            }
            else
            {
                smallestOne = (values + i);
            }
        }
    }

    return smallestOne->value;
}

template <typename E, size_t N>
E DoubleHashing<E, N>::max() const
{
    if (this->empty())
    {
        throw DoubleHashingEmptyException();
    }

    Element *biggestOne = 0;

    for (size_t i = 0; i < nmax; ++i)
    {

        if (values[i].state == occupied)
        {
            if (biggestOne)
            {
                if (values[i].value > (biggestOne->value))
                    biggestOne = (values + i);
            }
            else
            {
                biggestOne = (values + i);
            }
        }
    }

    return biggestOne->value;
}

template <typename E, size_t N>
size_t DoubleHashing<E, N>::apply(const Functor<E> &f, Order order) const
{
    register size_t rc = 0;

    arr = new E[n];
    register int arrpos = 0;

    for (size_t i = 0; i < nmax; ++i)
    {
        if (values[i].state == occupied)
        {
            arr[arrpos] = values[i].value;
            arrpos++;
        }
    }

    if (order == dontcare)
    {
        for (size_t i = 0; i < nmax; ++i)
        {
            if (values[i].state == occupied)
            {
                ++rc;

                if (!f(values[i].value))
                {
                    delete[] arr;
                    return rc;
                }
            }
        }

        delete[] arr;
        return rc;
    }

    else
    {
        sort();

        if (order == ascending)
        {
            for (size_t i = 0; i < n; ++i)
            {
                ++rc;

                if (!f(arr[i]))
                {
                    delete[] arr;
                    return rc;
                }
            }
        }
        else
        {
            if (!(this->empty()))
            {
                for (int i = n - 1; i >= 0; --i)
                {
                    ++rc;

                    if (!f(arr[i]))
                    {
                        delete[] arr;
                        return rc;
                    }
                }
            }
        }
    }

    delete[] arr;
    return rc;
}

#endif //DOUBLEHASHING_H