Security & Hacking

김재규님의 C++강좌를 보고 구현한 것입니다.
강의에 누락된 부분은 임이적으로 구현한 부분이 있으니 조심^^;


I've been studying the algorithms with Kim's lecture.
followings are results of that.

/*
virtual function 의 기능
 코드의 간결화
 하위클래스에서 정의한 함수를 상위 로직에 이용할 수있게 해줌

friend 의 기능
 private자원에 대한 접근을 허용

*/

#include<iostream>
#include<string>
#include<sstream>
#include<map>

using namespace std;
typedef void* POS;
/*
 Single Linked List
*/
template <class T> class SingleList{
 enum Exception{
  INVALID_POS,
  EMPTY_SingleList
 };
 struct Node {
  T data;
  Node *next;
 };
public:
 _init();

 SingleList();
 ~SingleList();
 // basic operation
 bool IsEmpty(){ return m_nCount == 0;}
 int GetCount(){ return m_nCount;}
 RemoveAll(void);
 T RemoveNext(POS pos);
 POS InsertNext(POS pos,const T& data);
// bool IsValid(POS pos){return true;}

 //head operation

 T RemoveHead(){return RemoveNext(m_pHead);}
 POS InsertHead(const T& data);
 T& GetHead();
 POS GetHeadPos() const { return m_pHead->next; };
 bool GetNext(POS& pos,T& value) ;
private:
 Node *m_pHead;
 Node *m_pTail;
 int m_nCount;
};
template <class T> SingleList<T>::_init()
{
 m_pHead = new Node;
 m_pTail = new Node;
 m_pHead->next = m_pTail;
 m_pTail->next = m_pTail;
 m_nCount = 0;
}
template <class T> SingleList<T>::SingleList()
{
 _init();
}
template <class T> SingleList<T>::~SingleList()
{
 RemoveAll();
}
template <class T> SingleList<T>::RemoveAll()
{
 Node *t = m_pHead->next, *p;
 while(t != m_pTail)
 {
  p = t;
  t = t->next;
  delete p;
 }
 m_pHead->next = m_pTail;

}
template <class T>
POS SingleList<T>::InsertNext(POS pos, const T& data)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0) return 0;
 if(pNode == m_pTail) return 0;

 Node *pNewNode = new Node;
 pNewNode->data = data;
 pNewNode->next = pNode->next;
 pNode->next = pNewNode;

 m_nCount ++;

 return pNewNode;
}
template <class T>
POS SingleList<T>::InsertHead(const T& data)
{
 return InsertNext(m_pHead,data);
}
template <class T>
T SingleList<T>::RemoveNext(POS pos)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0)
  throw INVALID_POS;
 if(pNode->next == m_pTail)
  throw INVALID_POS;
 
 Node *pNodeDel = pNode->next;
 pNode->next = pNode->next->next;

 T rt = pNodeDel->data;
 delete pNodeDel;

 m_nCount --;

 return rt;
}
template <class T>
bool SingleList<T>::GetNext(POS& pos,T& value)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0 || pNode == m_pTail )
  return false;// throw INVALID_POS;
 
 pos = (POS)((Node*)pos)->next;
 value = pNode->data;
 return true;
}

/*
 Double Linked List
*/

template <class T> class DoubleList{
public:
 enum Exception{
  INVALID_POS,
  EMPTY_DoubleList
 };
 struct Node {
  T data;
  Node *next;
  Node *prev;
 };
public:
 _init();

 DoubleList();
 ~DoubleList();
 // basic operation
 bool IsEmpty(){ return m_nCount == 0;}
 int GetCount() const { return m_nCount;}
 RemoveAll(void);
 T RemoveNext(POS pos);
 T RemovePrev(POS pos);
 POS InsertNext(POS pos,const T& data);
 POS InsertPrev(POS pos,const T& data);
 bool IsValid(POS pos){return true;}

 //head operation
 T RemoveHead() { return RemoveNext(m_pHead); }
 POS InsertHead(const T& data) { return InsertNext(m_pHead,data); }
 T& GetHead();
 POS GetHeadPos() const { return (POS)m_pHead->next; }

 //tail operation
 T RemoveTail(){return RemovePrev(m_pTail);}
 POS InsertTail(const T& data) { return InsertPrev(m_pTail,data); }
 void AddTail(const T& data) { InsertPrev(m_pTail,data); }
 bool IsTail(const POS& pos) const { return m_pTail == (Node*)pos; }

 // additional operation
 bool Find(const T& key, T& value);
 bool GetAt(const POS pos,T& value) const;
 bool GetNext(POS& pos,T& value) const; 
 bool DeleteAt(POS pos);

 // operator
 const DoubleList<T>& operator=(const DoubleList<T>& list);

private:
 Node *m_pHead;
 Node *m_pTail;
 int m_nCount;
public:
 bool _find(const T& key, POS& pos) const;
 //friend  class ListSeqMap;
};
template <class T> DoubleList<T>::_init()
{
 m_pHead = new Node;
 m_pTail = new Node;
 m_pHead->next = m_pTail;
 m_pHead->prev = m_pHead;
 m_pTail->next = m_pTail;
 m_pTail->prev = m_pHead;
 m_nCount = 0;
}
template <class T> DoubleList<T>::DoubleList()
{
 _init();
}
template <class T> DoubleList<T>::~DoubleList()
{
 RemoveAll();
}
template <class T> DoubleList<T>::RemoveAll()
{
 Node *t = m_pHead->next,*p;
 while(t != m_pTail){
  p = t;
  t = t->next;
  delete p;
 }
 m_pHead->next = m_pTail;
 m_pHead->prev = m_pHead;
 m_pTail->next = m_pTail;
 m_pTail->prev = m_pHead;

 m_nCount = 0;

}
template <class T>
const DoubleList<T>& DoubleList<T>::operator=(const DoubleList<T>& list)
{
 T t;
 POS pos = list.GetHeadPos();
 while ( !list.IsTail(pos) ) {
  list.GetAt(pos,t);
  InsertTail(t);
  list.GetNext(pos,t);
 }
 return *this;
}
template <class T>
bool DoubleList<T>::Find(const T& key, T& value)
{
 POS pos;
 if(!_find(key,pos))
  return false;
 value = GetAt(pos);
 return true;
}
template <class T>
bool DoubleList<T>::_find(const T& key, POS& pos) const
{
 for (Node *t = m_pHead->next; t != m_pTail ; t = t->next )
 {
  if (t->data == key) {
   pos = (POS)t;
   return true;
  }
 }
 return false;

}
template <class T>
bool DoubleList<T>::GetAt(const POS pos, T& value) const
{
 Node *pNode = (Node*) pos;
 if (pos == 0 || pos == m_pHead || pos == m_pTail)
  return false;
 value = pNode->data;

 return true;
}
template <class T>
bool DoubleList<T>::GetNext(POS& pos,T& value) const
{
 Node *pNode = (Node*) pos;
 if (pos == 0 || pos == m_pTail)
  return false;

 pos = (POS)pNode->next;
 value = pNode->next->data;
 return true;
}
template <class T>
bool DoubleList<T>::DeleteAt(POS pos)
{
 Node *pNode = (Node*) pos;
 if (pos == 0 || pos == m_pHead || pos == m_pTail)
  return false;
 
 pNode->next->prev = pNode->prev;
 pNode->prev->next = pNode->next;

 m_nCount --;
 delete pNode;
 return true;
}
template <class T>
POS DoubleList<T>::InsertNext(POS pos, const T& data)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0) return 0;
 if(pNode == m_pTail) return 0;

 Node *pNewNode = new Node;
 pNewNode->data = data;

 pNewNode->next = pNode->next;
 pNewNode->prev = pNode;
 pNewNode->next->prev = pNewNode;
 pNode->next = pNewNode;

 m_nCount ++;

 return pNewNode;
}

template <class T>
T DoubleList<T>::RemoveNext(POS pos)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0)
  throw INVALID_POS;
 if(pNode->next == m_pTail)
  throw INVALID_POS;
 
 Node *pNodeDel = pNode->next;
 pNode->next = pNode->next->next;
 pNodeDel->next->prev = pNode;

 T rt = pNodeDel->data;
 delete pNodeDel;

 m_nCount --;

 return rt;
}
template <class T>
POS DoubleList<T>::InsertPrev(POS pos, const T& data)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0) return 0;
 if(pNode == m_pHead) return 0;

 Node *pNewNode = new Node;
 pNewNode->data = data;

 pNewNode->next = pNode;
 pNewNode->prev = pNode->prev;
 pNewNode->next->prev = pNewNode;
 pNewNode->prev->next = pNewNode;

 m_nCount ++;

 return pNewNode;
}

template <class T>
T DoubleList<T>::RemovePrev(POS pos)
{
 Node *pNode = (Node*) pos;
 if(pNode == 0)
  throw INVALID_POS;
 if(pNode->prev == m_pHead)
  throw INVALID_POS;
 
 Node *pNodeDel = pNode->prev;
 pNodeDel->prev->next = pNode;
 pNode->prev = pNodeDel->prev;
 T rt = pNodeDel->data;
 delete pNodeDel;

 m_nCount --;

 return rt;
}

template <class T> class ListQueue{
public:
 ListQueue(){};
 POS Put(const T& data);
 T Get();
 bool IsEmpty(){return m_list.IsEmpty();}
private:
 DoubleList<T> m_list;
};
template <class T>
POS ListQueue<T>::Put(const T& data)
{
 return m_list.InsertHead(data);
}
template <class T>
T ListQueue<T>::Get()
{
 return m_list.RemoveTail();
}

template <class T> class ListStack{
public:
 ListStack(){}
// ~ListStack();
 POS Push(const T& data);
 T Pop();
 bool IsEmpty() {return m_list.IsEmpty();};

private:
 SingleList<T> m_list;
};
template <class T>
POS ListStack<T>::Push(const T& data)
{
 return m_list.InsertHead(data);
}
template <class T>
T ListStack<T>::Pop()
{
 return m_list.RemoveHead();
}

template <class T> class ArrayStack{
public:
 ArrayStack(int array_size);
 ~ArrayStack();
 Push(const T& data);
 T Pop();
 bool IsEmpty() { return (m_nTop == -1);}
private:
 T *m_pArray;
 int m_nTop;
 int m_nLen;
};
template <class T> ArrayStack<T>::ArrayStack(int array_size)
{
 m_pArray = new T[array_size];
 m_nTop = -1;
 m_nLen = array_size;
}
template <class T> ArrayStack<T>::~ArrayStack()
{
 if(m_pArray)
  delete []m_pArray;
}
template <class T> T ArrayStack<T>::Pop()
{
 if(!IsEmpty())
  return m_pArray[m_nTop--];
 throw "ERROR STACK UNDER FLOW";
}
template <class T> ArrayStack<T>::Push(const T& data)
{
 if(m_nTop < m_nLen -1 )
 {
  m_pArray[++m_nTop] = data;
 }
 else
  throw "ERROR STACK OVER FLOW";
}
/*
 toLong
*/
long toLong(string s)
{
 long r = 0;
 istringstream ss(s);
 ss >> r;
 return r;
}
/*
 toString
*/
string toString(long n)
{
 ostringstream ss;
 ss << n;
 return ss.str();
}

/*
 Greatest Common Divisor
*/
int gcd(int a, int b)
{
 while (b>0){
  int t = a % b;
  a = b;
  b = t;
 }
 return a;
}
template <class T> void SelectionSort(T a[], int n)
{
 T min;
 int minindex;
 int i,j;
 for( i=0; i< n-1; i++)
 {
  minindex = i;
  min = a[i];
  for ( j = i+1; j<n; j++)
  {
   if(min > a[j])
   {
    min  = a[j];
    minindex =j;
   }
  }
  a[minindex] = a[i];
  a[i] = min;
 }
}

class MyClass
{
public:
 MyClass();
 MyClass(const MyClass& c);
 bool operator==(const MyClass& c);
 bool operator>(const MyClass& c);
};
template <class T> void InsertionSrt(T a[], int n)
{
 int i,j;
 T t;
 for (i = 1; i < n ; i++)
 {
  t = a[i];
  j = i;
  while (a[j-1]> t && j>0)
  {
   a[j] = a[j-1];
   j--;
  }
  a[j] = t;
 }
}
template <class T> void BubbleSort(T a[], int n)
{
 int i,j;
 for(i=0;i<n-1;i++)
  for(j=1;j<n-i;j++)
  {
   if(a[j-1]>a[j]){
    T t = a[j-1];
    a[j-1] = a[j];
    a[j] = t;
   }
  }
}

template <class T> void BubbleSort1(T a[], int n)
{
 int i,j;
 for(i=0;i<n;i++)
  for(j=i+1;j<n;j++)
  {
   if(a[i]>a[j]){
    T t = a[i];
    a[i] = a[j];
    a[j] = t;
   }
  }
}
template <class T> int Partition(T a[], int n)
{
 T v, t;
 int i,j;
 v = a[n-1];
 i = -1;
 j = n -1;
 while (true)
 {
  while (a[++i] < v);
  while (a[--j] > v);
  if (i >= j) break;
  t = a[i]; a[i] = a[j]; a[i] =t;

 }
 t = a[i]; a[i] = a[n-1]; a[n-1] =t;
 return i;
}
template <class T> void QuickSort(T a[], int n)
{
 int i;
 if(n>1){
  i = Partition(a,n);
  QuickSort(a,i);
  QuickSort(a+i+1,n-i-1);
 }
}
// 난수분할
template <class T> void QuickSort_rn(T a[], int n)
{
 if(n>1)
 {
  pivot = GetRandom(n);
  Exchange(a[pivot],a[n-1]);
  i = Partition(a,n);
  QuickSort_rn(a,i);
  QuickSort_rn(a+i+1,n-n-1);
 }
}
// Median of three partition
template <class T> void QuickSort_median(T a[], int n)
{
 int i;
 if(n > 3)
 {
  SortThree(a[0],a[n/2],a[n-1]);
  pivot = a[n/2];
  Exchange(a[pivot], a[n-2]);
  i = Partition(a+1,n-2);
  QuickSort_median(a+1, n-2);
  QuickSort_median(a+i+2,n-i-2);
 }
 else
 {
  SortThree(a[0],a[n/2],a[n-1]);
 }
}
//Median of three partition + insert
template <class T>
void QuickSort_sub(T a[], int n)
{
 int i;
 if(n > 200)
 {
  i = Partition(a+1,n-2);
  QuickSort_sub(a+1,i-1);
  QuickSort_sub(a+i+1,n-i-2);
 }
 else
 {
  InsertionSort(a,n);
 }
}

