//=============================================================================
//
//		Copyright (C) 1995-1997 by Paul S. McCarthy and Eric Sunshine.
//				Written by Paul S. McCarthy and Eric Sunshine.
//							All Rights Reserved.
//
//		This notice may not be removed from this source code.
//
//		This object is included in the MiscKit by permission from the authors
//		and its use is governed by the MiscKit license, found in the file
//		"License.rtf" in the MiscKit distribution.	Please refer to that file
//		for a list of all applicable permissions and restrictions.
//		
//=============================================================================
//-----------------------------------------------------------------------------
// MiscIntList.M
//
//		A dynamically sizable list of integers.
//
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
// $Id: MiscIntList.M,v 1.7 97/01/22 04:01:47 sunshine Exp $
// $Log:		MiscIntList.M,v $
//	Revision 1.7  97/01/22	04:01:47  sunshine
//	v0.117: Fixed bug: std_cmp() was returning 0 for (x > y).
//	Added explicit (id) return types.  Updated formatting.
//	
//	Revision 1.6  96/07/16	22:00:53  zarnuk
//	Added searching methods.
//	
//	Revision 1.5  95/10/03	05:08:16  zarnuk
//	Fixed compiler warning.
//-----------------------------------------------------------------------------
#import <misckit/MiscIntList.h>

extern "Objective-C" {
#import <objc/Storage.h>
}

extern "C" {
#include <stdlib.h>
#include <stdio.h>
}

//-----------------------------------------------------------------------------
// std_cmp
//-----------------------------------------------------------------------------
static int std_cmp( void*, int x, int y )
	{
	if (x < y)
		return -1;
	if (x > y)
		return 1;
	return 0;
	}


//-----------------------------------------------------------------------------
// qsort_cmp
//-----------------------------------------------------------------------------
static MiscIntListCompareFunc cmp_func = 0;
static void* cmp_data = 0;
static int qsort_cmp( void const* px, void const* py )
	{
	return (*cmp_func)( cmp_data, *((int const*)px), *((int const*)py) );
	}


//=============================================================================
// IMPLEMENTATION
//=============================================================================
@implementation MiscIntList

//-----------------------------------------------------------------------------
// sortUsing:data:
//-----------------------------------------------------------------------------
- (void)sortUsing:(MiscIntListCompareFunc)func data:(void*)data
	{
	unsigned int const N = [self count];
	if (N > 1)
		{
		cmp_func = (func ? func : std_cmp);
		cmp_data = data;
		qsort( [array elementAt:0], N, sizeof(int), qsort_cmp );
		}
	}


//-----------------------------------------------------------------------------
// sort
//-----------------------------------------------------------------------------
- (void)sort
	{
	[self sortUsing:&std_cmp data:0];
	}


//-----------------------------------------------------------------------------
// bsearch:using:data:
//		Binary search with hook for user-defined comparisons.
//-----------------------------------------------------------------------------
- (int)bsearch:(int)x using:(MiscIntListCompareFunc)func data:(void*)data
	{
	if (func == 0) func = std_cmp;
	int const* const v = [self rawData];
	int lo = 0;
	int hi = (int) [self count] - 1;
	while (lo <= hi)
		{
		int const mid = (lo + hi) >> 1;
		int const cmp = (*func)( data, x, v[mid] );
		if (cmp < 0)
			hi = mid - 1;
		else if (cmp > 0)
			lo = mid + 1;
		else
			return mid;
		}
	return ~lo;
	}


//-----------------------------------------------------------------------------
// bsearch:
//		Straight binary search.
//-----------------------------------------------------------------------------
- (int)bsearch:(int)x
	{
	int const* const v = [self rawData];
	int lo = 0;
	int hi = (int) [self count] - 1;
	while (lo <= hi)
		{
		int const mid = (lo + hi) >> 1;
		int const y = v[mid];
		if (x < y)
			hi = mid - 1;
		else if (x > y)
			lo = mid + 1;
		else
			return mid;
		}
	return ~lo;
	}


//-----------------------------------------------------------------------------
// lsearch:using:data:
//		Linear search with hook for user-defined comparison.
//-----------------------------------------------------------------------------
- (int)lsearch:(int)x using:(MiscIntListCompareFunc)func data:(void*)data
	{
	if (func == 0) func = std_cmp;
	int const* const v = [self rawData];
	int const N = (int) [self count];
	for (int i = 0; i < N; i++)
		if ((*func)( data, x, v[i] ) == 0)
			return i;
	return -1;
	}


//-----------------------------------------------------------------------------
// lsearch:
//-----------------------------------------------------------------------------
- (int)lsearch:(int)x
	{
	int const* const v = [self rawData];
	int const N = (int) [self count];
	for (int i = 0; i < N; i++)
		if (x == v[i])
			return i;
	return -1;
	}


//-----------------------------------------------------------------------------
// init
//-----------------------------------------------------------------------------
- (id)init
	{
	[super init];
	array = [[Storage allocFromZone:[self zone]]
				initCount:0 elementSize:sizeof(int) description:"i"];
	return self;
	}


//-----------------------------------------------------------------------------
// initFromString:
//-----------------------------------------------------------------------------
- (id)initFromString:(char const*)s
	{
	[self init];
	[self readFromString:s];
	return self;
	}


