/*******************************************************************************
+
+  LEDA 3.5
+
+  _bin_heap.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

#include <LEDA/impl/bin_heap.h>

//------------------------------------------------------------------------------
// bin_heap: binary heaps  
//           (compressed representation with array doubling)
//
// S. Naeher (1993)
//
//------------------------------------------------------------------------------



#define KEY(i)   (HEAP[i]->key)
#define INF(i)   (HEAP[i]->inf)

bin_heap::bin_heap(int n)  
{ if (n <= 0) 
     error_handler(1,string("bin_heap constructor: illegal size = %d",n));
  HEAP = new bin_heap_item[n];
  for(int i = 0; i < n; i++) HEAP[i] = nil;
  count = 0; 
  max_size = n-2;  // sometimes we use HEAP[0], HEAP[count+1] as stoppers
}

bin_heap::bin_heap(const bin_heap& H)
{ max_size = H.max_size;
  count = H.count; 
  HEAP = new bin_heap_item[max_size+2];
  for(int i = 1; i <= count; i++) 
  { HEAP[i] = new bin_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
    H.copy_key(HEAP[i]->key);
    H.copy_inf(HEAP[i]->inf);
  }
}

bin_heap& bin_heap::operator=(const bin_heap& H)
{ clear();
  delete[] HEAP;
  max_size = H.max_size;
  count = H.count; 
  HEAP = new bin_heap_item[max_size+2];
  for(int i = 1; i <= count; i++) 
  { HEAP[i] = new bin_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
    copy_key(HEAP[i]->key);
    copy_inf(HEAP[i]->inf);
  }
  return *this;
}

bin_heap::~bin_heap()  
{ clear();
  delete[] HEAP; 
}

void bin_heap::clear()
{ for(int i=1; i <= count; i++) 
  { clear_key(KEY(i));
    clear_inf(INF(i));
    delete HEAP[i];
   }
  count = 0;
}


void bin_heap::rise(int pos, bin_heap_item it)
{ switch( key_type_id() ) {
  case INT_TYPE_ID    : int_rise(pos,it);
                        break;
  case DOUBLE_TYPE_ID : double_rise(pos,it);
                        break;
  default             : gen_rise(pos,it);
                        break;
  }
}


void bin_heap::gen_rise(int pos, bin_heap_item it)
{ HEAP[0] = it;  // use "it" as stopper
  int  pi = pos/2;                     // parent index
  bin_heap_item parent = HEAP[pi];     // parent node

  while (cmp(parent->key,it->key) > 0)
  { HEAP[pos] = parent;
    parent->index = pos;
    pos = pi;
    pi >>= 1;
    parent = HEAP[pi];
  }

  HEAP[pos] = it;
  it->index = pos;
}



void bin_heap::int_rise(int pos, bin_heap_item it)
{ HEAP[0] = it;  // use "it" as stopper
  int  pi = pos/2;                     // parent index
  bin_heap_item parent = HEAP[pi];     // parent node

  int  k0 = LEDA_ACCESS(int,it->key);

  while(LEDA_ACCESS(int,parent->key) > k0)
  { HEAP[pos] = parent;
    parent->index = pos;
    pos = pi;
    pi >>= 1;
    parent = HEAP[pi];
   }

  HEAP[pos] = it;
  it->index = pos;
}


void bin_heap::double_rise(int pos, bin_heap_item it)
{ HEAP[0] = it;  // use "it" as stopper
  int  pi = pos/2;                     // parent index
  bin_heap_item parent = HEAP[pi];     // parent node

  double  k0 = LEDA_ACCESS(double,it->key);

  while(LEDA_ACCESS(double,parent->key) > k0)
  { HEAP[pos] = parent;
    parent->index = pos;
    pos = pi;
    pi >>= 1;
    parent = HEAP[pi];
   }

  HEAP[pos] = it;
  it->index = pos;
}




void bin_heap::sink(int pos, bin_heap_item it)
{ switch( key_type_id() ) {
  case INT_TYPE_ID    : int_sink(pos,it);
                        break;
  case DOUBLE_TYPE_ID : double_sink(pos,it);
                        break;
  default             : gen_sink(pos,it);
                        break;
  }
}



void bin_heap::gen_sink(int pos, bin_heap_item it)
{ int ci = 2*pos;       // child index
  bin_heap_item child;  // child node
  HEAP[count+1] = HEAP[count];   // stopper

  while (ci <= count)
  { child = HEAP[ci];
    if (ci < count && cmp(KEY(ci+1),child->key) < 0) child = HEAP[++ci];
    if (cmp(it->key,child->key) <= 0) break; 
    HEAP[pos] = child;
    child->index = pos;
    pos = ci;
    ci <<= 1;
  }

  HEAP[pos] =it;
  it->index = pos;
}



void bin_heap::int_sink(int pos, bin_heap_item it)
{ int ci = 2*pos;       // child index
  bin_heap_item child;  // child node
  HEAP[count+1] = HEAP[count];   // stopper

  int k0 = LEDA_ACCESS(int,it->key);

  while (ci <= count)
  { child = HEAP[ci];
    if (LEDA_ACCESS(int,KEY(ci+1)) < LEDA_ACCESS(int,child->key)) 
      child = HEAP[++ci];
    if (k0 <= LEDA_ACCESS(int,child->key))  break;
    HEAP[pos] = child;
    child->index = pos;
    pos = ci;
    ci <<= 1;
   }

  HEAP[pos] =it;
  it->index = pos;
}

void bin_heap::double_sink(int pos, bin_heap_item it)
{ int ci = 2*pos;       // child index
  bin_heap_item child;  // child node
  HEAP[count+1] = HEAP[count];   // stopper

  double k0 = LEDA_ACCESS(double,it->key);

  while (ci <= count)
  { child = HEAP[ci];
    if (LEDA_ACCESS(double,KEY(ci+1)) < LEDA_ACCESS(double,child->key)) 
      child = HEAP[++ci];
    if (k0 <= LEDA_ACCESS(double,child->key))  break;
    HEAP[pos] = child;
    child->index = pos;
    pos = ci;
    ci <<= 1;
   }

  HEAP[pos] =it;
  it->index = pos;
}




void bin_heap::decrease_key(bin_heap_item it, GenPtr k)
{ if (cmp(it->key,k)<0) 
       error_handler(1,"bin_heap: key too large in decrease_key");
  clear_key(it->key);
  copy_key(k);
  it->key = k;
  rise(it->index, it);
}


bin_heap_item bin_heap::insert(GenPtr k, GenPtr i) 
{ 
  bin_heap_item* H;

  if (count == max_size)  // resize
  { // max_size *= 2;     // double array
    max_size += 1024;
    H = new bin_heap_item[max_size+2];
    for(int i=1; i<= count; i++) H[i] = HEAP[i];
    delete[] HEAP;
    HEAP = H;
   }

  count++;
  copy_key(k);
  copy_inf(i);
  bin_heap_item it = new bin_heap_elem(k,i,count);
  rise(count,it);

  return it;
}




void bin_heap::del_item(bin_heap_item it)
{ bin_heap_item p = HEAP[count];

  HEAP[count] = nil;

  count--;

  if (it != p)
  { if (cmp(p->key,it->key) > 0)
       sink(it->index, p);
    else
       rise(it->index, p);
   }

  clear_key(it->key);
  clear_inf(it->inf);

  delete it;
}


void bin_heap::change_inf(bin_heap_item it, GenPtr i) 
{ clear_inf(it->inf);
  copy_inf(i);
  it->inf = i; 
 }

void bin_heap::print()
{ cout << "size = " << count << endl;
  for(int i=1;i<=count;i++) 
  { print_key(KEY(i));
    cout << "-";
    print_inf(INF(i));
    cout << "  ";
   }
  newline;
}