template <class T> void QuickSort_nr(T a[], int n)
{
 T v, t;
 int i,j;
 int l,r;
 ListStack<int> stack;
 l = 0;
 r = n-1;
 stack.Push(r);
 stack.Push(l);
 while (!stack.IsEmpty())
 {
  l = stack.Pop();
  r = stack.Pop();
  if(r-l+1 > 1) //
  {
   v = a[r];
   i = l - 1;
   j = r;
   while(true)
   {
    while (a[++i] < v);
    while (a[--j] > v);
    if(i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[i]; a[i] = a[r]; a[r] = t;
   stack.Push(r);
   stack.Push(i+1);
   stack.Push(i-1);
   stack.Push(l);
  }
 }
}
/*
 qsort 가 stdlib.h 에 정의
 다음과 같이 비교함수를 인자로..
*/
int intcmp(const void* a, const void* b)
{
 return (*(int*)a - *(int*)b);
}

// Selection Problem
// Selection Sort를 이용한 방법
template <class T>
T Select_Linear(T a[], int n, int k)
{
 T min;
 int minindex;
 int i,j;
 for (i=0; i<n-1; i++) {
  minindex = i;
  min = a[i];
  for (j = i +1; j < n; j++) {
   if (min > a[j]){
    min = a[j];
    minindex = j;
   }
  }
  a[minindex] = a[i];
  a[i] = min;
  if(i == k)
   return min;
 }
 throw "Invalid k";
}
// 분할을 이용한 반법
template <class T>
T Selection(T a[], int l, int r, int k)
{
 int i;
 if(r > l)
 {
  i = Partition(a,l,r);
  if(i>l+k-1) Selection(a, l, i-1, k);
  if(i<l+k-1) Selection(a,i+1, r, k-i);
 }
}

template <class T>
T Selection_Partition(T a[], int n, int k)
{
 T v,t;
 int i,j,l,r;
 l = 1;
 r = n;
 while (r>l)
 {
  v = a[r];
  i = l -1;
  j = r;
  while (true)
  {
   while (a[++i] < v);
   while (a[--j] > v);
   if (i >= j) break;
   t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[r]; a[r] =t;
  if (i >= k) r = i -1;
  if (i <= k) l = i + 1;
 }
 return a[i];
}

/*
 힙정렬 HeapSort
 
   힙정렬에 사용되는 이진 트리의 조건
   -부모노드는 자식노드보다 크다.
   -따라서 root가 가장 큰값.
  
   부가로 메모리가 사용되지 않는다는 장점

 
*/
template <class T> class Heap
{
public:
 Heap();
 Heap(T a[], int n);
 T& a(int k) { return m_pArray[k-1];}
 int GetHeaplen() { return m_nHeapLen;}
 void SetHeapLen(int n) { m_nHeapLen = n;}
 void UpHeap(int k);
 void DownHeap(int k);
 void Insert(T v);
 T Extract(void);
private:
 T *m_pArray;
 int m_nArrayLen;
 int m_nHeapLen;
};
template <class T>
void Heap<T>::UpHeap(int k)
{
 T v;
 v = a(k);
 while (v > a(k/2) && k >1)
 {
  a(k) = a(k/2);
  k /= 2;
 }
 a(k) = v;
}
template <class T>
void Heap<T>::Insert(T v)
{
 a(++m_nHeapLen) = v;
 UpHeap(m_nHeapLen);
}
template <class T>
void Heap<T>::DownHeap(int k)
{
 int i;
 T v;
 v = a(k);
 while( k<= m_nHeapLen/2) {
  i = k*2;
  if(i <m_nHeapLen && a(i+1) > a(i)) i++;
  if(v > a(i) || v == a(i))break;
  a(k) = a(i);
  k = i;
 }
 a(k) = v;
}
template <class T>
T Heap<T>::Extract(void)
{
 T v = a(1);
 a(1) = a(m_nHeapLen--);
 DownHeap(1);
 return v;
}
// Heap개선 상향식으로
template <class T>
void HeapSort_up(T a[], int n)
{
 int k;
 Heap<T> heap(a,n);
 heap.SetHeapLen(n);

 //내부노드에 대해서만 DownHeap
 for (k = n/2; k >= 1; k--)
  heap.DownHeap(k);
 while(n>1)
  heap.a(n--) = heap.Extract();
}

//ShellSort h(n) = 2h(n-1)
template <class T>
void ShellSort(T a[], int n)
{
 int i,j,k,h;
 T v;
 for ( h = n/2 ; h > 0 ; h /= 2 )
 {
  for ( i = 0 ; i < h ; i++ ) // 변이
  {
   for ( j = i+h ; j < n ; j += h )
   {
    v = a[j];
    k = j;
    while ( k > h-1 && a[k-h] > v)
    {
     a[k] = a[k-h];
     k -= h;
    }
    a[k] = v;
   }
  }
 }
}
//ShellSort h(n) = 3h(n-1)+1
template <class T>
void ShellSort_3h(T a[], int n)
{
 int i,j,k,h;
 T v;
 for( h =1; h< n; h = 3*h+1);
 for ( h /=3 ; h > 0 ; h /= 3 )
 {
  for ( i = 0 ; i < h ; i++ ) // 변이
  {
   for ( j = i+h ; j < n ; j += h )
   {
    v = a[j];
    k = j;
    while ( k > h-1 && a[k-h] > v)
    {
     a[k] = a[k-h];
     k -= h;
    }
    a[k] = v;
   }
  }
 }
}

template <class T>
void MergeSort(T a[], int n)
{
 int i,j,k,first,second,size;
 T *b;
 b = new T[n];
 assert(b != 0);
 for(size = 1; size <n; size *= 2)
 {
  first = 0;
  second = size;
  while(second < n)
  {
   i = first;
   j = second;
   k = first;
   while (i<first + size || (j<second + size && j < n))
   {
    if (a[i] > a[j]) {
     if (j <second + size && j <n)
      b[k++] = a[j++];
     else
      b[k++] = a[i++];
    } else {
     if (i < first + size)
      b[k++] = a[i++];
     else
      b[k++] = a[j++];
    }
   }
   first += 2*size;
   second  += 2*size;
  }
  for (i=0; i<n; i++)
   a[i] = b[i];
 }
 delete [] b;
}

template <class T>
void MergeSort_ex(T a[], int n)
{
 int i,j,k,first,second,size;
 T *b;
 b = new T[n];
 assert(b != 0);
 T *src = a;
 T *tmp = b;
 for(size = 1; size <n; size *= 2)
 {
  first = 0;
  second = size;
  while(second < n)
  {
   i = first;
   j = second;
   k = first;
   while (i<first + size || (j<second + size && j < n))
   {
    if (src[i] > src[j]) {
     if (j <second + size && j <n)
      tmp[k++] = src[j++];
     else
      tmp[k++] = src[i++];
    } else {
     if (i < first + size)
      tmp[k++] = src[i++];
     else
      tmp[k++] = src[j++];
    }
   }
   first += 2*size;
   second  += 2*size;
  }
  //
  T *t= src;src = tmp; tmp = t;
 }
 if(tmp == a)
  for (int l =0 ; l<n; l++) a[i] = b[i];
 delete [] b;
}

template <class T>
bool CheckSort(T a[], int n)
{
 for ( int i=0; i < n-1 ; i++ )
 {
  if( a[i] > a[i+1] ) return false;
 }
 return true;
}

//기수 교환 정렬
unsigned long bits(unsigned long x, int k, int j)
{
 return (x >> k) & ~(~0 << j);
}
void RadixExchangeSort(unsigned long a[], int n, int b = 31)
{
 unsigned long t;
 int i,j;

 if ( n > 1 && b >= 0 ) //종료조건
 {
  i = 0;
  j = n - 1;
  while ( true )
  {
   while (bits(a[i],b,1) == 0 && i < j) i ++;
   while (bits(a[j],b,1) != 0 && i < j) j --;
   if ( i >= j ) break;
   t = a[i]; a[i] = a[j]; a[j] = t;
  }
  if ( bits(a[n-1],b,1) == 0) j++;
  RadixExchangeSort(a,j,b-1);
  RadixExchangeSort(a+j,n-j,b-1);
 }
}
void RadixExchangeSort_nr(unsigned long a[], int n)
{
 unsigned long t;
 int i,j;
 int l,r;
 int b = 31; // assume 32bit
 ArrayStack<int> stack(32*3 + 3);
 l = 0; r = n-1;
 stack.Push(b); stack.Push(r);stack.Push(l);
 while (!stack.IsEmpty()) {
  l = stack.Pop(); r = stack.Pop(); b = stack.Pop();
  if ( r > l && b >= 0 ) //종료조건
  {
   i = l; j = r;
   while ( true )
   {
    while (bits(a[i],b,1) == 0 && i < j) i ++;
    while (bits(a[j],b,1) != 0 && i < j) j --;
    if ( i >= j ) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   if ( bits(a[r],b,1) == 0) j++;
   stack.Push(b-1); stack.Push(r);stack.Push(j);
   stack.Push(b-1); stack.Push(j-1);stack.Push(l);
  }
 }
}

void StraightRaixSort(unsigned long a[], int n)
{
 int i,j;
 unsigned long *b, *count;
 unsigned long w = 32;
 unsigned long m = 8;
 unsigned long mv = (1 << m);

 b = new unsigned long [n];
 count = new unsigned long [mv];
 for(i = 0; i< w/m; i++){
  for (j =0; j < mv; j++)
   count[j] = 0;
  for (j =0; j < n; j++)
   count[bits(a[j],i*m,m)]++;
  for (j =1; j < mv; j++)
   count[j] = count[j] + count[j-1];
  for (j = n-1; j >= 0; j--)
   b[--count[bits(a[j],i*m,m)]] = a[j];
  for (j = 0; j < n; j++)
   a[j] = b[j];
 }
 delete []b;
 delete []count;
}

/*
 Search
  -주어진 자료집합에서 원하는 레크드를 찾는 것
  -Issues:삽입/검색/삭제
  -자료집합의 조직화 여부에 따라 성능이 달라짐
 순차검색
  -ArraySeqMap (삽입O(1), 검색O(N), 삭제O(N))
  -ListSeqMap (삽입O(1), 검색O(N), 삭제O(1))
 이분검색
  -BinMap(삽입:O(N) 검색:O(LogN) 삭제O(N))
 내분검색
  -ItpMap(삽입:O(N),검색:O(loglogN), 삭제O(N))
*/

/*
 *Map을 사용하기 위한 class 구조
 받드시 정의해야 할 것들
 *Default Constructor
 *Copy Constructor
 *operator =
 *operator ==
 *operator >
*/
class Person
{
public:
 int m_id; //key
 string m_name;
 Person() : m_id(0) {}
 Person(int id, const string& name) : m_id(id), m_name(name){}
 Person(const Person& p) { m_id = p.m_id;m_name = p.m_name;}
 Person operator = (const Person& p) {
  m_id = p.m_id; m_name = p.m_name; return *this;
 }
 bool operator == (const Person& p) const { return m_id == p.m_id;}
 bool operator > (const Person& p) const { return m_id> p.m_id;}
 
 //Radix Search를 위한 연산자 정의
 unsigned long operator>>(const unsigned long i) const {return m_id >> i;};
 friend class PersonHash;
// private 을 접근 허용하는 것이다.

};

class PersonHash
{
public:
 unsigned long hash(const Person& p)const {
  return (unsigned long)p.m_id * 11;
 }
};

/*
 Sequential Search?
  -무순서로 저장된 자료집합에서 검색하고자
  하는 key를 처음 부터 차례로 비교해서 찾아 내는 방법
 검색하는 방법
  - 삽입(insert)
   자료집합(array)의 제일 뒤에 새로운 자료추가 (갯수 증각)
  - 검색(Find)
   자료집합의 처음부터 key를 찾음
  - 제거(Remove)
   자료집합에서 keyfmf 찾아 해당 레크드를 삭제하고
   뒷부분을 앞으로 당김 (메모리 이동, 갯수감속)
 Complexity
  -Insertion : O(1)
  -Find : O(N)
  -Remove: O(N)

*/
template <class T> class ArraySeqMap
{
public:
 struct MapPos{
  T key;
  long index;
 };
public:
 ArraySeqMap(int nSize = 100);
 ~ArraySeqMap() {delete []m_pArray;}

 //utility function
 long GetCount() const {return m_nLen;}
 bool IsEmpty() const { return m_nLen == 0 ;}
 void RemoveAll() const { m_nLen = 0;}

 //operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
 bool FindFirst(const T& key, T& value, MapPos& pos) const;
 bool FindNext(T& value, MapPos& pos) const;
 bool RemoveAt(const MapPos& pos);
protected:
 T *m_pArray;
 long m_nArraySize;
 long m_nLen;
 virtual bool _find(MapPos& pos) const;
};
template <class T>
bool ArraySeqMap<T>::Insert(const T& value)
{
 //check for too may items
 if(m_nLen + 1 > m_nArraySize)
  return false;

 // add new item to end
 m _pArray[m_nLen++] = value;
 return true;
}

template <class T>
bool ArraySeqMap<T>::_find(MapPos& pos) const
{
 if(pos.index >= m_nLen) //범위를 벗어나면
  return false;
 
 bool found = false;
 for(int i = pos.index; i < m_nLen; i++){
  if(m_pArray[i] == pos.key) {
   found = true;
   break;
  }
 }
 if (found){
  pos.index = i;
  return treu;
 }else {
  return false;
 }
}
template <class T>
bool ArraySeqMap<T>::Find(const T& key, T& value) const
{
 MapPos pos;
 pos.index = 0;
 pos.key = key;
 if( !_find(pos))
  return false;
 value = m_pArray[pos.index];
 return true;
}
template <class T>
bool ArraySeqMap<T>::FindFirst(const T& key, T& value, MapPos& pos) const
{
 pos.index = 0;
 pos.key = key;
 if (!_find(pos))
  return false;
 value = m_pArray[pos.index];
 return true;
}
template <class T>
bool ArraySeqMap<T>::FindNext(T& value,MapPos& pos) const
{
 pos.index ++;
 if(!_find(pos))
  return false;
 value = m_pArray[pos.index];
 return true;
}
template <class T>
bool ArraySeqMap<T>::Remove(const T& key)
{
 MapPos pos;
 pos.index = 0;
 pos.key = key;
 if(!_find(pos))
  return false;
 RemoveAt(pos);
 return true;
}
template <class T>
bool ArraySeqMap<T>::RemoveAt(const MapPos& pos)
{
 // 뒷녀석들 당기기
 for(int i = pos.index +1; i< m_nLen; i++)
  m_pArray[i-1] = m_pArray[i];
 m_nLen--;
 return true;
}
/*
 ArraySeqMap개선:Lazy Deletion
 :키값과 Excape과의 구분이 가능할 경우
 -Remove 후 메모리를 이동하지 않고
 -삭제되었다는 표시만을 해두는 방법
 -예: key는 양의 정수만 있다면, Escape코드로 -1을 사용
 - 삽입의 효율을 위해 Empty List를 사용하는 것이 좋음
  *Empty List: 삭제된 곳의 index를 저장하는 리스트
*/

/*
 Linked List를 이용한 순차검색
 잇점
 Remove 동작이 단순하다.
  Array로 했을 경우 빈곳을 메우기 위한 메모리 이동
 그러나
  느리다.

 Complexity
  -Insert : O(1)
  -Find : O(N)
  -Delete : O(1)

*/
template <class T> class ListSeqMap
{
public:
 struct MapPos{
  T key;
  POS pos;
 };
public:
 ListSeqMap(){}
 ~ListSeqMap() {}

 //utility function
 long GetCount() const {return m_list.GetCount();}
 bool IsEmpty() const { return m_list.IsEmpty();}
 void RemoveAll() const { m_list.RemoveAll();}

 //operations
 bool Find(const T& key, T& value);
 bool Insert(const T& value);
 bool Remove(const T& key);
 bool FindFirst(const T& key, T& value, MapPos& pos);
 bool FindNext(T& value, MapPos& pos);
 bool RemoveAt(const MapPos& pos);
protected:
 DoubleList<T> m_list;
 virtual bool _find(MapPos& pos) const;

};
template <class T>
bool ListSeqMap<T>::_find(MapPos& pos) const
{
 if(!m_list._find(pos.key, pos.pos))
  return false;
 else
  return true;
}
/*
 MRU 기법 적용 (Most Recently Used)
  -가장 최근에 검색된 레코드를 앞으로 옮김
  -실세계에서 검색은
   *전체집합 중 극히 일부분에 대해 이루어지고
   *그 일부분에 대해 중복적으로 이루어지는 경우가 많다.
   *ex)전체 회원데이타베이스에서 Royalty높은 회원은 소수다.
*/

template <class T>
bool ListSeqMap<T>::Find(const T& key, T& value)
{
 MapPos pos;
 pos.pos = 0;
 pos.key = key;

 if(!_find(pos))
  return false;
 value = m_list.GetAt(pos.pos);

 //MRU 법칙으로 찾은 갑을 제일 앞으로 올림
 m_list.DeleteAt(pos.pos); //지우고
 m_list.AddHead(value); //해더 뒤에 넣는다.
 return true;
}
template <class T>
bool ListSeqMap<T>::Insert(const T& value)
{
 m_list.AddTail(value);
 return true;
}
template <class T>
bool ListSeqMap<T>::Remove(const T& key)
{
 MapPos pos;
 pos.pos = 0;
 pos.key = key;

 if(!_find(pos))
  return false;

 RemoveAt(pos);
 return true;
}
template <class T>
bool ListSeqMap<T>::RemoveAt(const MapPos& pos)
{
 bool result = true;
 try {
  m_list.DeleteAt(pos.pos);
 } catch (DoubleList<T>::Exception) {
  result = false;
 }
 return result;
}
template <class T>
bool ListSeqMap<T>::FindFirst(const T& key, T& value, MapPos& pos)
{
 pos.pos = 0;
 pos.key = key;

 if(!_find(pos))
  return false;
 value = m_list.GetAt(pos.pos);
 return true;
}
template <class T>
bool ListSeqMap<T>::FindNext(T& value, MapPos& pos)
{
 m_list.GetNext(pos.pos);
 if (pos.pos == 0)
  return false;
 if(!_find(pos))
  return false;
 value = m_list.GetAt(pos.pos);
 return true;
}
 

/*
 이분검색 Binary Search
 -자료집합은 정렬되어 있어야한다.
 -구간크기 > 0, key값과 중앙값을 비교하여
  *key 값 == 중앙값이면 찾은 것이다.
  *key 값 > 중앙값이면 오른쪽 구간 선택
 -Insert: 정렬된 상태가 유지 되어야 하므로
  *삽입정렬 알고리즘
 -Del: 삭제한 곳 뒤의 자료들을 앞으로 당긴다.
  *
 
 Complexity
  -Insert : O(N)
  -Find : O(logN)
  -Del : O(N)
*/
template <class T>
int BinarySearch(T a[], int left, int right, T key)
{
 while(right >=left){
  mid = (left + right)/2;
  if(a[mid] == key) return mid;
  if(key > a[mid]) left = mid+1;
  else right = mid -1;
 }
 // Not found!!!
}

template <class T> class BinMap : public ArraySeqMap<T>
{
public:
 BinMap(int nSize =100): ArraySeqMap<T>(nSize) {}
 ~BinMap() {} // m_pArray는 ~ArraySeqMap에저 지워줌
 //operation
 bool Insert(const T& value);
 bool FindFirst(const T& key, T& value, MapPos& pos) const;
 bool FindNext(T& value, MapPos& pos)const;
protected:
 bool _find(MapPos& pos) const;
};
template <class T>
bool BinMap<T>::_find(MapPos& pos) const
{
 int mid;
 int left = 0;
 int right = m_nLen -1;
 while (right >= left) {
  mid = (right +left) / 2;
  if(pos.key == m_pArray[mid]) {
   pos.index = mid;
   return true;
  }
  if (pos.key > m_pArray[mid]) lef = mid + 1;
  else right = mid -1;
 }
 return false;
}
template <class T>
bool BinMap<T>::Insert(const T& value)
{
 if(!ArraySeqMap<T>::Insert(value))
  return false;

 //Insertion Sort
 for(int j = m_nLen - 1; j>0; j--)
 {
  if(m_pArray[j] > value)
   m_pArray[j] = m_pArray[j-1];
  else
   break;
 }
 m_pArray[j] = value;
 return true;
}
/*
 ArraySeqMap 과의 차이가있음
*/
template <class T>
bool BinMap<T>::FindFirst(const T& key, T& value, MapPos& pos) const
{
 if(!ArraySeqMap<T>::FindFirst(key,value,pos))
  return false;
 for(int j = pos.index; j>0;j--){
  if(!(m_pArray[j-1]==value)) break;
 }
 pos.index =j;
 value = m_pArray[pos.index];
 return true;
}
template <class T>
bool BinMap<T>::FindNext(T& value, MapPos& pos) const
{
 if(pos.index + 1 >= m_nLen) return false;
 if(m_pArray[pos.index +1] == pos.key) {
  pos.index++;
  value = m_pArray[pos.index];
  return true;
 } else {
  return false;
 }
}

/*
 내분 검색 Interpolation Search
 :자료집합이 정렬된 선형 분포를 가진다고 가정하고
  -내분법(Interpolation)에 의해 mid값을 찾음
  -그외 과정은 이분검색과 동일
  -산술연산 가능한 숫자키만 가능
    *,/,-.+ 연산이 가능해야함
 
   이분법
   (right-left):(mid-left) = (a[right] -a[left]):(key - a[left])
   (mid-left)*(a[right]-a[left])=(right-left)*(key -a[left])
   mid = left + (right-left)*(key-a[left])/(a[right]-a[left])

 Complexity
  -삽입 : O(N)
  -검색 : O(log logN)
      성능은 그렇게 좋지 않음
   비교는 덜하나 무거운 double계산..;;
   이분검색 보다 빠르다는 것은 모름..;;

  -삭제 : O(N)
*/
template <class T> class ItpMap : public BinMap<T>
{
public:
 ItpMap(int nSize = 100) : BinMap<T>(nSize){}
 ~ItpMap(){}
protected:
 bool _find(MapPos& pos) const;
};
template <class T>
bool ItpMap<T>::_find(MapPos& pos) const
{
 int mid;
 int left = 0;
 int right = m_nLen -1;
 while(right >= left) {
  if(!(m_pArray[right] == m_pArray[left]))){
   mid = (int)(left + (double)(pos.key - m_pArray[left])*
      (right - left)/(m_pArray[right]-m_pArray[left]));
   if(mid <left)mid = left;
   if(mid >right)mid = right;
  } else
   mid = left; // 젯수가 0 인 경우,
      // left와 rigtht사이는 모두 같은 값, 아무거나 리턴
  if ( pos.key == m_pArray[mid]) {
   pos.index = mid;
   return true;
  }
  if (pos.key > m_pArray[mid]) left = mid +1;
  else right = mid -1;
 }
 // Not found
 return false;
}
/*
 트리 Tree

 -Node(vertex)와 Link(edge)로 구성됨
  *Node는 정보를 포함하고 있음
  *Link는 두 Node간의 연결관계를 나타냄
 -다음의 특징을 만족해야 함
  *Root가 하나 존재 : Root는 최상위 Node
  *Root를 제외한 모든 Node는 하나의 부모를 가져야 함
  *Node는 여러개의 자식을 가질 수 있음
  *한 Node로 부터 다른 Node로 가는 경로는 유일
 
    full binary tree
     :마지막레벨을 제외한 모든 레벨에 노드가 꽉차있음
    complete binary tree
     :모든 레벨이 노드가 꽉차있음

     Tree Traversal
   Stack 기반: Pre-order, Post-order, In-order
   Queue 기반: Level-order

  pre-order 1.Root 2. Left 3. Right
  post-order 1.Left 2. Root 3. Right
  in-order 1.Left 2.Right 3.Root

     수식트리 Parse Tree
  1.In-Order Traverse 하면 Infix Notation
  2.Pre-Order Traverse 하면 Prefix Notation
  3.Post-Order Traverse 하면 Postfix Notation

   후위표기에서 수식트리구성
     알고리즘
   1. Operand 는 Node를 만들어 Stack에 Push
   2. Operand 는 Node를 생성하여
     1. Stack에서 Pop한 노드를 오른쪽자식으로 하고
     2. Stack에서 또 Pop 한 노드를 왼쪽자식으로 하고
     3. Operator Node를 Stack에 Push
   3. Stack에 마지막으로남은 노드가 Root이다.
*/
/*
void BinaryTree::PreOrderTraverse(Node* pNode)
{
 if(pNode != m_pNodeTail)
 {
  Visit(pNode);
  PreOrderTraverse(pNode->pLeft);
  PreOrderTraverse(pNode->pRight);
 }
}
void BinaryTree::PreOrderTraverse_nr(Node *pNode)
{
 ListStack<Node*> stack;
 stack.Push(pNode);
 while (!stack.IsEmpty())
 {
  pNode = stack.Pop();
  if(pNode != m_pNodeTail)
  {
   Visit(pNode);
   stack.Push(pNode->pRight);
   stack.Push(pNode->pLeft);
  }
 }
}

*/

template <class T> class BinaryTree
{
public:
 BinaryTree();
 ~BinaryTree();
 void RemoveAll();

protected:
 struct Node {
  T data;
  Node* pLeft;
  Node* pRight;
 };
 Node* m_pNodeHead;
 Node* m_pNodeTail;
 void RemoveSubtree(Node *pNode);
};
template <class T>
BinaryTree<T>::BinaryTree()
{
 m_pNodeHead = new Node;
 m_pNodeTail = new Node;
 m_pNodeHead->pLeft = m_pNodeTail;
 m_pNodeHead->pRight = m_pNodeTail;
 m_pNodeTail->pLeft = m_pNodeTail;
 m_pNodeTail->pRight = m_pNodeTail;
}
template <class T>
BinaryTree<T>::~BinaryTree()
{
 RemoveAll();
 if(m_pNodeHead)
  delete m_pNodeHead;
 if(m_pNodeTail)
  delete m_pNodeTail;
}
template <class T>
void BinaryTree<T>::RemoveAll()
{
 RemoveSubtree(m_pNodeHead->pLeft);
}
template <class T>
void BinaryTree<T>::RemoveSubtree(Node *pNode)
{
 if(pNode != m_pNodeTail){
  RemoveSubtree(pNode->pLeft);
  RemoveSubtree(pNode->pRight);
  delete pNode;
 }
}

class ParseTree : public BinaryTree<string>
{
public:
 void BuildParseTree(const string& strPostfix);
 bool IsOperator(char c) {
  return (c =='+' || c=='-' ||c=='*'|| c== '/');
 }
 void PreOrderTraverse(Node *pNode =0);
 void PostOrderTraverse(Node *pNode = 0);
 void InOrderTraverse(Node *pNode =0);
 void LevelOrderTraverse(Node *pNode =0);
 void Visit(Node *pNode);
};
void ParseTree::BuildParseTree(const string& strPostfix)
{
 Node *pNode;
 int i=0;
 ListStack<Node*> NodeStack;
 RemoveAll();

 while(strPostfix[i])
 {
  while(strPostfix[i] == ' ')
   i++;
  pNode = new Node;
  if(IsOperator(strPostfix[i])) {
   pNode->data = strPostfix[i];
   i++;
   pNode->pRight = NodeStack.Pop();
   pNode->pLeft = NodeStack.Pop();
  }
  else {
   do {
    pNode->data += strPostfix[i];
    i++;
   } while (strPostfix[i] != ' ' &&
    i<strPostfix.length());
   pNode->pLeft = m_pNodeTail;
   pNode->pRight = m_pNodeTail;
  }
  NodeStack.Push(pNode);
 }
 m_pNodeHead->pLeft = NodeStack.Pop();
 
}
void ParseTree::PostOrderTraverse(Node* pNode)
{
 if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

 if(pNode != m_pNodeTail)
 {
  PostOrderTraverse(pNode->pLeft);
  PostOrderTraverse(pNode->pRight);
  Visit(pNode);
 }
}
void ParseTree::PreOrderTraverse(Node* pNode)
{
 if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

 if(pNode != m_pNodeTail)
 {
  Visit(pNode);
  PreOrderTraverse(pNode->pLeft);
  PreOrderTraverse(pNode->pRight);
 }
}
void ParseTree::InOrderTraverse(Node* pNode)
{
 if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

 if(pNode != m_pNodeTail)
 {
  InOrderTraverse(pNode->pLeft);
  Visit(pNode);
  InOrderTraverse(pNode->pRight);
 }
}
void ParseTree::LevelOrderTraverse(Node* pNode)
{
 if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

 ListQueue<Node*> queue;
 queue.Put(pNode);
 while(!queue.IsEmpty())
 {
  pNode = queue.Get();
  if(pNode != m_pNodeTail)
  {
   Visit(pNode);
   queue.Put(pNode->pLeft);
   queue.Put(pNode->pRight);
  }
 }
}

void ParseTree::Visit(Node *pNode)
{
 printf("%s ", pNode->data.c_str());
}

/*
 이진트리 검색 Binary Tree Search
 -Binary Tree를 이용하는 검색방법
 평균적으로 삽입/검색/삭제 모드 O(logN)의 성능
 이전 검색트리의 조건
  *부모노드는 왼족sub-tree의 모든 노드보다 크고
  *부모노드는 오른쪽 sub-tree의 모든 노드보다 작다
     따라서 이진트리를 In-Order Traversal하면 정렬된 순서다.
 
    삽입 : O(N), 균형이 맞으면 O(logN)
 검색 : O(N), 균형이 맞으면 O(logN)
 삭제 : O(logN)
  
*/

template <class T> class BinTreeMap : public BinaryTree<T>
{
public:
 enum Exception{
  INSUFFICIENT_MEMORY_FOR_SORT
 };
 BinTreeMap() : BinaryTree<T>() { m_nCount = 0;}
 ~BinTreeMap(){}
 //Utilities
 long GetCount() const {return m_nCount;}
 bool IsEmpty() const { return m_nCount == 0;}
 void RemoveAll() { BinaryTree<T>::RemoveAll(); m_nCount = 0;}
 //Operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
 //Special operatiokn for Binary Tree Search
 void Sort(T a[], int n, Node* p = 0) const;
 void Balance();
protected:
 long m_nCount;
 Node* _balance(T a[], int n, bool start=true);

};

template <class T>
bool BinTreeMap<T>::Find(const T& key, T& value) const
{
 Node *s = m_pNodeHead->pLeft;
 while(s != m_pNodeTail)
 {
  if(key==s->data) {
   value = s->data;
   return true;
  } else if ( key < s->data ) {
   s = s->pLeft;
  } else {
   s = s->Rigth;
  }
 }
 return false;
}
template <class T>
bool BinTreeMap<T>::Insert(const T& value)
{
 Node *p,*s;
 p = m_pNodeHead;
 s = m_pNodeHead->pLeft;
 while(s != m_pNodeTail)
 {
  p = s;
  if(value > s->data)
   s = s->pRight;
  else
   s = s->pLeft;
 }
 s = new Node;
 s->data = value;
 s->pLeft = m_pNodeTail;
 s->pRight = m_pNodeTail;

 if(value > p->data && p!=m_pNodeHead)
  p->pRight = s;
 else
  p->pLeft = s;
 
 m_nCount++;
 return true;
}
/*
 Leaf 노드 삭제는 간단함
 내부노드의 경우 자신을 대체할 노드를 선택해야함
  - 자신보다 작은 노드중 최대노드
  - 자신보다 큰 노드중 최소노드
 세가지 경우로 나누어 구현
  - 삭제할 노드의 오른쪽자식이 없는 경우
    cdd = del->pLeft
    delp의 left 혹은 right 자식으로 cdd연결
  - 삭제할 노드의 오른쪽자식의 왼쪽자식이 없는 경우
    cdd = del->pRight
    cdd->pLeft = del->pLeft;
    delp의 left 혹은 right 자식으로 cdd연결
  - 그외의 경우
    cdd = del의 오른쪽 서브트리에서 가장 왼쪽노드
    cddp->pLeft = cdd->pRight
    cdd->pLeft = del->pLeft;
    cdd->pRight = del->pRight;
  delp->pLeft of pRight = cdd;
  
*/
template <class T>
bool BinTreeMap<T>::Remove(const T& key)
{
 if(IsEmpty()) return false;
 Node *delp, *del;
 Node *cdd,*cddp;
 
 // find del
 delp = m_pNodeHead;
 del = m_pNodeHead->pLeft;
 while(!(key == del->data) && del != m_pNodeTail) {
  delp = del;
  if(key > del->data) del = del->pRight;
  else del = del->pLeft;
 }
 if (del = m_pNodeTrail) return false;
 if (del->pRight == m_pNodeTail) { // Case 1
  cdd = del->pLeft;
 } else if ( del->pRight->pLeft == m_pNodeTail) {// case 2
  cdd = del->pRight;
  cdd->pLeft = del->pLeft;
 } else { // case3
  cddp = del;
  cdd = del->pRight;
  while (cdd->pLeft != m_pNodeTail) {
   cddp = cdd;
   cdd = cdd->pLeft;
  }
  cddp->pLeft = cdd->pRight;
  cdd->pLeft = del->pLeft;
  cdd->pRight = del->pRight;
 }
 // delp의 자식으로 cdd를 결정
 if(key >del->data && delp != m_pNodeHead)
  delp->pRight =cdd;
 else delp->pLeft = cdd;
 delete del;
 m_nCount --;
 return true;
}

/*
 이진트리 정렬
  - N개의 자료를 Insert
  - 트리를 In-Order Traversal 하면 됨
  평균(NlogN) 최악 O(N2)
*/
template <class T>
void BinTreeMap<T>::Sort(T a[], int n, Node* p)const
{
 static int index = 0;
 if (p == 0)
 {
  if(m_nCount!=n)
   throw INSUFFICIENT_MEMORY_FOR_SORT;
  index =0;
  p = m_pNodeHead->pLeft;
 }
 if(p != m_pNodeTail)
 {
  Sort(a,n,p->pLeft);
  a[index++] = p->data;
  Sort(a,n,p->pRight);
 }
}
/*
 이진트리검색
*/
template <class T>
void BinaryTreeSort(T a[], int n)
{
 BinTreeMap<T> bintree;
 for(int i =0; i<n; i++)
  bintree.Insert(a[i]);
 bintree.Sort(a,n);
}

/*
 Binary Tree Balance Algorithm
*/
template <class T>
void BinTreeMap<T>::Balance()
{
 T *a;
 a = new T[m_nCount];
 Sort(a, m_nCount);
 int nCount = m_nCount;
 RemoveAll();
 m_pNodeHead->pLeft = _balance(a,nCout,true);
 m_nCount = nCount;
 delete []a;
}

template <class T>
BinTreeMap<T>::Node*
BinTreeMap<T>::_balance(T a[], int n, bool start)
{
 static int index = 0;
 if (start)
  index = 0;
 Node *p;
 int nl, nr;
 if (n >0) {
  nl = (n-1)/2;
  nr = n - nl -1;
  p = new Node;

  p->pLeft = _balance(a, nl, false);
  p->data = a[index++];
  p->pRight = _balance(a, nr, false);
  return p;
 }
 else
  return m_pNodeTail;
}
/*
 이진검색트리에서의 중복키 문제
 Binary Tree + Linked List 로 해결 ;;
*/

/*
 해쉬 Hash
 Hash Function : 키값을 수치로 변환하는 함수
  -인접키를 널리 퍼뜨리도록 하라
   * 키값을 제곱, 세제곱을 하면 퍼진다.
   * 비드연산으로 비트구성을 완전히 다르게 변환
  -빈도가 높은 키영역을 넓게 펴도록 하라.
   * 입력자료의 특성 분석 필요
  -해쉬테이블의 크기는 소수(Prime Number)로 하는 것이 좋다.
   * 적어도 20이하의 약수는 없도록

   ex) MFC MAP_SO.CPP
    inlien UINT CMapStringToOB::HashKey(LPCTSTR key) const
    {
   UINT nHash = 0;
   while (*key)
    nHash = (nHash<<5) + nHash + *key++;
   return nHash;
    }

 Hash Table:
 Collision 해결법
  -Linear Probing = Open Addressing
   예상입력 자료수의 2배의 해쉬 테이블 필요
   정적인 자료 검색에 유리
  -Separate Chaining

 Double Hash
  -충돌시 이차 해쉬함수 사용
  -연속된 클러스터가 더 적게 나올 수 있음
*/
template <class T,class HASH> class HashMap
{
public:
 struct MapPos {
  T key;
  long index;
 };
 enum NodeStatus{
  EMPTY, DELETED, AVAIL
 };
protected:
 struct Node {
  T data;
  NodeStatus status;
  Node() { status = EMPTY;}
 };
public:
 //HASH연산을 하는 클래스를 인자로 받음
 //unsigned long hash(const T& k) const;
 HashMap(const HASH& hash, int nSize =100);
 ~HashMap(){delete [] m_pArray;}
 //utility function
 long GetCount() const { return m_nCount; }
 bool IsEmpty() const { return m_nCount ==0;}
 void RemoveAll() {
  for (int i=0; i<m_nArraySize; i++)
   m_pArray[i].status = EMPTY;
 }
 //operations
 bool Find(const T& key, T& value);
 bool Insert(const T& value);
 bool Remove(const T& key);
 bool FindFirst(const T& key, T& value, MapPos& pos) const;
 bool FindNext(T& value, MapPos& pos) const;
 bool RemoveAt(const MapPos& pos);
protected:
 Node *m_pArray;
 long m_nArraySize;
 long m_nCount;
 HASH m_hash;
 bool _find(MapPos& pos) const;
 int _next(const T& key) const { return 1; }
};
template <class T, class HASH>
HashMap<T,HASH>::HashMap(const HASH& hash, int nSize)
{
 m_hash = hash;
 m_nArraySize = nSize;
 m_pArray = new Node[nSize];
}

template <class T, class HASH>
bool HashMap<T,HASH>::Insert(const T& value)
{
 int start, index;
 index = start = m_hash.hash(value) % m_nArraySize;
 while (m_pArray[index].status == AVAIL)
 {
  index = (index + _next(value)) % m_nArraySize;
  if(index == start) // full
   return false;
 }
 m_pArray[index].status = AVAIL;
 m_pArray[index].data = value;
 m_nCount ++;
 return true;
}
template <class T, class HASH>
bool HashMap<T,HASH>::_find(MapPos& pos)const
{
 int start, index;
 index = start = m_hash.hash(pos.key) % m_nArraySize;
 while (m_pArray[index].status != EMPTY) // AVAIL or DELETED
 {
  if(m_pArray[index].status == AVAIL && m_pArray[index].data == pos.key)
  {
   pos.index = index;
   return true;
  }
  index = (index + _next(pos.key)) % m_nArraySize;
  if(index == start) // 한바퀴 다 돌았다.;;
   return false;
 }
 return false;
}
template <class T,class HASH>
bool HashMap<T,HASH>::Find(const T& key, T& value)
{
 MapPos pos;
 pos.key = key;
 if(!_find(pos))
  return false;
 value = m_pArray[pos.index].data;
 return true;
}
template <class T,class HASH>
bool HashMap<T,HASH>::FindFirst(const T& key, T& value, MapPos& pos) const
{
 // not codig yet
 return true;
}
template <class T,class HASH>
bool HashMap<T,HASH>::FindNext(T& value, MapPos& pos) const
{
 // not coding yet
 return true;
}

template <class T,class HASH>
bool HashMap<T,HASH>::RemoveAt(const MapPos& pos)
{
 int(m_nCount <=0 || pos.index < 0 || pos.index >=m_nArraySize)
  return false;
 if(m_pArray[pos.index].status != AVAIL) // nothing to remove
  return false;
 m_pArray[pos.index].status = DELETED;
 m_nCount --;
 return true;
}
template <class T,class HASH>
bool HashMap<T,HASH>::Remove(const T& key)
{
 MapPos pos;
 pos.key = key;
 pos.index = 0;
 if(!_find(pos))
  return false;
 RemoveAt(pos);
 return true;
}
/*
 Separate Chaining
  해쉬테이블 = 연결리스트의 배열
  범용으로 사용가능
  동적인 상황에 유리
  삽입:DoubleList::AddHead()를 이용
  삭제:DoubleList::DeleteAt사용
  검색:DoubleList::Find를 이용
*/
template <class T,class HASH> class ChainMap
{
public:
 struct MapPos {
  T key;
  long index;
  POS pos; //링크드 리스트에서 이용
 };
public:
 ChainMap(const HASH& hash, int nSize =100);
 ~ChainMap() { delete [] m_pArray;}
 //utility functions
 long GetCount() const { return m_nCount;}
 bool IsEmpty() const { return m_nCount == 0;}
 void RemoveAll() {
  for (int i=0; i<m_nArraySize;i++)m_pArray[i].RemoveAll();
 }
 //operations
 bool Find(const T& key, T& value)const;
 bool Insert(const T& value);
 bool Remove(const T& key);
 bool FindFirst(const T& key, T& value, MapPos& pos) const;
 bool FindNext(T& value, MapPos& pos) const;
 bool RemoveAt(const MapPos& pos);
protected:
 ListSeqMap<T> *m_pArray;
 long m_nCount;
 long m_nArraySize;
 HASH m_hash;
 bool _find(MapPos& pos)const;
};
template <class T, class HASH>
ChainMap<T,HASH>::ChainMap(const HASH& hash, int nSize)
{
 m_pArray = new ListSeqMap[nSize];
 m_nArraySize = nSize;
 m_nCount = 0;
 m_hash = hash;
}
template <class T, class HASH>
bool ChainMap<T,HASH>::Insert(const T& value)
{
 int index = m_hash.hash(value) % m_nArraySize;
 if(m_pArray[index].AddHead(value) == 0) return false;
 else return true;
}
template <class T, class HASH>
bool ChainMap<T,HASH>::_find(MapPos& pos) const
{
 pos.index = m_hash.hash(pos.key) % m_nArraySize;
 pos.pos = m_pArray[pos.index].Find(pos.key,pos.pos);
 if(pos.pos == 0) return false;
 else return true;
}
template <class T, class HASH>
bool ChainMap<T,HASH>::Find(const T& key, T& value) const
{
// MapPos pos;
// pos.key = key;
// if(!_find(pos))
//  return false;
// value = m_pArray[pos.index]
}
template <class T, class HASH>
bool ChainMap<T,HASH>::RemoveAt(const MapPos& pos)
{
 int index = m_hash.hash(pos.key) % m_nArraySize;
 m_pArray[index].DeleteAt(pos.pos);
 return true;
}

/*
 기수 검색 Radix Search
 -Radix Tree, Radix Trie, Partricia, Extendible Hash( 주로 외부 검색(디시크)) ...
 키비트 배열을 이용하는 검색방법

*/
/*
 Radix Tree Search
 -노드의 레벨에 해당하는 비트의 값에 따라(LSB부터)
 -0은 왼쪽 자식으로 1은 오른쪽 자식으로 배치
 -키의 디지털 특성을 이용함
   쏠림현상 제거
 -키의 중복이 허용되지 않는다.
 키의 비트수가 M이라면
  자료는 2 에 M승 개가 들어갈수 있고
  트리의 높이는 최대 M+1이다.

    삽입
   -레벨에 따른 비트검사를 통해 Leaf로 이동
   -새로운 노드는 Leaf에 추가한다.
 검색
   -검색키의 비트검사를 통해 노드를 탐색
 삭제
   -삭제키키의 비트검사를 통해 노드를 탐색
   -세가지 경우로 나누어 노드를 삭제(이진 검색트리와 동일)
    경우1: 오른쪽자식이 없을때
    경우2: 오른쪽 자식의 왼쪽 자식이 없을째
    경우3: 그외의 경우
   
*/
template <class T> class RadixTreeMap : public BinaryTree<T>
{
public:
 RadixTreeMap() : BinaryTree<T>() { m_nCount = 0; }
 ~RadixTreeMap() {}
 //utilities
 long GetCount() const { return m_nCount;}
 bool IsEmpty() const { return m_nCount == 0;}
 void RemoveAll() { BinaryTree<T>::RemoveAll(); m_nCount =0;}
 //operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
protected:
 unsigned long bits(const T& x, unsigned long k, unsigned long j) const
 {
  return (x >> k) & ~(~0 << j);
 }
 long m_nCount;
};
//사용자정의 타입에서 사용하려면 operator>>를 구현해야 한다.
template <class T>
bool RadixTreeMap<T>::Insert(const T& value)
{
 Node *p, *t;
 unsigned b = 0; //검사 대상 비트
 // Leaf노드까지 진행
 p = m_pNodeHead;
 t = m_pNodeHead->pLeft;
 while (t!=m_pNodeTail){
  if(value == t->data) return false; //동일키 삽입금지
  p = t;
  t = bits(value,b++,1)? t->pRight:t->pLeft;
 }
 //새 노드 생성해서 Leaf에 추가
 t = new Node;
 t->data = value;
 t->pLeft = m_pNodeTail;
 t->pRight = m_pNodeTail;
 if (bits(value,b-1,1) && p != m_pNodeHead) p->pRight = t;
 else p->pLeft = t;
 m_nCount ++;
 return true;
}
template <class T>
bool RadixTreeMap<T>::Find(const T& key, T& value) const
{
 Node* t = m_pNodeHead->pLeft;
 unsigned b = 0;
 while(t != m_pNodeTail){
  if(t->data == key){
   value = t->data;
   return true;
  }
  t = bits(key,b++,1)?t->pRight:t->pLeft;
 }
 return false;
}
template <class T>
bool RadixTreeMap<T>::Remove(const T& key)
{
 if(IsEmpty()) return false;
 Node *del,*delp,*cdd,*cddp;
 unsigned b = 0;
 //find del node
 delp = m_pNodeHead;
 del = m_pNodeHead->pLeft;
 while (del != m_pNodeTail && !(key==del-data))
 {
  delp = del;
  del = bits(key,b++,1)?del->pRight:del->pLeft;
 }
 if(del == m_pNodeTail) return false;
 if(del->pRight == m_pNodeTail) { //case 1
  cdd =del->pLeft;
 } else if (del->pRight->pLeft == m_pNodeTail) {
  //case 2
  cdd = del->pRight;
  cdd->pLeft = del->pLeft;
 } else { // case 3
  cddp = del;
  cdd = del->pRight;
  while (cdd->pLeft != m_pNodeTail) {
   cddp = cdd;
   cdd = cdd->pLeft;
  }
  cddp->pLeft = cdd->pRight;
  cdd->pLeft = del->pLeft;
  cdd->pRight = del->pRight;
 }
 if (bits(key,b-1,1)&& delp!= m_pNodeHead)
  delp->pRight = cdd;
 else
  delp->pLeft = cdd;
 delete del;
 m_nCount --;
 return true;
}

/*
 Radix Trie Search
 -Trie의 노드는 정보노드와 분기노드 두종류가 있다.
  *정보노드(Information Node):실제 데이타를 저장
  *분기노드(Branch Node): 빈노드
 -정보노드는 항상 Leaf에 존재
 -모든 내부노드는 분기노드이다.
 -Radix Tree와 유사하게 Bit따라 좌/우 판단

 특징
  -자료의 입력순서와 무관
  -키의 중복이 허용되지 않음
  -키의 비트수가M이라면
   *자료는 2의 M승개 입력될 수 있고
   *트리의 높이는 M+1을 넘지 않느다.
    (즉 높이는 log(M) +1 이다)
  -키의 비교는 Lear에서 한번만 하면 된다.
   *키의 비교가 복잡한 경우에 유용.
*/
template <class T> class RadixTrieMap : public BinaryTree<T>
{
public:
 RadixTrieMap() : BinaryTree<T>(){m_nCount = 0;}
 ~RadixTrieMap(){}
 //utilities
 long GetCount() const { return m_nCount;}
 long IsEmpty() const { return m_nCount ==0;}
 void RemoveAll() { BinaryTree<T>::RemoveAll(); m_nCount =0;}
 //operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
protected:
 unsigned long bits(const T& x, unsigned long k, unsigned long j) const
 {
  return (x >> k) & ~(~0 << j);
 }
 bool IsBranch(Node *p) const
 {
  return (p->pLeft != m_pNodeTail || p->pRight != m_pNodeTail);
 }
 long m_nCount;
};

template <class T>
bool RadixTrieMap<T>::Find(const T& key, T& value) const
{
 Node *t;
 unsigned b = 0;
 t = m_pNodeHead->pLeft;

 while ( IsBranch(t))
 {
  t = bits(key,b++,1)?t->pRight:t->pLeft;
 }

 if(t->data == key)
 {
  value = t->data;
  return true;
 }
 else
  return false;
}
/*
 case1:첫번째 데이타
 case2:부모가 분기노드
 case3:부모가 정보노드
*/
template <class T>
bool RadixTrieMap<T>::Insert(const T& value)
{
 unsigned b = 0;
 Node *gp, *p, *t;
 gp = p = m_pNodeHead;
 t = m_pNodeHead->pLeft;
 while (t!= m_pNodeTail)
 {
  if(value == t->data)return false; // 중복금지
  gp = p;
  p = t;
  t = bits(value,b++,1)?t->pRight:t->pLeft;
 }
 b--;
 if(p==m_pNodeHead){ // case1
  t = new Node;
  t->pLeft = t->pRight = m_pNodeTail;
  t->data = value;
  p->pLeft = t;
 } else if (IsBranch(p)) { // case 2
  t = new Node;
  t->pLeft = t->pRight = m_pNodeTail;
  t->data = value;
  if(bits(value, b, 1))p->pRight = t;
  else p->pLeft = t;
 } else { // case 3
  do {
   t = new Node;
   t->pLeft = t->pRight = m_pNodeTail;
   if (gp != m_pNodeHead && bits(value, b-1, 1))
    gp->pRight =t;
   else gp->pLeft = t;
   gp = t;
   b++;
  } while (bits(value, b-1, 1) == bits(p->data, b-1, 1));
  t = new Node;
  t->data = value;
  t->pLeft = t->pRight = m_pNodeTail;
  if(bits(value,b-1,1)) {
   gp->pRight = t;
   gp->pLeft = p;
  } else {
   gp->pLeft = t;
   gp->pRight = p;
  }
 }
 m_nCount ++;
 return true;
}
/*
 case1: 형제노드가 분기노드
 case2: 형제노드가 정보노드
 
*/
template <class T>
bool RadixTrieMap<T>::Remove(const T& key)
{
 Node *delp, *del, *sib, *cp;
 unsigend b = 0, cpb = 0;
 cp = delp = m_pNodeHead;
 del = m_pNodeHead->pLeft;
 while (IsBrance(de)) {
  delp = del;
  if (del->pLeft != m_pNodeTail &&
   del->pRight != m_nNodeTail &&
   (IsBranch(del->pLeft) || IsBranch(del->pRight))) {
   // 자식이 두개인 노드: cp가 된다.
   cp = del;
   cpb = b;
  }
  del = bits(key, b++,1)?del->pRight: del->pLeft;
 }
 if(!(del->data == key)) return false; // not found
 // 경우 1,2 공통
 delete del;
 // sib찾기
 if(delp != m_pNodeHead && bits(key,b-1,1)) {
  delp->pRight = m_pNodeTail;
  sib = selp->pLeft;
 } else {
  delp->pLeft = m_pNodeTail;
  sib = delp->pRight;
 }
 if(!IsBranch(sib)){ //case 2
  delp = cp;
  del = bits(key,cpb,1)? delp->pRight:delp->pLeft;
  b = cpb + 1;
  while (IsBrach(del)) {
   delp = del;
   del = bits(key,b++, 1)?
    delp->pRight : delp->pLeft;
   delete delp;
  }
  if(cp != m_pNodeHead && bits(key,cpb,1))
   cp->pRight = sib;
  else
   cp->pLeft = sib;
 }
 m_nCount --;
 return true;
}
/*
 B-Tree
  Balanced Tree
   AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree ...
  B-Tree?
   -하나의 노드에 여러자료가 배치되는 트리구조
   -한 노드에 M개의 자료가 배치되면 M차 B-Tree
    *M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.
    *다음 알고리즘은 M이 3보다 크거나 같은 홀수라고 가정한다.
   짝수가 더어렵다.
   2-3 Tree == 2차 B-tree
   2-3-4 Tree == 3차 B-tree
   규칙1
    -노드의 자료수가 N이라면, 자식의 수는 N+1이어야 한다.
    -각 노드의 자료는 정렬된 상태여야 한다.
    -노드의 자료 Dk의 왼쪽 서브트리는 DK보다 작은 값들이고,
      DK의 오른쪽 서브트리 DK보다 큰 값들이어야 한다.

   규칙2
    -Root노드는 적어도 2개이상의 자식을 가져야 한다.
    -Root드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
    -외부노드로 가는 경로의 길이는 모두 같다.
     *외부노드는 모두 같은 레벨
    -입력 자료는 중복될 수 없다.

*/
template <class T> class BTreeMap
{
public:
 BTreeMap(int dim = 5) ;
// ~BReeMap();
 //utilities
 long GetCount() const { return m_nCount; }
 bool IsEmpty() const { return m_nCount ==0; }
 void RemoveAll();
 //operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
protected:
 typedef struct Node* PNODE;
 struct Node {
  T *m_pKeys;
  Node **m_pChildren;
  int m_nKeys;
  Node(int dim) {
   m_pKeys = new T[dim];
   m_pChildren = new Node* [dim+1];
   for(int i = 0; i<= dim; i++) m_pChildren[i] = 0;
   m_nKeys = 0;
  }
  ~Node() {
   delete [] m_pKeys;
   delete [] m_pChildren;
  }
  PNODE& Left(int n) { return m_pChildren[n]; }
  PNODE& Right(int n) { return m_pChildren[n+1]; }
  T& Key(int n) { return m_pKeys[n]; }
  int& Size() { return m_nKeys; }
  void AddValue(const T& value, Node* left, Node* right)
  {
   int i;
   i = m_nKeys; // Insert Sort
   while (i>0 && Key(i-1) > value) {
    Key(i) = Key(i-1);
    Left(i+1) = Left(i);
    i--;
   }
   m_nKeys++;
   Key(i) = value;
   Left(i) = left;
   Right(i) = right;;
  }
  void DelValue(int index)
  {
   for ( int i = index +1; i <Size(); i++) {
    Key(i-1) = Key(i);
    Left(i-1) = Left(i);
   }
   Left(i-1) = Left(i);
   m_nKeys--;
  }
  void FindKey(const T& key)
  {
   for(int i =0 ; i< m_nKeys; i++)
    if(key == Key(i)) return i;
    return -1;
  }
  void Clear(int dim)
  {
   m_nKeys = 0;
   for(int i =0; i<= dim; i++) m_pChildren[i] = 0;
  }
 };
 Node* m_pNodeHead;
 void _RemoveSubtree(Node *pNode);
 Node* _Split(const T& key, Node* pivot);
 bool _BorrowKey(Node *p, int index);
 Node* _BindNode(Node* p, int index);
 T _SwapKey(Node *del, int index);
 long m_mCount;
 long m_nDim; // B-Tree의 차수
};
template <class T>
bool BTreeMap<T>::Find(const T& key, T& value) const
{
 Node *t;
 int index;
 t = m_pNodeHead->Left(0);
 while ( t != 0 && (index = t->FindKey(key)) <0)
 {
  for(int i = 0; i< t->Size() && key > t->Key(i); i++);
  t = t->Left(i);
 }
 if(t == 0) return false; // not found
  value = t->Key(index); // found
  return true;
}
/*
 삽입 알고리즘1
 -자료는 항상 Leaf 노드에 추가된다.
  *Leaf의 선택은 삽입될 키의 하향 탐색에 의해 결정
 -추가될 Leaf노드에 여유가 있다면 그냥 삽입
 -추가될 Lear노드에 여유가 없다면 '분할'하기
 
 삽입 알고리즘2
 -분할을 위해서는 키 하나를 부모로 올려야 함
  * 부모가 꽈 차있다면 문제!
 -삽입을 위한 하향 탐색을 하면서 꽉찬 노드는 분할 해 주어야 함.

*/
/*
 pivot : 분할하고자하는 노드의 부모
 split : 분할하고자하는 노드
 key : 삽입하고자하는 키
 return 값 : 분할된 노드의 부모
*/
template <class T>
BTreeMap<T>::Node* BTreeMap<T>::_Split(const T& key, Node* pivot)
{
 Node *left, *right;
 Node *split; // 리턴할 노드
 int i,j;
 right = new Node(m_nDim);
 // case 1 : 분할할 노드가 Root인 경우
 if(pivot == m_pNodeHead) {
  split = pivot->Left(0);; // child == root;
  //left child 생성
  left = new Node(m_nDim);
  for(i=0;i<m_nDim/2;i++) {
   left->Key(i) = split->Key(i);
   left->Left(i) = split->Left(i);
  }
  left->Left(i) = split->Left(i);
  left->Size() = m_nDim/2;
  // right child 생성
  for (i=m_nDim/2+1, j=0; i<m_nDim; i++,j++){
   right->Key(j) = split->Key(i);
   right->Left(j) = split->Left(i);
  }
  right->Left(j) = split->Left(i);
  right->Size() = m_nDim/2;
  //부모노드 정리
  T temp = split->Key(m_nDim/2);
  split->Clear(m_nDim);
  split->AddValue(temp,left,right);
 } else { // case 2: 분할할 노드가 Root가 아닌경우
  // 분할할 노드를 찾기
  for(i=0;i<pivot->Size() && key > pivot->Key(i); i++);
  //왼쪽 노드는 이미 있는 노드이므로 갯수만 조정
  left = pivot->Left(i);
  left->Size() = m_nDim/2;
  //오른쪽 노드 생성
  for(i-m_nDim/2+1, j=0;i<m_nDim;i++, j++) {
   right->Key(j) = left->Key(i);
   right->Left(j) = left->Left(i);
  }
  right->Left(j) = left->Left(i);
  right->Size() = m_nDim /2;
  //중간키를 부모에 삽입
  pivot->AddValue(left->Key(m_nDim/2),left,right);
  split = pivot;
 }
 return split;
}
template <class T>
bool BTreeMap<T>::Insert(const T& value)
{
 Node *t, *p;
 int i;
 p = m_pNodeHead;
 t = m_pNodeHead->Left(0);
 if(t==0){ //root노드가 없다면 생성해 주어야함
  t = new Node(m_nDim);
  m_pNodeHead->Left(0) = t;
 }
 while(t!=0) {
  if(t->FindKey(value) >=0) // 중복키 삽입 금지
   return false;
  if(t->Size() == m_nDim) //꽉찬 노드이면 분할
   t =_Splist(value,p);
  p = t;
  for(i=0;i<t->Size() && value > t->Key(i); i++);
  t = t->Left(i);
 }
 p->AddValue(value,0,0);
 m_nCount++:
 return true;
}
/*
 B-Tree삭제 알고리즘
  -삭제하고자 하는 자료가 있는 노드가
   *삭제후 자료수가 M/2 이상이 되도록 보장해야 함!
  -형제에게 빌리기 VS 형제와 결합하기
   *빌리기:형제가 M/2보다 많은 자료를 가지고 있다면
   *결합하기:형제에게서 빌릴 수 없다면

  -삭제키가 내부노드인 경우
   *대체키를 찾아 대체해야 함(이진트리와 동일)
  -삭제를 위한 하향탐색을 하면서 자료수가 M/2이하인 노드는 형제에게 빌리든지 결합해야함

    
*/
/*
 p : 삭제할 노드의 부모노드
 index : 삭제할 노의의 index
*/
template <class T>
bool BTreeMap<T>::_BorrowKey(Node *p, int index)
{
 int from, to;
 Node *p1, *p2;
 to = index;
 if(index == p->Size()) // 가장 오른쪽인 경우 왼쪽 형제에게 빌림
  from = index -1;
 else // 아니면 오른쪽 형제에게서 빌림
  from = index + 1;
 p1 = p->Left(from); // p1 : 빌려주는 노드
 p2 = p->Left(to); // p2 : 빌리는 노드
 if (p1->Size() <= m_nDim/2) //빌려줄 키가 없을때 실패를 리턴
  return false;
 if(from > to) { // 오른쪽 형제에게서 빌림
  p2->AddValue(p->Key(to),p2->Left(p2->Size()),p1->Left(0));
  p->Key(to) = p1->Key(0);
  p1->DelValue(0);
 } eles { // 왼쪽 형제에게서 빌림
  p2->AddValue(p->Key(form,p1->Left(p1->Size()), p2->Left(0));
  p->Key(from) = p1->key(p1->Size() -1);
  p1->DelValue(p1->Size() -1));
 }
 return true;
}
template <class T>
BTreeMap<T>::Node* BTreeMap<T>::_BindNode(Node* p, int index)
{
 Node *left, *right;
 int i;
 if (index == p->Size()) index--; // 가장 오른쪽이면 index 감소
 left = p->Left(index);
 right = p->Right(index);
 left->Key(left->Size()++) = p->Key(index); //왼쪽노드에 부모키를 복사
 for(i=0; i<right->Size(); i++) { //왼쪽노드에 오른쪽 노드를 복사
  left->Key(left->Size()) = right->Key(i);
  left->Left(left->Size()++) = right->Left(i);
 }
 left->Left(left->Size()) = right->Left(i);
 p->DelValue(index); //부모노드에서 결합한 키를 삭제
 p->Left(index) = left; // 포인터 조절
 delete right;
 if(p->Size() == 0) { // root노드일 수 밖에 없음
  delete p;
  m_pNodeHead->Left(0) = left;
 }
 return left; // 결합된 노드를 리턴
}
template <class T>
T BTreeMap<T>::_SwapKey(Node* del, int index)
{
 Node *cdd, *cddp;
 cddp = del;
 cdd = cddp->Right(index); // 삭제키의 오른쪽 자식
 while (cdd->Left(0) != 0)
 {
  cddp = cdd;
  cdd = cdd->Left(0);
 }
 del->Key(index) = cdd->Key(0); // 키대체
 return cdd->Key(0);
}
template <class T>
bool BTreeMap<T>::Remove(const T& key)
{
 Node *t, *p;
 int pi = 0; // 부모의 index
 int ti = 0; // 현재노드의 index
 T value = key;
 p = m_pNodeHead;
 t = m_pNodeHead->Left(0);
 while(t != 0) {
  if(t->Size() <= m_nDim/2 && p != m_pNodeHead) { //확장할 필요가 있으면 확장
   if(!_BorrowKey(p,pi))// 형제에게 빌려보고 실패하면 형제와 결합
    t = _BindNode(p,pi);
  }
  if((ti = t->FindKey(value)) >= 0) { //삭제키가 이 노드에 있으면
   if(t->Left(0) == 0) break; //외부노드이면 break;
   else value = _SwapKey(t,ti); //내부노드이면 바꿈. 이제 새로운 value를 아래로 내려야 한다.
  }
  p = t;
  for(pi =0; pi <t->Size() && (value > t->Key(pi) || value == t->Key(pi));pi++);
  t = t->Left(pi);
 }
 if(t == 0) return false;
 if(t->Size() <= m_nDim/2 && p!=NodeHead) //외부노드인데 키수가 너무 적으면
  if(!_BorrowKey(p,pi)) t = _BindNode(p,pi);
 t->DelValue(t->FindKey(value)); //노드키를 삭제
 m_nCount--;
 return true;
}

/*
 Red-Black Tree의 특징
   - 2-3-4트리의 Balanced 특성을 Binary Tree 표현
    *2-3-4tree 3차 B-tree
 Red-Black Tree의 특성
   -빨간노드와 검정노드 두가지가 있음
   -빨간노드는 검정노드와 결합되는 의미
   -Red-Edge, Black-Edge로 표현하기도 함
  성질
   -부모노드는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.
   -Root에서 Leaf로 가는 경로의 검정노드의 수는 모두 같다.
   -새로 삽입되는 노드는 Leaf에 위치하며 빨간노드이다.
   -경로상에 연이어 두개의 빨간노드가 있을 수 없다. (회전필요)
   -부모의 두 자식노드가 모두 빨간노드이면, 부모를 빨간노드로 하고
   자식은 검정노드로 바뀔 수 있따. (생상변환)
   -Root노드는 빨간 노드일 수 없다.(검정색으로 변환)
   -빨간노드는 자식이 없던가, 있있다면 두개의 검정노드여야 한다.
   검정노드는 자식이 없던가. 있다면 하나의 빨간노드나 두개의 빨간노드나 두개의 검정노드를 가진다.
    *즉 단 하나의 검정노드를 자식으로 가질 수 없다.

 색변환(Color Flip)
  -상향색변환 : B-Tree의 Split 동작
   *빨강을 위로 올림
  -하향색변환 : B-Tree의 BindeNode 동작
   *빨강을 아래로 내림
 회전은
  -이진 트리의 규틱을 깨지 않고 트리를 재구성하는 방법
  -우회전(RightRotation)과 좌회전 (Left Rotation)
  -좌우의 트리높이를 맞추는 방향으로 회전함
   *AVL트리의 기본 Operation
 
*/
template <class T> class RBTreeMap
{
public:
 RBTreeMap();
 ~RBTreeMap();
 //Utilities
 long GetCount() const { return m_nCount; }
 bool IsEmpty() const { return m_nCount ==0; }
 void RemoveAll();
 void RemoveSubtree(Node* p);
 //Operations
 bool Find(const T& key, T& value) const;
 bool Insert(const T& value);
 bool Remove(const T& key);
protected:
 struct Node {
  T data;
  Node *pLeft; Node *pRight;
  bool Red;
  Node() {pLeft = pRight = 0; Red = false; }
 };
 Node* _Rotate(const T& key, Node* pivot);
 bool _IsLeafNode(const Node *p)const;
 bool _Is2Node(const Node *p)const;
 bool _DelLeafNode(const T& key, Node *delp, Node *del);
 bool _RedAsParent(Node *delgp, Node *delp, Node *sib);
 T _SwapKey(Node *del);
 bool _BorrowKey(Node *delgp, Node *delp, Node *del, Node *sib);
 void _BindNode(Node *delp);
 void RemoveSubtree(Node *pNode);
 Node *m_pNodeHead;
 long m_nCount;
};
template <class T>
RBTreeMap<T>::RBTreeMap()
{
 m_pNodeHead = new Node;
 m_pNodeHead->pRight = m_pNodeHead->pLeft =0;
}
template <class T>
RBTreeMap<T>::~RBTreeMap()
{
 RemoveAll();
 if(m_pNodeHead)
  delete m_pNodeHead;
}
template <class T> void
RBTreeMap<T>::RemoveAll()
{
 ListStack<Node*> stack;
 Node *t;
 stack.Push(m_pNodeHead->pLeft);
 while(!stack.IsEmpty())
 {
  t = stack.Pop();
  if(t){
   stack.Push(t->pRight);
   stack.Push(t->pLeft);
   delete t;
  }
 }
 m_pNodeHead->pLeft = 0;
 m_nCount = 0;
}

template <class T>
bool RBTreeMap<T>::Find(const T& key, T& value) const
{
 Node *s;
 s = m_pNodeHead->pLeft;
 while (s && !(key == s->data))
 {
  if(key >s->data) s = s->pRight;
  else s = s->pLeft;
 }
 if(s == 0) return false;
 value = s->data;
 return true;
}
/*
 Red-Black 트리 삽입 알고리즘
  -왼쪽서브트리 < 부모 < 오른쪽서브트리 규칙에 맞게 하향탐색
  -하향 탐색을 하면서 Color Promotion한다.
   *만일 빨간노드가 연속될때는 (Double) Rotation을 한다.
     -Leaf에 도달하면 빨간노드로 자료를 삽입한다.
   *만일 빨간노드가 연속될때는 (Double) Rotation을 한다.

*/
template <class T>
RBTreeMap<T>::Node* RBTreeMap<T>::_Rotate(const T& key, Node* pivot)
{
 Node *child, *gchild;
 if((key>pivot->data || key == pivot->data) && pivot != m_pNodeHead)
  child = (Node*)pivot->pRight;
 else
  child = (Node*)pivot->pLeft;
 if(key > child->data || key == child->data) //Rotate Left
 {
  gchild = (Node*)child->pRight;
  child->pRight = gchild->pLeft;
  gchild->pLeft = (Node*)child;
 }
 else // Rotate Right
 {
  gchild = (Node*)child->pLeft;
  child->pLeft = gchild->pRight;
  gchild->pRight = (Node*)child;
 }
 if((key>pivot->data || key == pivot->data) && pivot != m_pNodeHead)
  pivot->pRight = gchild;
 else
  pivot->pLeft = gchild;
 return gchild;
}
template <class T>
bool RBTreeMap<T>::Insert(const T& value)
{
 Node *t,*p,*gp,*ggp;
 ggp = gp = p = (Node*)m_pNodeHead;
 t = (Node*)m_pNodeHead->pLeft;
 while(t) {
  if(value == t->data) return false; //중복키 삽입금지
  if(t->pLeft && t->pRight &&
   t->pLeft->Red && t->pRight->Red) {
   // Color Promotion
   t->Red = true;
   t->pLeft->Red = t->pRight->Red = false;
   if(p->Red) { // 회전이 필요
    gp->Red = true;
    if((value>gp->data) !=(value>p->data))
     p = _Rotate(value,gp); // double-Rotation
    t = _Rotate(value,ggp);
    t->Red = false;
   }
   //뿌리는 검정으로
   m_pNodeHead->pLeft->Red = false;
  }
  ggp = gp; gp = p; p = t;
  if ( value > t->data) t = t->pRight;
  else t = t->pLeft;
 }
 t = new Node;
 t->data = value;
 t->pLeft = t->pRight = 0;
 t->Red = true; //새로삽입되는 노드는 레드
 if(value > p->data && p!= m_pNodeHead)
  p->pRight = t;
 else
  p->pLeft = t;
 m_nCount++;
 if(p->Red) { //부모가 빨강이면 회전
  gp->Red = true;
  if((value>gp->data)!=(value > p->data))
   p = _Rotate(value,gp); //double rotation
  t = _Rotate(value, ggp);
  t->Red = false;
 }
 // root는 검정으로
 m_pNodeHead->pLeft->Red = false;
 return true;
}
/*
 Red-Black 트리 삭제 알고리즘
 -원칙1: Leaf 3-4노드의 삭제는 Trivial하다.
 -원칙2: 3노드의 등가표현 중 하향탐색경로 쪽으로 빨간노드가 위치하도록 바꾼다.
   *Color Demotion의 편이를 위해
 -원칙3: 삭제키를 찾는 하향탐색 중에 2노드를 3-4노드로 부풀려야 한다.(Color Demotion)
   *형제에게서 빌리기 vs 형제와 결합하기
 -원칙4: 내부노드의 삭제는 In-Order Successor (Predecessor)와 바꿔치기 한 다음 Leaf 3-4노드의 삭제문제로 돌린다.

*/
template <class T>
bool RBTreeMap<T>::_DelLeafNode(const T& key, Node *delp, Node *del)
{
 if(key == del->data && !del->pLeft && !del->pRight) {
  //red leaf나 black leaf인 경우
  delete del;
  if((key > delp->data || key == delp->data)
   && delp->data != m_pNodeHead)
   delp->pRight = 0;
  else
   delp->pLeft = 0;
  return true;
 }
 else if (key == del->data) { //black node
  Node *ret;
  if(del->pLeft) {
   del->pLeft->pRight = del->pRight;
   ret = del->pLeft;
   ret->Red = false;
   delete del;
  } else if (del->pRight) { // Delete Right Child
   del->pRight->pLeft = del->pLeft;
   ret = del->pRight;
   ret->Red = false;
   delete del;
  }
  if((ret->data > delp->data || ret->data == delp->data)
   && delp != m_pNodeHead)
   delp->pRight = ret;
  else
   delp->pLeft = ret;
  return true;
 }
 else if ( del->pLeft && key == del->pLeft->data) {
  delete del->pLeft;
  del->pLeft = 0;
  return true;
 }
 else if ( del->pRight && key == del->pRight->data) {
  delete del->pRight;
  del->pRight = 0;
  return true;
 } else {
  return false;
 }
}
/*
 삭제의 하향 탐색 경로로 빨간노드 옮기는 함수
 Sibling 이 Red인경우
*/
template <class T>
bool RBTreeMap<T>::_RedAsParent(Node *delgp, Node *delp, Node *sib)
{
 if(sib == 0 || !sib->Red)
  return false;

 _Rotate(sib->data,delgp);
 sib->Red = false;
 delp->Red = true;
 return true;
}
/*
 형제와 결합하기
 sibling이 black node 이고 Sibling의 두자식도 black Node인 경우
 Color Demotion에 의해 노드병합

*/
template <class T>
void RBTreeMap<T>::_BindNode(Node *delp)
{
 delp->Red = false;

 delp->pLeft->Red = true;
 delp->pRight->Red = true;
}
/*
 형제에게 빌리기1(단일회전)
 sibling이 Black Node 이고 Sibling의 자식의 하나이상 Red Node
 
*/
template <class T>
bool RBTreeMap<T>::_BorrowKey(Node *delgp, Node *delp, Node* del, Node *sib)
{
 Node *sibrc;
 if(_Is2Node(sib)) return false;
 if(del->data > sib->data) {
  if(sib->pLeft && sib->pLeft->Red) sibrc = sib->pLeft;
  else sibrc = sib->pRight;
 } else {
  if(sib->pRight && sib->pRight->Red) sibrc = sib->pRight;
  else sibrc = sib->pLeft;
 }
 if((delp->data > sib->data) != (sib->data > sibrc->data)) {
  // double rotation
  _Rotate(sibrc->data,delp);
  _Rotate(sibrc->data,delgp);
  sib->Red = false;
  sibrc->Red = true;
 } else {
  // single rotation
  _Rotate(sib->data,delgp);
  sib->Red = true;
  sibrc->Red = false;
 }
 del->Red = true;
 delp->Red = false;
 // Root가 빨강이면 검정으로 바꾼다.
 if(m_pNodeHead->pLeft->Red)
  m_pNodeHead->pLeft->Red = false;
 return true;
}
template <class T>
bool RBTreeMap<T>::Remove(const T& key)
{
 Node *delgp, *delp, *del, *sib;
 T value = key;
 delgp = delp = m_pNodeHead;
 del = m_pNodeHead->pLeft;
 sib = 0;
 while (!_IsLeafNode(del)) {
  if(!del->Red) { // del이 Black이면 Rotation
   if(_RedAsParent(delgp,delp,sib)){
    // delgp 와 sib의 위치가 변했다. 새로수정
    delgp = sib;
    if(del->data > delp->data ||
     del->data == delp->data)
     sib = delp->pLeft;
    else
     sib = delp->pRight;
   }
   if(del!= m_pNodeHead->pLeft && _Is2Node(del)) {
    if(!_BorrowKey(delgp,delp,del,sib))_BindNode(delp);
   }
   if(value == del->data) value = _SwapKey(del);
   delgp = delp;
   delp = del;
   if(value > del->data || value == del->data) {
    sib = del->pLeft;
    del = del->pRight;
   } else {
    sib = del->pRight;
    del = del->pLeft;
   }
  }
 } 
 if(!del->Red) {
  if(_RedAsParent(delgp,delp,sib)){
   delgp = sib;
   if(del->data > delp->data ||
    del->data == delp->data)
    sib = delp->pLeft;
   else
    sib = delp->pRight;
  }
 }
 if(del != m_pNodeHead->pLeft &&
  _Is2Node(del)){
  if(!_BorrowKey(delgp,delp,dle,sib))
   _BindNode(delp);
 }
 if(_DelLeafNode(value,delp,del)){
  m_nCount--;
  return true;
 } else {
  return false;
 }
}

/*
 그래프 Graph
 구현방법
   -인접행렬법(Adjacency Matrix)
   -인접리스트법(Adjacency List)
 탐색방법
   -깊이우선탐색(Depth First Search)
   -너비우선탐색(Breadth First Search)

    정점(vertex),간선(Edge)의 집합
   -항공로: 공항과 노선
   -전자회로: Chip과 선로
   *위상(Topology)만 중요함
 경로(Path)
   -단순경로(Simple Path): 중복이 없는 경로
 회로(Cycle)
 부분그래프(Subgraph)
 신장나무(Spanning Tree) :회로가 없는 부분그래프(트리)
 완전그래프(Complete Graph) :정점의 갯수가 V일때 간선의 갯수가 V(V-1)/2 인 그래프
 밀집그래프(Dense Graph) : 간선이 많은
 희소그래프(Sparse Graphy) : 간선이 적은
 방향그래프(Directed Graph, Digraph)
 무향그래프(Indirected graph)
 가중그래프(Weighted Graph)
 네트웍(Network) : 방향그래프 & 가중그래프
 내차수(Indegree)
 외차수(Outdegree)

*/
/*
 인접행렬법 Adjacency Matrix

*/
typedef long EDGE;
template <class V> class ArrayGraph
{
public:
 ArrayGraph(int nSize = 100);
 ~ArrayGraph();
 // utilities
 bool AddEdge(const V& v1, const V& v2, EDGE w);
 bool AddEdgeDir(const V& v1, const V& v2, EDGE w);
 EDGE GetEdge(const V& v1, const V& v2);
 bool SetEdge(const V& v1, const V& v2, EDGE w);
 // virtual function
 virtual void Visit(const V& v) {}
 virtual void VisitEdge(const V& v1, const V& v2) {}
 //operations
 void DFS();
 void DFS_nr();
 void BFS();
 long CountComponents();
 void FindAP(SingleList<V>& aplist);
 void ShortestPath_Dijkstra(const V& start);
protected:
 long _FindVertex(const V& v);
 long _AddVertex(const V& v);
 EDGE _GetEdgeByIndex(long i, long j);
 bool _SetEdgeByIndex(long i, long j, EDGE w);
 void _DFS(long i, RBTreeMap<V>& checkmap);
 V* m_pVertices;
 long* m_pEdges;
 long m_nSize;
 long m_nCount;
};
template <class V>
ArrayGraph<V>::ArrayGraph(int nSize)
{
 m_pVertices = new V[nSize];
 m_pEdges = new long[nSize*nSize];
 memset(m_pEdges,0,nSize*nSize*sizeof(EDGE));
 m_nSize = nSize;
 m_nCount = 0;
}
template <class V>
ArrayGraph<V>::~ArrayGraph()
{
 delete[] m_pVertices;
 delete[] m_pEdges;
}
template <class V> long
ArrayGraph<V>::_FindVertex(const V& v)
{
 for(int i =0; i < m_nCount; i++) {
  if(m_pVertices[i] == v) return i;
 }
 return -1;
}
template <class V> long
ArrayGraph<V>::_AddVertex(const V& v)
{
 if(m_nCount >= m_nSize) return -1;
 m_pVertices[m_nCount] =v;
 return m_nCount++;
}
template <class V> EDGE
ArrayGraph<V>::_GetEdgeByIndex(long i, long j)
{
 return m_pEdges[i*m_nSize+j];
}
template <class V> bool
ArrayGraph<V>::_SetEdgeByIndex(long i, long j,EDGE w)
{
 if( i < 0 || i >= m_nCount || j < 0 || j>= m_nCount )
  return false;
 m_pEdges[i*m_nSize +j] = w;
 return true;
}
template <class V> bool
ArrayGraph<V>::AddEdge(const V& v1, const V& v2, EDGE w)
{
 long iv1, iv2;
 iv1 = _FindVertex(v1);
 if(iv1 <0) iv1 = _AddVertex(v1);
 if(iv1 <0) return false;

 iv2 = _FindVertex(v2);
 if(iv2 <0) iv2 = _AddVertex(v2);
 if(iv2 <0) return false;

 _SetEdgeByIndex(iv1,iv2,w);
 _SetEdgeByIndex(iv2,iv1,w);
 
 return true;
}
template <class V> bool
ArrayGraph<V>::AddEdgeDir(const V& v1, const V& v2, EDGE w)
{
 long iv1, iv2;
 iv1 = _FindVertex(v1);
 if(iv1 <0) iv1 = _AddVertex(v1);
 if(iv1 <0) return false;

 iv2 = _FindVertex(v2);
 if(iv2 <0) iv2 = _AddVertex(v2);
 if(iv2 <0) return false;

 _SetEdgeByIndex(iv1,iv2,w);
 
 return true;
}
template <class V> void
ArrayGraph<V>::DFS()
{
 RBTreeMap<V> checkmap;
 V v;
 for(int i =0; i<m_nCount; i++)
  if(!checkmap.Find(m_pVertices[i], v)) _DFS(i,checkmap);

}
template <class V> void
ArrayGraph<V>::_DFS(long i, RBTreeMap<V>& checkmap)
{
 long j;
 V v;
 checkmap.Insert(m_pVertices[i]); // 방문 표시
 Visit(m_pVertices[i]); // 방문
 for ( j =0; j< m_nCount; j++) {
  if(_GetEdgeByIndex(i,j) != 0 && !checkmap.Find(m_pVertices[j],v))
   _DFS(j,checkmap);
 }
}
template <class V> void
ArrayGraph<V>::DFS_nr()
{
 long i, j;
 ListStack<long> stack;
 RBTreeMap<V> checkmap;
 V v;
 for(i = 0; i < m_nCount; i++) {
  if(!checkmap.Find(m_pVertices[i], v)) {
   stack.Push(i);
   checkmap.Insert(m_pVertices[i]);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    Visit(m_pVertices[i]);
    for(j = 0; j < m_nCount; j++) {
     if(_GetEdgeByIndex(i, j) != 0 && !checkmap.Find(m_pVertices[j], v)) {
      stack.Push(j);
      ceckmap.Insert(m_pVertices[j]);
     }
    }
   }
  }
 }
}

/*
 Dijkstra Algorithm

*/
template <class V>
void ArrayGraph<V>::ShortestPath_Dijkstra(const V& start)
{
 int i;
 int count = 0;
 int x, y;
 int s = _FindVertex(start);
 bool *visited = new bool[m_nCount];
 EDGE *distance = new EDGE[m_nCount];
 int *parent = new int[m_nCount];
 for (i = 0; i < m_nCount; i++)
 {
  visited[i] = false;
  distance[i] = _GetEdgeByIndex(s,i);
  if (i != s)
   parent[i] = s;
  else
   parent[i] = -1;
 }
 visited[s] = true;
 count ++;
 while (count < m_nCount)
 {
  x = 0;
  while (visited[x]) x++;
  for (i = x; i < m_nCount; i++)
   if (!visited[i] && distance[i] > 0 && distance[i] < distance[x])
    x = i;
  visited[x] = true;
  count ++;
  for (y = 0; y < m_nCount; y++)
  {
   if (x == y || _GetEdgeByIndex(x, y) == 0 || visited[y]) continue;
   // y는 방문하지 않은 (x,y)간선이 존재하는 정점
   EDGE d = distance[x] + _GetEdgeByIndex(x, y);
   if (distance[y] == 0 || d < distance[y]) {
    distance[y] = d;
    parent[y] = x;
   }
  }
 }
 // visit edge
 for (i = 0; i < m_nCount; i++)
  if (parent[i] >= 0) VisitEdge(m_pVertices[parent[i]], m_pVertices[i]);
 delete[] visited;
 delete[] distance;
 delete[] parent;
}
class ACharGraph : public ArrayGraph<char>
{
public:
 ACharGraph(int nSize=100) : ArrayGraph<char>(nSize){}
 void Visit(const char& v) { printf("%c",v); }
 void VisitEdge(const char& v1, const char& v2) { printf("%c-->%c\n",v1,v2); }
};

/*
 인접리스트법 Adjacency List

*/
template <class V> class ListGraph
{
public:
 ListGraph(const ListGraph<V>* g);
 ListGraph(int nSize = 100);
 ~ListGraph();
 //utilities
 bool AddEdge(const V& v1, const V& v2, EDGE w);
 bool AddEdgeDir(const V& v1, const V& v2, EDGE w);
 EDGE GetEdge(const V& v1, const V& v2);
 bool SetEdge(const V& v1, const V& v2, EDGE w);
 // virtual function
 virtual void Visit(const V& v) {}
 virtual void VisitEdge(const V& v1, const V& v2) {}
 //operations
 void DFS();
 void DFS_nr();
 void BFS();
 long CountComponents();
 void FindAP(SingleList<V>& aplist);
 EDGE MCST_Pfs();
 EDGE MCST_Kruskal();
 void ShortestPath_Pfs(const V& start);
 void Reach_Dfs(const V& start);
 bool IsReachable(const V& strat, const V& end);
 void TransitiveClosure_Warshall();
 void StrongConnect();
 void TopologicalSort();
 void RevTopologicalSort();
 void CriticalActivity();
protected:
 struct Adj {
  V vertex;
  EDGE weight;
  bool operator==(const Adj& n) const
  {
   return vertex == n.vertex;
  }
  Adj(const V& v, EDGE w =1)
  {
   vertex = v; weight = w;
  }
  Adj() {}
 };
 struct Item {
  V vertex;
  DoubleList<Adj> list;
 };
 long _FindVertex(const V& v);
 long _AddVertex(const V& v);
 void _DFS(long i, RBTreeMap<V>& checkmap);
 int _StrongConnect(long i, long order, long* porder, ListStack<long>& stack);
 void _CriticalActivity_backward(int *latest, int initial);
 void _CriticalActivity_forward(int *earliest);
 Item *m_pVertices;
 long m_nSize;
 long m_nCount;
};
template <class V>
ListGraph<V>::ListGraph(const ListGraph<V>* g)
{
 m_pVertices = new Item[g->m_nSize];
 m_nSize = g->m_nSize;
 m_nCount = g->m_nCount;
 for(int i = 0; i < g->m_nCount; i++)
 {
  m_pVertices[i].vertex = g->m_pVertices[i].vertex;
  POS pos = g->m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while (g->m_pVertices[i].list.GetNext(pos,adj))
  {
   m_pVertices[i].list.InsertTail(adj);
  }
  
 }
}
template <class V>
ListGraph<V>::ListGraph(int nSize)
{
 m_pVertices = new Item[nSize];
 m_nSize = nSize;
 m_nCount = 0;
}
template <class V>
ListGraph<V>::~ListGraph()
{
 delete[] m_pVertices;
}
template <class V> long
ListGraph<V>::_FindVertex(const V& v)
{
 for (long i = 0; i < m_nCount; i++)
 {
  if(m_pVertices[i].vertex == v)
   return i;
 }
 return -1;
}
template <class V> long
ListGraph<V>::_AddVertex(const V& v)
{
 if(m_nCount >= m_nSize)
  return -1;
 m_pVertices[m_nCount].vertex = v;
 return m_nCount++;
}
template <class V> bool
ListGraph<V>::AddEdge(const V& v1, const V& v2, EDGE w)
{
 long iv1, iv2;
 iv1 = _FindVertex(v1);
 if(iv1 <0) iv1 = _AddVertex(v1);
 if(iv1 <0) return false;

 iv2 = _FindVertex(v2);
 if(iv2 <0) iv2 = _AddVertex(v2);
 if(iv2 <0) return false;

 m_pVertices[iv1].list.InsertHead(Adj(v2,w));
 m_pVertices[iv2].list.InsertHead(Adj(v1,w));
 
 return true;
}
template <class V> bool
ListGraph<V>::AddEdgeDir(const V& v1, const V& v2, EDGE w)
{
 long iv1, iv2;
 iv1 = _FindVertex(v1);
 if(iv1 <0) iv1 = _AddVertex(v1);
 if(iv1 <0) return false;

 iv2 = _FindVertex(v2);
 if(iv2 <0) iv2 = _AddVertex(v2);
 if(iv2 <0) return false;

 m_pVertices[iv1].list.InsertHead(Adj(v2,w));
// m_pVertices[iv2].list.InsertHead(Adj(v1,w));
 
 return true;
}
/*
 깊이우선탐색(DFS)
 정점 v의 방문하지 않은 인접 정점에 대해 재귀적으로 방문하기
 재귀호출은 Stack을 이용해서 비재귀호출로 바꿀 수 있음
*/
template <class V> void
ListGraph<V>::DFS()
{
 RBTreeMap<V> checkmap;
 V v;
 for(long i=0; i < m_nCount; i++)
  if(!checkmap.Find(m_pVertices[i].vertex,v)) _DFS(i,checkmap);
}
template <class V> void
ListGraph<V>::_DFS(long i, RBTreeMap<V>& checkmap)
{
 V v;
 checkmap.Insert(m_pVertices[i].vertex);
 Visit(m_pVertices[i].vertex);
 POS pos = m_pVertices[i].list.GetHeadPos();
 Adj adj;
 while(m_pVertices[i].list.GetNext(pos,adj))
 {
  if(!checkmap.Find(adj.vertex,v)) {
   _DFS(_FindVertex(adj.vertex),checkmap);
  }
 }
}
template <class V> void
ListGraph<V>::DFS_nr()
{
 RBTreeMap<V> checkmap;
 ListStack<long> stack;
 V v;
 for(long i=0; i<m_nCount;i++)
 {
  if(!checkmap.Find(m_pVertices[i].vertex,v))
  {
   stack.Push(i);
   checkmap.Insert(m_pVertices[i].vertex);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    POS pos = m_pVertices[i].list.GetHeadPos();
    Visit(m_pVertices[i].vertex);
    Adj adj;
    while(m_pVertices[i].list.GetNext(pos,adj))
    {
     if(!checkmap.Find(adj.vertex,v))
     {
      stack.Push(_FindVertex(adj.vertex));
      checkmap.Insert(adj.vertex);
     }
    }
   }
  }
 }
}
template <class V>
long ListGraph<V>::CountComponents()
{
 RBTreeMap<V> checkmap;
 ListStack<long> stack;
 long count=0;
 V v;
 for(long i=0; i<m_nCount;i++)
 {
  if(!checkmap.Find(m_pVertices[i].vertex,v))
  {
   count ++;
   stack.Push(i);
   checkmap.Insert(m_pVertices[i].vertex);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    POS pos = m_pVertices[i].list.GetHeadPos();
    Adj adj;
    while(m_pVertices[i].list.GetNext(pos,adj))
    {
     if(!checkmap.Find(adj.vertex,v))
     {
      stack.Push(_FindVertex(adj.vertex));
      checkmap.Insert(adj.vertex);
     }
    }
   }
  }
 } 
 return count;
}

