/*****************************************************************************/
/*                                                                           */
/*           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 "list.h"
#include "header.h"

/*                                                                           */
/* function prototypes of functions provided in this file                    */
/*                                                                           */
void RemoveZeroEdges(listdef* list, list_ind *ind);
void FreeList(listdef* list);
list_ind MakeHook(listdef* list);
void DeleteHook(listdef* list, int curr_loop);
int MakeLoopHeader(listdef* list);
void DecrementLoops(listdef* list);
list_ind MakeNode(listdef* list, int index);
void InsertAfter(listdef* list, list_ind ind1, list_ind ind2);
void DeleteLinks(listdef* list, list_ind ind);
list_ind FetchNextData(listdef* list, list_ind ind1, int *index);
list_ind FetchPrevData(listdef* list, list_ind ind1, int *index);
int CountListElements(listdef* list, list_ind ind1);
void UpdateIndex(listdef* list, list_ind ind, int index);
void SwapLinks(listdef* list, list_ind ind1);
boolean InPolyList(listdef* list, list_ind ind);
boolean InLoopList(listdef* list, int loop);
//void InitAngle(listdef* list, list_ind ind, int convex);
void ResetPolyList(listdef* list, list_ind ind);
list_ind GetNode(listdef* list);
int GetOriginal(listdef* list, list_ind ind);
void SetOriginal(listdef* list, list_ind ind, int original);
#ifdef NORMALS
void SetTexNormData(listdef* list, list_ind ind, int index1, int index2);
int GetNormalIndex(listdef* list, list_ind ind);
int GetTextureIndex(listdef* list, list_ind ind);
#endif
void SplitSplice(listdef* list, list_ind ind1, list_ind ind2, list_ind ind3, list_ind ind4);
void RotateLinks(listdef* list, list_ind ind1, list_ind ind2);
void ResetListData(listdef* list);
void StoreChain(listdef* list, list_ind ind);
list_ind GetNextChain(listdef* list, boolean *done);
void InitStorageList(listdef* list, int number);
void InitStorageLoops(listdef* list, int number);
void InitFace(listdef* list, int number);
void DecrementFaces(listdef* list);
int GetNumList(listdef* list);
boolean GetBridgeNode(listdef* list, list_ind ind);
void SetBridgeNodePair(listdef* list, list_ind ind1, list_ind ind2);
#ifdef PARTITION_FIST
boolean isCorner(global_struct *all, int current_partition, list_ind ind);
#endif

#define MEGA_BLOCK_SIZE  65536
#define BLOCK_SIZE       16384
#define HALF_BLOCK_SIZE    512
#define MARK_LIST_BOUND     40

void InitListDefaults(listdef* list)
{
	list->list = (list_node*)NULL;
	list->num_list = 0;
	list->max_num_list = 0;

	list->loops = (list_ind*)NULL;
	list->num_loops = 0;
	list->max_num_loops = 0;

	list->faces = (int*)NULL;
	list->num_faces = 0;
	list->max_num_faces = 0;

	list->first_node = 0;

	list->chains = (list_ind*)NULL;
	list->num_chains = 0;
	list->max_num_chains = 0;
}


int GetNumList(listdef* list)
{
   return list->num_list;
}


void ResetListData(listdef* list)
{
   list->num_list   = 0;
   list->num_chains = 0;
   list->first_node = 0;

   return;
}




void FreeList(listdef* list)
{
   FreeMemory(list->memptr, (void**) &list->list, "list:list");
   FreeMemory(list->memptr, (void**) &list->loops, "list:loops");
   FreeMemory(list->memptr, (void**) &list->faces, "list:faces");
   FreeMemory(list->memptr, (void**) &list->chains, "list:chains");
   
   list->max_num_list   = 0;
   list->num_list       = 0;
   list->max_num_loops  = 0;
   list->num_loops      = 0;
   list->max_num_chains = 0;
   list->num_chains     = 0;
   list->max_num_faces  = 0;
   list->num_faces      = 0;

   return;
}

