/*

Miranda IM: the free IM client for Microsoft* Windows*

Copyright 2000-2009 Miranda ICQ/IM project, 
all portions of this codebase are copyrighted to the people
listed in contributors.txt.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, 
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#include "..\..\core\commonheaders.h"

/* a simple sorted list implementation */

SortedList* List_Create(int p_limit, int p_increment)
{
	SortedList* result = (SortedList*)mir_calloc(sizeof(SortedList));
	if (result == NULL)
		return(NULL);

	result->increment = p_increment;
	result->limit = p_limit;
	return(result);
}

void List_Destroy(SortedList* p_list)
{
	if (p_list == NULL)
		return;

	if (p_list->items != NULL) {
		mir_free(p_list->items);
		p_list->items = NULL;
	}

	p_list->realCount = p_list->limit = 0;
}

void* List_Find(SortedList* p_list, void* p_value)
{
	int index;
	
	if ( !List_GetIndex(p_list, p_value, &index))
		return(NULL);

	return(p_list->items[ index ]);
}

#ifdef _DEBUG
#pragma optimize("gt", on)
#endif

int List_GetIndex(SortedList* p_list, void* p_value, int* p_index)
{
	if (p_value == NULL)
	{
		*p_index = -1;
		return 0;
	}

	switch ((INT_PTR)p_list->sortFunc)
	{
	case 0:
		break;

	case HandleKeySort:
#ifdef _WIN64
		{
			const unsigned __int64 val = *(unsigned __int64 *)p_value;
			int low  = 0;
			int high = p_list->realCount - 1;

			while (low <= high)
			{  
				int i = (low + high) / 2;
				unsigned __int64 vali = *(unsigned __int64 *)p_list->items[i];
				if (vali == val)
				{	
					*p_index = i;
					return 1;
				}

				if (vali < val)
					low = i + 1;
				else
					high = i - 1;
			}

			*p_index = low;
		}
		break;
#endif

	case NumericKeySort:
		{
			const unsigned val = *(unsigned *)p_value;
			int low  = 0;
			int high = p_list->realCount - 1;

			while (low <= high)
			{  
				int i = (low + high) / 2;
				unsigned vali = *(unsigned *)p_list->items[i];
				if (vali == val)
				{	
					*p_index = i;
					return 1;
				}

				if (vali < val)
					low = i + 1;
				else
					high = i - 1;
			}

			*p_index = low;
		}
		break;

	case PtrKeySort:
		{
			int low  = 0;
			int high = p_list->realCount - 1;

			while (low <= high)
			{  
				int i = (low + high) / 2;
				const void* vali = p_list->items[i];
				if (vali == p_value)
				{	
					*p_index = i;
					return 1;
				}

				if (vali < p_value)
					low = i + 1;
				else
					high = i - 1;
			}

			*p_index = low;
		}
		break;

	default:
		{
			int low  = 0;
			int high = p_list->realCount - 1;

			while (low <= high)
			{  
				int i = (low + high) / 2;
				int result = p_list->sortFunc(p_list->items[i], p_value);
				if (result == 0)
				{	
					*p_index = i;
					return 1;
				}

				if (result < 0)
					low = i + 1;
				else
					high = i - 1;
			}

			*p_index = low;
		}
		break;
	}

	return 0;
}

int List_IndexOf(SortedList* p_list, void* p_value)
{
	if (p_value == NULL)
		return -1;

	int i;
	for (i=0; i < p_list->realCount; i++)
		if (p_list->items[i] == p_value)
			return i;

	return -1;
}

#ifdef _DEBUG
#pragma optimize("", on)
#endif

int List_Insert(SortedList* p_list, void* p_value, int p_index) 
{
	if (p_value == NULL || p_index > p_list->realCount)
		return 0;

   if (p_list->realCount == p_list->limit)
	{
		p_list->items = (void**)mir_realloc(p_list->items, sizeof(void*)*(p_list->realCount + p_list->increment));
		p_list->limit += p_list->increment;
	}

	if (p_index < p_list->realCount)
		memmove(p_list->items+p_index+1, p_list->items+p_index, sizeof(void*)*(p_list->realCount-p_index));

   p_list->realCount++;

   p_list->items[ p_index ] = p_value;
   return 1;
}

int List_InsertPtr(SortedList* list, void* p)
{
	if (p == NULL)
		return -1;

	int idx = list->realCount;
	List_GetIndex(list, p, &idx);
	return List_Insert(list, p, idx);
}

int List_Remove(SortedList* p_list, int index)
{
	if (index < 0 || index > p_list->realCount)
		return(0);

   p_list->realCount--;
   if (p_list->realCount > index)
	{
		memmove(p_list->items+index, p_list->items+index+1, sizeof(void*)*(p_list->realCount-index));
      p_list->items[ p_list->realCount ] = NULL;
	}

   return 1;
}

int List_RemovePtr(SortedList* list, void* p)
{
	int idx = -1;
	if (List_GetIndex(list, p, &idx))
		List_Remove(list, idx);

	return idx;
}

void List_Copy(SortedList* s, SortedList* d, size_t itemSize)
{
	d->increment = s->increment;
	d->limit     = s->limit;
	d->realCount = s->realCount;
	d->items = (void**)mir_alloc( sizeof(void*) * d->realCount);
	memcpy(d->items, s->items, sizeof(void*) * d->realCount);
}

void List_ObjCopy(SortedList* s, SortedList* d, size_t itemSize)
{
	int i;

	d->increment = s->increment;
	d->sortFunc  = s->sortFunc;

	for (i = 0; i < s->realCount; i++) {
		void* item = new char[ itemSize ];
		memcpy(item, s->items[i], itemSize);
		List_Insert(d, item, i);
}	}