template <class V> EDGE
ListGraph<V>::MCST_Pfs()
{
 long i, j;
 EdgeHeap<char> pq;
 EdgeHeap<char>::Pair p;
 EDGE sum = 0;
 bool *visited = new bool[m_nCount];
 for(i = 0; i < m_nCount; i++) visited[i] = false;

 for(i = 0; i < m_nCount; i++)
 {
  if(!visited[i])
  {
   pq.Insert(m_pVertices[i].vertex, m_pVertices[i].vertex, 0);
   visited[i] = true;
   while (!pq.IsEmpty())
   {
    p = pq.Extract();
    if(p.v1 != p.v2)
    {
     VisitEdge(p.v1, p.v2);
     sum += -p.w;
    }
    j = _FindVertex(p.v2);
    POS pos = m_pVertices[j].list.GetHeadPos();
    Adj adj;
    while(m_pVertices[j].list.GetNext(pos,adj))
    {
     int k = _FindVertex(adj.vertex);
     if(!visited[k])
     { //방문하지 않은 정점들에 대해서
      pq.Insert(m_pVertices[j].vertex, adj.vertex, -adj.weight);
      visited[k] = true;
     } else { // 방문한 정점들에 대해서.
      pq.Update(m_pVertices[j].vertex, adj.vertex, -adj.weight);
     }
    }
   }
  }
 }
 delete[] visited;
 return sum;
}
/*
 최소비용신장트리 (Minimum Cost Spanning Tree)
 -유일한 해답이 있는게 아님
 -알려진 알고리즘들
   *우선순위탐색, Kruskal, Sollin, Prim ...
 -응용예
   *최소의 비용으로 모든 정점을 연결하는 방법
   *최소의 비용으로 컴퓨터 네트웍 구성
   *최소의 비용으로 모든 도시를 연결하는 항공로 구성

 우선순위탐색 Priority First Search
 -우선순위를 기준으로 탐색하는 방법
 -DFS vs BFS vs PFS

*/
template <class V>
EDGE ListGraph<V>::MCST_Kruskal()
{
 EdgeHeap<char> pq;
 Set<char> set;
 int i;
 EDGE sum = 0;
 int nEdge = 0;
 //insert all edges to heap
 for (i = 0; i < m_nCount; i++) {
  POS pos = m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while(m_pVertices[i].list.GetNext(pos,adj))
  {
   if(_FindVertex(adj.vertex) > i) //간선의 중복을 피하기 위해
    pq.Insert(m_pVertices[i].vertex, adj.vertex, -adj.weight);
  }
 }
 while (!pq.IsEmpty() && nEdge < m_nCount -1)
 {
  // MCST의 간선수는 정점수 -1
  EdgeHeap<char>::Pair p = pq.Extract();
  int i1 = set.Find(p.v1);
  if (i1 < 0) i1 = set.AddSet(p.v1);
  int i2 = set.Find(p.v2);
  if (i2 < 0) i2 = set.AddSet(p.v2);
  if (i1 >= 0 && i2 >= 0 && i1 != i2)  //회로가 아니면
  {
   VisitEdge(p.v1,p.v2);
   nEdge++;
   sum += -p.w;
   set.UnionByIndex(i1,i2);
  }
 }
 return sum;
}

