///////////////////////////////////////////////////////////////////////
#ifndef DARRAY_H
#define DARRAY_H

class dArray{
  int* pA;
  int Size, containerSize;
  void pointerCheck(int* pa) const;
  void reSize();
  void swap(int i, int j);

 public:
  dArray() : pA(0), Size(0), containerSize(0) {}
  dArray(int size, const int* pa);
  dArray(int size);

  dArray(const dArray& v);
  ~dArray();

  dArray& operator=(const dArray& v);
  int operator[](int k) const;

  void quickSort(int left, int right);
  void append(int value);
  void insert(int k, int value);
  int getSize() const {return Size;}
  int getContainerSize() const {return containerSize;}

  friend class Heap;
};
#endif


//dArray.cpp
#include <iostream>
#include <cstdlib>
#include <cmath>
#include "dArray.h"

using std::cout; using std::endl;

dArray::dArray(int size, const int* pa){
  Size = size;
  containerSize = 2*Size;
  pA = new(std::nothrow) int[containerSize];
  pointerCheck(pA);
  for(int i = 0; i < Size; i++)
    pA[i] = pa[i];
}

dArray::dArray(int size) : Size(size){
  containerSize = 2*Size;
  pA = new(std::nothrow) int[containerSize];
  pointerCheck(pA);
}

dArray::dArray(const dArray& v){

  Size = v.Size;
  pA = new(std::nothrow) int[Size];
  pointerCheck(pA);
  for(int i = 0; i < Size; i++)
    pA[i] = v.pA[i];
}

dArray::~dArray(){
  if(Size != 0)
    delete[] pA;
}

dArray& dArray::operator=(const dArray& v){
  if(this == &v)
    return *this;

  if(pA == 0){
    //will be true if left hand side does not already exist
    this->Size = v.Size;
    this->containerSize = v.containerSize;
    pA = new(std::nothrow) int[v.containerSize];
    pointerCheck(pA);
    return *this;
  }

  if(pA != 0 & Size < v.Size){
    delete[] pA;
    pA = new(std::nothrow) int[v.containerSize];
    pointerCheck(pA);
  }
  
  Size = v.Size;
  containerSize = v.containerSize;
  for(int i = 0; i < Size; i++)
    pA[i] = v.pA[i];
  return *this;
}

int dArray::operator[](int k) const {
  if(k > Size){
    std::cout << "This is not a valid index!" << std::endl;
    exit(1);
  }

  return pA[k];
}

void dArray::append(int value){
  if(Size < containerSize){
    pA[Size] = value;
    Size++;
  }
  else{
    reSize();
    pA[Size] = value;
    Size++;
  }
}

void dArray::insert(int k, int value){
  if(k > Size){
    std::cout << "This is not a valid index!" << std::endl;
    exit(1);
  }

  if(Size == containerSize)
    reSize();

  Size++;
  for(int j = Size; j > k; j--)
    pA[j] = pA[j - 1];
  pA[k] = value;
}
  
void dArray::reSize(){
  std::cout << "Resize was called" << std::endl;
  containerSize *= 2;
  int* temp = new(std::nothrow) int[containerSize];
  pointerCheck(temp);
  for(int i = 0; i < Size; i++)
    temp[i] = pA[i];

  delete[] pA;
  pA = temp;
}

void dArray::pointerCheck(int* pa) const{
  if(pa == 0){
    std::cout << "Memory allocation failed!" << std::endl;
    exit(1);
  }
}

void dArray::swap(int i, int j){
  int temp = pA[i];
  pA[i] = pA[j];
  pA[j] = temp;
}

void dArray::quickSort(int left, int right){
 
  int pivotIndex = floor((left + right)/2);
  int pivot = pA[pivotIndex];
  int low = left, high = right;
  while(high >= low){
    while(pivot > pA[low])
      low++;
    while(pA[high] > pivot)
      high--;
    if(low <= high){
      swap(low, high);
      low++; high--;
    }
  }
  if(left < low - 1)
    quickSort(left, low - 1);
  if(low < right)
    quickSort(low, right);
} 

//dArrayDriver.cpp
#include <iostream>
#include "dArray.h"

