Nebula 1995 August/NEBULA.mdf/SourceCode/Classes/SortedList/SortedList.m

Text File | 1992-03-09 | 18.1 KB | 613 lines

/*###########################################################
    Written by Don McGregor  Version 1.0, Feb 1992.

    This code is free for any use.  GNU copyleft
    rules apply.  This code has no warrantability
    of fitness for a particular use, I am not
    responsible for any damage to data that might
    be caused by bugs, etc, etc.

    I encourage others to examine and improve on this
    code, and to post the improvements to the net.

    Don McGregor, [e-mail] (for now).

 ###########################################################*/

#import "SortedList.h"

@implementation SortedList

+ initialize
{
  /*-----------------------------------------------------------
      Sets the class version; useful for unarchiving several
      older versions of the object as time improves it.
  -----------------------------------------------------------*/

  [SortedList setVersion:CURRENT_SORTED_LIST_VERSION];

  return self;
}

- initCount:(unsigned int)numSlots
{
  /*-----------------------------------------------------------
      Initialize the data and internal structures.  This should
      not be used to reinitialize an already alloc'd and init'd
      instance; instead, free the list first and then create
      a new one.

      This is the designated initializer for the class.
    -----------------------------------------------------------*/

    [super initCount:numSlots];

    sortOrder         = ASCENDING;
    caseSensitive     = YES;
    keyDataType        = -1;        //causes error if not set
                        //to something else

    return self;
}

- setKeyMethod:(SEL)theMethod
{
  /*-----------------------------------------------------------
      set the method used to sort the key by.  This uses the SEL to
      do that, so the user can set an arbitrary method by which
      to sort, rather than forcing a particular method name to be
      used on the objects that make up the sortedList.

      This also checks to make sure all the objects currently in
      the list can respond to the message.  If any object can't,
      nil is returned instead of self.  (The key method is still
      reset, though.)

      if the accessor method is new the SortedList is also completely
       resorted when this method is called.  Since there is a new
      accessor method, the list order might be completely different.
    -----------------------------------------------------------*/
   int    i, listSize;
   BOOL    uhOh     = NO;

   if(keyMethod != theMethod)
     {
       keyMethod = theMethod;

       listSize = [self count];  //Could have just directly gotten inst. var...

       for(i = 0; i < listSize; i++)
           {
               if(!([[self objectAt:i] respondsTo:keyMethod]))
             uhOh = YES;
           }

       if(uhOh == YES)        //Return nil, punt on trying to reorder list
         return nil;

       [self insertionSort];      //new accessor method, new order too.
   }

   return self;
}

- (SEL)keyMethod
{
  /*-----------------------------------------------------------
      Returns the method by which the sortedList finds the
      key the list is sorted by.
    -----------------------------------------------------------*/

   return keyMethod;
}

- setSortOrder:(int)theSortOrder
{
  /*-----------------------------------------------------------
      Just sets the way in which the sortedList is maintained,
      either ascending order (1,2,3,4...) or descending (5,4,3,2,1).

      Also resorts the list if this is a change from the prior
      sort order.  This can be done by simply reversing the order
      of the list; no fancy sorts needed.  This does it by removing
      the top object and putting it at the end size times.

      Can't use addObject: in the for loop, even though it looks
      like a good place for it; that method calls insertObject:at:
      internally and sends the message to self.  that blows up
      when the message gets sent to this object.
    -----------------------------------------------------------*/
    int    i, size;
    id    tempObj;

    if(sortOrder != theSortOrder)
        {
            sortOrder = theSortOrder;
        size = [self count];

        for(i = 0; i < size; i++)
          {
              tempObj = [self removeObjectAt:0];
            [super insertObject:tempObj at:(size - 1)];
          }
    }

    return self;
}

- (int)sortOrder
{
  /*-----------------------------------------------------------
      Returns the sort order.
  -----------------------------------------------------------*/

  return sortOrder;
}

-setCaseSensitive:(BOOL)isIt
{
  /*-----------------------------------------------------------
     Whether or not compares on strings are case sensitive
  -----------------------------------------------------------*/

  caseSensitive = isIt;

  return self;
}

- (BOOL)caseSensitive
{
  return caseSensitive;
}