/*
 최단경로찾기 문제
  -시작정점으로 부터 다른 정점에 이르는 최소비용의 간선집합을 찾아라!
  -최단경로트리가 얻어짐
 A* 이라는 알고리즘이 실전에서 쓰임
 (위치 가중치를 주어 거대한 그래프에서 사용)
*/
template <class V>
void ListGraph<V>::ShortestPath_Pfs(const V& start)
{
 long i, j;
 EdgeHeap<char> pq;
 EdgeHeap<char>::Pair p;
 bool *visited = new bool[m_nCount];
 for (i = 0; i < m_nCount; i++) visited[i] = false;
 i = _FindVertex(start);
 if (i < 0) return;
 pq.Insert(m_pVertices[i].vertex, m_pVertices[i].vertex, 0);
 visited[i] = true;
 while (!pq.IsEmpty())
 {
  p = pq.Extract();
  if (p.v1 != p.v2)
   VisitEdge(p.v1,p.v2);
  j = _FindVertex(p.v2);
  Adj adj;
  POS pos = m_pVertices[j].list.GetHeadPos();
  while (m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   if (!visited[k]) {//방문하지 않은 정점들에 대해서
    pq.Insert(m_pVertices[j].vertex, adj.vertex, p.w - adj.weight);
    visited[k] = true;
   } else { // 방문하지 않은 정점들에 대해서
    pq.Update(m_pVertices[j].vertex, adj.vertex, p.w - adj.weight);
   }
  }
  
 }
}

