home *** CD-ROM | disk | FTP | other *** search
/ Nebula / nebula.bin / SourceCode / Classes / SortedList / SortedList.m < prev    next >
Text File  |  1992-03-09  |  19KB  |  613 lines
  1.  
  2. /*###########################################################
  3.     Written by Don McGregor  Version 1.0, Feb 1992.
  4.  
  5.     This code is free for any use.  GNU copyleft
  6.     rules apply.  This code has no warrantability
  7.     of fitness for a particular use, I am not 
  8.     responsible for any damage to data that might
  9.     be caused by bugs, etc, etc. 
  10.     
  11.     I encourage others to examine and improve on this
  12.     code, and to post the improvements to the net.
  13.     
  14.     Don McGregor, mcgregdr@conan.ie.orst.edu (for now).
  15.  
  16.  ###########################################################*/
  17.  
  18. #import "SortedList.h"
  19.  
  20. @implementation SortedList
  21.  
  22. + initialize
  23. {
  24.   /*-----------------------------------------------------------
  25.       Sets the class version; useful for unarchiving several
  26.       older versions of the object as time improves it.
  27.   -----------------------------------------------------------*/
  28.   
  29.   [SortedList setVersion:CURRENT_SORTED_LIST_VERSION];
  30.   
  31.   return self;
  32. }
  33.  
  34. - initCount:(unsigned int)numSlots
  35. {
  36.   /*-----------------------------------------------------------
  37.       Initialize the data and internal structures.  This should
  38.       not be used to reinitialize an already alloc'd and init'd
  39.       instance; instead, free the list first and then create
  40.       a new one.
  41.       
  42.       This is the designated initializer for the class.
  43.     -----------------------------------------------------------*/
  44.     
  45.     [super initCount:numSlots];
  46.                     
  47.     sortOrder         = ASCENDING;
  48.     caseSensitive     = YES;
  49.     keyDataType        = -1;        //causes error if not set
  50.                         //to something else
  51.       
  52.     return self;
  53. }
  54.  
  55. - setKeyMethod:(SEL)theMethod
  56. {
  57.   /*-----------------------------------------------------------
  58.       set the method used to sort the key by.  This uses the SEL to 
  59.       do that, so the user can set an arbitrary method by which
  60.       to sort, rather than forcing a particular method name to be
  61.       used on the objects that make up the sortedList.
  62.       
  63.       This also checks to make sure all the objects currently in
  64.       the list can respond to the message.  If any object can't,
  65.       nil is returned instead of self.  (The key method is still
  66.       reset, though.)  
  67.       
  68.       if the accessor method is new the SortedList is also completely
  69.        resorted when this method is called.  Since there is a new 
  70.       accessor method, the list order might be completely different.
  71.     -----------------------------------------------------------*/
  72.    int    i, listSize;
  73.    BOOL    uhOh     = NO;
  74.  
  75.    if(keyMethod != theMethod)
  76.      {
  77.        keyMethod = theMethod;
  78.    
  79.        listSize = [self count];  //Could have just directly gotten inst. var...
  80.    
  81.        for(i = 0; i < listSize; i++)
  82.            {
  83.                if(!([[self objectAt:i] respondsTo:keyMethod]))
  84.              uhOh = YES;
  85.            }
  86.      
  87.        if(uhOh == YES)        //Return nil, punt on trying to reorder list
  88.          return nil;
  89.      
  90.        [self insertionSort];      //new accessor method, new order too.        
  91.    }
  92.    
  93.    return self;
  94. }
  95.  
  96. - (SEL)keyMethod
  97. {
  98.   /*-----------------------------------------------------------
  99.       Returns the method by which the sortedList finds the
  100.       key the list is sorted by.
  101.     -----------------------------------------------------------*/
  102.  
  103.    return keyMethod;
  104. }
  105.  
  106. - setSortOrder:(int)theSortOrder
  107. {
  108.   /*-----------------------------------------------------------
  109.       Just sets the way in which the sortedList is maintained,
  110.       either ascending order (1,2,3,4...) or descending (5,4,3,2,1).
  111.       
  112.       Also resorts the list if this is a change from the prior
  113.       sort order.  This can be done by simply reversing the order
  114.       of the list; no fancy sorts needed.  This does it by removing
  115.       the top object and putting it at the end size times.
  116.       
  117.       Can't use addObject: in the for loop, even though it looks
  118.       like a good place for it; that method calls insertObject:at:
  119.       internally and sends the message to self.  that blows up 
  120.       when the message gets sent to this object.
  121.     -----------------------------------------------------------*/
  122.     int    i, size;
  123.     id    tempObj;
  124.     
  125.     if(sortOrder != theSortOrder)
  126.         {
  127.             sortOrder = theSortOrder;
  128.         size = [self count];
  129.         
  130.         for(i = 0; i < size; i++)
  131.           {
  132.               tempObj = [self removeObjectAt:0];
  133.             [super insertObject:tempObj at:(size - 1)];
  134.           }
  135.     }
  136.     
  137.     return self;
  138. }
  139.  
  140. - (int)sortOrder
  141. {
  142.   /*-----------------------------------------------------------
  143.       Returns the sort order.
  144.   -----------------------------------------------------------*/
  145.   
  146.   return sortOrder;
  147. }
  148.  
  149. -setCaseSensitive:(BOOL)isIt
  150. {
  151.   /*-----------------------------------------------------------
  152.      Whether or not compares on strings are case sensitive
  153.   -----------------------------------------------------------*/
  154.   
  155.   caseSensitive = isIt;
  156.   
  157.   return self;
  158. }
  159.  
  160. - (BOOL)caseSensitive
  161. {
  162.   return caseSensitive;
  163. }
  164.  
  165.  
  166. - setKeyDataType:(int)theKeyDataType
  167. {
  168.   /*-----------------------------------------------------------
  169.       sets a flag that tells of the type of data contained the
  170.       list is sorted by.  Right now this is  DOUBLE, FLOAT, INT, 
  171.       or ATOM (NXAtoms, the NeXT version of strings).
  172.     -----------------------------------------------------------*/
  173.     
  174.     keyDataType = theKeyDataType;
  175.     
  176.     return self;
  177. }
  178.  
  179. - (int)keyDataType
  180. {
  181.   /*-----------------------------------------------------------
  182.      Returns the type of data the list is sorted by.
  183.   -----------------------------------------------------------*/
  184.   
  185.   return keyDataType;
  186. }
  187.  
  188. - printKeyValues
  189. {
  190.   /*-----------------------------------------------------------
  191.       Prints out the key values of the objects in the sortedList,
  192.       in the order they are stored in the list.  This is really
  193.       just an internal debugging sort of thing, but most people
  194.       wind up using something like this sooner or later.
  195.       
  196.       This method should not be called in any production code.
  197.   -----------------------------------------------------------*/
  198.   
  199.   int    count, i;
  200.   id    listObject;
  201.   
  202.   printf("---------------\n");
  203.   count = [self count];
  204.   
  205.   for(i = 0; i < count; i++)
  206.     {
  207.   
  208.       listObject = [self objectAt:i];
  209.     
  210.       switch(keyDataType)
  211.             {
  212.                   case DOUBLE:    
  213.                          printf("%d: %g, for object %d\n", i, 
  214.                       ((double(*)())[listObject methodFor:keyMethod])(), listObject);
  215.                      break;
  216.             case FLOAT:    
  217.                          printf("%d: %g, for object %d\n", i, 
  218.                       ((float(*)())[listObject methodFor:keyMethod])(), listObject);
  219.                      break;
  220.             case INT:    
  221.                          printf("%d: %d, for object %d\n", i, 
  222.                       ((int(*)())[listObject methodFor:keyMethod])(), listObject);
  223.                      break;
  224.  
  225.                   
  226.             case ATOM:         printf("%d: %s, for object %d\n", i,
  227.                          [[self objectAt:i]
  228.                              perform:keyMethod], listObject);
  229.                      break;
  230.                      
  231.             default:         [self error:"attempt print contents of SortedList when the key value of object is of unknown type"];
  232.                          break;
  233.         }
  234.         
  235.    }
  236.    
  237.  printf("---------------\n");
  238.  
  239.  
  240.  return self;
  241. }
  242.  
  243.  
  244. - addObject:anObject
  245. {
  246.   /*-----------------------------------------------------------
  247.      Adds an object to the sortedList.  Uses a binary search to
  248.      find the insert point.
  249.      
  250.      By convention, the "top" of the list is at 0, and the "bottom"
  251.      of the list is at the last slot.  Conceptually this is a 
  252.      top-to bottom arrangement, a convention followed in naming
  253.      the variables here.
  254.      
  255.      If the object does not respond to the accessor method, we
  256.      should catch it here and punt big-time.
  257.    -----------------------------------------------------------*/
  258.    
  259.    int    topPtr = 0, bottomPtr, pivot;
  260.    int    compareResult;
  261.    
  262.    bottomPtr     = [self count] - 1;
  263.    pivot     = (int)((topPtr + bottomPtr)/2);
  264.    
  265.        //Make sure the new object can respond to the accessor
  266.        //method.
  267.     
  268.    if(!([anObject respondsTo:keyMethod]))
  269.       {
  270.        [self error:"attempt to add object to SortedList without correct accesor method.  The object was of Class %s\n", [anObject name]];
  271.         return nil;
  272.       }
  273.  
  274.        //empty list; insert and get out of here
  275.     
  276.    if(bottomPtr == -1)    
  277.      {
  278.        [super insertObject:anObject at:0];
  279.        return self;
  280.      }  
  281.    
  282.    
  283.        //The real interest.  Do a binary search until the insertion pt
  284.     //is found.
  285.     
  286.    compareResult = [self compare:[self objectAt:pivot] to:anObject];
  287.  
  288.    do
  289.      {      
  290.        if(compareResult > 0)
  291.                   bottomPtr     = pivot - 1;
  292.          else
  293.             topPtr     = pivot + 1;
  294.             
  295.        pivot = (int)((topPtr + bottomPtr)/2);
  296.     compareResult = [self compare:[self objectAt:pivot] to:anObject];
  297.      }
  298.    while ((compareResult != 0) && (topPtr < bottomPtr));
  299.    
  300.        //Insert the new object
  301.     
  302.    if(compareResult >= 0)
  303.       [super insertObject:anObject at:pivot];
  304.      else 
  305.          [super insertObject:anObject at:pivot+1];
  306.  
  307.   return self;
  308. }
  309.  
  310. - addObjectIfAbsent:anObject
  311. {
  312.   /*-----------------------------------------------------------
  313.      More overrides of List methods.  We need to make sure all additions
  314.      are done through the addObject: method to ensure it all stays
  315.      sorted.
  316.   -----------------------------------------------------------*/
  317.   
  318.  if([self indexOf:anObject] == NX_NOT_IN_LIST)
  319.      {
  320.        [self addObject:anObject];
  321.      }
  322.  return self;
  323. }
  324.  
  325. - (BOOL)isEqual:anObject
  326. {
  327.   /*-----------------------------------------------------------
  328.      Similar to the list op,which compares the to lists for equality.
  329.      We also need to check for the new instance vars declared
  330.      in this object, and make sure this is a SortedList rather
  331.      than just a List.
  332.   -----------------------------------------------------------*/
  333.   
  334.   if([self class] != [anObject class])
  335.      return NO;
  336.   
  337.   if(([anObject sortOrder]     != [self sortOrder])      ||
  338.      ([anObject keyMethod]     != [self keyMethod])      ||
  339.      ([anObject caseSensitive]     != [self caseSensitive]) ||
  340.      ([anObject keyDataType]     != [self keyDataType]))
  341.         return NO;
  342.  
  343.    return [super isEqual:anObject];
  344. }
  345.   
  346.  
  347.  
  348.  
  349.  
  350. - (int)compare:thisObject to:thatObject
  351. {
  352.   /*-----------------------------------------------------------
  353.      Compares the values of the keys of thisObject and thatObject.
  354.      
  355.      returns a number larger than zero if the first object's key is 
  356.      larger than the other object's, a number smaller than zero if  
  357.      the first object is less than the second, and zero if they have 
  358.      the same key values.  For complex sorts, "larger" means that it
  359.      comes after the object when sorted in ascending order.
  360.      
  361.      This can deal with ints, doubles, floats, and atoms at this point.
  362.      Feel free to expand it to other types.   
  363.      
  364.      There is a built-in capability to expand this to other comparision
  365.      (sorting) operations, perhaps with complex structs or multiple
  366.      keys.  If the return type is not one of the pre-defined (and fairly
  367.      common) types such as int, double, or atom, the program
  368.      sends the SEL message to thisObject with an argument of thatObject.
  369.      The OBJECTS IN THE LIST should respond to this message and return
  370.      the results of a comparision operation.  Eg,
  371.      
  372.      result = [thisObject compareTo:thatObject];
  373.      return result;
  374.      
  375.      where the compareTo: method takes the other object as an arg,
  376.      and does the possibly complex comparision.  If thisObject is
  377.      "greater" than thatObject, by whatever criterion, the method
  378.      should return an int greater than zero.  If thisObject is "less"
  379.      than thatObject, it should return a negative integer, and if the
  380.      two are equal zero should be returned.
  381.      
  382.      The ATOM type is case sensitive by default.  The default string
  383.      ordering table is used.  You should be using NXUniqueString to to
  384.      the atoms before passing them in, and the should be null-terminated.
  385.      
  386.     -----------------------------------------------------------*/
  387.    
  388.        //protos for ptr to function that returns a <type> and takes the usual
  389.     //objc parameters: an id and a SEL.
  390.    typedef    double (*keyValueFunctionDouble)(id, SEL);
  391.    typedef    int    (*keyValueFunctionInt)(id, SEL);
  392.    typedef    NXAtom (*keyValueFunctionAtom)(id, SEL);
  393.    typedef    float  (*keyValueFunctionFloat)(id, SEL);
  394.    
  395.        //pointer to key value function for each of the objects passed in.
  396.     //A function pointer for each type that the sortedList can hold.
  397.         
  398.    keyValueFunctionDouble    thisObjectKeyFunctionDouble, 
  399.                    thatObjectKeyFunctionDouble;
  400.                 
  401.    keyValueFunctionInt        thisObjectKeyFunctionInt, 
  402.                    thatObjectKeyFunctionInt;
  403.                                 
  404.    keyValueFunctionFloat    thisObjectKeyFunctionFloat, 
  405.                    thatObjectKeyFunctionFloat;                                
  406.             
  407.    double        compareResults;        //difference between two numerics
  408.    int            orderFlag;
  409.    
  410.    
  411.        //This can be either ascending or descending.  To do with compares we'll
  412.     //just use a flag, -1 or 1, and multiply that by the integer result.
  413.     //that'll flip the comparision results depending on asc or desc.
  414.     
  415.    orderFlag = (sortOrder == ASCENDING) ? 1 : -1;
  416.       
  417.    switch(keyDataType)
  418.      {
  419.          case DOUBLE:    
  420.              thisObjectKeyFunctionDouble = (keyValueFunctionDouble)[thisObject methodFor:keyMethod];
  421.                thatObjectKeyFunctionDouble = (keyValueFunctionDouble)[thatObject methodFor:keyMethod];
  422.      
  423.              compareResults =    ( thisObjectKeyFunctionDouble(thisObject, keyMethod) -
  424.                               thatObjectKeyFunctionDouble(thatObject, keyMethod));
  425.             
  426.                 //return -1, 0, or 1.
  427.             if(compareResults < 0) return orderFlag * (-1);
  428.             if(compareResults > 0) return orderFlag * 1;
  429.             return 0;
  430.             
  431.             break;
  432.             
  433.      case FLOAT:    
  434.              thisObjectKeyFunctionFloat = (keyValueFunctionFloat)[thisObject methodFor:keyMethod];
  435.                thatObjectKeyFunctionFloat = (keyValueFunctionFloat)[thatObject methodFor:keyMethod];
  436.              compareResults =    (double)( thisObjectKeyFunctionFloat(thisObject, keyMethod) -
  437.                               thatObjectKeyFunctionFloat(thatObject, keyMethod));
  438.             
  439.                 //return -1, 0, or 1.
  440.             if(compareResults < 0) return orderFlag * (-1);
  441.             if(compareResults > 0) return orderFlag * 1;
  442.             return 0;
  443.             
  444.             break;
  445.  
  446.     case INT:    
  447.              thisObjectKeyFunctionInt = (keyValueFunctionInt)[thisObject methodFor:keyMethod];
  448.                thatObjectKeyFunctionInt = (keyValueFunctionInt)[thatObject methodFor:keyMethod];
  449.      
  450.              compareResults =    (double)( thisObjectKeyFunctionInt(thisObject, keyMethod) -
  451.                               thatObjectKeyFunctionInt(thatObject, keyMethod));
  452.             
  453.                 //return -1, 0, or 1.
  454.             if(compareResults < 0) return orderFlag * (-1);
  455.             if(compareResults > 0) return orderFlag * 1;
  456.             return 0;
  457.             
  458.             break;
  459.             
  460.      case ATOM:    
  461.              return orderFlag * NXOrderStrings((unsigned char*)[thisObject perform:keyMethod],
  462.                            (unsigned char *)[thatObject perform:keyMethod],
  463.                           caseSensitive, -1, NULL);
  464.             break;
  465.             
  466.      case OTHER:    
  467.              return orderFlag * (int)[thisObject perform:keyMethod with:thisObject];
  468.              break;
  469.             
  470.     default:    [self error:"unspecified type of comparision operator\n"];
  471.     }
  472.     
  473.     return 0;        //foo-faw to fool the compiler; should never get here
  474. }
  475.  
  476.  
  477. - insertionSort;
  478. {
  479.   /*-----------------------------------------------------------
  480.      do a simple insertion sort.  This is good for files that
  481.      are "alomst sorted", as I suspect that many data sets
  482.      will be in this application.  Besides, it's easy to program
  483.      and I'm lazy right now :-)
  484.      
  485.      I'm sure someone can do something more sophisticated 
  486.      than this.
  487.   -----------------------------------------------------------*/
  488.   
  489.   int    i, j, dataSize, compareResult;
  490.   id    listEl;
  491.   
  492.   dataSize = [self count];
  493.   
  494.   for(i = 1; i < dataSize; i++)
  495.     {
  496.       j = i-1;
  497.       listEl = [self objectAt:i];
  498.       
  499.       while(((compareResult = [self compare:[self objectAt:j] to:listEl]) > 0) &&
  500.                         (j >=1))
  501.     j--;
  502.       
  503.       if(compareResult > 0)
  504.         {
  505.             [super removeObjectAt:i];
  506.           [super insertObject:listEl at:j];
  507.     }
  508.     
  509.    }
  510.    
  511.  return self;
  512. }
  513.         
  514.     
  515. -copy
  516. {
  517.   /*-----------------------------------------------------------
  518.      An override to keep things hunky-dory with all the instance 
  519.      vars.
  520.   -----------------------------------------------------------*/
  521.   
  522.   id    newList;
  523.   
  524.   newList = [super copy];
  525.   
  526.   [newList setKeyMethod:    [self keyMethod]];
  527.   [newList setSortOrder:    [self sortOrder]];
  528.   [newList setCaseSensitive:    [self caseSensitive]];
  529.   [newList setKeyDataType:    [self keyDataType]];
  530.   
  531.   return newList;
  532. }
  533.   
  534. -copyFromZone:(NXZone*)zone
  535. {
  536.   /*-----------------------------------------------------------
  537.       Ditto above method.
  538.   -----------------------------------------------------------*/
  539.   
  540.   id    newList;
  541.   
  542.   newList = [super copyFromZone:zone];
  543.   
  544.   [newList setKeyMethod:    [self keyMethod]];
  545.   [newList setSortOrder:    [self sortOrder]];
  546.   [newList setCaseSensitive:    [self caseSensitive]];
  547.   [newList setKeyDataType:    [self keyDataType]];
  548.   
  549.   return newList;
  550. }
  551.  
  552.  
  553. /*-----------------------------------------------------------  
  554.          Methods that return a rutime error if called 
  555.   -----------------------------------------------------------*/
  556.  
  557. - insertObject:anObject at:(unsigned int)index
  558. {
  559.   [self error:" objects should not be sent insertObject:at: messages.\n"];
  560.     
  561.   return self;    //foo-faw to keep the compiler happy 'bout return types
  562. }
  563.  
  564. - replaceObjectAt:(unsigned int)index with:newObject 
  565. {
  566.   [self error:"%s objects should not be sent replaceObjectAt:with: messages.\n"];
  567.     
  568.   return self;    //foo-faw to keep the compiler happy 'bout return types
  569.  
  570. }
  571.  
  572. - replaceObject:anObject with:newObject
  573. {
  574.   [self error:"%s objects should not be sent replaceObject:with: messages.\n"];
  575.     
  576.   return self;    //foo-faw to keep the compiler happy 'bout return types
  577.  
  578. }
  579.  
  580. /*-----------------------------------------------------------
  581.                     Archiving methods
  582. -----------------------------------------------------------*/
  583.  
  584. -write:(NXTypedStream*)stream
  585. {
  586.   /*-----------------------------------------------------------
  587.      Write out the instance variables and the superclass
  588.      object structure.
  589.   -----------------------------------------------------------*/
  590.   
  591.   [super write:stream];
  592.   NXWriteTypes(stream, "ic:i", &sortOrder, 
  593.           &caseSensitive, &keyMethod, &keyDataType);
  594.             
  595.   return self;
  596. }
  597.  
  598. - read:(NXTypedStream*)stream
  599. {
  600.   /*-----------------------------------------------------------
  601.     Read the object back in
  602.   -----------------------------------------------------------*/
  603.   
  604.   [super read:stream];
  605.   NXReadTypes(stream, "ic:i", &sortOrder, 
  606.           &caseSensitive, &keyMethod, &keyDataType);
  607.  
  608.   return self;
  609. }
  610.  
  611.   
  612. @end
  613.