/* -------------------------------------------------------------------
#import <objc/List.h>
	RDR, Inc. 

	Objective-C source file for the class List-Ordered

	COPYRIGHT (C), 1991, RDR, Inc.
	ALL RIGHTS RESERVED.

	Responsible:			Approved:
	RDR:Ernest Prabhakar		

	Date:				Rev:
	1991-Jun-28			___

                             List-Ordered                             





	1. Introduction
	This Category adds behavior not supplied in the standard list.
	That includes sorting, searching, and other things that rely on
	knowing the properties of the object - e.g, a Card.

	To be searched, objects must implement 'findSTR:' - or, even better,
	'findSTR:dir:'
	To be sorted, objects must implement 'rankRelativeTo:'

	2. Revision History

	___	The starting point.	Ernest Prabhakar/1991-Jun-28


	3. Source Code

------------------------------------------------------------------- */

/* ------------------------- Import files ------------------------- */
#import <appkit/nextstd.h>
#import <limits.h>
#import <regex.h>

/* ------------------------  Classes used  ------------------------ */
#import "Card.h"
#import "Random.h"

#import <appkit/Panel.h>

/* --------------------------  Defines  --------------------------- */

#define ZAlloc(Class)  [Class allocFromZone:[self zone]]
#define copyIds(From, To, N) bcopy(From, To, sizeof(id) * N)

/* ----------------------  Class variables  ----------------------- */
static Random *ranGen;		/* returns a random number */

/* --------------------  Auxiliary Functions  --------------------- */

static int qcomp(const void *a, const void *b)
{
    return[*(id*)a compare:*(id*)b];
}

BOOL regexString(const char *expr)
{
    char *result = re_comp((char *)expr);
    return (result) ?  NO :  YES;
}

static void mixup(id *from, id *to, int n)
{
    int i;
    id *toIndex = to + n;	/* Fill in Backwards */
    id *toStop = to + (n-- / 5);	/* Mix 80% of indices */
	while (toIndex > toStop) {	/* Pull in at Random */
	while (from[i = [ranGen randMax:n]] == nil);
	*(--toIndex) = from[i];
	from[i] = nil;
    }
    --from;
    while (toIndex > to) {	/* Get rest */
	while (*(++from) == nil);
	*(--toIndex) = *from;
    }
}

/* -------------------------  Constants  -------------------------- */

/*====================================================================
                 Implementation of class List-Ordered                 
====================================================================*/
#import "List-Ordered.h"

@implementation List (Ordered)

#ifndef BUGGY
/*====================================================================
                          Import and Export                           
====================================================================*/

/*--------------------------------------------------------------------
|-importFrom:(NXStream *)stream| 
Import data using the "Card" object.
Expects tab seperated, newline delimited like NXTabular.
Returns self.
                                          Ernest Prabhakar/1991-Jul-01
--------------------------------------------------------------------*/
-importFrom:(NXStream *)stream
{
    id card=nil;
    id next;

    do {
	card = [ZAlloc(Card) initCount:0];
	next = [card importFrom:stream];
	if ([card count]) {
	    [self addObject:card];
	} else {
	    [card free];
	}
    } while (next);
    
    return self;
}

/*--------------------------------------------------------------------
|-exportTo:(NXStream *)stream| 
If cards can export, it writes them out in order.
Returns self.
                                          Ernest Prabhakar/1991-Jul-01
--------------------------------------------------------------------*/
-exportTo:(NXStream *)stream
{
    id *dataIndex = dataPtr;
    id *dataEnd = dataPtr + numElements;

    if (![*dataIndex respondsTo:@selector(exportTo:)]) return nil;

    while (dataIndex < dataEnd)
	[*dataIndex++ exportTo:stream];

    return self;
}

/*====================================================================
                          Dispense Objects                            
====================================================================*/