/*
 Dijkstra 알고리즘
 -시작점을 제외한 다른 정점이 모두 시작점을 가리킨다고 가정
 -연결되어 있지 않은 정점은 무한대의 비용임
 -A-C간선의 비용이 A-B,B-C간선 비용보다 크다면
  C는 B를 가리키도록 한다.

*/

/*
 도달 가능성 문제 Reachability
*/
template <class V>
void ListGraph<V>::Reach_Dfs(const V& start)
{
 long i, j;
 ListStack<long> stack;
 bool *visited = new bool[m_nCount];
 for (i = 0; i < m_nCount; i++)
  visited[i] = false;
 i = _FindVertex(start);
 if (i < 0) return;
 stack_Push(i);
 visited[i] = true;
 while (!stack.IsEmpty())
 {
  j = stack.Pop();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  while (m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   if (!visited[k])
   {
    stack.Push(k);
    visited[k] = true;
   }
  }
 }
 delete[] visited;
}

/*
 Transitive Closure 이행적 폐쇄
 Warshall알고리즘
   A->B와 B->를 만족하는 경로가 있으면 A->C로 가는 경로도 존재한다.
   자기자신으로 가는 경로는 있다고 가정. 즉 A->A
   Warshall(Graph g)
   {
  for (x = all vertices) {
   for (y = all vertices) {
    if (x->y is reachable) {
     for (z = all vertices) {
      if (y->z is reachable)
       x->z is reachable;
      }
     }
    }
   }
  }
   }
*/
template <class V>
void ListGraph<V>::TransitiveClosure_Warshall()
{
 //graph 복사
 ListGraph<V> g(this);
 int x, y, z;
 Adj adj1, adj2, adj3;

 for (x = 0; x < g.m_nCount; x++) {
  for (y = 0; y < g.m_nCount; y++) {
   Adj adj;
   if(g.m_pVertices[x].list.Find(g.m_pVertices[y].vertex,adj1))
   {
    for (z = 0; z < g.m_nCount; z++) {
     if(g.m_pVertices[y].list.Find(g.m_pVertices[z].vertex,adj2))
     {
      //x->z is reachable
     // if(
     // m_pVertices[x].list.InsertHead(Adj(z,w1+w2));
      if(g.m_pVertices[x].list.Find(g.m_pVertices[z].vertex,adj3))
      {
       if (adj3.weight > adj1.weight + adj2.weight)
        adj3.weight = adj1.weight + adj2.weight;
      }
      else
      {
       g.m_pVertices[x].list.InsertHead(Adj(g.m_pVertices[z].vertex,adj1.weight+adj2.weight));
      }
     }
    }
   }
  }
 }

 for (x = 0; x < g.m_nCount; x++)
  g.m_pVertices[x].list.InsertHead(Adj(m_pVertices[x].vertex,1));

}

