/*****************************************************************************/
/*                                                                           */
/*           F I S T :  Fast, Industrial-Strength Triangulation              */
/*                                                                           */
/*****************************************************************************/
/*                                                                           */
/* (C)                            Martin Held                                */
/* (C)            Universitaet Salzburg, Salzburg, Austria                   */
/*                                                                           */
/* This code is not in the public domain. All rights reserved! Please make   */
/* sure to read the full copyright statement contained in api_functions.cpp. */
/*                                                                           */
/*****************************************************************************/

/* get standard i/o library */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* get my header file */
#include "fpkernel.h"
#include "martin.h"
#include "defs.h"
#include "header.h"
#include "basic.h"

/*                                                                           */
/* function prototypes of functions provided in this file                    */
/*                                                                           */
void InitHeapDefaults(heapdef *hp);
void FreeHeap(heapdef *hp);
boolean InHeap(heapdef *hp, list_ind ind);
void DumpOnHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
                list_ind next);
void InsertIntoHeap(heapdef *hp, machine_double ratio, list_ind ind, 
                    list_ind prev,
                    list_ind next);
boolean DeleteFromHeap(heapdef *hp, list_ind *ind, list_ind *prev, 
                       list_ind *next);
void InitHeap(heapdef *hp, datadef *data);
void MakeHeap(heapdef *hp);

#ifdef PARTITION_FIST
void InitPartitionedHeap(global_struct *all);
#endif

#define BLOCK_SIZE    65536


#define StoreHeapData(addr, s_ratio, s_ind, s_prev, s_next) \
 { \
   addr->ratio = s_ratio; \
   addr->index = s_ind; \
   addr->prev  = s_prev; \
   addr->next  = s_next; \
 }



#define GetHeapData(addr, s_ind, s_prev, s_next) \
 { \
   s_ind   = addr->index; \
   s_prev  = addr->prev; \
   s_next  = addr->next; \
 }



void InitHeapDefaults(heapdef *hp)
{
	hp->heap = (heap_node*)NULL;
	hp->num_heap = 0;
	hp->max_num_heap = 0;
	hp->num_zero = 0;

	hp->deleted = false;
	hp->not_updated = false;
	hp->sorted = false;
	hp->ear_right = true;
}

boolean InHeap(heapdef *hp, list_ind ind)
{
   return ((ind >= 0)  &&  (ind < hp->num_heap));
}





void FreeHeap(heapdef *heap)
{
#ifdef PARTITION_FIST
   char name[14];
   sprintf(name,"heap:heap%04i",heap->heap_idx);
   FreeMemory(heap->memptr, (void**) &heap->heap, name);
#else
   FreeMemory(heap->memptr, (void**) &heap->heap, "heap:heap");
#endif

   heap->max_num_heap = 0;
   heap->num_heap     = 0;
   heap->num_zero     = 0;

   return;
}



void DumpOnHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
                list_ind next)
{
   heap_node *addr;

   if (hp->num_heap >= hp->max_num_heap)  {
	   hp->max_num_heap += BLOCK_SIZE;
#ifdef PARTITION_FIST
      char name[14];
      sprintf(name,"heap:heap%04i",hp->heap_idx);
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), name);
#else
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), "heap:heap");
#endif
   }
   if (ratio == 0.0) {
      if (hp->num_zero < hp->num_heap) hp->heap[hp->num_heap] = hp->heap[hp->num_zero];
      addr = &(hp->heap[hp->num_zero]);
      ++hp->num_zero;
   }
   else {
      addr = &(hp->heap[hp->num_heap]);
   }

   StoreHeapData(addr, ratio, ind, prev, next);
   ++hp->num_heap;

   return;
}




void UpdateHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
                list_ind next)
{
   int i, j, j1, j2;
   heap_node *addr;

   i  = 0;
   j1 = 2 * i + 1;
   j2 = j1 + 1;

   while (j2 < hp->num_heap) {
      if (hp->heap[j1].ratio < hp->heap[j2].ratio)  j = j1;
      else                                          j = j2;

      if (hp->heap[j].ratio < ratio) {
    	 hp->heap[i] = hp->heap[j];
         i  = j;
         j1 = 2 * i + 1;
         j2 = j1 + 1;
      }
      else {
         j1 = j2 = hp->num_heap;
      }
   }

   if (j1 < hp->num_heap) {
      if (hp->heap[j1].ratio < ratio) {
    	 hp->heap[i] = hp->heap[j1];
         addr = &(hp->heap[j1]);
         StoreHeapData(addr, ratio, ind, prev, next);
      }
      else {
         addr = &(hp->heap[i]);
         StoreHeapData(addr, ratio, ind, prev, next);
      }
   }
   else {
      addr = &(hp->heap[i]);
      StoreHeapData(addr, ratio, ind, prev, next);
   }

   return;
}




void ExtendHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
                list_ind next)
{
   int i, j;
   heap_node *addr;
   
   if (hp->num_heap == 0) hp->sorted = true;
   else                   assert(hp->sorted);
   j = hp->num_heap;
   ++hp->num_heap;

   if (hp->num_heap >= hp->max_num_heap)  {
	  hp->max_num_heap += BLOCK_SIZE;
#ifdef PARTITION_FIST
      char name[14];
      sprintf(name,"heap:heap%04i",hp->heap_idx);
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), name);
#else
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), "heap:heap");
#endif
   }

   while (j > 0) {
      i = (j - 1) / 2;
      if (hp->heap[i].ratio > ratio) {
    	 hp->heap[j] = hp->heap[i];
         j = i;
      }
      else {
         addr = &(hp->heap[j]);
         StoreHeapData(addr, ratio, ind, prev, next);
         return;
      }
   }

   addr = &(hp->heap[0]);
   StoreHeapData(addr, ratio, ind, prev, next);

   return;
}



void InsertIntoHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
                    list_ind next)
{
   if (hp->ears_sorted) {
      if (hp->deleted)  {
         UpdateHeap(hp, ratio, ind, prev, next);
      }
      else {
         ExtendHeap(hp, ratio, ind, prev, next);
      }
      hp->deleted     = false;
      hp->not_updated = false;
   }
   else {
      DumpOnHeap(hp, ratio, ind, prev, next);
   }

   return;
}




boolean DeleteFromHeap(heapdef *hp, list_ind *ind, list_ind *prev, list_ind *next)
{
   heap_node *addr;
   int rnd_ind, macro_var;

   if (hp->ears_sorted) {
      /*                                                                     */
      /* clip ears according to my quality heuristic                         */
      /* this corresponds to the run-time flags "--sorted", "--fancy", or    */
      /* "--top"                                                             */
      /*                                                                     */
      if (hp->deleted  &&  hp->not_updated) {
         if (hp->num_heap <= 1) {
        	 hp->num_heap = 0;
            return false;
         }
         --hp->num_heap;
         assert(hp->sorted);
         addr = &(hp->heap[hp->num_heap]);
         UpdateHeap(hp, addr->ratio, addr->index, addr->prev, addr->next);
         hp->not_updated = false;
         hp->deleted     = false;
      }
      else if (hp->num_heap <= 0)
         return  false;
      
      assert(hp->sorted);
      addr  = &(hp->heap[0]);
      GetHeapData(addr, *ind, *prev, *next);
      hp->not_updated = true;
      hp->deleted     = true;

      return  true;
   }
   else if (hp->num_zero > 0) {
      /*                                                                     */
      /* if we don't use sorted or fancy clipping then I make sure to clip   */
      /* degenerate ears first. such ears have 0.0 as their quality!         */
      /*                                                                     */
      assert(hp->num_heap >= hp->num_zero);
      --hp->num_zero;
      --hp->num_heap;
      addr  = &(hp->heap[hp->num_zero]);
      GetHeapData(addr, *ind, *prev, *next);
      hp->heap[hp->num_zero] = hp->heap[hp->num_heap];
      return  true;
   }
   else if (hp->ears_random) {
      /*                                                                     */
      /* clip ears in random order.                                          */
      /* this corresponds to the run-time flag "--random"                    */
      /*                                                                     */
      if (hp->num_heap <= 0) {
    	 hp->num_heap = 0;
         return false;
      }
      rnd_ind = RandomInteger(macro_var,hp->num_heap);
      assert((rnd_ind >= 0)  &&  (rnd_ind < hp->num_heap));
      --hp->num_heap;
      addr    = &(hp->heap[rnd_ind]);
      GetHeapData(addr, *ind, *prev, *next);
      hp->heap[rnd_ind] = hp->heap[hp->num_heap];

      return true;
   }
   else  {
      /*                                                                     */
      /* let's clip the ears in the inverse order as we find them.           */
      /* this corresponds to the run-time flag "--sequen"                    */
      /*                                                                     */
      if (hp->num_heap <= 0) {
    	 hp->num_heap = 0;
         return false;
      }
      --hp->num_heap;
      addr = &(hp->heap[hp->num_heap]);
      GetHeapData(addr, *ind, *prev, *next);
     
      return true;
   }
}