/*--------------------------------------------------------------------
|-next| 					Returns object at top.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-next
{
    return [self removeObjectAt:0];
}

/*--------------------------------------------------------------------
|-emptyTo:(List *)aList| 		      Give all to another List
End up empty.
Returns self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-emptyTo:(List *)aList
{
    id card;
    while (card = [self next])
	[aList addObject:card];
    return self;
}

/*--------------------------------------------------------------------
|-(unsigned)dealTo:(List *) handList| 
Deal contents out equally to all the contents of handList.
Returns number of cards remaining.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-(unsigned)dealTo:(List *) handList
{
    return[self dealTo:handList each:numElements];
}

/*--------------------------------------------------------------------
|-(unsigned)dealTo:(List *) handList each:(int)numCards| 
Deal numCards (or largest equal number) to each item in list.
Returns remaining cards.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-(unsigned)dealTo:(List *) handList each:(int)numCards
{
    int hands = [handList count];
    int c, h;
    if (hands * numCards > numElements)
	numCards = numElements / hands;

    for (c = 0; c < numCards; c++)
	for (h = 0; h < hands; h++)
	    [NX_ADDRESS(handList)[h] addObject:[self next]];

    return numElements;
}

/*====================================================================
                           Manipulate List                            
====================================================================*/

/*--------------------------------------------------------------------
|-cutAt:(unsigned)index| 			    Cut List at index.
Returns nil if out of bounds, otherwise self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-cutAt:(unsigned)index
{
    id *copyPtr;

    if ((!index) || (index > numElements)) return nil;
    NX_MALLOC(copyPtr, id, numElements);
    copyIds(dataPtr, copyPtr, numElements);

    copyIds(copyPtr + index, dataPtr, numElements - index);
    copyIds(copyPtr, dataPtr + (numElements - index), index);

    NX_FREE(copyPtr);
    return self;
}


/*--------------------------------------------------------------------
|-shuffle| 					Randomly Shuffle List.
Returns self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-shuffle
{
    id *copyPtr;
    if (!ranGen) ranGen = [ZAlloc(Random) init];
    NX_MALLOC(copyPtr, id, numElements);
    mixup(dataPtr, copyPtr, numElements);
    mixup(copyPtr, dataPtr, numElements);
    NX_FREE(copyPtr);
    return self;
}

/*--------------------------------------------------------------------
|-sort| 		      Sort using the 'rankRelativeTo:' method.
Returns self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-sort
{
    if (numElements && [*dataPtr respondsTo:@selector(compare:)]) {
	qsort((void *)dataPtr, numElements, sizeof(id), qcomp);
	return self;
    }
    return nil;
}

/*--------------------------------------------------------------------
|-reverse| 		     Reverse the order of Objects in the List.
Returns self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-reverse
{
    id         *copyPtr, *copyIndex;
    id         *dataIndex;

    NX_MALLOC(copyPtr, id, numElements);
    copyIds(dataPtr, copyPtr, numElements);

    dataIndex = dataPtr + numElements;	/* Fill in Backwards */
    copyIndex = copyPtr;

    while (dataIndex > dataPtr)	/* Get rest */
	*(--dataIndex) = *(copyIndex++);

    NX_FREE(copyPtr);
    return self;
}

/*====================================================================
                            Find a String                             
====================================================================*/

/*--------------------------------------------------------------------
|-findSTR:(const char *) aString| 
Find the first object containg this string.
Can use any regular expression.
The object must recognize 'findSTR:' itself.
Returns object, if any, else nil.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-findSTR:(const char *) aString
{
    return [self findSTR:aString dir:0];
}

/*--------------------------------------------------------------------
|-findSTR:(const char *) aString dir:(int)flag| 
Same as 'findSTR:', but nonzero flag means reverse.
Returns self.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-findSTR:(const char *) aString dir:(int)flag
{
    id *dataIndex = dataPtr-1;
    id *dataEnd = dataPtr + numElements;

    if (!regexString(aString)) return nil;

    while (dataIndex < (dataEnd-1)) {
	if (!flag) {
	    if ([*(++dataIndex) findSTR:aString])
		return *dataIndex;
	} else {
	    if ([*(--dataEnd) findSTR:aString])
		return *dataEnd;
	}		    
    }
    return nil;
}

/*--------------------------------------------------------------------
|-findAllSTR:(const char *) aString| 
Returns all objects containing the specified string.
                                          Ernest Prabhakar/1991-Jun-28
--------------------------------------------------------------------*/
-findAllSTR:(const char *) aString
{
    id         *dataIndex, *dataEnd;
    id          list;
    dataEnd = dataPtr + numElements;
    list = [ZAlloc(List) init];
    if (regexString(aString))
	for (dataIndex = dataPtr; dataIndex < dataEnd; ++dataIndex)
	    if ([*dataIndex findSTR:aString])
		[list addObject:*dataIndex];

    if ([list count]) {
	return list;
    } else {
	[list free];
	return nil;
    }
}
#endif
@end