int main(){
  int* pa;
  pa = new int[2];
  pa[0] = 2; pa[1] = 4;
  
  dArray v(2, pa);
  v.append(7); v.append(14);
  std::cout << v.getSize() << " " << v.getContainerSize() 
	    << std::endl;  
  v.insert(1, 9);  
  std::cout << v.getSize() << " " << v.getContainerSize() 
	    << std::endl;  
  for(int i = 0; i < v.getSize(); i++)
    std::cout << v[i] << " ";
  std::cout << std::endl;

  return 0;
}

#dArray.mk
dA : dArrayDriver.o dArray.o
	g++ -o dA dArrayDriver.o dArray.o

dArray.o : dArray.cpp dArray.h
	g++ -c dArray.cpp

dArrayDriver.o : dArrayDriver.cpp dArray.h
	g++ -c dArrayDriver.cpp
///////////////////////////////////////////////////////////////////////
//sortDriver.cpp
#include <iostream>
#include "dArray.h"

int main(){
  int* pa = new int[11];
  pa[0] = 15; pa[1] = 1; pa[2] = 18; pa[3] = 28; pa[4] = 27; 
  pa[5] = 19; pa[6] = 49; pa[7] = 38; pa[8] = 6; pa[9] = 2; 
  pa[10] = 40;

   dArray dArrayObj(11, pa);
   dArrayObj.quickSort(0, 10);
   for(int i = 0; i < 10; i++)
     std::cout << dArrayObj[i]  << " ";
   std::cout << std::endl;

   return 0;
}

#dArraySort.mk
dA : sortDriver.o dArray.o
	g++ -o dA sortDriver.o dArray.o

dArray.o : dArray.cpp dArray.h
	g++ -c dArray.cpp

sortDriver.o : sortDriver.cpp dArray.h
	g++ -c sortDriver.cpp
///////////////////////////////////////////////////////////////////////
//simpleList.cpp
#include <iostream>

struct Node{
  int dataValue;
  int keyValue;
  Node* Next;

  Node (){}
  Node (int data, int key, Node* next = 0) 
  : dataValue(data), keyValue(key), Next(next) {}
};

struct linkedList{
  Node* Head;
  int Size;

  void mergeSortList(Node** pHead);
  Node* merge(Node* a, Node* b);
  void split(Node* head, Node** midNode);

  linkedList(){Head = 0;}
  linkedList(const linkedList& L);
  ~linkedList();
  linkedList& operator=(const linkedList& L);

  void push(int newData, int newKey);
  Node* lookUp(int key) const;
  void insert(int newData, int newKey, int key);
  void sort(){mergeSortList(&Head);}
};

linkedList::linkedList(const linkedList& L){

  if(L.Size == 0){
    Head = 0;
    Size = 0;
  }
  else{
    Size = L.Size;
    Node* temp = 0;
    for(Node* iter = L.Head; iter !=0; iter = iter->Next){
      if(temp == 0){//empty list
	Head = new Node(iter->dataValue, iter->keyValue);
	temp = Head;
      }
      else{
	temp->Next = new Node(iter->dataValue, iter->keyValue);
	temp = temp->Next;
      }
    }
    temp->Next = 0;//null pointer as Next for tail node
  }
}

linkedList& linkedList::operator=(const linkedList& L){

  if(this == &L)
    return *this;

  if(L.Size == 0){
    Head = 0;
    Size = 0;
  }
  else{
    Size = L.Size;
    Node* temp = 0;
    for(Node* iter = L.Head; iter !=0; iter = iter->Next){
      if(temp == 0){//empty list
	Head = new Node(iter->dataValue, iter->keyValue);
	temp = Head;
      }
      else{
	temp->Next = new Node(iter->dataValue, iter->keyValue);
	temp = temp->Next;
      }
    }
    temp->Next = 0;//null pointer as Next for tail node
  }
  return *this;
}

linkedList::~linkedList(){
  Node* temp;
  while(Head != 0){
    temp = Head->Next;
    delete Head;
    Head = temp;
  }
}

void linkedList::push(int newData, int newKey){
  Node* newNode = new Node(newData, newKey, Head);
  Head = newNode;
  Size++;
}

Node* linkedList::lookUp(int key) const {
  Node* iter = Head;
  while(iter != 0){
    if(iter->keyValue == key){
      return iter;
    }
    iter = iter->Next;
  }
  return 0;
}

