#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "main.h"
#include "list.h"
#include "index.h"

static int* index_newInt(int x)
{
	int *new;
	new = malloc( sizeof(int) );
	*new = x;
	return new;
}

static void printIndex(list_t *list)
{
	int i;

	printf("printIndex\n");

	for( i = 0 ; i < list->count ; i++ )
	{
		int thisIndex;

		thisIndex = *(int *)list->list[i];
		printf("%d\n", thisIndex);
	}
}

#ifdef CHECK_INDEX
static void checkIndex(list_t *list)
{
	int index, thisIndex;
	int i;

	//printf("check index\n");

	if( list->count == 0 )
	{
		printf("nothing\n");
		return;
	}

	thisIndex = *(int *)list->list[0];


	for( i = 1 ; i < list->count ; i++ )
	{
		index = *(int *)list->list[i];
		//printf("check %d\n", index);

		if( index <= thisIndex )
		{
			printIndex(list);
			assert( ! "error" );
		}

		thisIndex = index;
	}
}
#endif

list_t* newIndex()
{
	return newList();
}

int addToIndex(list_t *list, int index)
{
	int min, max;
	int point;
	int point_index;
	int len;

	len = list->count;

	//printf("addToIndex (%p, %d)\n", list, index);
	//printIndex(list);

	min = 0;
	max = len-1;

	for(;;)
	{
		point = min + ( max - min ) / 2;

		if(  max < 0 )
		{
			insList(list, 0, index_newInt(index));
#ifdef CHECK_INDEX
			checkIndex(list);
#endif
			return 0;
		}

		if(  min >= len )
		{
			addList(list, index_newInt(index) );
#ifdef CHECK_INDEX
			checkIndex(list);
#endif
			return len;
		}
		
		point_index = *(int *)list->list[point];

		if( min > max )
		{
			insList(list, point,  index_newInt(index) );
#ifdef CHECK_INDEX
			checkIndex(list);
#endif
			return point;
		}

		if( index > point_index )
		{
			min = point + 1;
			continue;
		}

		if( index < point_index )
		{
			max = point - 1;
			continue;
		}
	}
}

int getFormIndex(list_t *list, int index)
{
	int point_index;
	int len;
	int min, max;
	int point;

	//printf("getFormIndex %d\n", index);
	//printIndex(list);

	len =list->count;

	min = 0;
	max = len-1;

	for(;;)
	{
		point = min + ( max - min ) / 2;

		if(  max < 0 || point >= len || max < min )
		{
			return -1;
		}

		point_index = *(int *)list->list[point];

		if( point_index == index )
		{
			return point;
		}

		if( index > point_index )
		{
			min = point + 1;
			continue;
		}

		if( index < point_index )
		{
			max = point - 1;
			continue;
		}
	}
}

void delFromIndex(list_t *list, int index)
{
	int offset;

	offset = getFormIndex(list, index);
	assert( offset != -1 );

	delListItem(list, offset, free);
}

void destroyIndex(list_t *list)
{
	assert( list != NULL);

	destroyListItem(list, free);
}