void InitHeap(heapdef *hp, datadef *data)
{
   if (hp->heap == (heap_node*)NULL)  hp->max_num_heap = 0;
   if ((2 * data->num_pnts) > hp->max_num_heap)  {
	   hp->max_num_heap = 2 * data->num_pnts;
#ifdef PARTITION_FIST
      char name[14];
      sprintf(name,"heap:heap%04i",hp->heap_idx);
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), name);
#else
      hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
                                              sizeof(heap_node), "heap:heap");
#endif
   }
   hp->num_heap      = 0;
   hp->deleted       = false;
   hp->not_updated   = false;
   hp->sorted        = false;
   hp->num_zero      = 0;
   hp->ear_right     = true;

   return;
}

#ifdef PARTITION_FIST
void InitPartitionedHeap(global_struct *all) {
   heapdef *hp;
   
   all->c_heap = (heapdef*)NULL;
   all->corner_nodes = (list_ind*)NULL;
   
   all->c_heap = (heapdef*) ReallocateArray((debug_memdef*)&all->c_mem, all->c_heap,
                                            all->number_of_heaps,
                                            sizeof(heapdef), "all:heaps");

   all->corner_nodes = (list_ind*) ReallocateArray((debug_memdef*)&all->c_mem,
                                                   all->corner_nodes,
                                                   all->number_of_heaps,
                                                   sizeof(list_ind), "all:corners");
   
   for(int i = 0; i < all->number_of_heaps; ++i) {
      hp = &all->c_heap[i];
      hp->heap_idx = i;
      hp->heap = (heap_node*)NULL;
   }
}
#endif


void MakeHeap(heapdef *hp)
{
   int h_comp(const void *, const void *);

   if (!hp->ears_sorted)  return;

   /*                                                                        */
   /* sort the heap entries according to their ratios                        */
   /*                                                                        */
   qsort(hp->heap, hp->num_heap, sizeof(heap_node), &h_comp);
   hp->sorted = true;

   return;
}



int h_comp(const void *a, const void *b)
{
   if (((heap_node*)a)->ratio < ((heap_node*)b)->ratio)        return -1;
   else if (((heap_node*)a)->ratio > ((heap_node*)b)->ratio)   return  1;
   else                                                        return  0;
}





void TestTree(heapdef *hp)
{
   int i, i1, i2, bound;
   
   if (hp->num_heap <= 1)  return;

   bound = (hp->num_heap + 1) / 2 - 1;

   for (i = 0;  i < bound;  ++i) {
      i1 = 2 * i + 1;
      i2 = i1 + 1;
      assert(hp->heap[i1].ratio >= hp->heap[i].ratio);
      assert(hp->heap[i2].ratio >= hp->heap[i].ratio);
   }
   
   i  = bound;
   i1 = 2 * i + 1;
   i2 = i1 + 1;
  
   if (i1 < hp->num_heap) assert(hp->heap[i1].ratio >= hp->heap[i].ratio);
   if (i2 < hp->num_heap) assert(hp->heap[i2].ratio >= hp->heap[i].ratio);

   return;
}