void linkedList::insert(int newData, int newKey, int key){
  if(lookUp(newKey) == 0){//key does not exits
    Node* iter = lookUp(key);
    if(iter != 0){//target does exist
      Node* newNode = new Node(newData, newKey);
      newNode->Next = iter->Next;
      iter->Next = newNode;
      Size++;
    }
    else
      std::cout << "Key not found!" << std::endl;
  }
  else
    std::cout << "Duplicate key!" << std::endl;
}

void linkedList::mergeSortList(Node** pHead){
  Node* head = *pHead;
  Node* midNode;
 
  if (head == 0 || head->Next == 0)//nothing to do
    return;

   split(head, &midNode);

  //recursion
  mergeSortList(&head);
  mergeSortList(&midNode);
 
  //now merge
  *pHead = merge(head, midNode);
}
 
Node* linkedList::merge(Node* a, Node* b){
  Node* newHead;
 
  if(a == 0)
    return(b);
  else if(b == 0)
    return(a);
 
  if (a->keyValue > b->keyValue){//a is new head node
      newHead = a;
      newHead->Next = merge(a->Next, b);
    }
  else{//b is new head node
      newHead = b;
      newHead->Next = merge(a, b->Next);
    }
  return newHead;
}

void linkedList::split(Node* head, Node** midNode){
  struct Node* fast;
  struct Node* slow;
  if (head == 0 || head->Next == 0)
     *midNode = 0;

  else{
    slow = head;
    fast = head->Next;
    
    while (fast != 0){
      fast = fast->Next;
      if (fast != 0){
	  slow = slow->Next;
	  fast = fast->Next;
	}
    }
    *midNode = slow->Next;//new list has slow->Next as head node
    slow->Next = 0;//terminate the other list at slow
    }
}

void f(linkedList L){
  std::cout << L.Head->Next->dataValue << std::endl;
}
    
 int main(){
  linkedList L;
  L.push(2, 15); L.push(3, 18); L.push(4, 28); L.push(5, 27);
  L.push(6, 19); L.push(7, 49); L.push(2, 38); L.push(4, 6);
  L.push(100, 2); L.push(-1, 40);
  L.insert(-4, 1, 18);
  f(L);//test of copy constructor
  std::cout << L.lookUp(1)->dataValue << std::endl;
  Node* iter;
  for(iter = L.Head; iter != 0; iter = iter->Next)
    std::cout << iter->keyValue << " ";
  std::cout << std::endl;

  L.sort();
  for(iter = L.Head; iter != 0; iter = iter->Next)
    std::cout << iter->keyValue << " ";
  std::cout << std::endl;
  
  return 0;
}
///////////////////////////////////////////////////////////////////////
//simpleHash.cpp
#include <iostream>
#include <cmath>
#include <utility>

using std::cout; using std::endl; using std::pair;

struct newPair : public pair <int, int>
{
  bool isNull;
  newPair() : pair<int, int>() {
    isNull = true;
  }

  newPair(const int& key, const int& data) : 
    pair<int, int>(key, data){
    isNull = false;
  }

  newPair(const newPair& pairObj) : 
  pair<int, int>(pairObj.first, pairObj.second)
    {this->isNull = pairObj.isNull;}
};

class hashTable {
  int Size, tableSize;
  int Shift;
  newPair* pTable;

  bool empty(int i) const {
    cout << std::boolalpha << " isNull is " 
	 << pTable[i].isNull << endl;
    return pTable[i].isNull;
  }

public:
  hashTable() {};
  hashTable(int tablesize, int shift = 1);
  hashTable(const hashTable& hT);
  ~hashTable();

  hashTable& operator=(const hashTable& hT);
  bool operator==(const hashTable& hT) const;
  int insert(newPair a);
  int lookUp(int a) const;
  int hash(int a) const;
  int getData(int a) const;  
};

hashTable::hashTable(int tablesize, int shift): 
  tableSize(tablesize), Shift(shift), Size(0) {
  pTable = new newPair[tableSize];
}  

hashTable::~hashTable(){
  if(pTable != 0)
    delete[] pTable;
}

hashTable::hashTable(const hashTable& hT){

  this->Size = hT.Size; this->tableSize = hT.tableSize;
  this->Shift = hT.Shift; 
  this->pTable = new newPair[tableSize];
  for(int i = 0; i < Size; i++)
    this->pTable[i] = hT.pTable[i];
}