#ifdef PARTITION_FIST
boolean isCorner(global_struct *all, int current_partition, list_ind ind) {
   if (ind == all->corner_nodes[current_partition])
      return true;
   if (ind == all->corner_nodes[(current_partition+1) % all->number_of_heaps])
      return true;
   
   return false;
}
#endif


/*                                                                           */
/* allocates storage for a dummy list node; pointers are set to itself;      */
/* returns pointer to node                                                   */
/*                                                                           */
list_ind MakeHook(listdef* list)
{
   list_ind ind;
   list_node *addr;

   if (list->num_list >= list->max_num_list)  {
      list->max_num_list += MEGA_BLOCK_SIZE;
      list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
                                                sizeof(list_node), "list:list");
   }
   ind = list->num_list;
   addr = &(list->list[list->num_list]);
   addr->prev   = ind;
   addr->next   = ind;
   addr->index  = NIL;
   addr->bridge = false;
#ifdef PARTITION_FIST
   addr->delete_reflex = false;
#endif
   ++list->num_list;
   
   return ind;
}



void DeleteHook(listdef* list, int curr_loop)
{
   list_ind ind1, ind2;

   assert(InLoopList(list,curr_loop));
   ind1 = list->loops[curr_loop];
   assert(InPolyList(list,ind1));
   ind2 = list->list[ind1].next;
   assert(InPolyList(list,ind2));
   DeleteLinks(list,ind1);
   list->loops[curr_loop] = ind2;

   return;
}


int MakeLoopHeader(listdef* list)
{
   int i;
   list_ind ind;

   ind = MakeHook(list);

   if (list->num_loops >= list->max_num_loops) {
	   list->max_num_loops += BLOCK_SIZE;
	   list->loops = (list_ind*) ReallocateArray(list->memptr, list->loops, list->max_num_loops,
                                                sizeof(list_ind), "list:loops");
   }
   list->loops[list->num_loops] = ind;
   i                = list->num_loops;
   ++list->num_loops;

   return  i;
}



void DecrementLoops(listdef* list)
{
   assert(list->num_loops > 0);
   --list->num_loops;

   return;
}



void InitStorageList(listdef* list, int number)
{
   if (number >= list->max_num_list)  {
	   list->max_num_list = number;
      list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
                                                sizeof(list_node), "list:list");
   }

   return;
}




void InitStorageLoops(listdef* list, int number)
{
   if (number >= list->max_num_loops)  {
	   list->max_num_loops = number;
	   list->loops = (list_ind*) ReallocateArray(list->memptr, list->loops, list->max_num_loops,
                                                sizeof(list_ind), "list:loops");
   }

   return;
}




/*                                                                           */
/* allocates storage for a new list node, and stores the index of the point  */
/* at this node; pointers are set to NIL; returns pointer to node            */
/*                                                                           */
list_ind MakeNode(listdef* list, int index)
{
   list_ind ind;
   list_node *addr;

   if (list->num_list >= list->max_num_list)  {
	  list->max_num_list += BLOCK_SIZE;
      list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
                                                sizeof(list_node), "list:list");
   }
   ind  = list->num_list;
   addr = &(list->list[list->num_list]);
   addr->index  = index;
   addr->prev   = NIL;
   addr->next   = NIL;
   addr->bridge = false;
#ifdef PARTITION_FIST
   addr->delete_reflex = false;
#endif
   ++list->num_list;

   return ind;
}


/*                                                                           */
/* inserts node ind2 after node ind1                                         */
/*                                                                           */
void InsertAfter(listdef* list, list_ind ind1, list_ind ind2)
{
   list_ind ind3;

   assert(InPolyList(list,ind1));
   assert(InPolyList(list,ind2));
   list->list[ind2].next = list->list[ind1].next;
   list->list[ind2].prev = ind1;
   list->list[ind1].next = ind2;
   ind3            = list->list[ind2].next;
   assert(InPolyList(list,ind3));
   list->list[ind3].prev = ind2;

   return;
}



