home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / developm / source / iconclr.cpt / Sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-14  |  5.8 KB  |  311 lines
  1. /*
  2.     FileList 1.4
  3.     "Sort.c"
  4. */
  5.  
  6. #include "Main.h"
  7. #include "Stack.h"
  8. #include "Search.h"
  9. #include "Utilities.h"
  10. #include "Sort.h"
  11.  
  12. #define SHOW    0        /* 0 = Don't show sorting time */
  13. #define SORT    1        /* 1 = Shell sort, 2 = Quick sort */
  14.  
  15. /*
  16.     Sorting times (ticks, 60.15 ticks/second):
  17.  
  18.                                 Shell        Quick
  19.  
  20.     1182 files    size -> name       65           57    (88 %)
  21.                 name -> name       27         1709
  22.                 name -> size       21           18    (86 %)
  23.                 size -> size        9          661
  24.  
  25.     5195 files    size -> name      431          354    (82 %)
  26.                 name -> name      162        27325
  27.                 name -> size      149          118    (79 %)
  28.                 size -> size       53        11170
  29.     
  30.     14550 files    size -> name     1625         1215    (75 %)
  31.                 name -> name      522            -
  32.                 name -> size      631          439    (70 %)
  33.                 size -> size      632            -
  34.  
  35.     Conclusion: Quick sort is the fastest, but degenerates dramatically
  36.     if the data is already sorted. The Shell sort is nearly as fast as
  37.     the Quick sort, and much faster under the conditions where Quick sort
  38.     degenerates.
  39. */
  40.  
  41. typedef short (*PFI)();    /* Pointer to function returning short */
  42.  
  43. /* ----- Compare records ----------------------------------------------- */
  44. /* return <0 if Rec1 < Rec2, =0 if Rec1 == Rec2, >0 if Rec1 > Rec2 */
  45.  
  46. static short CompareName (                /* By name */
  47. register FileInfoPtr p1,
  48. register FileInfoPtr p2)
  49. {
  50.     return StrCompare(p1->name, p2->name);
  51. }
  52.  
  53. static short CompareSize (                /* By size/total (name) */
  54. register FileInfoPtr p1,
  55. register FileInfoPtr p2)
  56. {
  57.     register long d;
  58.  
  59.     d = p1->size - p2->size;
  60.     if (d < 0)
  61.         return -1;
  62.     if (d > 0)
  63.         return 1;
  64.     return CompareName(p1, p2);
  65. }
  66.  
  67. static short CompareType (                /* By type/free (name) */
  68. register FileInfoPtr p1,
  69. register FileInfoPtr p2)
  70. {
  71.     register long d;
  72.  
  73.     d = p1->type - p2->type;
  74.     if (d < 0)
  75.         return -1;
  76.     if (d > 0)
  77.         return 1;
  78.     return CompareName(p1, p2);
  79. }
  80.  
  81. static short CompareCreator (            /* By creator/files (name) */
  82. register FileInfoPtr p1,
  83. register FileInfoPtr p2)
  84. {
  85.     register long d;
  86.  
  87.     d = p1->creator - p2->creator;
  88.     if (d < 0)
  89.         return -1;
  90.     if (d > 0)
  91.         return 1;
  92.     return CompareName(p1, p2);
  93. }
  94.  
  95. static short CompareCdate (                /* By creation date (name) */
  96. register FileInfoPtr p1,
  97. register FileInfoPtr p2)
  98. {
  99.     register long d;
  100.  
  101.     d = p1->cdate - p2->cdate;
  102.     if (d < 0)
  103.         return -1;
  104.     if (d > 0)
  105.         return 1;
  106.     return CompareName(p1, p2);
  107. }
  108.  
  109. static short CompareMdate (                /* By modification date (name) */
  110. register FileInfoPtr p1,
  111. register FileInfoPtr p2)
  112. {
  113.     register long d;
  114.  
  115.     d = p1->mdate - p2->mdate;
  116.     if (d < 0)
  117.         return -1;
  118.     if (d > 0)
  119.         return 1;
  120.     return CompareName(p1, p2);
  121. }
  122.  
  123. static short CompareVolume (            /* By volume (name) */
  124. register FileInfoPtr p1,
  125. register FileInfoPtr p2)
  126. {
  127.     register short i;
  128.  
  129.     if (!(i = StrCompare(GetVolume(p1), GetVolume(p2))))
  130.         i = CompareName(p1, p2);
  131.     return i;
  132. }
  133.  
  134. static short ComparePath (                /* By volume (path, name) */
  135. register FileInfoPtr p1,
  136. register FileInfoPtr p2)
  137. {
  138.     register unsigned char *s1, *s2;
  139.     register short i;
  140.     STACK stack1, stack2;
  141.  
  142.     InitPath(p1, &stack1);
  143.     InitPath(p2, &stack2);
  144.     do {
  145.         s1 = NextPath(&stack1);
  146.         s2 = NextPath(&stack2);
  147.         i = StrCompare(s1 ? s1 : EmptyStr, s2 ? s2 : EmptyStr);
  148.     } while (s1 && s2 && !i);
  149.     if (!i)
  150.         i = CompareName(p1, p2);
  151.     return i;
  152. }
  153.  
  154. #if SHOW
  155. /* ----- Show sort time ------------------------------------------------ */
  156.  
  157. static void ShowTime (register unsigned long ticks)
  158. {
  159.     register DialogPtr dialog;
  160.     short item;
  161.     unsigned char number[10];
  162.  
  163.     NumToString(ticks, number);
  164.     ParamText(number, "\p ticks", EmptyStr, EmptyStr);
  165.     CenterDialog('DLOG', MessageDialog);
  166.     if (dialog = GetNewDialog(MessageDialog, 0L, -1L)) {
  167.         ModalDialog(0L, &item);
  168.         DisposDialog(dialog);
  169.     }
  170. }
  171. #endif
  172.  
  173. #if SORT == 1
  174. /* ----- Sort records (Shell sort) ------------------------------------- */
  175.  
  176. static void Sort (
  177.     register long *xp,
  178.     register long n,
  179.     register PFI compare)
  180. {
  181.     register long i, j, gap, temp;
  182.     register char *fp;
  183. #if SHOW
  184.     unsigned long start;
  185.     while ((start = Ticks) == Ticks)
  186.         ;
  187. #endif
  188.  
  189.     fp = InfoBase;
  190.     for (gap = 1; gap <= n; gap = 3*gap + 1)
  191.         ;
  192.     while(gap > 3) {
  193.         gap = gap/3;
  194.         for (i = gap; i < n; ++i) {
  195.             temp = xp[i];
  196.             j = i;
  197.             while ((j >= gap) &&
  198.                 ((*compare)(
  199.                     fp + (xp[j-gap] & 0x7FFFFFFF),
  200.                     fp + (temp & 0x7FFFFFFF)) > 0)) {
  201.                 xp[j] = xp[j-gap];
  202.                 j -= gap;
  203.             }
  204.             xp[j] = temp;
  205.         }
  206.     }
  207. #if SHOW
  208.     ShowTime(Ticks - start);
  209. #endif
  210. }
  211. #endif
  212.  
  213. #if SORT == 2
  214. /* ----- Sort records (Quick sort) ------------------------------------- */
  215.  
  216. static long *Xp;
  217. static PFI Compare;
  218.  
  219. static void Swap (
  220.     register long i,
  221.     register long j)
  222. {
  223.     register long t;
  224.  
  225.     t = Xp[i];
  226.     Xp[i] = Xp[j];
  227.     Xp[j] = t;
  228. }
  229.  
  230. static void Qsort (
  231.     register long first,
  232.     register long last)
  233. {
  234.     static long i;
  235.     register long j;
  236.  
  237.     while (last - first > 1) {
  238.         i = first;
  239.         j = last;
  240.         for (;;) {
  241.             while (++i < last &&
  242.                     (*Compare)(InfoBase + Xp[i], InfoBase + Xp[first]) < 0)
  243.                 ;
  244.             while (--j > first &&
  245.                     (*Compare)(InfoBase + Xp[j], InfoBase + Xp[first]) > 0)
  246.                 ;
  247.             if (i >= j)
  248.                  break;
  249.             Swap(i, j);
  250.         }
  251.         Swap(first, j);
  252.         if (j - first < last - (j + 1)) {
  253.             Qsort(first, j);
  254.             first = j + 1;
  255.         }
  256.         else {
  257.             Qsort(j + 1, last);
  258.             last = j;
  259.         }
  260.     }
  261. }
  262.  
  263. static void Sort (
  264.     register long *xp,
  265.     long n,
  266.     register PFI compare)
  267. {
  268. #if SHOW
  269.     unsigned long start;
  270.     while ((start = Ticks) == Ticks)
  271.         ;
  272. #endif
  273.     Xp = xp;
  274.     Compare = compare;
  275.     Qsort (0, n);
  276. #if SHOW
  277.     ShowTime(Ticks - start);
  278. #endif
  279. }
  280. #endif
  281.  
  282. /* ----- Sort interface ------------------------------------------------ */
  283.  
  284. static PFI FileCompare[] = {
  285.         CompareName,
  286.         CompareSize,
  287.         CompareType,
  288.         CompareCreator,
  289.         CompareCdate,
  290.         CompareMdate,
  291.         CompareVolume,
  292.         ComparePath };
  293.  
  294. static PFI VolumeCompare[] = {
  295.         CompareName,
  296.         CompareType,
  297.         CompareSize,
  298.         CompareCreator,
  299.         CompareCdate,
  300.         CompareMdate };
  301.  
  302. void SortFiles (register short how)
  303. {
  304.     Sort(FileData.base, FileData.count, FileCompare[how]);
  305. }
  306.  
  307. void SortVolumes(register short how)
  308. {
  309.     Sort(VolumeData.base, VolumeData.count, VolumeCompare[how]);
  310. }
  311.