sp0204

// sp0205.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <Windows.h>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename IDATA>
class IndexedList {
    class INode
    {
    public:
        IDATA value;
        unsigned int index;
        class INode *next;
        INode() {};
        INode(IDATA v, unsigned int p)
        {
            value = v;
            index = p;
        }
    };

    INode* head, *tail;
    IDATA default_value;
    unsigned int maxpos;
public:
    IndexedList() { head=tail=NULL; default_value=0; maxpos=0;}
    IndexedList(IDATA initV, unsigned int pos, IDATA df) {
        head=tail=new INode (initV, pos);
        default_value=df;
        maxpos=pos;
    }
    bool addNodeByIndex(IDATA val, unsigned pos);
    IDATA getNodeByIndex(unsigned pos);
    bool DeleteNodeByIndex(unsigned pos);
    IDATA operator[](int nSubscript) { return getNodeByIndex(nSubscript); }
};


template <typename IDATA>
class HashedList {
    class INode
    {
    public:
        IDATA value;
        unsigned int index;
        class INode *next;
        INode() {};
        INode(IDATA v, unsigned int p)
        {
            value = v;
            index = p;
        }
    };

    INode* *hashTable;
    unsigned int hashTableSize;
    IDATA default_value;
    unsigned int maxpos;
public:
    HashedList() { hashTableSize = 100; }
    HashedList(IDATA initV, unsigned int pos, IDATA df) {
        hashTableSize = 1000;
        hashTable = new INode*[hashTableSize];
        for (unsigned int i = 0; i < hashTableSize; i++)
        {
            hashTable[i]=NULL;
        }
        addNodeByIndex(initV, pos);
        default_value = df;
        maxpos = pos;
    }
    bool addNodeByIndex(IDATA val, unsigned pos);
    IDATA getNodeByIndex(unsigned pos);
    bool DeleteNodeByIndex(unsigned pos);
    IDATA operator[](int nSubscript) { return getNodeByIndex(nSubscript); }
    int hash(unsigned int pos) { return (pos % hashTableSize); }
};


template <typename IDATA>
bool IndexedList<IDATA>::addNodeByIndex(IDATA val, unsigned pos)
{
    if (val == default_value)
        return false;

    INode* newElement = new INode(val,pos);
    if (pos > maxpos)
    {
        tail = tail->next = newElement;
        maxpos = pos;
    }
    else{
            INode* i = head;
            while (i->next->index < pos)
                i = i->next;
            newElement->next = i->next;
            i->next = newElement;
        }
    return true;
}

template <typename IDATA>
IDATA IndexedList<IDATA>::getNodeByIndex(unsigned pos){
    if (pos<=maxpos)
        for (INode* i = head; i!=NULL; i = i->next)
            if (i->index == pos) return i->value;
    return default_value;
}

template <typename IDATA>
bool IndexedList<IDATA>::DeleteNodeByIndex(unsigned pos)
{
    class INode* temp, *temp1;
    temp= temp1 = head;
    if (head->index == pos)
    {
        head = temp->next;
        delete temp;
        return true;
    }
    else
    {
        for (temp = head->next; temp != NULL; temp1 = temp, temp = temp->next)
            if (temp->index == pos) {
            temp1->next = temp->next;
            delete temp;
            return true;
            }
    }
    return false;
}

template <typename IDATA>
bool HashedList<IDATA>::addNodeByIndex(IDATA val, unsigned pos)
{
    INode *p, *p0;
    int bucket;
    if (val == default_value)
        return false;

    bucket = hash(pos);
    p0 = hashTable[bucket];
    p = new INode(val, pos);
    hashTable[bucket] = p;
    p->next = p0;

    return true;
}

template <typename IDATA>
IDATA HashedList<IDATA>::getNodeByIndex(unsigned pos){
    INode *p;
    for (p = hashTable[hash(pos)]; p!=NULL; p=p->next)
    {
        if (p->index == pos) return p->value;
    }

    return default_value;
}

template <typename IDATA>
bool HashedList<IDATA>::DeleteNodeByIndex(unsigned pos)
{
    return false;
}

LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
LARGE_INTEGER Frequency;

int _tmain(int argc, _TCHAR* argv[])
{
    FILE *fileA, *fileB;
    int xVal;
    long int scalar_d=0;
    int index = 0;
    std::vector<int> A;
    std::vector<int> B;
    errno_t err;

    err=fopen_s(&fileA,"vector_a.txt","rt");
    if (err!=0)
    {
        printf ("Error %d",err);
        return -1;
    }

    fscanf_s(fileA,"%d",&xVal);
    HashedList<int> listA(xVal,index,0);
    A.push_back(xVal);
    while (fscanf_s(fileA, "%d", &xVal) > 0)
    {
        listA.addNodeByIndex(xVal, ++index);
        A.push_back(xVal);
    }
    fclose(fileA);

    err=fopen_s(&fileB,"vector_b.txt","rt");
    if (err!=0)
    {
        printf ("Error %d",err);
        return -1;
    }

    fscanf_s(fileB,"%d",&xVal);
    index=0;
    HashedList<int> listB(xVal, index, 0);
    B.push_back(xVal);
    while (fscanf_s(fileB, "%d", &xVal) > 0) {
        listB.addNodeByIndex(xVal, ++index);
        B.push_back(xVal);
    }

    fclose(fileB);
    QueryPerformanceCounter(&StartingTime);
    for (int i = 0; i <10000; i++)
    {
        scalar_d += listA[i] * listB[i];
    }
    QueryPerformanceCounter(&EndingTime);

    ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;;
    printf( "\n%2.1ld \n", ElapsedMicroseconds.QuadPart );
    printf("\nS=%ld", scalar_d);

    QueryPerformanceCounter(&StartingTime);
    scalar_d = std::inner_product(A.begin(), A.end(), B.begin(), 0);
    QueryPerformanceCounter(&EndingTime);

    ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;;
    printf("\n%2.1ld \n", ElapsedMicroseconds.QuadPart);
    printf("\nS=%ld", scalar_d);

    return 0;
}