- setKeyDataType:(int)theKeyDataType
{
  /*-----------------------------------------------------------
      sets a flag that tells of the type of data contained the
      list is sorted by.  Right now this is  DOUBLE, FLOAT, INT,
      or ATOM (NXAtoms, the NeXT version of strings).
    -----------------------------------------------------------*/

    keyDataType = theKeyDataType;

    return self;
}

- (int)keyDataType
{
  /*-----------------------------------------------------------
     Returns the type of data the list is sorted by.
  -----------------------------------------------------------*/

  return keyDataType;
}

- printKeyValues
{
  /*-----------------------------------------------------------
      Prints out the key values of the objects in the sortedList,
      in the order they are stored in the list.  This is really
      just an internal debugging sort of thing, but most people
      wind up using something like this sooner or later.

      This method should not be called in any production code.
  -----------------------------------------------------------*/

  int    count, i;
  id    listObject;

  printf("---------------\n");
  count = [self count];

  for(i = 0; i < count; i++)
    {

      listObject = [self objectAt:i];

      switch(keyDataType)
            {
                  case DOUBLE:
                         printf("%d: %g, for object %d\n", i,
                      ((double(*)())[listObject methodFor:keyMethod])(), listObject);
                     break;
            case FLOAT:
                         printf("%d: %g, for object %d\n", i,
                      ((float(*)())[listObject methodFor:keyMethod])(), listObject);
                     break;
            case INT:
                         printf("%d: %d, for object %d\n", i,
                      ((int(*)())[listObject methodFor:keyMethod])(), listObject);
                     break;


            case ATOM:         printf("%d: %s, for object %d\n", i,
                         [[self objectAt:i]
                             perform:keyMethod], listObject);
                     break;

            default:         [self error:"attempt print contents of SortedList when the key value of object is of unknown type"];
                         break;
        }

   }

 printf("---------------\n");


 return self;
}


- addObject:anObject
{
  /*-----------------------------------------------------------
     Adds an object to the sortedList.  Uses a binary search to
     find the insert point.

     By convention, the "top" of the list is at 0, and the "bottom"
     of the list is at the last slot.  Conceptually this is a
     top-to bottom arrangement, a convention followed in naming
     the variables here.

     If the object does not respond to the accessor method, we
     should catch it here and punt big-time.
   -----------------------------------------------------------*/

   int    topPtr = 0, bottomPtr, pivot;
   int    compareResult;

   bottomPtr     = [self count] - 1;
   pivot     = (int)((topPtr + bottomPtr)/2);

       //Make sure the new object can respond to the accessor
       //method.

   if(!([anObject respondsTo:keyMethod]))
      {
       [self error:"attempt to add object to SortedList without correct accesor method.  The object was of Class %s\n", [anObject name]];
        return nil;
      }

       //empty list; insert and get out of here

   if(bottomPtr == -1)
     {
       [super insertObject:anObject at:0];
       return self;
     }


       //The real interest.  Do a binary search until the insertion pt
    //is found.

   compareResult = [self compare:[self objectAt:pivot] to:anObject];

   do
     {
       if(compareResult > 0)
                  bottomPtr     = pivot - 1;
         else
            topPtr     = pivot + 1;

       pivot = (int)((topPtr + bottomPtr)/2);
    compareResult = [self compare:[self objectAt:pivot] to:anObject];
     }
   while ((compareResult != 0) && (topPtr < bottomPtr));

       //Insert the new object

   if(compareResult >= 0)
      [super insertObject:anObject at:pivot];
     else
         [super insertObject:anObject at:pivot+1];

  return self;
}

- addObjectIfAbsent:anObject
{
  /*-----------------------------------------------------------
     More overrides of List methods.  We need to make sure all additions
     are done through the addObject: method to ensure it all stays
     sorted.
  -----------------------------------------------------------*/

 if([self indexOf:anObject] == NX_NOT_IN_LIST)
     {
       [self addObject:anObject];
     }
 return self;
}

