////////////////////////////////////////// hashtable cpp ////////////

#include "HashTable.h"
#include <fstream>

int HashTable::hashFunc(const line& d) const //hash function (utilizes horner's method to prevent overflow on large strings)
{
    int hashVal=0,asc;
  std::string s = d.name;
    for(int i=0;i<s.size();i++)
    {
        asc=s[i]>96?s[i]-96:s[i]-64;
        hashVal=(hashVal*32+asc)%arrSize;
    }
    return hashVal;
}

int HashTable::getPrime(int n) const //return the smallest prime number >= 2*n
{
    int i=2*n;
    while(!isPrime(i))
        i++;
    return i;
}

bool HashTable::isPrime(int n) const //check whether n is prime, helper function for getPrime()
{
    bool isPrime=true;
        for(int count=2;count<n && isPrime; count++)
            if(n%count==0)
                isPrime=false;
    return isPrime;
}

void HashTable::deepCopy(const HashTable& h)
{
    if(h.arr!=NULL)
    {
        numOfItems=h.size();
        arrSize=h.maxSize();
        arr=new LinkedList[arrSize];
        for(int i=0;i<arrSize;i++)
            arr[i]=h.arr[i];
    }
}

std::vector<line> HashTable::get() const //returns a vector of all the lines in the hash table
{
    std::vector<line> v,tmp_v;
    for(int i=0;i<maxSize();i++)
    {
        tmp_v=arr[i].get();
        for(int j=0;j<tmp_v.size();j++)
            v.push_back(tmp_v[j]);
    }
    return v;
}

HashTable::HashTable() //default constructor
{
    arrSize=101;
    arr=new LinkedList[arrSize];
    numOfItems=0;
}

HashTable::HashTable(int n) //creates a hash table to store n items where the size of the array is the smallest prime number >= 2*n
{
    arrSize=getPrime(n);
    arr=new LinkedList[arrSize];
    numOfItems=0;
}


HashTable::HashTable(const HashTable& h) //copy constructor
{
    deepCopy(h);
}


HashTable::~HashTable() //destructor
{
    delete[] arr;
}

HashTable& HashTable::operator=(const HashTable& h) //assignment operator
{
    if(this!=&h)
    {
        if(h.arr!=NULL)
            delete[] arr;
        deepCopy(h);
    }
    return *this;
}

bool HashTable::insert(const line& s) //inserts line s if it doesn't exist in the hash table and returns 1 if insertion successful, 0 otherwise
{
    int hash=hashFunc(s);
    bool successOrFail=arr[hash].insert(s);
    numOfItems++;
    return successOrFail;
}

bool HashTable::remove(const line& s) //removes line s if s exist in the hash table and returns 1 if removal successful, 0 otherwise
{
    int hash=hashFunc(s);
    bool successOrFail=arr[hash].remove(s);
    numOfItems--;
    return successOrFail;
}

bool HashTable::search(const line& s) const //returns 1 if s exist in the hash table, 0 otherwise
{
    int hash=hashFunc(s);
    bool found=arr[hash].search(s);
    return found;
}


int HashTable::size() const //returns numOfItems
{
    return numOfItems;
}

int HashTable::maxSize() const //returns arrSize
{
    return arrSize;
}

double HashTable::loadFactor() const //returns the load factor of the hash table
{
    return (numOfItems*1.0)/arrSize;
}

void HashTable::print() const
{
        for(int i=0;i<arrSize;i++)
        {
                if(arr[i].front != NULL)
                {
                        arr[i].printList();
                }
        }
}
void HashTable::HashTableToFile(const std::string &filename_items) const
{
        std::ofstream ofs(filename_items);
        for(int i=0;i<arrSize;i++)
        {
                if(arr[i].front != NULL)
                {
                        ofs << arr[i];
                }
        }
}

std::vector<line> HashTable::intersection(const HashTable& h) const //returns a vector of line containing intersection of calling object's data and h's data
{
    std::vector<line> ret_v;
    std::vector<line> v=this->get();
    for(int i=0;i<v.size();i++)
        if(h.search(v[i]))
            ret_v.push_back(v[i]);
    return ret_v;
}

std::vector<line> HashTable::unions(const HashTable& h) const //returns a vector of line containing union of calling object's data and h's data
{
    std::vector<line> ret_v;
    std::vector<line> v1=this->get();
    std::vector<line> v2=h.get();
    for(int i=0;i<v2.size();i++) //push_back all h elements
        ret_v.push_back(v2[i]);
    for(int i=0;i<v1.size();i++) //push_back caller elements that are not found in h
        if(!h.search(v1[i]))
            ret_v.push_back(v1[i]);
    return ret_v;
}

std::vector<line> HashTable::difference(const HashTable& h) const //returns a vector of line containing set difference of calling object's data and h's data
{
        std::vector<line> ret_v;
    std::vector<line> v1=this->get();
    std::vector<line> v2=h.get();
    for(int i=0;i<v1.size();i++) //push_back caller's elements that are not found in h
        if(!h.search(v1[i]))
            ret_v.push_back(v1[i]);
    for(int i=0;i<v2.size();i++) //push_back h's elements that are not found in caller
        if(!this->search(v2[i]))
            ret_v.push_back(v2[i]);
    return ret_v;
}



/////////////////////////////hashtable h////////////////////////
#ifndef HASHTABLE_H_INCLUDED
#define HASHTABLE_H_INCLUDED

#include "LinkedList.h"

