home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / MiscKit / Source / MiscSortedList.m < prev    next >
Encoding:
Text File  |  1994-03-22  |  7.1 KB  |  445 lines
  1. //
  2. //    MiscSortedList.m -- a List subclass with a cursor
  3. //        Written by Doug McClure (c) 1994 by Doug McClure.
  4. //                Version 1.0.  All rights reserved.
  5. //
  6. //        This notice may not be removed from this source code.
  7. //
  8. //    This object is included in the MiscKit by permission from the author
  9. //    and its use is governed by the MiscKit license, found in the file
  10. //    "LICENSE.rtf" in the MiscKit distribution.  Please refer to that file
  11. //    for a list of all applicable permissions and restrictions.
  12. //    
  13.  
  14.  
  15. /*
  16.  * $RCSfile$
  17.  *
  18.  * $Author$
  19.  *
  20.  * $Revision$
  21.  *
  22.  * $Date$
  23.  *
  24. */
  25.  
  26. #import <misckit/MiscSortedList.h>
  27.  
  28. #define MiscSortedListVersion    100
  29. #define PART_SIZE    5
  30.  
  31. #define SortSwitch(a,b)    \
  32.   [super replaceObjectAt:b with:[super replaceObjectAt:a with:[self objectAt:b]]]
  33.  
  34.  
  35. @interface MiscSortedList (Private)
  36.  
  37. - (unsigned int)pivotObject:anObject caseCheck:(BOOL)flag;
  38. - setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag;
  39. - setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag;
  40. - setSortOrder:(int)order wait:(BOOL)waitFlag;
  41. - sortFrom:(int)first to:(int)last;
  42.  
  43. @end
  44.  
  45.  
  46. /**************************************************************/
  47.  
  48.  
  49. @implementation MiscSortedList
  50.  
  51. - (int)compare:objectA to:objectB caseCheck:(BOOL)flag
  52. {
  53.   if ( flag && ignoreCase )
  54.     {
  55.       return (sortOrder * [objectA compare:objectB ignoreCase:YES]);
  56.     }
  57.   else
  58.     {
  59.       return (sortOrder * [objectA compare:objectB]);
  60.     }
  61. }
  62.  
  63.  
  64. - (BOOL)ignoreCase
  65. {
  66.   return ignoreCase;
  67. }
  68.  
  69.  
  70. - insertObjectBySort:anObject
  71. {
  72.   int pivot;
  73.   
  74.   if ( !(anObject && [anObject conformsTo:@protocol(MiscCompare)]) )
  75.     {
  76.       return nil;
  77.     }
  78.  
  79.   if ( ![self count] )
  80.     {
  81.       return [super insertObject:anObject at:[self count]];
  82.     }
  83.  
  84.   pivot = [self pivotObject:anObject caseCheck:YES];
  85.  
  86.   if ( 0 <= [self compare:[self objectAt:pivot] to:anObject caseCheck:YES] )
  87.     {
  88.       return [super insertObject:anObject at:pivot];
  89.     }
  90.  
  91.   if ( [self count] < (pivot+1) )
  92.     {
  93.       return [super insertObject:anObject at:[self count]];
  94.     }
  95.  
  96.   return [super insertObject:anObject at:(pivot+1)];
  97. }
  98.  
  99.  
  100. - setIgnoreCase:(BOOL)flag
  101. {
  102.   return [self setIgnoreCase:flag wait:NO];
  103. }
  104.  
  105.  
  106. - setSortEnabled:(BOOL)flag
  107. {
  108.   return [self setSortEnabled:flag wait:NO];
  109. }
  110.  
  111.  
  112. - setSortOrder:(int)order
  113. {
  114.   return [self setSortOrder:order wait:NO];
  115. }
  116.  
  117.  
  118. - sort
  119. {
  120.   if ( !sorted )
  121.     {
  122.       [self sortFrom:0 to:[self count]];
  123.       sorted = YES;
  124.     }
  125.   
  126.   return self;
  127. }
  128.  
  129.  
  130. - (BOOL)sorted
  131. {
  132.   return sorted;
  133. }
  134.  
  135.  
  136. - (BOOL)sortEnabled
  137. {
  138.   return sortEnabled;
  139. }
  140.  
  141.  
  142. - (int)sortOrder
  143. {
  144.   return sortOrder;
  145. }
  146.  
  147. @end
  148.  
  149.  
  150. /**************************************************************/
  151.  
  152.  
  153. @implementation MiscSortedList(Override)
  154.  
  155. + initialize
  156. {
  157.   [MiscSortedList setVersion:MiscSortedListVersion];
  158.   return self;
  159. }
  160.  
  161.  
  162. - addObject:anObject
  163. {
  164.   return [self insertObject:anObject at:[self count]];
  165. }
  166.  
  167.  
  168. - appendList:(List *)otherList
  169. {
  170.   int pos;
  171.   int listSize = [otherList count];
  172.   
  173.   for ( pos = 0 ; pos < listSize ; pos++ )
  174.     {
  175.       if ( ![[otherList objectAt:pos] conformsTo:@protocol(MiscCompare)] )
  176.     {
  177.       return nil;
  178.     }
  179.     }
  180.   
  181.   return [super appendList:otherList];
  182. }
  183.  
  184.  
  185. - copyFromZone:(NXZone *)zone
  186. {
  187.   id copy = [super copyFromZone:zone];
  188.  
  189.   [copy setIgnoreCase:ignoreCase wait:YES];
  190.   [copy setSortOrder:sortOrder wait:YES];
  191.   [copy setSortEnabled:sortEnabled wait:YES];
  192.  
  193.   return copy;
  194. }
  195.  
  196.  
  197. - (unsigned int)indexOf:anObject
  198. {
  199.   int pivot;
  200.  
  201.   if ( !sorted )
  202.     {
  203.       return [super indexOf:anObject];
  204.     }
  205.       
  206.   pivot = [self pivotObject:anObject caseCheck:NO];
  207.  
  208.   if ( anObject == [self objectAt:pivot] )
  209.     {
  210.       return pivot;
  211.     }
  212.   
  213.   return NX_NOT_IN_LIST;
  214. }
  215.  
  216.  
  217. - initCount:(unsigned int)numSlots
  218. {
  219.   [super initCount:numSlots];
  220.   ignoreCase = NO;
  221.   sorted = YES;
  222.   sortOrder = Misc_ASCENDING;
  223.   sortEnabled = YES;
  224.  
  225.   return self;
  226. }
  227.  
  228.  
  229. - insertObject:anObject at:(unsigned int)index
  230. {
  231.   if ( sortEnabled )
  232.     {
  233.       return [self insertObjectBySort:anObject];
  234.     }
  235.   
  236.   sorted = NO;
  237.   return [super insertObject:anObject at:index];
  238. }
  239.  
  240.  
  241. - read:(NXTypedStream *)stream
  242. {
  243.   [super read:stream];
  244.   NXReadTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  245.   return self;
  246. }
  247.  
  248.  
  249. - replaceObject:anObject with:newObject
  250. {
  251.   int index;
  252.   
  253.   if ( !anObject && ((index = [self indexOf:anObject]) != NX_NOT_IN_LIST) )
  254.     {
  255.       return [self replaceObjectAt:index with:newObject];
  256.     }
  257.  
  258.   return nil;
  259. }
  260.  
  261.   
  262. - replaceObjectAt:(unsigned int)index with:newObject
  263. {
  264.   id oldObject;
  265.   
  266.   if (!newObject || (index > [self count]) || ![newObject conformsTo:@protocol(MiscCompare)] )
  267.     {
  268.       return nil;
  269.     }
  270.  
  271.   if ( sortEnabled )
  272.     {
  273.       if ( oldObject = [self removeObjectAt:index] )
  274.     {
  275.       return nil;
  276.     }
  277.  
  278.       [self insertObjectBySort:newObject];
  279.       return oldObject;
  280.     }
  281.   
  282.   return [super replaceObjectAt:index with:newObject];
  283. }
  284.  
  285.  
  286. - write:(NXTypedStream *)stream
  287. {
  288.   [super write:stream];
  289.   NXWriteTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  290.   return self;
  291. }
  292.  
  293. @end
  294.  
  295.  
  296. /**************************************************************/
  297.  
  298.  
  299. @implementation MiscSortedList(Private)
  300.  
  301. - (unsigned int)pivotObject:anObject caseCheck:(BOOL)flag
  302. {
  303.   int compare;
  304.   int top = 0;
  305.   int bottom = [self count] - 1;
  306.   int pivot = 0;
  307.  
  308.   while ( top <= bottom )
  309.     {
  310.       pivot = (int)((top + bottom) / 2);
  311.       compare = [self compare:[self objectAt:pivot] to:anObject caseCheck:flag];
  312.  
  313.       if ( compare > 0 )
  314.     {
  315.       bottom = pivot - 1;
  316.     }
  317.       else if ( compare < 0 )
  318.     {
  319.       top = pivot + 1;
  320.     }
  321.       else
  322.     {
  323.       break;
  324.     }
  325.     }
  326.  
  327.   return pivot;
  328. }
  329.  
  330.  
  331. - setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag
  332. {
  333.   if ( caseFlag != ignoreCase )
  334.     {
  335.       ignoreCase = caseFlag;
  336.  
  337.       if ( !waitFlag )
  338.     {
  339.       [self sort];
  340.     }
  341.     }
  342.  
  343.   return self;
  344. }  
  345.  
  346.  
  347. - setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag
  348. {
  349.   if ( sortFlag != sortEnabled )
  350.     {
  351.       sortEnabled = sortFlag;
  352.  
  353.       if ( !(waitFlag || sorted) )
  354.     {
  355.       [self sort];
  356.     }
  357.     }
  358.  
  359.   return self;
  360. }
  361.  
  362.  
  363. - setSortOrder:(int)order wait:(BOOL)waitFlag
  364. {
  365.   int listSize, pos;
  366.   
  367.   if ( ((order != Misc_ASCENDING) && (order != Misc_DESCENDING)) || (sortOrder == order) )
  368.     {
  369.       return self;
  370.     }
  371.  
  372.   sortOrder = order;
  373.  
  374.   if ( sortEnabled && !waitFlag )
  375.     {
  376.       if ( sorted )
  377.     {
  378.       listSize = [self count] - 1;
  379.       
  380.       for ( pos = 0 ; pos < listSize ; pos++ )
  381.         {
  382.           [super insertObject:[self removeLastObject] at:pos];
  383.         }
  384.     }
  385.       else
  386.     {
  387.       [self sort];
  388.     }
  389.     }
  390.   
  391.   return self;
  392. }
  393.  
  394.  
  395. - sortFrom:(int)first to:(int)last
  396. {
  397.   id x, a;
  398.   int split, unknown;
  399.   int i, j, low;
  400.  
  401.   if ( (last-first) >= PART_SIZE )
  402.     {
  403.       x = [self objectAt:first];
  404.       split = first;
  405.   
  406.       for ( unknown = (first+1) ; unknown < last ; unknown++ )
  407.     {
  408.       if ( 0 < [self compare:x to:[self objectAt:unknown] caseCheck:YES] )
  409.         {
  410.           split++;
  411.           SortSwitch(split, unknown);
  412.         }
  413.     }
  414.       
  415.       SortSwitch(first, split);
  416.       [self sortFrom:first to:split];
  417.       [self sortFrom:(split+1) to:last];
  418.     }
  419.   else
  420.     {
  421.       for ( i = first ; i < last ; i++ )
  422.     {
  423.       low = i;
  424.       x = [self objectAt:low];
  425.       
  426.       for ( j = (i+1) ; j <= last ; j++ )
  427.         {
  428.           a = [self objectAt:j];
  429.  
  430.           if ( 0 < [self compare:x to:a caseCheck:YES] )
  431.         {
  432.           low = j;
  433.           x = a;
  434.         }
  435.         }
  436.       
  437.       SortSwitch(i,low);
  438.     }
  439.     }
  440.  
  441.   return self;
  442. }
  443.  
  444. @end
  445.