- (BOOL)isEqual:anObject
{
  /*-----------------------------------------------------------
     Similar to the list op,which compares the to lists for equality.
     We also need to check for the new instance vars declared
     in this object, and make sure this is a SortedList rather
     than just a List.
  -----------------------------------------------------------*/

  if([self class] != [anObject class])
     return NO;

  if(([anObject sortOrder]     != [self sortOrder])      ||
     ([anObject keyMethod]     != [self keyMethod])      ||
     ([anObject caseSensitive]     != [self caseSensitive]) ||
     ([anObject keyDataType]     != [self keyDataType]))
        return NO;

   return [super isEqual:anObject];
}





- (int)compare:thisObject to:thatObject
{
  /*-----------------------------------------------------------
     Compares the values of the keys of thisObject and thatObject.

     returns a number larger than zero if the first object's key is
     larger than the other object's, a number smaller than zero if
     the first object is less than the second, and zero if they have
     the same key values.  For complex sorts, "larger" means that it
     comes after the object when sorted in ascending order.

     This can deal with ints, doubles, floats, and atoms at this point.
     Feel free to expand it to other types.

     There is a built-in capability to expand this to other comparision
     (sorting) operations, perhaps with complex structs or multiple
     keys.  If the return type is not one of the pre-defined (and fairly
     common) types such as int, double, or atom, the program
     sends the SEL message to thisObject with an argument of thatObject.
     The OBJECTS IN THE LIST should respond to this message and return
     the results of a comparision operation.  Eg,

     result = [thisObject compareTo:thatObject];
     return result;

     where the compareTo: method takes the other object as an arg,
     and does the possibly complex comparision.  If thisObject is
     "greater" than thatObject, by whatever criterion, the method
     should return an int greater than zero.  If thisObject is "less"
     than thatObject, it should return a negative integer, and if the
     two are equal zero should be returned.

     The ATOM type is case sensitive by default.  The default string
     ordering table is used.  You should be using NXUniqueString to to
     the atoms before passing them in, and the should be null-terminated.

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

       //protos for ptr to function that returns a <type> and takes the usual
    //objc parameters: an id and a SEL.
   typedef    double (*keyValueFunctionDouble)(id, SEL);
   typedef    int    (*keyValueFunctionInt)(id, SEL);
   typedef    NXAtom (*keyValueFunctionAtom)(id, SEL);
   typedef    float  (*keyValueFunctionFloat)(id, SEL);

       //pointer to key value function for each of the objects passed in.
    //A function pointer for each type that the sortedList can hold.

   keyValueFunctionDouble    thisObjectKeyFunctionDouble,
                   thatObjectKeyFunctionDouble;

   keyValueFunctionInt        thisObjectKeyFunctionInt,
                   thatObjectKeyFunctionInt;

   keyValueFunctionFloat    thisObjectKeyFunctionFloat,
                   thatObjectKeyFunctionFloat;

   double        compareResults;        //difference between two numerics
   int            orderFlag;


       //This can be either ascending or descending.  To do with compares we'll
    //just use a flag, -1 or 1, and multiply that by the integer result.
    //that'll flip the comparision results depending on asc or desc.

   orderFlag = (sortOrder == ASCENDING) ? 1 : -1;

   switch(keyDataType)
     {
         case DOUBLE:
             thisObjectKeyFunctionDouble = (keyValueFunctionDouble)[thisObject methodFor:keyMethod];
               thatObjectKeyFunctionDouble = (keyValueFunctionDouble)[thatObject methodFor:keyMethod];

             compareResults =    ( thisObjectKeyFunctionDouble(thisObject, keyMethod) -
                              thatObjectKeyFunctionDouble(thatObject, keyMethod));

                //return -1, 0, or 1.
            if(compareResults < 0) return orderFlag * (-1);
            if(compareResults > 0) return orderFlag * 1;
            return 0;

            break;

     case FLOAT:
             thisObjectKeyFunctionFloat = (keyValueFunctionFloat)[thisObject methodFor:keyMethod];
               thatObjectKeyFunctionFloat = (keyValueFunctionFloat)[thatObject methodFor:keyMethod];
             compareResults =    (double)( thisObjectKeyFunctionFloat(thisObject, keyMethod) -
                              thatObjectKeyFunctionFloat(thatObject, keyMethod));

                //return -1, 0, or 1.
            if(compareResults < 0) return orderFlag * (-1);
            if(compareResults > 0) return orderFlag * 1;
            return 0;

            break;

    case INT:
             thisObjectKeyFunctionInt = (keyValueFunctionInt)[thisObject methodFor:keyMethod];
               thatObjectKeyFunctionInt = (keyValueFunctionInt)[thatObject methodFor:keyMethod];

             compareResults =    (double)( thisObjectKeyFunctionInt(thisObject, keyMethod) -
                              thatObjectKeyFunctionInt(thatObject, keyMethod));

                //return -1, 0, or 1.
            if(compareResults < 0) return orderFlag * (-1);
            if(compareResults > 0) return orderFlag * 1;
            return 0;

            break;

     case ATOM:
             return orderFlag * NXOrderStrings((unsigned char*)[thisObject perform:keyMethod],
                           (unsigned char *)[thatObject perform:keyMethod],
                          caseSensitive, -1, NULL);
            break;

     case OTHER:
             return orderFlag * (int)[thisObject perform:keyMethod with:thisObject];
             break;

    default:    [self error:"unspecified type of comparision operator\n"];
    }

    return 0;        //foo-faw to fool the compiler; should never get here
}


- insertionSort;
{
  /*-----------------------------------------------------------
     do a simple insertion sort.  This is good for files that
     are "alomst sorted", as I suspect that many data sets
     will be in this application.  Besides, it's easy to program
     and I'm lazy right now :-)

     I'm sure someone can do something more sophisticated
     than this.
  -----------------------------------------------------------*/

  int    i, j, dataSize, compareResult;
  id    listEl;

  dataSize = [self count];

  for(i = 1; i < dataSize; i++)
    {
      j = i-1;
      listEl = [self objectAt:i];

      while(((compareResult = [self compare:[self objectAt:j] to:listEl]) > 0) &&
                        (j >=1))
    j--;

      if(compareResult > 0)
        {
            [super removeObjectAt:i];
          [super insertObject:listEl at:j];
    }

   }

 return self;
}