bool hashTable::operator==(const hashTable& hT) const{
  if(this->Size == hT.Size && this->tableSize == hT.tableSize  
     && this->Shift == hT.Shift && this->pTable == hT.pTable)
    return true;
  return false;
}

hashTable& hashTable::operator=(const hashTable& hT){
  if(hT == *this)
    return *this;

  this->Size = hT.Size; this->tableSize = hT.tableSize;
  this->Shift = hT.Shift; 
  this->pTable = new newPair[tableSize];
  for(int i = 0; i < Size; i++)
    this->pTable[i] = hT.pTable[i];

  return *this;
}

int hashTable::hash(int a) const { 
  cout << a << " hashes to " << a % tableSize << endl;
  return a % tableSize; 
}

int hashTable::lookUp(int a) const {

  int ind = hash(a);
  while (!empty(ind) and !(pTable[ind].first == a)) {
	cout << "Collision at " << ind << endl;
	cout << "Next try " << ind + Shift;
	ind = (ind + Shift) % tableSize;
	cout << " that hashes to " << ind << endl;
  }
  return ind;
}

int hashTable::getData(int a) const { 
  return pTable[lookUp(a)].second; 
}

int hashTable::insert(newPair a) {

  int ind = lookUp(a.first);
  if (pTable[ind].first == a.first) {
	cout << "Already inserted this value" << endl;
	return -1;
  }
  cout << "Inserting at " << ind << endl;
  pTable[ind] = a;
  Size++;
  return ind;
}

int main(){
  hashTable ht(53, 13);
  ht.insert(newPair(213, 10));
  ht.insert(newPair(54, 11));
  cout << ht.getData(54) << endl;
  return 0;
}  
///////////////////////////////////////////////////////////////////////
//simpleHeap.h
#ifndef HEAP_H
#define HEAP_H
#include "dArray.h"

class Heap {

  dArray A;

  void swap(int i, int j){
    int temp = A.pA[i]; A.pA[i] = A.pA[j];
    A.pA[j] = temp;
  }
  void upHeapify(int i);
  void downHeapify(int i, int size);

 public:

  Heap(int x) : A(dArray(1, &x)) {}
  Heap(const dArray& a);
  void insert(const int& x);
  int minimum() const {
    return A.pA[0];
  }
  int& extractMin();
  void heapSort();
  void printHeap() const;
};
#endif

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

Heap::Heap(const dArray& a) {
    A = dArray(a.Size, A.pA);
    for(int i = 1; i < A.Size; i++)
      upHeapify(a[i]);
}  

void  Heap::heapSort(){
  for(int i = A.Size - 1; i > 0; i--){
    swap(i, 0);
    downHeapify(0, i - 1);
  }
  
  for(int i = 0; i <= (A.Size - 1)/2; i++)
    swap(i, A.Size - 1 - i);
}

void Heap::downHeapify(int i, int size){
  int temp = i, newTemp;
  bool done = 0;
  while(2*temp + 1 <= size && !done){//still a remaining node
    if(2*temp + 1 == size){//no right child: bottom of the heap
      if(A.pA[temp] > A.pA[2*temp + 1])
	swap(temp, 2*temp + 1);
      done = 1;
    }
    else if(A.pA[2*temp + 1] < A.pA[2*temp + 2] && !done){
      if(A.pA[temp] > A.pA[2*temp + 1])
	swap(temp, 2*temp + 1);
      newTemp = 2*temp + 1;
    }
    else if(A.pA[2*temp + 1] >= A.pA[2*temp + 2] && !done){
      if(A.pA[temp] > A.pA[2*temp + 2])
	swap(temp, 2*temp + 2);
      newTemp = 2*temp + 2;
    }
    else
      done = 1;
    temp = newTemp;
  }
}

void Heap::upHeapify(int i){
  int temp = i;
  while(A.pA[(temp - 1)/2] > A.pA[temp]){
    swap(temp, (temp - 1)/2);
    temp = (temp - 1)/2;
  }
}

void Heap::insert(const int& x){
  A.append(x);
  upHeapify(A.Size - 1);
}

int& Heap::extractMin(){
  if(A.Size == 1)//only 1 object in the heap
    return A.pA[0];

  swap(A.Size - 1, 0);
  A.Size--;

  downHeapify(0, A.Size);

  return A.pA[A.Size];
}

