home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / SourceCode / MiscKit1.2.6 / Source / MiscSortedStorage.m < prev    next >
Encoding:
Text File  |  1994-03-22  |  6.7 KB  |  403 lines
  1. //
  2. //    MiscSortedStorage.m -- a MiscStorage which keeps the elements sorted
  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.  * $RCSfile$
  16.  *
  17.  * $Author$
  18.  *
  19.  * $Revision$
  20.  *
  21.  * $Date$
  22.  *
  23. */
  24.  
  25. #import <misckit/MiscSortedStorage.h>
  26.  
  27. #define MiscSortedStorageVersion    100
  28. #define PART_SIZE       5
  29.  
  30.  
  31. @interface MiscSortedStorage(Private)
  32.  
  33. - (unsigned int)pivotElement:(void *)anElement caseCheck:(BOOL)flag;
  34. - setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag;
  35. - setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag;
  36. - setSortOrder:(int)order wait:(BOOL)waitFlag;
  37. - sortFrom:(int)first to:(int)last;
  38. - sortSwitch:(int)a :(int)b;
  39.  
  40. @end
  41.  
  42.  
  43. /**************************************************************/
  44.  
  45.  
  46. @implementation MiscSortedStorage
  47.  
  48. - (int)compare:(void *)elementA to:(void *)elementB caseCheck:(BOOL)flag
  49. {
  50.   [self subclassResponsibility:_cmd];
  51.   return 0;
  52. }
  53.  
  54.  
  55. - (BOOL)ignoreCase
  56. {
  57.   return ignoreCase;
  58. }
  59.  
  60.  
  61. - insertElementBySort:(void *)anElement
  62. {
  63.   int pivot;
  64.   
  65.   if ( !anElement )
  66.     {
  67.       return nil;
  68.     }
  69.   
  70.   if ( ![self count] )
  71.     {
  72.       return [super insertElement:anElement at:[self count]];
  73.     }
  74.   
  75.   pivot = [self pivotElement:anElement caseCheck:YES];
  76.   
  77.   if ( 0 <= [self compare:[self elementAt:pivot] to:anElement caseCheck:YES] )
  78.     {
  79.       return [super insertElement:anElement at:pivot];
  80.     }
  81.   
  82.   if ( [self count] < (pivot+1) )
  83.     {
  84.       return [super insertElement:anElement at:[self count]];
  85.     }
  86.   
  87.   return [super insertElement:anElement at:(pivot+1)];
  88. }
  89.  
  90.  
  91. - (void *)lastElement
  92. {
  93.   if ( [self count] )
  94.     {
  95.       return [self elementAt:([self count]-1)];
  96.     }
  97.  
  98.   return nil;
  99. }
  100.  
  101.  
  102. - setIgnoreCase:(BOOL)flag
  103. {
  104.   return [self setIgnoreCase:flag wait:NO];
  105. }
  106.  
  107.   
  108. - setSortEnabled:(BOOL)sort
  109. {
  110.   return [self setSortEnabled:sort wait:NO];
  111. }
  112.  
  113.  
  114. - setSortOrder:(int)order
  115. {
  116.   return [self setSortOrder:order wait:NO];
  117. }
  118.  
  119.  
  120. - sort
  121. {
  122.   if ( !sorted )
  123.     {
  124.       [self sortFrom:0 to:[self count]];
  125.       sorted = YES;
  126.     }
  127.   
  128.   return self;
  129. }
  130.  
  131.  
  132. - (BOOL)sorted
  133. {
  134.   return sorted;
  135. }
  136.  
  137.  
  138. - (BOOL)sortEnabled
  139. {
  140.   return sortEnabled;
  141. }
  142.  
  143.  
  144. - (int)sortOrder
  145. {
  146.   return sortOrder;
  147. }
  148.  
  149.  
  150. @end
  151.  
  152.  
  153. /**************************************************************/
  154.  
  155.  
  156. @implementation MiscSortedStorage(Override)
  157.  
  158. + initialize
  159. {
  160.   [MiscSortedStorage setVersion:MiscSortedStorageVersion];
  161.   return self;
  162. }
  163.  
  164.  
  165. - addElement:(void *)anElement
  166. {
  167.   return [self insertElement:anElement at:[self count]];
  168. }
  169.  
  170.  
  171. - initCount:(unsigned int)count elementSize:(unsigned int)sizeInBytes description:(const char *)string
  172. {
  173.   [super initCount:count elementSize:sizeInBytes description:string];
  174.   ignoreCase = NO;
  175.   sorted = YES;
  176.   sortOrder = Misc_ASCENDING;
  177.   sortEnabled = YES;
  178.   
  179.   return self;
  180. }
  181.  
  182.  
  183. - copyFromZone:(NXZone *)zone
  184. {
  185.   id copy = [super copyFromZone:zone];
  186.  
  187.   [copy setIgnoreCase:ignoreCase wait:YES];
  188.   [copy setSortOrder:sortOrder wait:YES];
  189.   [copy setSortEnabled:sortEnabled wait:YES];
  190.  
  191.   return copy;
  192. }
  193.  
  194.  
  195. - insertElement:(void *)anElement at:(unsigned int)index
  196. {
  197.   if ( sortEnabled )
  198.     {
  199.       return [self insertElementBySort:anElement];
  200.     }
  201.  
  202.   sorted = NO;
  203.   return [super insertElement:anElement at:index];
  204. }
  205.  
  206.  
  207. - read:(NXTypedStream *)stream
  208. {
  209.   [super read:stream];
  210.   NXReadTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  211.   return self;
  212. }
  213.  
  214.  
  215. - replaceElementAt:(unsigned int)index with:(void *)anElement
  216. {
  217.   if (!anElement || (index > [self count]) )
  218.     {
  219.       return nil;
  220.     }
  221.  
  222.   if ( sortEnabled )
  223.     {
  224.       [self removeElementAt:index];
  225.       [self insertElementBySort:anElement];
  226.       return self;
  227.     }
  228.  
  229.   return [super replaceElementAt:index with:anElement];
  230. }
  231.  
  232.  
  233. - write:(NXTypedStream *)stream
  234. {
  235.   [super write:stream];
  236.   NXWriteTypes(stream, "ccic", &sorted, &ignoreCase, &sortOrder, &sortEnabled);
  237.   return self;
  238. }
  239.  
  240. @end  
  241.  
  242.  
  243. /**************************************************************/
  244.  
  245.  
  246. @implementation MiscSortedStorage(Private)
  247.  
  248. - (unsigned int)pivotElement:(void *)anElement caseCheck:(BOOL)flag
  249. {
  250.   int compare;
  251.   int top = 0;
  252.   int bottom = [self count] - 1;
  253.   int pivot = 0;
  254.   
  255.   while ( top <= bottom )
  256.     {
  257.       pivot = (int)((top + bottom) / 2);
  258.       compare = [self compare:[self elementAt:pivot] to:anElement caseCheck:flag];
  259.       
  260.       if ( compare > 0 )
  261.     {
  262.       bottom = pivot - 1;
  263.     }
  264.       else if ( compare < 0 )
  265.     {
  266.       top = pivot + 1;
  267.     }
  268.       else
  269.     {
  270.       break;
  271.     }
  272.     }
  273.  
  274.   return pivot;
  275. }
  276.  
  277.  
  278. - setIgnoreCase:(BOOL)caseFlag wait:(BOOL)waitFlag
  279. {
  280.   if ( caseFlag != ignoreCase )
  281.     {
  282.       ignoreCase = caseFlag;
  283.  
  284.       if ( !waitFlag )
  285.         {
  286.           [self sort];
  287.         }
  288.     }
  289.  
  290.   return self;
  291. }
  292.  
  293.   
  294. - setSortEnabled:(BOOL)sortFlag wait:(BOOL)waitFlag
  295. {
  296.   if ( sortFlag != sortEnabled )
  297.     {
  298.       sortEnabled = sortFlag;
  299.  
  300.       if ( !(waitFlag || sorted) )
  301.         {
  302.           [self sort];
  303.         }
  304.     }
  305.  
  306.   return self;
  307. }
  308.  
  309.  
  310. - setSortOrder:(int)order wait:(BOOL)waitFlag
  311. {
  312.   int listSize, pos;
  313.  
  314.   if ( ((order != Misc_ASCENDING) && (order != Misc_DESCENDING)) || (sortOrder == order) )
  315.     {
  316.       return self;
  317.     }
  318.  
  319.   sortOrder = order;
  320.  
  321.   if ( sortEnabled && !waitFlag )
  322.     {
  323.       if ( sorted )
  324.         {
  325.           listSize = [self count] - 1;
  326.  
  327.           for ( pos = 0 ; pos < listSize ; pos++ )
  328.             {
  329.               [super insertElement:[self removeLastElement] at:pos];
  330.             }
  331.         }
  332.       else
  333.         {
  334.           [self sort];
  335.         }
  336.     }
  337.  
  338.   return self;
  339. }
  340.  
  341.  
  342. - sortFrom:(int)first to:(int)last
  343. {
  344.   void *x, *a;
  345.   int split, unknown;
  346.   int i, j, low;
  347.   
  348.   if ( (last-first) >= PART_SIZE )
  349.     {
  350.       x = [self elementAt:first];
  351.       split = first;
  352.       
  353.       for ( unknown = (first+1) ; unknown < last ; unknown++ )
  354.     {
  355.       if ( 0 < [self compare:x to:[self elementAt:unknown] caseCheck:YES] )
  356.         {
  357.           split++;
  358.           [self sortSwitch:split :unknown];
  359.         }
  360.     }
  361.       
  362.       [self sortSwitch:first :split];
  363.       [self sortFrom:first to:split];
  364.       [self sortFrom:(split+1) to:last];
  365.     }
  366.   else
  367.     {
  368.       for ( i = first ; i < last ; i++ )
  369.     {
  370.       low = i;
  371.       x = [self elementAt:low];
  372.       
  373.       for ( j = (i+1) ; j <= last ; j++ )
  374.         {
  375.           a = [self elementAt:j];
  376.           
  377.           if ( 0 < [self compare:x to:a caseCheck:YES] )
  378.         {
  379.           low = j;
  380.           x = a;
  381.         }
  382.         }
  383.       
  384.       [self sortSwitch:i :low];
  385.     }
  386.     }
  387.   
  388.   return self;
  389. }
  390.  
  391.  
  392. - sortSwitch:(int)a :(int)b
  393. {
  394.   void *elementA = [self elementAt:a];
  395.   void *elementB = [self elementAt:b];
  396.   [super replaceElementAt:a with:elementB];
  397.   [super replaceElementAt:b with:elementA];
  398.  
  399.   return self;
  400. }
  401.  
  402. @end
  403.