-copy
{
  /*-----------------------------------------------------------
     An override to keep things hunky-dory with all the instance
     vars.
  -----------------------------------------------------------*/

  id    newList;

  newList = [super copy];

  [newList setKeyMethod:    [self keyMethod]];
  [newList setSortOrder:    [self sortOrder]];
  [newList setCaseSensitive:    [self caseSensitive]];
  [newList setKeyDataType:    [self keyDataType]];

  return newList;
}

-copyFromZone:(NXZone*)zone
{
  /*-----------------------------------------------------------
      Ditto above method.
  -----------------------------------------------------------*/

  id    newList;

  newList = [super copyFromZone:zone];

  [newList setKeyMethod:    [self keyMethod]];
  [newList setSortOrder:    [self sortOrder]];
  [newList setCaseSensitive:    [self caseSensitive]];
  [newList setKeyDataType:    [self keyDataType]];

  return newList;
}


/*-----------------------------------------------------------
         Methods that return a rutime error if called
  -----------------------------------------------------------*/

- insertObject:anObject at:(unsigned int)index
{
  [self error:" objects should not be sent insertObject:at: messages.\n"];

  return self;    //foo-faw to keep the compiler happy 'bout return types
}

- replaceObjectAt:(unsigned int)index with:newObject
{
  [self error:"%s objects should not be sent replaceObjectAt:with: messages.\n"];

  return self;    //foo-faw to keep the compiler happy 'bout return types

}

- replaceObject:anObject with:newObject
{
  [self error:"%s objects should not be sent replaceObject:with: messages.\n"];

  return self;    //foo-faw to keep the compiler happy 'bout return types

}

/*-----------------------------------------------------------
                    Archiving methods
-----------------------------------------------------------*/

-write:(NXTypedStream*)stream
{
  /*-----------------------------------------------------------
     Write out the instance variables and the superclass
     object structure.
  -----------------------------------------------------------*/

  [super write:stream];
  NXWriteTypes(stream, "ic:i", &sortOrder,
          &caseSensitive, &keyMethod, &keyDataType);

  return self;
}

- read:(NXTypedStream*)stream
{
  /*-----------------------------------------------------------
    Read the object back in
  -----------------------------------------------------------*/

  [super read:stream];
  NXReadTypes(stream, "ic:i", &sortOrder,
          &caseSensitive, &keyMethod, &keyDataType);

  return self;
}


@end