void Heap::printHeap() const {
  for(int i = 0; i < A.Size; i++)
    std::cout << A.pA[i] << " ";
  std::cout << std::endl;
}

//heapDriver.cpp
#include "simpleHeap.h"

int main(){
  Heap H(5);
  H.insert(6); H.insert(8); H.insert(12); H.insert(7);
  H.insert(9); H.insert(18); H.insert(15); H.insert(25);
  H.insert(13); H.insert(11); H.insert(10);
  H.printHeap();
  H.heapSort();
  H.printHeap();
  return 0;
}

#simpleHeap.mk
dH : heapDriver.o simpleHeap.o dArray.o
	g++ -o dH heapDriver.o simpleHeap.o dArray.o

dArray.o : dArray.cpp dArray.h
	g++ -c dArray.cpp

simpleHeap.o : simpleHeap.h simpleHeap.cpp dArray.h
	g++ -c simpleHeap.cpp

dArrayDriver.o : heapDriver.cpp simpleHeap.h dArray.h
	g++ -c heapDriver.cpp
///////////////////////////////////////////////////////////////////////
//simpleSet.cpp
#include <iostream>
#include <string>
#include <utility>

using std::cout; using std::endl; using std::string; using std::pair;

struct Node : public pair <int, int>
{

  Node *Left, *Right; 
  Node() : pair<int, int>() {
    Left = 0; Right = 0;
  }

  Node(const int& key, const int& data) : pair<int, int>(key, data){
    Left = 0; Right = 0;
  }  
};

std::ostream& operator<<(std::ostream& out, const Node& node) {
  out << "(" <<  node.first << ", " << node.second <<")";
  return out;
}

class Tree{
  Node* Root; 
  int Size;

 public:

  Tree() : Root(0), Size(0){}

  const Node* insert(const pair<int, int>& pairObj); 
  const Node* lookUp(const int& key) const;
  const Node* getMin() const;
  const Node* getMax() const;
  int getSize() const {return Size;}
};

const Node* Tree::getMin() const {
  Node* temp = Root;
  if(temp != 0){
    while(temp->Left != 0)
      temp = temp->Left;
  }
  return temp;
}

const Node* Tree::getMax() const {
  Node* temp = Root;
  if(temp != 0){
    while(temp->Right != 0)
      temp = temp->Right;
  }
  return temp;
}

const Node* Tree::insert(const pair<int, int>& pairObj){
  Node *Previous, *Next = Root;
  Node* newNode = new Node(pairObj.first, pairObj.second);

  if(Next == 0){
    Root = newNode;
    Size++;
    return Root;
  }

  while(Next !=0){
    Previous = Next;
    if(pairObj.first < Next->first){
      Next = Next->Left;
    }
    else
      Next = Next->Right;
  }

  //an empty spot has been found
  if(newNode->first < Previous->first){
    Previous->Left = newNode;
  }
  else{
    Previous->Right = newNode;
  }

  Size ++;
  return newNode;
}

const Node* Tree::lookUp(const int& key) const {

  const Node* temp = Root;
  while(temp != 0 && temp->first != key){
    if(key < temp->first)
      temp = temp->Left;
    else
      temp = temp->Right;
  }
  return temp;
}


int main(){
  Tree T;
  T.insert(pair<int, int> (4, 4)); 
  T.insert(pair<int, int> (0, 1));
  T.insert(pair<int, int> (1, 2)); 
  T.insert(pair<int, int> (3, 1));
  T.insert(pair<int, int> (2, 11)); 
  T.insert(pair<int, int> (6, 5));
  T.insert(pair<int, int> (7, 4)); 
  T.insert(pair<int, int> (5, 5));
  T.insert(pair<int, int> (21, -3)); 
  T.insert(pair<int, int> (-15,99));
  T.insert(pair<int, int> (-16, 5)); 
  T.insert(pair<int, int> (-3, -3));
  T.insert(pair<int, int> (-1, 9)); 
  T.insert(pair<int, int> (-2, 14));

  cout << "The minimum is at " << *T.getMin() << endl;
  cout << "The maximum is at " << *T.getMax() << endl;

  cout << "The data value for key -1 is " 
       <<  T.lookUp(-1)->second << endl;
  return 0;
}
///////////////////////////////////////////////////////////////////////
//pointerArithmetic Ex.cpp
#include <iostream>

