#include <iostream>
#include <cstring>
#include <string>
#include "ArrayCollection.h"
#include "ArraySet.h"
#include "ArrayList.h"
#include "ex/SetByCollection.h"
#include "ex/StackByList.h"
#include "ex/PQByList.h"
#include "ArrayStack.h"
#include "ArrayQueue.h"
#include "BinaryHeap.h"
#include "ex/SimpleHash.h"
#include "ex/LinearProbingHashInt.h"
#include "LinkedList.h"
#include "LinkedCollection.h"
#include "SinglyLinkedList.h"
#include "BinaryTree.h"
#include "BSTree.h"


using namespace std;

typedef ArrayCollection<float> FloatArrayCollection;

class classA {
    public:
    void whoAreYou() {
        printf("hahahha\n");
    }
    void getName() {
        printf(" i am A\n");
    }
    int myName;
};

class classB : public classA {
    public:
    void getName() {
        printf(" i am B %d\n",myName);
    }
};

void testClass() {
    classA *x = new classB();
    x->whoAreYou();
    x->getName();
}

void testStack() {
    Stack<int> *st = new StackByList<int>(10);
    st->push(10);
    st->push(8);
    st->push(3);
    printf("pop = %d\n",st->pop());
    printf("pop = %d\n",st->pop());
    st->push(1);
    st->push(2);
    st->push(3);
    printf("pop = %d\n",st->pop());
    printf("pop = %d\n",st->pop());
    printf("pop = %d\n",st->pop());
    printf("pop = %d\n",st->pop());
}

void testList() {
    List<int> *tmp = new ArrayList<int>(10);
    tmp->add(3);
    List<string> *list = new ArrayList<string>(10);
    list->add(0,"yes");
    list->add(0,"no");
    list->add(0,"ok");
    list->add(1,"cancel");

    for (int i = 0;i < list->size();i++)
        printf("the data at position %d is %s\n",i,list->get(i).c_str());
    printf("*\n");

    list->removeByPos(2);

    for (int i = 0;i < list->size();i++)
        printf("the data at position %d is %s\n",i,list->get(i).c_str());
    printf("*\n");

    list->add(0,"front");
    string x("back");
    list->add(x);

    for (int i = 0;i < list->size();i++)
        printf("the data at position %d is %s\n",i,list->get(i).c_str());
    printf("*\n");

    printf("the position of \"yes\" is %d\n",list->indexOf("yes"));
    printf("the position of \"haha\" is %d\n",list->indexOf("haha"));
}


void testSet()
{
    Set<int> *set = new SetByCollection<int>(10);
    set->add(1);
    set->add(2);
    set->add(3);
    set->add(3);

    int toFind;

    toFind = 3;
    printf("set has %d: %s\n",toFind, (set->contains(toFind)) ? "true" : "false");
    printf("the size of the set is %d\n", set->size());

    set->remove(3);

    toFind = 3;
    printf("set has %d: %s\n",toFind, (set->contains(toFind)) ? "true" : "false");
    printf("the size of the set is %d\n", set->size());
}

void testArrayCollection()
{
    ArrayCollection<int> *col = new ArrayCollection<int>(1);

    col->add(1);
    col->add(2);
    col->add(3);
    col->add(4);

    int toFind;

    toFind = 6;
    printf("col has %d is %s\n", toFind, (col->contains(toFind)) ? "true" : "false");

    toFind = 4;
    printf("col has %d is %s\n", toFind, (col->contains(toFind)) ? "true" : "false");

    col->add(3);
    col->add(4);

    col->remove(4);
    col->remove(4);
    col->remove(4);

    toFind = 4;
    printf("col has %d is %s\n", toFind, (col->contains(toFind)) ? "true" : "false");


    FloatArrayCollection *fcol = new FloatArrayCollection(10);
    fcol->add(1.4);
    fcol->add(2.0);
    fcol->add(561.2);
    fcol->remove(1.4);
    printf("fcol has %f is %s\n", 1.4, (fcol->contains(1.4)) ? "true" : "false");
}