/*
 강한결합요소
  -정점 A에서 B로 가는 방향성 경로도 존재하고, B에서 A로가는 장향성경로도 존재
  -강한결합요소는 정점하나를 제거해도 연결은 유지된다.
   VS 이중연결(Biconnectivity)
 강한결합요소 찾기

*/
template <class V>
void ListGraph<V>::StrongConnect()
{
 int i;
 ListStack<long> stack;
 long *porder = new long[m_nCount];
 for (i = 0; i < m_nCount; i++) porder[i] = 0;
 for (i = 0; i < m_nCount; i++)
  if (porder[i] == 0)
   _StrongConnect(i, 0, porder, stack);
 delete[] porder;
}
/*
 FindAP와 유사한 구조
*/
template <class V>
int ListGraph<V>::_StrongConnect(long i, long order, long* porder, ListStack<long>& stack)
{
 int m, min, k;
 bool cycle;
 porder[i] = min = ++order;
 stack.Push(i);
 POS pos = m_pVertices[i].list.GetHeadPos();
 Adj adj;
 m_pVertices[i].list.GetAt(pos,adj);
 while (!m_pVertices[i].list.IsTail(pos))
 {
  k = _FindVertex(adj.vertex);
  if (porder[k] == 0) //방문하지 않은 정점이면
   m = _StrongConnect(k, order, porder, stack);
  else
   m = porder[k];
  if (m < min) min = m;
  m_pVertices[i].list.GetNext(pos,adj);
 }
 if (min == porder[i]) //자기자신을 가리키면
 {
  cycle = false;
  while ((k = stack.Pop()) != i) {
   Visit(m_pVertices[k].vertex);
   porder[k] = m_nCount + 1; //다시는 출력되지 않도록 체크
   cycle = true;
  }
  if (cycle) Visit(m_pVertices[k].vertex);
  //여기까지가 한묶음. 정점 하나만 출력되는 걸 막음
 }
 return min;
}

