//
//	MiscSortedList.m -- a List subclass with a cursor
//		Written by Doug McClure (c) 1994 by Doug McClure.
//				Version 1.0.  All rights reserved.
//
//		This notice may not be removed from this source code.
//
//	This object is included in the MiscKit by permission from the author
//	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.
//	


/*
 * $RCSfile$
 *
 * $Author$
 *
 * $Revision$
 *
 * $Date$
 *
*/

#import <misckit/MiscSortedList.h>

#define MiscSortedListVersion	100
#define PART_SIZE	5

#define SortSwitch(a,b)	\
  [super replaceObjectAt:b with:[super replaceObjectAt:a with:[self objectAt:b]]]


@interface MiscSortedList (Private)

- (unsigned int)pivotObject:anObject caseCheck:(BOOL)flag;
- setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag;
- setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag;
- setSortOrder:(int)order wait:(BOOL)waitFlag;
- sortFrom:(int)first to:(int)last;

@end


/**************************************************************/


@implementation MiscSortedList

- (int)compare:objectA to:objectB caseCheck:(BOOL)flag
{
  if ( flag && ignoreCase )
    {
      return (sortOrder * [objectA compare:objectB ignoreCase:YES]);
    }
  else
    {
      return (sortOrder * [objectA compare:objectB]);
    }
}


- (BOOL)ignoreCase
{
  return ignoreCase;
}


- insertObjectBySort:anObject
{
  int pivot;
  
  if ( !(anObject && [anObject conformsTo:@protocol(MiscCompare)]) )
    {
      return nil;
    }

  if ( ![self count] )
    {
      return [super insertObject:anObject at:[self count]];
    }

  pivot = [self pivotObject:anObject caseCheck:YES];

  if ( 0 <= [self compare:[self objectAt:pivot] to:anObject caseCheck:YES] )
    {
      return [super insertObject:anObject at:pivot];
    }

  if ( [self count] < (pivot+1) )
    {
      return [super insertObject:anObject at:[self count]];
    }

  return [super insertObject:anObject at:(pivot+1)];
}


- setIgnoreCase:(BOOL)flag
{
  return [self setIgnoreCase:flag wait:NO];
}


- setSortEnabled:(BOOL)flag
{
  return [self setSortEnabled:flag wait:NO];
}


- setSortOrder:(int)order
{
  return [self setSortOrder:order wait:NO];
}


- sort
{
  if ( !sorted )
    {
      [self sortFrom:0 to:[self count]];
      sorted = YES;
    }
  
  return self;
}


- (BOOL)sorted
{
  return sorted;
}


- (BOOL)sortEnabled
{
  return sortEnabled;
}


- (int)sortOrder
{
  return sortOrder;
}

@end


/**************************************************************/


@implementation MiscSortedList(Override)

+ initialize
{
  [MiscSortedList setVersion:MiscSortedListVersion];
  return self;
}


- addObject:anObject
{
  return [self insertObject:anObject at:[self count]];
}


- appendList:(List *)otherList
{
  int pos;
  int listSize = [otherList count];
  
  for ( pos = 0 ; pos < listSize ; pos++ )
    {
      if ( ![[otherList objectAt:pos] conformsTo:@protocol(MiscCompare)] )
	{
	  return nil;
	}
    }
  
  return [super appendList:otherList];
}


- copyFromZone:(NXZone *)zone
{
  id copy = [super copyFromZone:zone];

  [copy setIgnoreCase:ignoreCase wait:YES];
  [copy setSortOrder:sortOrder wait:YES];
  [copy setSortEnabled:sortEnabled wait:YES];

  return copy;
}


- (unsigned int)indexOf:anObject
{
  int pivot;

  if ( !sorted )
    {
      return [super indexOf:anObject];
    }
      
  pivot = [self pivotObject:anObject caseCheck:NO];

  if ( anObject == [self objectAt:pivot] )
    {
      return pivot;
    }
  
  return NX_NOT_IN_LIST;
}


- initCount:(unsigned int)numSlots
{
  [super initCount:numSlots];
  ignoreCase = NO;
  sorted = YES;
  sortOrder = Misc_ASCENDING;
  sortEnabled = YES;

  return self;
}


