home *** CD-ROM | disk | FTP | other *** search
/ Best Objectech Shareware Selections / UNTITLED.iso / boss / word / text / 024 / sort.c < prev    next >
C/C++ Source or Header  |  1993-06-04  |  24KB  |  725 lines
  1. /*
  2.  * These functions sort lines according to keys in a marked BOX block.
  3.  *
  4.  * Being that the data structure was changed from a big text buffer to a
  5.  * linked list, we can replace the simple insertion sort algorithm with a
  6.  * much faster sort algorithm.  The classic search and sort reference is by
  7.  * Donald E. Knuth, _The Art of Computer Programming; Volume 3:  Sorting and
  8.  * Searching_.  One of the fastest and most widely used general purpose
  9.  * sorting algorithms is the "Quicksort" algorithm.
  10.  *
  11.  * For implementation hints and guidelines on the Quicksort algorithm, one
  12.  * might read the original Quicksort paper by C. A. R. Hoare or anything
  13.  * by Robert Sedgewick.  Although Dr. Sedgewick includes a chapter on
  14.  * Quicksort in his intro computer science textbooks, _Algorithms in X_,
  15.  * I prefer the detailed hints and guidelines in his 1978 CACM paper.
  16.  * Incidentally, Dr. Sedgewick's Ph.D. dissertation was on the modification
  17.  * and mathematical analysis of the Quicksort algorithm.
  18.  *
  19.  *
  20.  * See:
  21.  *
  22.  *   Charles Antony Richard Hoare, "Algorithm 63: Partition."  _Communications
  23.  *      of the ACM_, 4 (No. 7): 321, 1961.
  24.  *
  25.  *   Charles Antony Richard Hoare, "Algorithm 64: Quicksort."  _Communications
  26.  *      of the ACM_, 4 (No. 7): 321, 1961.
  27.  *
  28.  *   Charles Antony Richard Hoare, "Quicksort."  _The Computer Journal_,
  29.  *      5 (April 1962 - January 1963): 10-15, 1962.
  30.  *
  31.  * See also:
  32.  *
  33.  *   Donald Ervin Knuth, _The Art of Computer Programming; Volume 3:  Sorting
  34.  *     and Searching_, Addison-Wesley, Reading, Mass., 1973, Chapter 5,
  35.  *     Sorting, pp 114-123.  ISBN 0-201-03803-X.
  36.  *
  37.  *   Robert Sedgewick, "Implementing Quicksort Programs."  _Communications
  38.  *      of the ACM_, 21 (No. 10): 847-857, 1978.
  39.  *
  40.  *
  41.  *                           Quicksort in TDE
  42.  *
  43.  * Quicksort in TDE is a stable, non-recursive implementation based on
  44.  * Program 2, page 851, CACM, 21 (No. 10), 1978, by Robert Sedgewick.  My
  45.  * partition algorithm finds the median-of-three.  Then, it walks from the
  46.  * head of the list, comparing nodes, and uses the first occurrence of the
  47.  * key of the median-of-three as the partition node.  Mostly by accident
  48.  * and partly by design, my partition routine uses a "fat pivot" to keep
  49.  * equal nodes in the same relative order as they appear in the file (the
  50.  * definition of a stable sort).  By using the first median-of-three node
  51.  * as the partitioning node, 1) sorting a sorted list is fairly fast and
  52.  * 2) encountering a worst case is very unlikely.  TDE will sort, fairly
  53.  * fast, multiple keys ascending or descending, ignore or match case, and
  54.  * preserve order in the file, while using a custom sort sequence for your
  55.  * favorite domestic or foreign language.
  56.  *
  57.  *
  58.  * New editor name:  TDE, the Thomson-Davis Editor.
  59.  * Author:           Frank Davis
  60.  * Date:             June 5, 1991, version 1.0
  61.  * Date:             July 29, 1991, version 1.1
  62.  * Date:             October 5, 1991, version 1.2
  63.  * Date:             January 20, 1992, version 1.3
  64.  * Date:             February 17, 1992, version 1.4
  65.  * Date:             April 1, 1992, version 1.5
  66.  * Date:             June 5, 1992, version 2.0
  67.  * Date:             October 31, 1992, version 2.1
  68.  * Date:             April 1, 1993, version 2.2
  69.  * Date:             June 5, 1993, version 3.0
  70.  *
  71.  * This code is released into the public domain, Frank Davis.
  72.  * You may use and distribute it freely.
  73.  */
  74.  
  75. #include "tdestr.h"
  76. #include "common.h"
  77. #include "tdefunc.h"
  78. #include "define.h"
  79.  
  80.  
  81. /*
  82.  * Name:    sort_box_block
  83.  * Purpose: sort lines according to text in marked BOX block
  84.  * Date:    June 5, 1992
  85.  * Passed:  window:  pointer to current window
  86.  * Notes:   quick sort and insertion sort the lines in the BOX buff according
  87.  *           to stuff in a box block.
  88.  */
  89. int  sort_box_block( WINDOW *window )
  90. {
  91. int  prompt_line;
  92. int  block_type;
  93. line_list_ptr ll;
  94. register file_infos *file;
  95. WINDOW *sw;
  96. int  rc;
  97. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  98.  
  99.    /*
  100.     * make sure block is marked OK
  101.     */
  102.    rc = OK;
  103.    prompt_line = window->bottom_line;
  104.    entab_linebuff( );
  105.    if (un_copy_line( window->ll, window, TRUE ) == ERROR)
  106.       return( ERROR );
  107.    check_block( );
  108.    if (g_status.marked == TRUE) {
  109.       file  = g_status.marked_file;
  110.       block_type = file->block_type;
  111.       if (block_type == BOX) {
  112.          /*
  113.           * sort ascending or descending?
  114.           */
  115.          rc = get_sort_order( window );
  116.          if (rc != ERROR) {
  117.             file->modified = TRUE;
  118.             if (mode.do_backups == TRUE) {
  119.                sw = g_status.window_list;
  120.                for (; ptoul( sw->file_info ) != ptoul( file );)
  121.                   sw = sw->next;
  122.                backup_file( sw );
  123.             }
  124.  
  125.             /*
  126.              * figure the width of the block.
  127.              */
  128.             sort.block_len = file->block_ec + 1 - file->block_bc;
  129.  
  130.             /*
  131.              * save the prompt line and print the quicksort message.
  132.              */
  133.             save_screen_line( 0, prompt_line, line_buff );
  134.             eol_clear( 0, prompt_line, g_display.text_color );
  135.             set_prompt( block22a, prompt_line );
  136.  
  137.             /*
  138.              * set up the sort structure.
  139.              */
  140.             sort.bc  = g_status.marked_file->block_bc;
  141.             sort.ec  = g_status.marked_file->block_ec;
  142.             sort.order_array = (mode.search_case == IGNORE) ?
  143.                                     sort_order.ignore : sort_order.match;
  144.  
  145.             /*
  146.              * save the previous node for use with insertion sort.
  147.              */
  148.             ll = file->block_start->prev;
  149.             quick_sort_block( file->block_br, file->block_er,
  150.                               file->block_start, file->block_end );
  151.  
  152.             /*
  153.              * get back previous node and clean up list with insertion
  154.              *   sort.
  155.              */
  156.             if (ll == NULL)
  157.                ll = file->line_list;
  158.             else
  159.                ll = ll->next;
  160.             set_prompt( block22b, prompt_line );
  161.             insertion_sort_block( file->block_br, file->block_er, ll );
  162.  
  163.             /*
  164.              * housekeeping.  mark the file as dirty and restore the
  165.              *   cursors, which are scrambled during the sort.
  166.              */
  167.             file->dirty = GLOBAL;
  168.             restore_cursors( file );
  169.             restore_screen_line( 0, prompt_line, line_buff );
  170.          }
  171.       } else {
  172.          /*
  173.           * can only sort box blocks
  174.           */
  175.          error( WARNING, prompt_line, block23 );
  176.          rc = ERROR;
  177.       }
  178.    } else {
  179.       /*
  180.        * box not marked
  181.        */
  182.       error( WARNING, prompt_line, block24 );
  183.       rc = ERROR;
  184.    }
  185.    return( rc );
  186. }
  187.  
  188.  
  189. /*
  190.  * Name:    quick_sort_block
  191.  * Purpose: sort lines according to text in marked BOX block
  192.  * Date:    Jaunary 10, 1993
  193.  * Passed:  low:        starting line in box block
  194.  *          high:       ending line in a box block
  195.  *          low_node:   starting node in box block
  196.  *          high_node:  ending node in box block
  197.  * Notes:   Quicksort lines in the BOX block according to keys in
  198.  *           a box block.
  199.  *          because the median of three method is used to find the partion
  200.  *           node,  high - low  should be greater than or equal to 2.
  201.  *          with end recursion removal and sorting the smallest sublist
  202.  *           first, our stack only needs room for log2 (N+1)/(M+2) nodes.
  203.  *           a stack size of 24 can reliably handle almost 500 million lines.
  204.  */
  205. void quick_sort_block( long low, long high, line_list_ptr low_node,
  206.                        line_list_ptr high_node )
  207. {
  208. long low_rline_stack[24];
  209. long high_rline_stack[24];
  210. line_list_ptr low_node_stack[24];
  211. line_list_ptr high_node_stack[24];
  212. long low_count;
  213. long high_count;
  214. long count;
  215. line_list_ptr low_start;
  216. line_list_ptr low_head;
  217. line_list_ptr low_tail;
  218. line_list_ptr high_end;
  219. line_list_ptr high_head;
  220. line_list_ptr high_tail;
  221. line_list_ptr equal_head;
  222. line_li