//
//	MiscSortedStorage.m -- a MiscStorage which keeps the elements sorted
//		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/MiscSortedStorage.h>

#define MiscSortedStorageVersion	100
#define PART_SIZE       5


@interface MiscSortedStorage(Private)

- (unsigned int)pivotElement:(void *)anElement 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;
- sortSwitch:(int)a :(int)b;

@end


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


@implementation MiscSortedStorage

- (int)compare:(void *)elementA to:(void *)elementB caseCheck:(BOOL)flag
{
  [self subclassResponsibility:_cmd];
  return 0;
}


- (BOOL)ignoreCase
{
  return ignoreCase;
}


- insertElementBySort:(void *)anElement
{
  int pivot;
  
  if ( !anElement )
    {
      return nil;
    }
  
  if ( ![self count] )
    {
      return [super insertElement:anElement at:[self count]];
    }
  
  pivot = [self pivotElement:anElement caseCheck:YES];
  
  if ( 0 <= [self compare:[self elementAt:pivot] to:anElement caseCheck:YES] )
    {
      return [super insertElement:anElement at:pivot];
    }
  
  if ( [self count] < (pivot+1) )
    {
      return [super insertElement:anElement at:[self count]];
    }
  
  return [super insertElement:anElement at:(pivot+1)];
}


- (void *)lastElement
{
  if ( [self count] )
    {
      return [self elementAt:([self count]-1)];
    }

  return nil;
}


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

  
- setSortEnabled:(BOOL)sort
{
  return [self setSortEnabled:sort 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 MiscSortedStorage(Override)

+ initialize
{
  [MiscSortedStorage setVersion:MiscSortedStorageVersion];
  return self;
}


- addElement:(void *)anElement
{
  return [self insertElement:anElement at:[self count]];
}


- initCount:(unsigned int)count elementSize:(unsigned int)sizeInBytes description:(const char *)string
{
  [super initCount:count elementSize:sizeInBytes description:string];
  ignoreCase = NO;
  sorted = YES;
  sortOrder = Misc_ASCENDING;
  sortEnabled = YES;
  
  return self;
}


- 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;
}


- insertElement:(void *)anElement at:(unsigned int)index
{
  if ( sortEnabled )
    {
      return [self insertElementBySort:anElement];
    }

  sorted = NO;
  return [super insertElement:anElement at:index];
}


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


- replaceElementAt:(unsigned int)index with:(void *)anElement
{
  if (!anElement || (index > [self count]) )
    {
      return nil;
    }

  if ( sortEnabled )
    {
      [self removeElementAt:index];
      [self insertElementBySort:anElement];
      return self;
    }

  return [super replaceElementAt:index with:anElement];
}


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

@end  


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


@implementation MiscSortedStorage(Private)

- (unsigned int)pivotElement:(void *)anElement 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 elementAt:pivot] to:anElement 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 insertElement:[self removeLastElement] at:pos];
            }
        }
      else
        {
          [self sort];
        }
    }

  return self;
}


- sortFrom:(int)first to:(int)last
{
  void *x, *a;
  int split, unknown;
  int i, j, low;
  
  if ( (last-first) >= PART_SIZE )
    {
      x = [self elementAt:first];
      split = first;
      
      for ( unknown = (first+1) ; unknown < last ; unknown++ )
	{
	  if ( 0 < [self compare:x to:[self elementAt:unknown] caseCheck:YES] )
	    {
	      split++;
	      [self sortSwitch:split :unknown];
	    }
	}
      
      [self 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 elementAt:low];
	  
	  for ( j = (i+1) ; j <= last ; j++ )
	    {
	      a = [self elementAt:j];
	      
	      if ( 0 < [self compare:x to:a caseCheck:YES] )
		{
		  low = j;
		  x = a;
		}
	    }
	  
	  [self sortSwitch:i :low];
	}
    }
  
  return self;
}


- sortSwitch:(int)a :(int)b
{
  void *elementA = [self elementAt:a];
  void *elementB = [self elementAt:b];
  [super replaceElementAt:a with:elementB];
  [super replaceElementAt:b with:elementA];

  return self;
}

@end