//-----------------------------------------------------------------------------
// free
//-----------------------------------------------------------------------------
- (id)free
	{
	[array free];
	return [super free];
	}


//-----------------------------------------------------------------------------
// copyFromZone:
//-----------------------------------------------------------------------------
- (id)copyFromZone:(NXZone*)zone
	{
	MiscIntList* clone = [super copyFromZone:zone];
	clone->array = [array copyFromZone:zone];
	return clone;
	}


//-----------------------------------------------------------------------------
// empty
//-----------------------------------------------------------------------------
- (id)empty
	{
	[array empty];
	return self;
	}


//-----------------------------------------------------------------------------
// count
//-----------------------------------------------------------------------------
- (unsigned int)count
	{
	return [array count];
	}


//-----------------------------------------------------------------------------
// intAt:
//-----------------------------------------------------------------------------
- (int)intAt:(unsigned int)pos
	{
	return (pos < [self count] ? (*(int*)[array elementAt:pos]) : 0);
	}


//-----------------------------------------------------------------------------
// addInt:
//-----------------------------------------------------------------------------
- (void)addInt:(int)value
	{
	[self insertInt:value at:[self count]];
	}


//-----------------------------------------------------------------------------
// addIntList:
//-----------------------------------------------------------------------------
- (void)addIntList:(MiscIntList*)list
	{
	if (list != 0)
		{
		unsigned int const lim = [list count];
		for (unsigned int i = 0; i < lim; i++)
			[self addInt:[list intAt:i]];
		}
	}


//-----------------------------------------------------------------------------
// insertInt:at:
//-----------------------------------------------------------------------------
- (void)insertInt:(int)value at:(unsigned int)pos
	{
	[array insertElement:&value at:pos];
	}


//-----------------------------------------------------------------------------
// removeIntAt:
//-----------------------------------------------------------------------------
- (void)removeIntAt:(unsigned int)pos
	{
	[array removeElementAt:pos];
	}


//-----------------------------------------------------------------------------
// replaceIntAt:with:
//-----------------------------------------------------------------------------
- (void)replaceIntAt:(unsigned int)pos with:(int)value
	{
	[array replaceElementAt:pos with:&value];
	}


//-----------------------------------------------------------------------------
// append_char
//-----------------------------------------------------------------------------
static void append_char( char c, char*& buff, int& buff_size, 
						int& len, BOOL can_expand )
	{
	if (buff != 0)
		{
		if (len >= buff_size)
			if (!can_expand)
				buff = 0;
			else
				{
				buff_size <<= 1;		// Double the size.
				buff = (char*) realloc( buff, buff_size );
				}
		if (buff != 0)
			buff[ len++ ] = c;
		}
	}


//-----------------------------------------------------------------------------
// append_int
//-----------------------------------------------------------------------------
static void append_int( int x, char*& buff, int& buff_size, 
						int& len, BOOL can_expand )
	{
	char tmp[ 64 ];
	sprintf( tmp, "%d", x );
	for (char const* t = tmp;  *t != 0 && buff != 0;  t++)
		append_char( *t, buff, buff_size, len, can_expand );
	}


//-----------------------------------------------------------------------------
// - writeToString:size:canExpand:
//-----------------------------------------------------------------------------
- (char*)writeToString:(char*)buff size:(int)buff_size
	canExpand:(BOOL)can_expand
	{
	int const START_SIZE = 32;
	int i,x,len;
	int const lim = [self count];

	if ((buff == 0 || buff_size == 0) && can_expand)
		{
		buff = (char*) malloc( START_SIZE );
		buff_size = START_SIZE;
		}

	if (buff_size == 0)
		buff = 0;

	len = 0;
	for (i = 0;	 buff != 0 && i < lim;	i++)
		{
		x = [self intAt:i];
		if (i > 0)
			append_char( ' ', buff, buff_size, len, can_expand );
		append_int( x, buff, buff_size, len, can_expand );
		}

	append_char( '\0', buff, buff_size, len, can_expand );

	return buff;
	}


//-----------------------------------------------------------------------------
// - writeToString:size:
//-----------------------------------------------------------------------------
- (char*)writeToString:(char*)buff size:(int)buff_size
	{
	return [self writeToString:buff size:buff_size canExpand:NO];
	}


//-----------------------------------------------------------------------------
// writeToString
//-----------------------------------------------------------------------------
- (char*)writeToString
	{
	return [self writeToString:0 size:0 canExpand:YES];
	}


//-----------------------------------------------------------------------------
// readFromString:
//-----------------------------------------------------------------------------
- (int)readFromString:(char const*)s
	{
	[self empty];
	if (s != 0)
		{
		while (*s != 0)
			{
			while (*s != 0 && *s != '-' && (*s < '0' || '9' < *s))
				s++;

			BOOL is_neg = NO;
			if (*s == '-')
				{
				is_neg = YES;
				s++;
				}

			if ('0' <= *s && *s <= '9')
				{
				int x = 0;
				do	{
					x = x * 10 + *s - '0';
					s++;
					}
				while ('0' <= *s && *s <= '9');
				[self addInt:(is_neg ? -x : x)];
				}
			}
		}
	return [self count];
	}


//-----------------------------------------------------------------------------
// rawData
//-----------------------------------------------------------------------------
- (int const*)rawData
	{
	if ([self count] == 0)
		return 0;
	return (int const*) [array elementAt:0];
	}

@end