class HashTable
{
public:
    HashTable(); //default constructor
    HashTable(int); //one parameter constructor
    HashTable(const HashTable&); //copy constructor
    ~HashTable(); //destructor
    HashTable& operator=(const HashTable&); //assignment operator
    bool insert(const line&);
    bool remove(const line&);
    bool search(const line&) const;
    int size() const; //return numOfItems
    int maxSize() const; //return arrSize
    double loadFactor() const;
    std::vector<line> intersection(const HashTable&) const;
    std::vector<line> unions(const HashTable&) const;
    std::vector<line> difference(const HashTable&) const;
    void HashTableToFile(const std::string &filename_items) const;
    void print() const;

private:
    LinkedList* arr;
    int arrSize;
    int numOfItems;
    int hashFunc(const line&) const;
    int getPrime(int) const;
    bool isPrime(int) const;
    void deepCopy(const HashTable& h);
    std::vector<line> get() const; //returns a vector of all the lines in the HashTable
};
#endif



///////////////////////////////////////////LinkedList cpp //////////////////////////

#include "LinkedList.h"
#include <iostream>

LinkedList::LinkedList() //default constructor
{
    front=NULL;
}

LinkedList::LinkedList(const LinkedList& ls) //copy constructor
{
    deepCopy(ls);
}

LinkedList::~LinkedList() //destructor
{
    deleteList();
}

LinkedList& LinkedList::operator=(const LinkedList& ls) //assignment operator
{
    if(this!=&ls)
    {
        deleteList();
        deepCopy(ls);
    }
    return *this;
}

bool LinkedList::insert(const line& s)
{
        Node* temp=front;
        while(temp!=NULL) //Traverse list
        {
            if(temp->data.name == s.name)
            {
                    temp->data.quant+=s.quant;
                    return true;
            }
            temp = temp->next;
        }
        front=new Node(s,front);
        return true;
}

bool LinkedList::remove(const line& s)
{
    Node* temp=front;
    if(temp==NULL) //list is empty
        return false;
    if(temp->data==s) //s is first string in list
    {
        front=temp->next;
        delete temp;
        return true;
    }
    else
    {
        while(temp->next!=NULL){
            if(temp->next->data==s)
            {
                Node* deletedNode=temp->next;
                temp->next=temp->next->next;
                delete deletedNode;
                return true;
            }
            temp=temp->next;
        }
        return false;
    }
}

void  LinkedList::printList() const
{
    Node* temp=front;
    while(temp!=NULL)
    {
        std::cout << temp->data.name << " v kolichesve " <<  temp->data.quant <<  std::endl;
        temp = temp->next;
    }
}

std::ostream& operator<< (std::ostream &out, const LinkedList &p)
{
        LinkedList::Node* temp=p.front;
        while(temp!=NULL)
        {
                out << temp->data.name <<", " <<  temp->data.quant <<  std::endl;
                temp = temp->next;
            }

    return out;
}

bool LinkedList::search(const line& s) const
{
    Node* temp=front;
    while(temp!=NULL) //Traverse list
    {
        if(temp->data.name ==s.name)
            return true;
        temp = temp->next;
    }
    return false;
}

std::vector<line> LinkedList::get() const
{
    std::vector<line> str_vec;
    for(Node* temp=front;temp!=NULL;temp=temp->next)
        str_vec.push_back(temp->data);
    return str_vec;
}

void LinkedList::deepCopy(const LinkedList& ls)
{
    front=NULL;
    if(ls.front!=NULL) //Only copy if ls is non-empty
    {
        Node* original=ls.front;
        Node* copy;
        copy=new Node(original->data, NULL);
        front=copy;
        original=original->next;
        while(original!=NULL) //Traverse the original copying each node
        {
            copy->next=new Node(original->data, NULL);
            copy=copy->next;
            original=original->next;
        }
    }
}


void LinkedList::deleteList()
{
    Node* tmp;
    while(front!=NULL){
        tmp=front->next;
        delete front;
        front=tmp;
    }
}


//////////////////////////////linkedlist h///////////////////////////////
#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED

#include <cstdlib>
#include <vector>
#include <string>


class line
{
public:
  std::string name;
  int quant;
  line(){}
  line(const std::string namedet,int x)
  {
      name = namedet;
      quant = x;
  }
  line(const line &rhs)
  {
      name = rhs.name;
      quant = rhs.quant;
  }
  line& operator=(const line& rhs)
  {
      name = rhs.name;
      quant = rhs.quant;
      return *this;
  }
  bool  operator==(const line &rhs)
  {
      return name == rhs.name;
  }
};

class LinkedList
{
public:
    LinkedList(); //default constructor
    LinkedList(const LinkedList& ls);//copy constructor
    ~LinkedList(); //destructor
    LinkedList& operator=(const LinkedList&); //assignment operator
    bool insert(const line&);
    bool remove(const line&);
    bool search(const line&) const;
    std::vector<line> get() const;
  void printList() const;

private:
    class Node
    {
    public:
        line data;
        Node* next;
        Node(line s)
    {
        data = s;
        next = NULL;
    }
        Node(line s,Node* nd)
    {
        data = s;
        next = nd;
    }
    };
    Node* front;
    void deepCopy(const LinkedList& ls);
    void deleteList();
  friend class HashTable;
  friend std::ostream& operator<< (std::ostream &out, const LinkedList &point);
};

#endif
/////////////////////////////////////////////////