/*
 비순환방향그래프 Directed Acyclic Graph
 
   여러 공정으로 이루어지는 작업을 모델링하는데 주로 사용함
   ( 집짓기 )
   AOV Network ( Activity On Vertex Network )
   공정모델링은 건축/토목분야에 많이 연구됩

 
*/
/*
 위상정렬 개념
 
   위상정렬 ( Topological Sort )
    -DAG 정점의 일련순서를 구하는 것
    -ex) 집짓기를 혼자 한다면 어떤 순서로 일해야 하나?
    In-Degree 가 0인 지점부터 시작
   역위상정렬 ( Reverse Topological Sort )
    Out-Degree 가 0인 지점부터 시작
  
*/
template <class V>
void ListGraph<V>::TopologicalSort()
{
 int i;
 ListQueue<int> queue;
 // indegree 배열, 설정
 int *indegree = new int[m_nCount];
 for (i = 0; i < m_nCount; i++) indegree[i] = 0;
 for (i = 0; i < m_nCount; i++)
 {
  Adj adj;
  POS pos = m_pVertices[i].list.GetHeadPos();
  m_pVertices[i].list.GetAt(pos,adj);
  while (!m_pVertices[i].list.IsTail(pos))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k] ++;
   m_pVertices[i].list.GetNext(pos,adj);
  }
 }
 for (i = 0; i < m_nCount; i++)
  if (indegree[i] == 0) queue.Put(i);
 for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
 {
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  m_pVertices[j].list.GetAt(pos,adj);
  while ( !m_pVertices[j].list.IsTail(pos))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k]--;
   if (indegree[k] == 0) queue.Put(k);
   m_pVertices[j].list.GetNext(pos,adj);
  }
 }
 delete[] indegree;
}
template <class V>
void ListGraph<V>::RevTopologicalSort()
{
 int i;
 ListQueue<int> queue;
 // outdegree 배열, 설정
 int *outdegree = new int[m_nCount];
 for (i = 0; i < m_nCount; i++) outdegree[i] = 0;
 for (i = 0; i < m_nCount; i++)
  outdegree[i] = m_pVertices[i].list.GetCount();
 for (i = 0; i < m_nCount; i++)
  if (outdegree[i] == 0) queue.Put(i);
 for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
 {
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  for (int k = 0; k < m_nCount; k++)
  {
   POS pos = m_pVertices[k].list.GetHeadPos();
   Adj adj;
   while ( m_pVertices[k].list.GetNext(pos,adj))
   {
    if (adj.vertex == m_pVertices[j].vertex)
    {
     outdegree[k]--;
     if (outdegree[k] == 0) queue.Put(k);
    }
   }
  }
 }
 delete[] outdegree;
}

/*
 AOE ( Network Acitivity On Edge Network )
 간선은 공정을 의미, 정점은 공정이 완료된 상태를 의미함
 공정에 가중치를 주기 위해 AOE Network를 사용함

 임계작업 Critical Activity
  -전체 공정의 소요비용을 결정하는 작업들
   ex) ab, bc, ce, ef
  
  최단시간 Earliest Time
  -위상순서대로 진행하면서, 최초 정점의 earliest는 0
  -earliest(Y) = max(earlist(Xk) + <Xk, Y> cost
  최장시간 Latest Time

*/
template <class V>
void ListGraph<V>::_CriticalActivity_forward(int *earliest)
{
 int i;
 ListQueue<int> queue;
 // indegree 배열, 설정
 int *indegree = new int[m_nCount];
 for (i = 0; i < m_nCount; i++)
 {
  indegree[i] = 0;
  earliest[i] = 0;
 }
 for (i = 0; i < m_nCount; i++)
 {
  Adj adj;
  POS pos = m_pVertices[i].list.GetHeadPos();
  while (m_pVertices[i].list.GetNext(pos, adj))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k] ++;
  }
 }
 for (i = 0; i < m_nCount; i++)
  if (indegree[i] == 0) queue.Put(i);
 for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
 {
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  while ( m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k]--;
   if (indegree[k] == 0) queue.Put(k);
   if (earlieset[k] < earliest[j] + adj.weight)
    earliest[k] = earliest[j] + adj.weight;
  }
 }
 delete[] indegree;
}

template <class V>
void ListGraph<V>::_CriticalActivity_backward(int *latest, int initial)
{
 int i;
 ListQueue<int> queue;
 // outdegree 배열, 설정
 int *outdegree = new int[m_nCount];
 for (i = 0; i < m_nCount; i++)
 {
  outdegree[i] = 0;
  latest[i] = initial;
 }
 for (i = 0; i < m_nCount; i++)
  outdegree[i] = m_pVertices[i].list.GetCount();
 for (i = 0; i < m_nCount; i++)
  if (outdegree[i] == 0) queue.Put(i);
 for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
 {
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  for (int k = 0; k < m_nCount; k++)
  {
   POS pos = m_pVertices[k].list.GetHeadPos();
   Adj adj;
   while ( m_pVertices[k].list.GetNext(pos,adj))
   {
    if (adj.vertex == m_pVertices[j].vertex)
    {
     outdegree[k]--;
     if (outdegree[k] == 0) queue.Put(k);
     if (latest[k] > latest[j] - adj.weight)
      latest[k] = latest[j] - adj.weight;
    }
   }
  }
 }
 delete[] outdegree;
}
template <class V>
void ListGraph<V>::CriticalActivity()
{
 int *earliest = new int[m_nCount];
 int *latest = new int[m_nCount];

 _CriticalActivity_forward(earliest);
 int initial = 0;
 for (int i = 0; i < m_nCount; i++) {
  if (initial < earliest[i]) initial = earliest[i];
 }
 _CriticalActivity_backward(latest, initial);

 for (i = 0; i< m_nCount; i++)
 {
  POS pos = m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while (m_pVertices[i].list.GetNext(pos,adj))
  {
   int e = earliest[i];
   int l = latest[_FindVertex(adj.vertex)] - adj.weight;
   if (l - e == 0)
    VisitEdge(m_pVertices[i].vertex, adj.vertex);
  }
 }
 delete[] earliest;
 delete[] latest;
}
/*
 결론
 방향 그래프는
  -단방향간선으로 이루어진 그래프
  -Cycle이 없는 경우 DAG라고 함
  -방향 그래프이면서 가중그래프인 경우 Network
 방향 그래프 문제
  -Reachability, Transitive Closure
  -Strongly Connected Components
  -Topological Sort / Reverse Topological Sort
  -AOE Network and Critical Activity

*/

class LCharGraph : public ListGraph<char>
{
public:
 LCharGraph(int nSize=100) : ListGraph<char>(nSize){}
 void Visit(const char& v) { printf("%c",v);}
 void VisitEdge(const char& v1,const char& v2) { printf("%c-->%c\n",v1,v2); }
};

template <class V> class EdgeHeap
{
public:
 struct Pair {
  V v1;
  V v2;
  EDGE w;
  Pair(const V& vv1, const V& vv2, EDGE ww) {
   v1 = vv1; v2 = vv2; w = ww;
  }
  Pair() { w = 0; }
 };
public:
 EdgeHeap(int nSize = 100) {
  m_pArray = new Pair[nSize];
  m_nArrayLen = nSize;
  m_nHeapLen = 0;
 }
 ~EdgeHeap() { delete[] m_pArray; }
 Pair& a(int k) { return m_pArray[k-1]; }
 bool IsEmpty() { return m_nHeapLen == 0; }
 void UpHeap(int k);
 void DownHeap(int k);
 bool Insert(const V& p, const V& v, EDGE w);
 Pair Extract() ;
 bool Update(const V& p, const V& v, EDGE w);
private:
 Pair *m_pArray;
 int m_nArrayLen;
 int m_nHeapLen;

};
template <class V>
void EdgeHeap<V>::UpHeap(int k)
{
 Pair p = a(k);
 while (p.w > a(k/2).w && k > 1) {
  a(k) = a(k/2) ; k /= 2;
 }
 a(k) = p;
}