/*                                                                           */
/* deletes node ind from list (with destroying its data fields)              */
/*                                                                           */
void DeleteLinks(listdef* list, list_ind ind)
{
   list_node *addr;

   assert(InPolyList(list,ind));
   addr = &(list->list[ind]);
   assert(InPolyList(list,addr->prev));
   assert(InPolyList(list,addr->next));
   if (list->first_node == ind) list->first_node = addr->next;
   list->list[addr->next].prev = addr->prev;
   list->list[addr->prev].next = addr->next;
   addr->prev = addr->next = ind;

   return;
}




/*                                                                           */
/* returns pointer to the successor ind2 of ind1, and its data               */
/*                                                                           */
list_ind FetchNextData(listdef* list, list_ind ind1, int *index)
{
   list_ind ind2;

   assert(InPolyList(list,ind1));
   ind2 = list->list[ind1].next;
   assert(InPolyList(list,ind2));
   *index = list->list[ind2].index;

   return ind2;
}




/*                                                                           */
/* returns pointer to the successor ind2 of ind1, and its data               */
/*                                                                           */
list_ind FetchPrevData(listdef* list, list_ind ind1, int *index)
{
   list_ind ind2;

   assert(InPolyList(list,ind1));
   ind2 = list->list[ind1].prev;
   assert(InPolyList(list,ind2));
   *index = list->list[ind2].index;

   return ind2;
}




/*                                                                           */
/* this function counts the number of elements of a circular list            */
/*                                                                           */
int CountListElements(listdef* list, list_ind ind1)
{
   int num_ele = 1;
   list_ind ind2;
   
   assert(InPolyList(list,ind1));
   ind2 = list->list[ind1].next;
   
   while (ind2 != ind1) { 
      assert(InPolyList(list,ind2));
      ++num_ele;
      ind2 = list->list[ind2].next;
   }

   return  num_ele;
}



void UpdateIndex(listdef* list, list_ind ind, int index)
{
   assert(InPolyList(list,ind));
   list->list[ind].index = index;

   return;
}



/*                                                                           */
/* swap the list pointers in order to change the orientation                 */
/*                                                                           */
void SwapLinks(listdef* list, list_ind ind1)
{
   list_ind ind2, ind3;

   assert(InPolyList(list,ind1));
   ind2 = list->list[ind1].next;
   assert(InPolyList(list,ind2));
   list->list[ind1].next = list->list[ind1].prev;
   list->list[ind1].prev = ind2;
   ind3 = ind2;
   while (ind2 != ind1) {
      assert(InPolyList(list,ind2));
      ind3 = list->list[ind2].next;
      list->list[ind2].next = list->list[ind2].prev;
      list->list[ind2].prev = ind3;
      ind2 = ind3;
   }
   
   return;
}



boolean InPolyList(listdef* list, list_ind ind)
{
   return  ((ind >= 0)  &&  (ind < list->num_list)  &&  (list->num_list <= list->max_num_list));
}



boolean InLoopList(listdef* list, int loop)
{
   return  ((loop >= 0)  &&  (loop < list->num_loops)  &&
            (list->num_loops <= list->max_num_loops));
}




void ResetPolyList(listdef* list, list_ind ind)
{
   assert(InPolyList(list,ind));
   list->first_node = ind;

   return;
}




list_ind GetNode(listdef* list)
{
   assert(InPolyList(list,list->first_node));

   return list->first_node;
}



int GetOriginal(listdef* list, list_ind ind)
{
   assert(InPolyList(list,ind));
   return  list->list[ind].original;
}



void SetOriginal(listdef* list, list_ind ind, int original)
{
   assert(InPolyList(list,ind));
   list->list[ind].original = original;

   return;
}
   


boolean GetBridgeNode(listdef* list, list_ind ind)
{
   assert(InPolyList(list,ind));
   
   return list->list[ind].bridge;
}