- insertObject:anObject at:(unsigned int)index
{
  if ( sortEnabled )
    {
      return [self insertObjectBySort:anObject];
    }
  
  sorted = NO;
  return [super insertObject:anObject at:index];
}


- read:(NXTypedStream *)stream
{
  [super read:stream];
  NXReadTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  return self;
}


- replaceObject:anObject with:newObject
{
  int index;
  
  if ( !anObject && ((index = [self indexOf:anObject]) != NX_NOT_IN_LIST) )
    {
      return [self replaceObjectAt:index with:newObject];
    }

  return nil;
}

  
- replaceObjectAt:(unsigned int)index with:newObject
{
  id oldObject;
  
  if (!newObject || (index > [self count]) || ![newObject conformsTo:@protocol(MiscCompare)] )
    {
      return nil;
    }

  if ( sortEnabled )
    {
      if ((oldObject = [self removeObjectAt:index]))
	{
	  return nil;
	}

      [self insertObjectBySort:newObject];
      return oldObject;
    }
  
  return [super replaceObjectAt:index with:newObject];
}


- write:(NXTypedStream *)stream
{
  [super write:stream];
  NXWriteTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  return self;
}

@end


/**************************************************************/


@implementation MiscSortedList(Private)

- (unsigned int)pivotObject:anObject caseCheck:(BOOL)flag
{
  int compare;
  int top = 0;
  int bottom = [self count] - 1;
  int pivot = 0;

  while ( top <= bottom )
    {
      pivot = (int)((top + bottom) / 2);
      compare = [self compare:[self objectAt:pivot] to:anObject caseCheck:flag];

      if ( compare > 0 )
	{
	  bottom = pivot - 1;
	}
      else if ( compare < 0 )
	{
	  top = pivot + 1;
	}
      else
	{
	  break;
	}
    }

  return pivot;
}


- setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag
{
  if ( caseFlag != ignoreCase )
    {
      ignoreCase = caseFlag;

      if ( !waitFlag )
	{
	  [self sort];
	}
    }

  return self;
}  


- setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag
{
  if ( sortFlag != sortEnabled )
    {
      sortEnabled = sortFlag;

      if ( !(waitFlag || sorted) )
	{
	  [self sort];
	}
    }

  return self;
}


- setSortOrder:(int)order wait:(BOOL)waitFlag
{
  int listSize, pos;
  
  if ( ((order != Misc_ASCENDING) && (order != Misc_DESCENDING)) || (sortOrder == order) )
    {
      return self;
    }

  sortOrder = order;

  if ( sortEnabled && !waitFlag )
    {
      if ( sorted )
	{
	  listSize = [self count] - 1;
	  
	  for ( pos = 0 ; pos < listSize ; pos++ )
	    {
	      [super insertObject:[self removeLastObject] at:pos];
	    }
	}
      else
	{
	  [self sort];
	}
    }
  
  return self;
}


- sortFrom:(int)first to:(int)last
{
  id x, a;
  int split, unknown;
  int i, j, low;

  if ( (last-first) >= PART_SIZE )
    {
      x = [self objectAt:first];
      split = first;
  
      for ( unknown = (first+1) ; unknown < last ; unknown++ )
	{
	  if ( 0 < [self compare:x to:[self objectAt:unknown] caseCheck:YES] )
	    {
	      split++;
	      SortSwitch(split, unknown);
	    }
	}
      
      SortSwitch(first, split);
      [self sortFrom:first to:split];
      [self sortFrom:(split+1) to:last];
    }
  else
    {
      for ( i = first ; i < last ; i++ )
	{
	  low = i;
	  x = [self objectAt:low];
	  
	  for ( j = (i+1) ; j <= last ; j++ )
	    {
	      a = [self objectAt:j];

	      if ( 0 < [self compare:x to:a caseCheck:YES] )
		{
		  low = j;
		  x = a;
		}
	    }
	  
	  SortSwitch(i,low);
	}
    }

  return self;
}

@end