using std::cout; using std::endl;

int main(){
  int* begin = new int[5];
  int* end = begin + 5; 
  int* iter = begin;
  int i = 0;
  while(iter != end){
    *iter = 3*i;
    cout << *iter << " ";
    iter++;
    i++;
  }
  cout << endl;
  return 0;
}

// int main(){
//   int* begin = new int[5];
//   int* end =  begin + 5;
//   int i = 0;
//   for(int* iter = begin; iter < end; iter++){
//     *iter = 3*i;
//     cout << *iter << " ";
//     i++;
//   }
//   cout << endl;

//   return 0;
// }

// int main(){
//   int* p = new int[5];
//   for(int i = 0; i < 5; i++)
//     *(p + i) = 3*i;
//   for(int i = 0; i < 5; i++)
//     cout << *(p++) << " ";
//   cout << endl;

//   return 0;
//}
///////////////////////////////////////////////////////////////////////
//simpleLinkedList.cpp
#include <iostream>
#include <utility>

template <class Key, class Data>
struct Node {
  Data dataValue;
  Key keyValue;
  Node* Next;

  Node(){}
  Node (Data data, Key key, Node* next = 0)
    : dataValue(data), keyValue(key), Next(next) {}
};

template <class Key, class Data> 
struct LTC{

  Node<Key, Data>* Head;
  int Size;

  LTC(){Head = 0;}
  LTC(const LTC<Key, Data>& L);
  ~LTC();
  LTC<Key, Data>& operator=(const LTC<Key, Data>& L);

  //nested iterator class
  struct iterator{

    Node<Key, Data>* current;

    iterator(Node<Key, Data>* node = 0){current = node;}    
    iterator(const LTC<Key, Data>& L) : current(L.Head) {}   

    Node<Key, Data>& operator*();
    Node<Key, Data>* operator->();
    iterator& operator=(const iterator& iter);
    bool operator==(const iterator& iter) const;
    bool operator!=(const iterator& iter) const;
    iterator operator++();
    iterator operator++(int){return operator++();}
 };

  struct const_iterator : public iterator{
    const_iterator(Node<Key, Data>* node = 0) : iterator(node) {}    
    const_iterator(const LTC<Key, Data>& L) : iterator(L){} 

    const Node<Key, Data>& operator*();
    const Node<Key, Data>* operator->();
    const_iterator& operator=(const const_iterator& iter);
  };


  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;

  void push(const Data& newData, const Key& newKey);
  iterator lookUp(const Key& key);
  iterator insert(const Data& newData, const Key& newKey, 
	const Key& key);
};

template <class Key, class Data> LTC<Key, Data>::LTC(const LTC& L){
  if(L.Size == 0){
    Head = 0;
    Size = 0;
  }
  else{
 
    Size = L.Size;
    const_iterator iter;
    Node<Key, Data>* temp = 0;
    for(iter = L.begin(); iter != L.end(); iter++){
      if(temp == 0){//empty list
	Head = new Node<Key, Data>(iter->dataValue, 
	iter->keyValue);
	temp = Head;
      }
      else{
	temp->Next = new Node<Key, Data>(iter->dataValue, 
	iter->keyValue);
	temp = temp->Next;
      }
    }
    temp->Next = 0;//null pointer as Next for tail node
  }
}

template <class Key, class Data> LTC<Key, Data>::~LTC(){
  iterator iter(*this);;
  while( iter != end()){
    iter++;
    delete Head;
    Head = iter.current;
  }
}

template <class Key, class Data> LTC<Key, Data>& 
        LTC<Key, Data>::operator=(const LTC& L){
  if(this == &L)
    return *this;

  if(L.Head == 0){
    Head = 0; Size = 0;
    return *this;
  }

  Size = L.Size;
  Node<Key, Data>* temp = 0;
  for(const_iterator iter = L.begin(); iter !=L.end(); iter++){
    if(temp == 0){//empty list
       Head = new Node<Key, Data>(iter->Data, iter->Key);
       temp = Head;
    }
    else{
      temp->Next = new Node<Key, Data>(iter->Data, iter->Key);
      temp = temp->Next;
    }

    temp->Next = 0;//Next for tail node
  }  
  return *this;
}
    
