home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fonts 1 / freshfonts1.bin / bbs / programs / amiga / makeindex.lha / makeindex-2.12 / src / sortid.c < prev   
C/C++ Source or Header  |  1993-05-26  |  8KB  |  361 lines
  1. /*
  2.  *
  3.  *  This file is part of
  4.  *    MakeIndex - A formatter and format independent index processor
  5.  *
  6.  *  Copyright (C) 1989 by Chen & Harrison International Systems, Inc.
  7.  *  Copyright (C) 1988 by Olivetti Research Center
  8.  *  Copyright (C) 1987 by Regents of the University of California
  9.  *
  10.  *  Author:
  11.  *    Pehong Chen
  12.  *    Chen & Harrison International Systems, Inc.
  13.  *    Palo Alto, California
  14.  *    USA
  15.  *    (phc@renoir.berkeley.edu or chen@orc.olivetti.com)
  16.  *
  17.  *  Contributors:
  18.  *    Please refer to the CONTRIB file that comes with this release
  19.  *    for a list of people who have contributed to this and/or previous
  20.  *    release(s) of MakeIndex.
  21.  *
  22.  *  All rights reserved by the copyright holders.  See the copyright
  23.  *  notice distributed with this software for a complete description of
  24.  *  the conditions under which it is made available.
  25.  *
  26.  */
  27.  
  28. #include    "mkind.h"
  29.  
  30. static    long    idx_gc;
  31.  
  32. static    int    check_mixsym ARGS((char *x,char *y));
  33. static    int    compare ARGS((struct KFIELD * *a,struct KFIELD * *b));
  34. static    int    compare_one ARGS((char *x,char *y));
  35. static    int    compare_page ARGS((struct KFIELD * *a,struct KFIELD * *b));
  36. static    int    compare_string ARGS((unsigned char *a,unsigned char *b));
  37. static    int    new_strcmp ARGS((unsigned char *a, unsigned char *b,
  38.                  int option));
  39.  
  40. void
  41. sort_idx(VOID_ARG)
  42. {
  43.     MESSAGE("Sorting entries...", "");
  44.     idx_dc = 0;
  45.     idx_gc = 0L;
  46.     qqsort((char *) idx_key, (int) idx_gt, (int) sizeof(FIELD_PTR), 
  47.     (int (*) ARGS((char*,char*)))compare);
  48.     MESSAGE("done (%ld comparisons).\n", idx_gc);
  49. }
  50.  
  51. static int
  52. #if STDC
  53. compare(FIELD_PTR *a, FIELD_PTR *b)
  54. #else
  55. compare(a, b)
  56. FIELD_PTR *a;
  57. FIELD_PTR *b;
  58. #endif
  59. {
  60.     int     i;
  61.     int     dif;
  62.  
  63.     idx_gc++;
  64.     IDX_DOT(CMP_MAX);
  65.  
  66.     for (i = 0; i < FIELD_MAX; i++) {
  67.     /* compare the sort fields */
  68.     if ((dif = compare_one((*a)->sf[i], (*b)->sf[i])) != 0)
  69.         break;
  70.  
  71.     /* compare the actual fields */
  72.     if ((dif = compare_one((*a)->af[i], (*b)->af[i])) != 0)
  73.         break;
  74.     }
  75.  
  76.     /* both key aggregates are identical, compare page numbers */
  77.     if (i == FIELD_MAX)
  78.     dif = compare_page(a, b);
  79.     return (dif);
  80. }
  81.  
  82. static int
  83. #if STDC
  84. compare_one(char *x,char *y)
  85. #else
  86. compare_one(x, y)
  87. char   *x;
  88. char   *y;
  89. #endif
  90. {
  91.     int     m;
  92.     int     n;
  93.  
  94.     if ((x[0] == NUL) && (y[0] == NUL))
  95.     return (0);
  96.  
  97.     if (x[0] == NUL)
  98.     return (-1);
  99.  
  100.     if (y[0] == NUL)
  101.     return (1);
  102.  
  103.     m = group_type(x);
  104.     n = group_type(y);
  105.  
  106.     /* both pure digits */
  107.     if ((m >= 0) && (n >= 0))
  108.     return (m - n);
  109.  
  110.     /* x digit, y non-digit */
  111.     if (m >= 0) {
  112.     if (german_sort)
  113.         return (1);
  114.     else
  115.         return ((n == -1) ? 1 : -1);
  116.     }
  117.     /* x non-digit, y digit */
  118.     if (n >= 0) {
  119.     if (german_sort)
  120.         return (-1);
  121.     else
  122.         return ((m == -1) ? -1 : 1);
  123.     }
  124.     /* strings started with a symbol (including digit) */
  125.     if ((m == SYMBOL) && (n == SYMBOL))
  126.     return (check_mixsym(x, y));
  127.  
  128.     /* x symbol, y non-symbol */
  129.     if (m == SYMBOL)
  130.     return (-1);
  131.  
  132.     /* x non-symbol, y symbol */
  133.     if (n == SYMBOL)
  134.     return (1);
  135.  
  136.     /* strings with a leading letter, the ALPHA type */
  137.     return (compare_string((unsigned char*)x, (unsigned char*)y));
  138. }
  139.  
  140. static int
  141. #if STDC
  142. check_mixsym(char *x, char *y)
  143. #else
  144. check_mixsym(x, y)
  145. char   *x;
  146. char   *y;
  147. #endif
  148. {
  149.     int     m;
  150.     int     n;
  151.  
  152.     m = ISDIGIT(x[0]);
  153.     n = ISDIGIT(y[0]);
  154.  
  155.     if (m && !n)
  156.     return (1);
  157.  
  158.     if (!m && n)
  159.     return (-1);
  160.  
  161.     return (strcmp(x, y));
  162. }
  163.  
  164.  
  165. static int
  166. #if STDC
  167. compare_string(unsigned char *a, unsigned char *b)
  168. #else
  169. compare_string(a, b)
  170. unsigned char   *a;
  171. unsigned char   *b;
  172. #endif
  173. {
  174.     int     i = 0;
  175.     int     j = 0;
  176.     int     al;
  177.     int     bl;
  178.  
  179.     while ((a[i] != NUL) || (b[j] != NUL)) {
  180.     if (a[i] == NUL)
  181.         return (-1);
  182.     if (b[j] == NUL)
  183.         return (1);
  184.     if (letter_ordering) {
  185.         if (a[i] == SPC)
  186.         i++;
  187.         if (b[j] == SPC)
  188.         j++;
  189.     }
  190.     al = TOLOWER(a[i]);
  191.     bl = TOLOWER(b[j]);
  192.  
  193.     if (al != bl)
  194.         return (al - bl);
  195.     i++;
  196.     j++;
  197.     }
  198.     if (german_sort)
  199.     return (new_strcmp(a, b, GERMAN));
  200. #if (OS_BS2000 | OS_MVSXA)           /* in EBCDIC 'a' is lower than 'A' */
  201.     else
  202.     return (new_strcmp(a, b, ASCII));
  203. #else
  204.     else
  205.     return (strcmp((char*)a, (char*)b));
  206. #endif                       /* (OS_BS2000 | OS_MVSXA) */
  207. }
  208.  
  209. static int
  210. #if STDC
  211. compare_page(FIELD_PTR *a, FIELD_PTR *b)
  212. #else
  213. compare_page(a, b)
  214. FIELD_PTR *a;
  215. FIELD_PTR *b;
  216. #endif
  217. {
  218.     int     m = 0;
  219.     short   i = 0;
  220.  
  221.     while ((i < (*a)->count) && (i < (*b)->count) &&
  222.        ((m = (*a)->npg[i] - (*b)->npg[i]) == 0))
  223.     {
  224.     i++;
  225.     }
  226.     if (m == 0)
  227.     {                /* common leading page numbers match */
  228.     if ((i == (*a)->count) && (i == (*b)->count))
  229.     {            /* all page numbers match */
  230. #if 0    /* Faulty code replaced at 2.11 */
  231.         /* identical entries, except possibly in encap fields */
  232.         if (STREQ((*a)->encap, (*b)->encap))
  233.         {                /* encap fields identical */
  234.         if (((*a)->type != DUPLICATE) &&
  235.             ((*b)->type != DUPLICATE))
  236.             (*b)->type = DUPLICATE;
  237.  
  238.         else if ((*(*a)->encap == idx_ropen) ||
  239.              (*(*b)->encap == idx_rclose))
  240.             m = -1;
  241.         else if ((*(*a)->encap == idx_rclose) ||
  242.              (*(*b)->encap == idx_ropen))
  243.             m = 1;
  244.         }
  245.         else        /* encap fields differ */
  246.         {
  247.         if ((*(*a)->encap == idx_ropen) &&
  248.             (*(*b)->encap == idx_rclose))
  249.             m = -1;
  250.         else if ((*(*a)->encap == idx_rclose) &&
  251.              (*(*b)->encap == idx_ropen))
  252.             m = 1;
  253.         /* else leave m == 0 */
  254.         }
  255. #else    /* new 2.11 code */
  256.         /***********************************************************
  257.         We have identical entries, except possibly in encap fields.
  258.         The ordering is tricky here.  Consider the following input
  259.         sequence of index names, encaps, and page numbers:
  260.  
  261.         foo|(    2
  262.         foo|)    6
  263.         foo|(    6
  264.         foo|)    10
  265.  
  266.         This might legimately occur when a page range ends, and
  267.         subsequently, a new range starts, on the same page.  If we
  268.         just order by range_open and range_close (here, parens),
  269.         then we will produce
  270.  
  271.         foo|(    2
  272.         foo|(    6
  273.         foo|)    6
  274.         foo|)    10
  275.  
  276.         This will later generate the index entry
  277.  
  278.         foo, 2--6, \({6}, 10
  279.  
  280.         which is not only wrong, but has also introduced an illegal
  281.         LaTeX macro, \({6}, because the merging step treated this
  282.         like a \see{6} entry.
  283.  
  284.         The solution is to preserve the original input order, which
  285.         we can do by treating range_open and range_close as equal,
  286.         and then ordering by input line number.  This will then
  287.         generate the correct index entry
  288.  
  289.         foo, 2--10
  290.  
  291.         Ordering inconsistencies from missing range open or close
  292.         entries, or mixing roman and arabic page numbers, will be
  293.         detected later.
  294.         ***********************************************************/
  295.  
  296. #define isrange(c) ( ((c) == idx_ropen) || ((c) == idx_rclose) )
  297.  
  298.         /* Order two range values by input line number */
  299.  
  300.         if (isrange(*(*a)->encap) && isrange(*(*b)->encap))
  301.         m = (*a)->lc - (*b)->lc;
  302.  
  303.         /* Handle identical encap fields; neither is a range delimiter */
  304.  
  305.         else if (STREQ((*a)->encap, (*b)->encap))
  306.         {
  307.         /* If neither are yet marked duplicate, mark the second
  308.         of them to be ignored. */
  309.         if (((*a)->type != DUPLICATE) &&
  310.             ((*b)->type != DUPLICATE))
  311.             (*b)->type = DUPLICATE;
  312.         /* leave m == 0 to show equality */
  313.         }
  314.  
  315.         /* Encap fields differ: only one may be a range delimiter, */
  316.         /* or else neither of them is.   If either of them is a range */
  317.         /* delimiter, order by input line number; otherwise, order */
  318.         /* by name. */
  319.  
  320.         else
  321.         {
  322.         if ( isrange(*(*a)->encap) || isrange(*(*b)->encap) )
  323.             m = (*a)->lc - (*b)->lc; /* order by input line number */
  324.         else            /* order non-range items by */
  325.                     /* their encap strings */
  326.             m = compare_string((unsigned char*)((*a)->encap),
  327.                        (unsigned char*)((*b)->encap));
  328.         }
  329. #endif
  330.     }
  331.     else if ((i == (*a)->count) && (i < (*b)->count))
  332.         m = -1;
  333.     else if ((i < (*a)->count) && (i == (*b)->count))
  334.         m = 1;
  335.     }
  336.     return (m);
  337. }
  338.  
  339.  
  340. static int
  341. #if STDC
  342. new_strcmp(unsigned char *s1, unsigned char *s2, int option)
  343. #else
  344. new_strcmp(s1, s2, option)
  345. unsigned char   *s1;
  346. unsigned char   *s2;
  347. int     option;
  348. #endif
  349. {
  350.     int     i;
  351.  
  352.     i = 0;
  353.     while (s1[i] == s2[i])
  354.     if (s1[i++] == NUL)
  355.         return (0);
  356.     if (option)                   /* ASCII */
  357.     retu