void testQueue() {
    Queue<int> *pq = new BinaryHeap<int>(3);
    pq->enqueue(1);
    pq->enqueue(20);
    pq->enqueue(9);                       //PQ result// Q result
    printf("pop = %d\n",pq->dequeue());   //20       // 1
    printf("pop = %d\n",pq->dequeue());   // 9       // 20
    pq->enqueue(100);
    pq->enqueue(55);
    printf("pop = %d\n",pq->dequeue());   // 100     // 9
    printf("pop = %d\n",pq->dequeue());   // 55      // 100
    printf("pop = %d\n",pq->dequeue());   // 1       // 55
}

void testPQ() {
    Queue<int> *pq = new BinaryHeap<int>(3);
    pq->enqueue(1);
    pq->enqueue(20);
    pq->enqueue(9);                       //PQ result// Q result
    printf("pop = %d\n",pq->dequeue());   //20       // 1
    printf("pop = %d\n",pq->dequeue());   // 9       // 20
    pq->enqueue(100);
    pq->enqueue(55);
    printf("pop = %d\n",pq->dequeue());   // 100     // 9
    printf("pop = %d\n",pq->dequeue());   // 55      // 100
    printf("pop = %d\n",pq->dequeue());   // 1       // 55
}

void testSimpleHash()
{
    char x ='¹';
    int p = x;
    printf("%d\n",p);

    SimpleHash *h = new SimpleHash();
    h->add("A");
    h->add("B");
    h->add("C");
    h->add("C");
    h->add("x");
    h->add("x");
    h->add("A");
    h->add("B");
    h->add("C");

    h->remove("A");

    printf("The size of hash is %d\n",h->size() );
}

void testIntHash() {
    LinearProbingHashInt *h = new LinearProbingHashInt(13);
    h->add(10);
    h->add(100);
    h->add(1000);

}

void testBinaryTree()
{
    BinaryTree<int> *b = new BinaryTree<int>(20,
                             new BinaryTree<int>(10,NULL,NULL),
                             new BinaryTree<int>(30,
                                 new BinaryTree<int>(40,NULL,NULL),
                                 NULL
                             )
                         );

    PrintVisitor<int> *v = new PrintVisitor<int>();
    b->preOrder(v);
    printf("The height and the size of the tree is %d and %d, respectively\n",b->height(),b->numNodes());
    b->print(0);
}

void testBSTree() {
    BSTree<int> *set = new BSTree<int>();
    set->add(1);
    set->add(2);
    set->add(3);
    set->add(4);
    set->print();

    int toFind;

    toFind = 3;
    printf("set has %d: %s\n",toFind, (set->contains(toFind)) ? "true" : "false");
    printf("the size of the set is %d\n", set->size());

    set->remove(3);

    toFind = 3;
    printf("set has %d: %s\n",toFind, (set->contains(toFind)) ? "true" : "false");
    printf("the size of the set is %d\n", set->size());
}

int comp(const void *a,const void *b) {
  return ( *(int*)a - *(int*)b );
}


void testAdd(int *d,int n,BSTree<int> *b)
{
    for (int i = 0;i < n;i++) {
        b->add(d[i]);
    }
}

void testBSAdd() {
    int n;
    int *d;
    printf("enter number of data: ");scanf("%d",&n);
    d = new int[n];
    for (int i = 0;i < n;i++) {
        int x;
        printf("enter data #%d: ",i+1);scanf("%d",&x);
        d[i] = x;
    }
    qsort(d,n,sizeof(int),comp);
    BSTree<int> *b = new BSTree<int>();
    testAdd(d,n,b);
    b->print();


}

int main()
{

    /*
    printf("------   testing Collection --------\n");
    testArrayCollection();
    printf("------   testing Set --------\n");
    testSet();
    printf("------   testing List --------\n");
    testList();
    printf("------   testing Stack --------\n");
    testStack();
    printf("------   testing Queue --------\n");
    testPQ();
    printf("------   testing PriorityQueue --------\n");
    testQueue();
    printf("------   testing hash --------\n");
    testSimpleHash();
    printf("------   testing BinaryTree --------\n");
    testBinaryTree();
    printf("------   testing BSTree --------\n");
    testBSTree();
    */
    testBSAdd();


    return 0;
}