home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / AIE8908.ZIP / SORT.C < prev   
Encoding:
C/C++ Source or Header  |  1988-05-04  |  11.0 KB  |  313 lines
  1. /*********************************************************/
  2. /*    File:         sort.c                               */
  3. /*                                                       */
  4. /*    Description:  This file contains source code for   */
  5. /*                  a program written in C which sorts   */
  6. /*                  text files.  It is a demonstration   */
  7. /*                  of LISP-like list procedures.        */
  8. /*                                                       */
  9. /*    Version Date     History                           */
  10. /*    1.00    14SEP88  Original                          */
  11. /*********************************************************/
  12.  
  13. #include <stdlib.h>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include <malloc.h>
  17.  
  18. /*********************************************************/
  19. /*    typedefs                                           */
  20. /*********************************************************/
  21.  
  22. typedef void   *POINTER;      /* General purpose pointer */
  23.  
  24. typedef struct                /* A CONS is two pointers  */
  25.    {
  26.    POINTER  car;
  27.    POINTER  cdr;
  28.    } CONS;
  29.  
  30. typedef CONS    *LIST;        /* A LIST is a pointer to  */
  31.                               /* a CONS                  */
  32.  
  33.  
  34. /*********************************************************/
  35. /*    return codes at the program level                  */
  36. /*********************************************************/
  37.  
  38. #define  RET_NORMAL  0  /* Normal return code            */
  39. #define  RET_IOERR   2  /* I/O Error                     */
  40. #define  RET_MEMERR  3  /* Memory allocation error       */
  41.  
  42. /*********************************************************/
  43. /*    Manifest Constants                                 */
  44. /*********************************************************/
  45.  
  46. #define  LINESIZE 500   /* size of local buffer          */
  47.                         /* lines larger then this will   */
  48.                         /* read as multiple lines        */
  49.  
  50.  
  51. /*********************************************************/
  52. /*    Prototypes                                         */
  53. /*********************************************************/
  54.  
  55. LIST     reverse(LIST  lst);
  56. LIST     merge(LIST lst1,LIST lst2,int (*compare)());
  57. LIST     sort(LIST lst,int (*compare)());
  58. CONS     *cons(POINTER a,POINTER b);
  59. LIST     cpush(CONS *z,LIST *lst);
  60. LIST     push(POINTER item,LIST *lst);
  61. CONS     *cpop(POINTER *lst);
  62. POINTER  pop(POINTER  *lst);
  63. LIST     outputlist(LIST lst,FILE *stream);
  64. int      string_compare(char *a,char *b);
  65. char     *getaline(FILE *stream);
  66.  
  67.  
  68. /*********************************************************/
  69. /*    main     sort program                              */
  70. /*                                                       */
  71. /*    Reads lines of text from stdin, sorts them, and    */
  72. /*    outputs the result to stdout.                      */
  73. /*********************************************************/
  74. int main(void)
  75. {
  76.  
  77.    LIST mylist=NULL;       /* List of text records as    */
  78.                            /* read from stdin            */
  79.  
  80.    char  *lp;              /* pointer to duplicate string*/
  81.  
  82.    while  ( (lp = getaline(stdin)) != NULL )
  83.       push(lp,&mylist);
  84.  
  85.    outputlist(sort(mylist,string_compare),stdout);
  86.  
  87.    return RET_NORMAL;
  88. }
  89.  
  90.  
  91. /*********************************************************/
  92. /*    getaline         get a line of text                */
  93. /*                                                       */
  94. /*    Returns a pointer to a line of text read from      */
  95. /*    stream.  Returns NULL if end of file.  Exits       */
  96. /*    on error.                                          */
  97. /*********************************************************/
  98. char *getaline(FILE *stream)
  99. {
  100.    char  line[LINESIZE];   /* input buffer               */
  101.    char  *lp;              /* points to strdup buffer    */
  102.  
  103.    if (fgets(line,LINESIZE,stream) != NULL)
  104.       {
  105.       if ( (lp = strdup(line)) != NULL)
  106.          return lp;        /* normal return              */
  107.       else
  108.          exit(RET_MEMERR); /* strdup could not malloc    */
  109.       }
  110.    else
  111.       {
  112.       if (feof(stream))
  113.          return NULL;      /* end of file                */
  114.       else
  115.          exit(RET_IOERR);  /* I/O error in fgets         */
  116.       }
  117. }
  118.  
  119. /*********************************************************/
  120. /*    string_compare    compares strings                 */
  121. /*                                                       */
  122. /*    Returns TRUE value if string a is ordered after    */
  123. /*    string b. Returns  FASE if string a is equal to    */
  124. /*    or ordered before string b.                        */
  125. /*********************************************************/
  126. int string_compare(char *a,char *b)
  127. {
  128.    return strcmp(a,b) > 0;
  129. }
  130.  
  131. /*********************************************************/
  132. /*    push          push an item onto a list             */
  133. /*                                                       */
  134. /*    Uses cons to create a CONS and sets its car cell   */
  135. /*    to item.  Its cdr is set to *lst.  *lst is set to  */
  136. /*    point to the CONS created.  A pointer to the CONS  */
  137. /*    is also returned.                                  */
  138. /*********************************************************/
  139. LIST push(POINTER item,LIST *lst)
  140. {
  141.    return *lst = cons(item,*lst);
  142. }
  143.  
  144. /*********************************************************/
  145. /*    cons          create a CONS                        */
  146. /*                                                       */
  147. /*    Uses malloc to allocate a CONS and set its         */
  148. /*    car cell to a and its cdr cell to b.  Exits if     */
  149. /*    malloc fails!                                      */
  150. /*********************************************************/
  151. CONS *cons(POINTER a,POINTER b)
  152. {
  153.    CONS  *z;
  154.    z = (CONS *) malloc(sizeof(CONS));
  155.    if (z == NULL) exit(RET_MEMERR);
  156.    z->car = a;
  157.    z->cdr = b;
  158.    return z;
  159. }  
  160.  
  161.  
  162. /*********************************************************/
  163. /*    pop         pop an item off a list                 */
  164. /*                                                       */
  165. /*    Uses cpop to pop a CONS off lst.  Return NULL      */
  166. /*    if lst is empty.  free the CONS and return the     */
  167. /*    car cell of the CONS.                              */
  168. /*********************************************************/
  169. POINTER  pop(LIST  *lst)
  170. {
  171.    POINTER  item;
  172.    CONS     *z;
  173.  
  174.    z = cpop(lst);
  175.    if(z == NULL) return NULL; /* list is empty           */
  176.  
  177.    item = z->car;             /* get what cons pointed to*/
  178.  
  179.    free(z);                   /* release the cons        */
  180.  
  181.    return item;
  182. }
  183.  
  184. /*********************************************************/
  185. /*    cpop         pop a CONS off a list                 */
  186. /*                                                       */
  187. /*    if *lst is empty return NULL, else set *lst to the */
  188. /*    the car cell of the first CONS on *lst and return  */
  189. /*    a pointer to the first CONS on *lst.               */
  190. /*********************************************************/
  191. CONS    *cpop(LIST *lst)
  192. {
  193.    LIST  rvalue;
  194.    rvalue = *lst;
  195.    if (rvalue != NULL)
  196.       *lst = rvalue->cdr;
  197.    return rvalue;
  198. }
  199.  
  200. /*********************************************************/
  201. /*    outputlist   output each item in a list            */
  202. /*                                                       */
  203. /*    start with the first item in the list, output it   */
  204. /*    to stream assuming it is a string, repeat for each */
  205. /*    item in the list.  Return lst.                     */
  206. /*********************************************************/
  207. LIST outputlist(LIST lst,FILE *stream)
  208. {
  209.    CONS *acons;
  210.    LIST  l=lst;
  211.  
  212.    while ( acons=cpop(l) != NULL )
  213.       fputs( (char *) acons->car,stream);
  214.    return lst;
  215. }
  216.  
  217.  
  218. /*********************************************************/
  219. /*    cpush      cons push                               */
  220. /*                                                       */
  221. /*    Adds a CONS to the head of a list                  */
  222. /*    modify the cdr cell of *z to point to *lst.  set   */
  223. /*    *lst to point to the CONS z and return a pointer   */
  224. /*    to the CONS.                                       */
  225. /*********************************************************/
  226. LIST cpush(CONS *z,LIST *lst)
  227. {
  228.    z->cdr = *lst;
  229.    return *lst = z;
  230. }
  231.  
  232. /*********************************************************/
  233. /*    reverse      reverse a list                        */
  234. /*                                                       */
  235. /*    distructively modify the cdr cells of the CONS     */
  236. /*    which make up lst so that a new list is created    */
  237. /*    which is the reverse of the original list.         */
  238. /*    return the new list.                               */
  239. /*********************************************************/
  240. LIST  reverse(LIST  lst)
  241. {
  242.    LIST  rlst=NULL;
  243.  
  244.    while (lst != NULL) cpush(cpop(&lst),&rlst);
  245.    return rlst;
  246. }
  247.  
  248.  
  249.  
  250. /*********************************************************/
  251. /*    split      split a list in half                    */
  252. /*                                                       */
  253. /*    Find the mid CONS in lst.  set its cdr cell to     */
  254. /*    NULL.  return the remainder of lst, i.e. a pointer */
  255. /*    to the next CONS after the mid CONS.               */
  256. /*********************************************************/
  257. LIST split(LIST lst)
  258. {
  259.    LIST tail=lst->cdr;
  260.  
  261.    if ( (lst == NULL) || (tail == NULL) )
  262.       return lst;
  263.  
  264.    while( (tail != NULL) && ( (tail=tail->cdr) != NULL) )
  265.       {
  266.         lst = lst->cdr;
  267.         tail = tail->cdr;
  268.       }
  269.    tail = lst->cdr;
  270.    lst->cdr=NULL;
  271.    return tail;
  272. }
  273.  
  274.  
  275. /*********************************************************/
  276. /*    sort        sort a list                            */
  277. /*                                                       */
  278. /*    If cmp is a two argument ordering procedure,       */
  279. /*    sort the items in lst based on cmp and             */
  280. /*    return the results                                 */
  281. /*********************************************************/
  282. LIST  sort( LIST lst,int (*cmp)())
  283. {
  284.    LIST lst2;
  285.  
  286.    if ((lst == NULL) || (lst->cdr == NULL)) return lst;
  287.  
  288.    lst2 = split(lst);
  289.    return merge(sort(lst,cmp),sort(lst2,cmp),cmp);
  290. }
  291.  
  292.  
  293. /*********************************************************/
  294. /*    merge        merge two lists                       */
  295. /*                                                       */
  296. /*    If cmp is a two argument ordering procedure,       */
  297. /*    merge the items in l1 and l2 based on cmp and      */
  298. /*    return the results                                 */
  299. /*********************************************************/
  300. LIST  merge(LIST l1,LIST l2,int (*cmp)())
  301. {
  302.    LIST  rlst=NULL;
  303.  
  304.    while ( (l1 != NULL) && (l2 != NULL) )
  305.       cpush((cmp(l2->car,l1->car) ? cpop(&l1) : cpop(&l2)), &rlst);
  306.  
  307.    while ( l1 != NULL ) cpush(cpop(&l1),&rlst);
  308.    while ( l2 != NULL ) cpush(cpop(&l2),&rlst);
  309.  
  310.    return reverse(rlst);
  311. }
  312.  while ( l1 != NULL ) cpush(cpop(&l1),&rlst);
  313.    while ( l