template <class V>
void EdgeHeap<V>::DownHeap(int k)
{
 int i; Pair p;
 p = a(k);
 while (k <= m_nHeapLen/2) {
  i = k * 2;
  if(i < m_nHeapLen && a(i+1).w > a(i).w) i++;
  if(p.w > a(i).w || p.w == a(i).w)break;
  a(k) = a(i);
  k = i;
 }
 a(k) = p;
}
template <class V>
bool EdgeHeap<V>::Insert(const V& p, const V& v, EDGE w)
{
 if(m_nHeapLen >= m_nArrayLen - 1) return false;
 a(++m_nHeapLen) = Pair(p, v, w);
 UpHeap(m_nHeapLen);
 return true;
}
template <class V>
bool EdgeHeap<V>::Update(const V& p, const V& v, EDGE w)
{
 //vertex 찾기
 for( int i = 0; i < m_nHeapLen; i++) {
  if(m_pArray[i].v2 == v && m_pArray[i].w < w) {
   m_pArray[i].w = w;
   m_pArray[i].v1 = p;
   for(int k = m_nHeapLen/2; k >= 1; k--)
    DownHeap(k);
   return true;
  }
 }
 return false;
}
template <class V>
EdgeHeap<V>::Pair EdgeHeap<V>::Extract()
{
 Pair p;
 p = a(1);
 a(1) = a(m_nHeapLen--);
 DownHeap(1);
 return p;
}

/*
 집합 연산 Union-Find

 Find 문제
  어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별
 Union 문제
  서로 다른 두개의 집합을 하나의 집합으로 합병

    상향식 트리구조로 구현하는 것이 가장 효율적

*/
template <class T> class Set
{
public:
 struct Item {
  T elem;
  int parent;  // parent index
  int height;
 };
public:
 Set(int nSize = 100) {
  m_pArray = new Item[nSize];
  m_nArrayLen = nSize;
  m_nCount = 0;
 }
 ~Set() { delete[] m_pArray; }
 T& GetItem(int index) const { return m_pArray[index].elem; }
 int GetParent(int index) const { return m_pArray[index].parent; }
 int   GetIndex(const T& t) const {
  for (int i = 0; i < m_nCount; i++)
   if (m_pArray[i].elem == t) return i;
  return -1;
 }
 int AddSet(const T& t);
 int Find(const T& t);
 void Union(const T& t1, const T& t2);
 void UnionByIndex(int i1, int i2);
private:
 Item *m_pArray;
 int m_nArrayLen;
 int m_nCount;
};
template <class T>
int Set<T>::AddSet(const T& t)
{
 if (m_nCount >= m_nArrayLen) return false;
 m_pArray[m_nCount].elem = t;
 m_pArray[m_nCount].parent = -1;
 m_pArray[m_nCount].height = 1;
 return m_nCount++;
}
template <class T>
int Set<T>::Find(const T& t)
{
 for (int i = 0; i < m_nCount && m_pArray[i].elem != t; i++);
 if(i >= m_nCount) return -1;
 while (m_pArray[i].parent >= 0) i = m_pArray[i].parent;
 return i;
}
template <class T>
void Set<T>::Union(const T& t1, const T& t2)
{
 int i1 = Find(t1);
 int i2 = Find(t2);
 if(i1 < 0 || i2 < 0) return;
 UnionByIndex(i1,i2);
}
template <class T>
void Set<T>::UnionByIndex(int i1, int i2)
{
 if(m_pArray[i1].height > m_pArray[i2].height)
 {
  m_pArray[i2].parent = i1;
 } else if (m_pArray[i1].height < m_pArray[i2].height) {
  m_pArray[i1].parent = i2;
 } else { // 두개의 높이가 같은 경우
  m_pArray[i2].parent = i1;
  m_pArray[i1].height++;
 }
}
  
/*
 방향그래프

 도달가능성 Reachability

*/

/*
 수치해석 Numerical Analysis
 다항식 Polynomial
 -컴퓨터의 연산기능을 이용, 해석적으로 문제 풀이
 다항식 모델링
 -다항식 클래스 Polynomial
 -다항식 사칙연산, 미적분
 -다항식의 계산
 Lagrange Interpolation
 -N+1개의 점을 지나는 N차 다항식 구하기

 컴퓨터와 수학
 CPU Central Process Unit

 정수타입
 int long char
 C++ 의 실수타입
 float
  -4byte
 1비트의 부호, 8비트의 지수부, 23비트의 가수부
 약 3.4E + 38까지 표현가능
 double
  -8Byte
 1비트의 부호, 11비트의 지수부, 52비트의 가수부
 SIGN | EXPONENT | MANTISSA
 약 1.8E + 308까지 표현가능
 
   회귀분석
    입력자료를 통해 방정식 유추
   스플라인
   -Bezier, Hermite, B Spline
    선을 부드럽게 그리는 방법
*/
/*
 다항식
  -항(Term) : 계수와 지수로 구성됨
   *ex)

*/
class Polynomial
{
public:
 struct Term {
  int exp; //지수
  double coef; //계수
 };
 Polynomial() {}
 Polynomial(const Polynomial& p) { m_list = p.m_list; }
 const Polynomial& operator=(const Polynomial& p) {
  m_list = p.m_list;
  return * this;
 }

 void InsertTerm(int exp, double coef);
 void AddTerm(int exp, double coef);

 void Print();
 Polynomial operator+(const Polynomial& p);
 Polynomial operator-(const Polynomial& p);
 Polynomial operator*(const Polynomial& p);

 void Differential();
 void Integral();
 double Evaluate(double x);
 void Lagrange(double pt[][2], int n);
protected:
 DoubleList<Term> m_list;
};
void Polynomial::AddTerm(int exp, double coef)
{
 Term term,t;
 term.exp = exp;
 term.coef = coef;

 POS pos = m_list.GetHeadPos();

 while (!m_list.IsTail(pos))
 {
  if (!m_list.GetAt(pos,t)) break;
  if(t.exp == term.exp)
  {
   t.coef += coef;
   if (t.coef == 0.0)
    m_list.DeleteAt(pos);
   return;
  }
  if(t.exp < term.exp) {
   m_list.InsertPrev(pos,term);
   return;
  }
  m_list.GetNext(pos,t);
 }
 m_list.AddTail(term);
}
void Polynomial::InsertTerm(int exp, double coef)
{
 if (coef == 0.0) return;
 Term term,t;
 term.exp = exp; term.coef = coef;
 POS pos = m_list.GetHeadPos();
 while ( !m_list.IsTail(pos))
 {
  if(!m_list.GetAt(pos,t)) break;
 
  if (t.exp == term.exp) {
   t.coef = coef;
   return;
  }
  if (t.exp < term.exp) {
   m_list.InsertPrev(pos,term);
   return;
  }
  m_list.GetNext(pos,t);
 }
 m_list.AddTail(term);
}
void Polynomial::Print()
{
 POS pos = m_list.GetHeadPos();
 Term t;
 while (!m_list.IsTail(pos))
 {
  m_list.GetAt(pos,t);
  printf("%dX^%d ",(int)t.coef,(int)t.exp);
  m_list.GetNext(pos,t);
 }
}
Polynomial Polynomial::operator+(const Polynomial& p)
{
 Polynomial r;
 POS pos1 = m_list.GetHeadPos();
 POS pos2 = p.m_list.GetHeadPos();
 Term t1, t2;

 while (!m_list.IsTail(pos1) && !p.m_list.IsTail(pos2))
 {
  m_list.GetAt(pos1,t1);
  p.m_list.GetAt(pos2,t2);

  if (t1.exp > t2.exp) {
   r.m_list.AddTail(t1);
   m_list.GetNext(pos1,t1);
  } else if (t1.exp < t2.exp) {
   r.m_list.AddTail(t2);
   p.m_list.GetNext(pos2,t2);
  } else {
   if(t1.coef + t2.coef != 0.0) {
    t1.coef += t2.coef;
    r.m_list.AddTail(t1);
   }
   m_list.GetNext(pos1,t1);
   p.m_list.GetNext(pos2,t2);
  }
 }
 m_list.GetAt(pos1,t1);
 while (!m_list.IsTail(pos1)) {
  r.m_list.AddTail(t1);
  m_list.GetNext(pos1,t1);
 }
 p.m_list.GetAt(pos2,t2);
 while (!p.m_list.IsTail(pos2)) {
  r.m_list.AddTail(t2);
  p.m_list.GetNext(pos2,t2);
 }
 return r;
 
}
Polynomial Polynomial::operator-(const Polynomial& p)
{
 Polynomial r;
 POS pos1 = m_list.GetHeadPos();
 POS pos2 = p.m_list.GetHeadPos();
 Term t1, t2;

 while (!m_list.IsTail(pos1) && !p.m_list.IsTail(pos2))
 {
  m_list.GetAt(pos1,t1);
  p.m_list.GetAt(pos2,t2);

  if (t1.exp > t2.exp) {
   r.m_list.AddTail(t1);
   m_list.GetNext(pos1,t1);
  } else if (t1.exp < t2.exp) {
   r.m_list.AddTail(t2);
   p.m_list.GetNext(pos2,t2);
  } else {
   if(t1.coef - t2.coef != 0.0) {
    t1.coef -= t2.coef;
    r.m_list.AddTail(t1);
   }
   m_list.GetNext(pos1,t1);
   p.m_list.GetNext(pos2,t2);
  }
 }
 m_list.GetAt(pos1,t1);
 while (!m_list.IsTail(pos1)) {
  r.m_list.AddTail(t1);
  m_list.GetNext(pos1,t1);
 }
 p.m_list.GetAt(pos2,t2);
 while (!p.m_list.IsTail(pos2)) {
  r.m_list.AddTail(t2);
  p.m_list.GetNext(pos2,t2);
 }
 return r;
}

Polynomial Polynomial::operator*(const Polynomial& p)
{
 Polynomial r;
 POS pos1 = m_list.GetHeadPos();
 Term t1, t2;

 while (!m_list.IsTail(pos1))
 {
  m_list.GetAt(pos1,t1);
  POS pos2 = p.m_list.GetHeadPos();
  p.m_list.GetAt(pos2,t2);
  
  while (!p.m_list.IsTail(pos2)) {
   p.m_list.GetAt(pos2,t2);
   r.AddTerm(t1.exp + t2.exp, t1.coef * t2.coef);
   p.m_list.GetNext(pos2,t2);
  }
  m_list.GetNext(pos1,t1);

 }
 return r;

}
//미분
void Polynomial::Differential()
{
 Polynomial r;
 POS pos = m_list.GetHeadPos();
 Term t;
 while (!m_list.IsTail(pos))
 {
   m_list.GetAt(pos,t);
   if(t.exp > 0)
    r.InsertTerm(t.exp -1, t.coef*t.exp);
   m_list.GetNext(pos,t);
 }
 *this = r;
}
//적분
void Polynomial::Integral()
{
 Polynomial r;
 POS pos = m_list.GetHeadPos();
 Term t;
 while (!m_list.IsTail(pos))
 {
  m_list.GetAt(pos,t);
  r.InsertTerm(t.exp + 1, t.coef / (t.exp +1));
 }
 *this = r;
}
/*
 거듭제곱함수만들기
*/
double power_simple(double x, int n)
{
 double r = 1.0;
 while (n--) r*= x;
 return r;
}
double power_recur(double x, int n)
{
 if(n == 0) return 1.0;
 return x* power_recur(x,n-1);
}
/*
 Divde and Conquer
 -곱셈의 수를 획기적으로 줄임
 
*/
double power_dnq(double x, int n)
{
 if (n == 0) return 1.0;
 if (n == 1) return x;
 double half = power_dnq(x,n/2);
 if(n %2 == 0) return half*half;
 else return half*half*x;
}
double Polynomial::Evaluate(double x)
{
 double r = 0.0;
 POS pos = m_list.GetHeadPos();
 Term t;
 while (!m_list.IsTail(pos))
 {
   m_list.GetNext(pos,t);
   r += t.coef * power_dnq(x,t.exp);
 }
 return r;
}
 
/*
 Lagrange 보간법
 * Lagrange Interpolation
 -N+1개의 주어진 점을 지나는 N차의 다항식을 구하는 문제
 -예) 네개의 점(x0,y0),(x1,y1),(x2,y2),(x3,y3)을 지나는
  g(x) = a0 + a1x + a2x^2 + a3x^3를 구하는 문제
 
*/
double combi(double x, int n, int r)
{
 if (n <= 0 || r < 0 || n <r) return 0;
 if (n == r) return x;
 if (r == 0) return 1;
 return x[n-1]*combi(n-1,r-1) + combi(n-1, r);
}
void main(){
 Polynomial poly,poly1,poly2,poly3;
// ListSeqMap<int> listseq;

 poly.AddTerm(1,3);
 poly.AddTerm(2,-4);
// poly.Print();

 poly.Print();
 printf("%f", poly.Evaluate(1));

 poly1.AddTerm(1,2);
 poly1.AddTerm(2,1);

 poly2 = poly * poly1;

// poly2.Print();
// poly3 = poly - poly1;
// poly3.Print();
/// listseq.Insert(2);
// listseq.Insert(4);
// listseq.Insert(5);

// printf("%d\n",listseq.GetCount());

// listseq.Remove(2);
// listseq.Remove(4);
// listseq.Remove(5);

// printf("%d\n",listseq.GetCount());

// ACharGraph ag;
// ag.AddEdge('A','B',1);
// ag.AddEdge('B','C',1);
// ag.AddEdge('C','D',3);
// ag.AddEdge('D','E',2);
// ag.AddEdge('E','F',1);

// ag.ShortestPath_Dijkstra('A');

// LCharGraph lg;
// lg.AddEdgeDir('A','B',1);
// lg.AddEdgeDir('A','D',1);
// lg.AddEdgeDir('A','C',1);
// lg.AddEdgeDir('D','F',1);
// lg.AddEdgeDir('D','C',1);
// lg.AddEdgeDir('F','D',1);
// lg.AddEdgeDir('F','E',1);
// lg.AddEdgeDir('E','A',1);
// lg.AddEdgeDir('G','D',1);
// lg.AddEdgeDir('G','J',1);
// lg.AddEdgeDir('J','F',1);
// lg.AddEdgeDir('J','K',1);
// lg.AddEdgeDir('J','I',1);
// lg.AddEdgeDir('I','G',1);
// lg.AddEdgeDir('H','G',1);
// lg.AddEdgeDir('H','I',1);

// lg.StrongConnect();
// lg.TopologicalSort();

// LCharGraph llg(lg);

// llg.DFS();
// lg.TransitiveClosure_Warshall();
// ag.DFS();
// lg.DFS_nr();
// printf("\n");
// printf("%d\n",lg.CountComponents());

// lg.MCST_Pfs();
// printf("\n");
// lg.MCST_Kruskal();
// lg.ShortestPath_Pfs('A');

// HashMap<Person,PersonHash> map(PersonHash(),13);
/// map.Insert(Person(5,"Heather"));
// map.Insert(Person(3,"Carlos"));
//
// Person key;
// Person rt;
// key.m_id = 3;
// if(map.Find(key,rt))
//  printf("name : %s\n",rt.m_name.c_str());
// else
//  printf("Not found\n");

// RadixTreeMap<int> rtree;
// rtree.Insert(1);
// rtree.Insert(3);
// rtree.Find(1,a);
// printf("count %d\n",rtree.GetCount());
// RadixTrieMap<Person> rtrie;
// rtrie.Insert(Person(1,"Heather"));
// rtrie.Insert(Person(2,"Carlos"));

// Person key1(1,"");
// Person value;
// rtrie.Find(key1,value);
// printf("name :%s\n",value.m_name.c_str());
// printf("rtrie count: %d\n",rtrie.GetCount());
// int a[]={1,2,3,7,3,2,5};
// BinaryTreeSort(a,7);
// for(int i=0; i< 7;i++)
//  printf("%d ",a[i]);
// printf("\n");
// ParseTree tree;
// tree.BuildParseTree("A B + C D - * E / F G * +");
// tree.PreOrderTraverse();
// printf("\n");
// tree.PostOrderTraverse();
// printf("\n");
// tree.InOrderTraverse();
// printf("\n");
// tree.LevelOrderTraverse();
// printf("\n");
// ListQueue<int> queue;
// queue.Put(1);
// queue.Put(2);
// while(!queue.IsEmpty())
//  printf("%d\n",queue.Get());
// ListStack<int> stack;
// stack.Push(5);
// stack.Push(6);
// while(!stack.IsEmpty())
//  printf("%d\n",stack.Pop());
// printf("%d\n",stack.GetTop());
// map<int,Person> pmap;
// pmap.insert(make_pair(1,Person(15,"Jake")));
/// pmap.insert(make_pair(2,Person(41,"Heather")));
/// pmap.insert(make_pair(3,Person(11,"Carlos")));
// pmap.insert(make_pair(4,Person(21,"Totoro")));

// Person key;
// key.m_id = 1;
// Person value;
// pmap.find();

//printf("%s\n",value.m_name);
 
// ArrayStack<int> stack(3);
// stack.Push(1);
// stack.Push(2);
// stack.Push(3);
// stack.Push(4);
// while(!stack.IsEmpty())
//  printf("%d\n",stack.Pop());
 //// int a[32000],i;
// for(i = 0; i < 32000 ; i++)
//  a[i] = rand()/500;
// ShellSort(a,32000);
// if(CheckSort(a,32000))
//  printf("true\n");
// else
//  printf("false\n");
// for(i =0 ; i<32000 ; i++)
//  printf("%d\n",a[i]);
 //qsord
// int a[10000];
// qsort(a,10000,sizeof(int),intcmp);

// cout<<gcd(6,4);
// cout<<toString(6);
// int i[]={0,5,4,3,6,7,7};
// BubbleSort(i,8);
// for(int j = 0; j < 7 ; j++)
// {
//  printf("%d\n",i[j]);
// }
}