void SetBridgeNodePair(listdef* list, list_ind ind1, list_ind ind2)
{
   assert(InPolyList(list,ind1));
   assert(InPolyList(list,ind2));

   list->list[ind1].bridge = true;
   list->list[ind2].bridge = true;

   return;
}


#ifdef NORMALS
void SetTexNormData(listdef* list, list_ind ind, int t_index, int n_index)
{
   assert(InPolyList(list,ind));
   list->list[ind].t_index = t_index;
   list->list[ind].n_index = n_index;

   return;
}


int GetTextureIndex(listdef* list, list_ind ind)
{
   assert(InPolyList(list,ind));
   
   return  list->list[ind].t_index;
}


int GetNormalIndex(listdef* list, list_ind ind)
{
   assert(InPolyList(list,ind));
   
   return list->list[ind].n_index;
}
#endif



void SplitSplice(listdef* list, list_ind ind1, list_ind ind2, list_ind ind3, list_ind ind4)
{
   assert(InPolyList(list,ind1));
   assert(InPolyList(list,ind2));
   assert(InPolyList(list,ind3));
   assert(InPolyList(list,ind4));
   assert(list->list[ind1].next == ind2);
   assert(list->list[ind2].prev == ind1);
   assert(list->list[ind3].next == ind4);
   assert(list->list[ind4].prev == ind3);

   list->list[ind1].next = ind4;
   list->list[ind4].prev = ind1;
   list->list[ind2].prev = ind3;
   list->list[ind3].next = ind2;

   return;
}



void RotateLinks(listdef* list, list_ind ind1, list_ind ind2)
{
   list_ind ind;
   list_ind ind0, ind3;

   assert(InPolyList(list,ind1));
   assert(InPolyList(list,ind2));
   ind0 = list->list[ind1].next;
   ind3 = list->list[ind2].next;
   assert(InPolyList(list,ind0));
   assert(InPolyList(list,ind3));

   Swap(list->list[ind1].next, list->list[ind2].next, ind);
   list->list[ind0].prev = ind2;
   list->list[ind3].prev = ind1;

   return;
}





void StoreChain(listdef* list, list_ind ind)
{
   if (list->num_chains >= list->max_num_chains)  {
	   list->max_num_chains += HALF_BLOCK_SIZE;
	   list->chains = (list_ind*) ReallocateArray(list->memptr, list->chains, list->max_num_chains,
                                                 sizeof(list_ind), "list:chains");
   }
   list->chains[list->num_chains] = ind;
   ++list->num_chains;

   return;
}




list_ind GetNextChain(listdef* list, boolean *done)
{
   if (list->num_chains > 0) {
      *done = true;
      --list->num_chains;
      return  list->chains[list->num_chains];
   }
   else {
      *done      = false;
      list->num_chains = 0;
      return 0;
   }
}



void InitFace(listdef* list, int number)
{
   if (list->num_faces >= list->max_num_faces) {
	   list->max_num_faces += BLOCK_SIZE;
	   list->faces = (int*) ReallocateArray(list->memptr, list->faces, list->max_num_faces,
                                           sizeof(int), "list:faces");
   }
   list->faces[list->num_faces] = number;
   ++list->num_faces;

   return;
}



void DecrementFaces(listdef* list)
{
   assert(list->num_faces > 0);
   --list->num_faces;

   return;
}



void RemoveZeroEdges(listdef* list, list_ind *ind)
{
   list_ind ind1, ind2, ind3;
   int i1, i2;

   ind1 = *ind;
   i1   = GetIndex(list,ind1);
   ind2 = GetNextNode(list,ind1);
   do {
      i2 = GetIndex(list,ind2);
      if (i1 == i2) {
         ind3 = GetNextNode(list,ind2);
         DeleteLinks(list,ind2);
         ind2 = ind3;
      }
      else {
         i1 = i2;
         ind2 = GetNextNode(list,ind2);
      }
   } while (ind2 != ind1);
 
   i2 = GetIndex(list,ind2);
   if (i1 == i2) {
      *ind = GetNextNode(list,ind2);
      DeleteLinks(list,ind1);
   }

   return;
}