template <class Key, class Data> void 
        LTC<Key, Data>::push(const Data& data, const Key& key){
  Node<Key, Data>* newNode = new Node<Key, Data>(data, key, Head);
  Head = newNode;
  Size++;
}

template <class Key, class Data> typename LTC<Key, Data>::iterator 
        LTC<Key, Data>::lookUp(const Key& key) {
  iterator iter(*this);
  while(iter != end()){
    if(iter->keyValue == key)
      return iter;
    iter++;
  }
  return 0;
}

template <class Key, class Data> typename LTC<Key,Data>::iterator 
        LTC<Key, Data>::insert(const Data& newData, 
	const Key& newKey, const Key& key){
  if(lookUp(newKey) == end()){//key does not exits
    iterator iter = lookUp(key);
    if(iter != end()){//target does exist
      Node<Key, Data>* newNode = 
	new Node<Key, Data>(newData, newKey);
      newNode->Next = iter->Next;
      iter->Next = newNode;
      Size++;
      return iter;
    }
    else{
      std::cout << "Key not found!" << std::endl;
      return end();
    }
  }
  else{
    std::cout << "Duplicate key!" << std::endl;
    return end();
  }
}

template <class Key, class Data> typename LTC<Key, Data>::iterator 
        LTC<Key, Data>::begin(){
  return iterator(*this);
}

template <class Key, class Data> typename LTC<Key, Data>::iterator 
        LTC<Key, Data>::end(){
  return iterator();
}

template <class Key, class Data> typename LTC<Key, Data>::const_iterator 
        LTC<Key, Data>::begin() const {
  return const_iterator(*this);
}

template <class Key, class Data> typename LTC<Key, Data>::const_iterator 
        LTC<Key, Data>::end() const {
  return const_iterator();
}

//iterator class method definitions

template <class Key, class Data> Node<Key, Data>& 
        LTC<Key, Data>::iterator::operator*(){
  if(current != 0)
    return *current;
}

template <class Key, class Data> Node<Key, Data>* 
        LTC<Key, Data>::iterator::operator->(){
  if(current != 0)
    return current;
  else return 0;
}
    
template <class Key, class Data> typename LTC<Key, Data>::iterator& 
        LTC<Key, Data>::iterator::operator=(const iterator& iter){
  if(this == &iter) return *this;
  current = iter.current;
  return *this;
}
    
template <class Key, class Data> bool 
        LTC<Key, Data>::iterator::operator==(const iterator& iter) 
  const {
  return (current == iter.current);
}

template <class Key, class Data> bool 
        LTC<Key, Data>::iterator::operator!=(const iterator& iter) 
  const {
  return !(*this == iter);
}

template <class Key, class Data> typename LTC<Key, Data>::iterator 
        LTC<Key, Data>::iterator::operator++(){
  if(current != 0)
    current = current->Next;
  return *this;
}

template <class Key, class Data> const Node<Key, Data>& 
        LTC<Key, Data>::const_iterator::operator*(){
  if(iterator::current != 0)
    return *iterator::current;
}

template <class Key, class Data> const Node<Key, Data>* 
        LTC<Key, Data>::const_iterator::operator->(){
  if(iterator::current != 0)
    return iterator::current;
  else return 0;
}

template <class Key, class Data> typename LTC<Key, Data>::const_iterator& 
        LTC<Key, Data>::const_iterator::operator=(const const_iterator& iter){
  if(this == &iter) return *this;
  this->iterator::operator=(iter);
  return *this;
}

//test program

void f(const LTC<int, int>  L){
  std::cout << L.Head->Next->dataValue << std::endl;
}
    
 int main(){
   LTC<int, int> L;
   L.push(2, 15); L.push(3, 18); L.push(4, 28); L.push(5, 27);
   L.push(6, 19); L.push(7, 49); L.push(2, 38); L.push(4, 6);
   L.push(100, 2); L.push(-1, 40);
   L.insert(-4, 1, 18);
   f(L);//test of copy constructor
   std::cout << L.lookUp(1)->dataValue << std::endl;
   LTC<int, int>::iterator iter(L);
   for(iter = L.begin(); iter != L.end(); iter++)
     std::cout << iter->keyValue << " ";
   std::cout << std::endl;

   LTC<int, int> newL = L;//test of = operator
   std::cout << newL.Head->Next->keyValue << std::endl;
  
  return 0;
}
///////////////////////////////////////////////////////////////////////