home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / thesrc15.zip / sort.c < prev    next >
C/C++ Source or Header  |  1993-11-17  |  21KB  |  540 lines
  1. /***********************************************************************/
  2. /* SORT.C - Functions related to the SORT command.                     */
  3. /***********************************************************************/
  4. /*
  5.  * THE - The Hessling Editor. A text editor similar to VM/CMS xedit.
  6.  * Copyright (C) 1991-1993 Mark Hessling
  7.  *
  8.  * This program is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU General Public License as
  10.  * published by the Free Software Foundation; either version 2 of
  11.  * the License, or any later version.
  12.  *
  13.  * This program is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16.  * General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU General Public License
  19.  * along with this program; if not, write to:
  20.  *
  21.  *    The Free Software Foundation, Inc.
  22.  *    675 Mass Ave,
  23.  *    Cambridge, MA 02139 USA.
  24.  *
  25.  *
  26.  * If you make modifications to this software that you feel increases
  27.  * it usefulness for the rest of the community, please email the
  28.  * changes, enhancements, bug fixes as well as any and all ideas to me.
  29.  * This software is going to be maintained and enhanced as deemed
  30.  * necessary by the community.
  31.  *
  32.  * Mark Hessling                     email: M.Hessling@gu.edu.au
  33.  * 36 David Road                     Phone: +61 7 849 7731
  34.  * Holland Park                      Fax:   +61 7 875 5314
  35.  * QLD 4121
  36.  * Australia
  37.  */
  38.  
  39. /*
  40. $Header: C:\THE\RCS\sort.c 1.4 1993/09/01 16:25:34 MH Interim MH $
  41. */
  42.  
  43. #include <stdio.h>
  44.  
  45. #include "the.h"
  46. #include "proto.h"
  47.  
  48.  
  49. static int cmp();                /* this deliberately has no prototype */
  50.  
  51. #define MAX_SORT_FIELDS 10
  52.  
  53. #define SF_ERROR    0
  54. #define SF_START    1
  55. #define SF_ORDER    2
  56. #define SF_LEFT     3
  57.  
  58. struct sort_field
  59.  {
  60.   char order;                         /* A - ascending, D - descending */
  61.   int left_col;                                         /* left column */
  62.   int right_col;                                       /* right column */
  63.  };
  64. typedef struct sort_field SORT_FIELD;
  65.  
  66. char *sort_field_1;
  67. char *sort_field_2;
  68.  
  69. SORT_FIELD sort_fields[MAX_SORT_FIELDS];
  70.  
  71. int num_fields;
  72.  
  73. /*-------------------------- external data ----------------------------*/
  74. extern VIEW_DETAILS *vd_current,*vd_first,*vd_mark;
  75. extern char current_screen;
  76. /***********************************************************************/
  77. #ifdef PROTO
  78. int execute_sort(char *params)
  79. #else
  80. int execute_sort(params)
  81. #endif
  82. /***********************************************************************/
  83. {
  84. /*-------------------------- external data ----------------------------*/
  85.  extern char in_profile;   /* indicates if processing profile */
  86.  extern char *temp_cmd;
  87. /*--------------------------- local data ------------------------------*/
  88. #define SOR_PARAMS  32
  89.  char *word[SOR_PARAMS+1];
  90.  unsigned short num_params;
  91.  LINE **lfirst,**lp,*curr,*first,*last;
  92.  long num_lines,i,true_line;
  93.  int rc,max_column_width=0;
  94.  int left_col,right_col,state;
  95.  char order='A';
  96. /*--------------------------- processing ------------------------------*/
  97. #ifdef TRACE
  98.  trace_function("sort.c:    execute_sort");
  99. #endif
  100. /*---------------------------------------------------------------------*/
  101. /* Parse the parameters and set up the sort_fields[] array with valid  */
  102. /* values.                                                             */
  103. /*---------------------------------------------------------------------*/
  104.  num_params = param_split(params,word,SOR_PARAMS,WORD_DELIMS,TEMP_PARAM);
  105.  true_line = get_true_line();
  106.  if ((num_lines = valid_target(word[0],true_line)) == TARGET_ERROR)
  107.    {
  108.     display_error(4,(char *)word[0]);
  109. #ifdef TRACE
  110.     trace_return();
  111. #endif
  112.     return(RC_TARGET_NOT_FOUND);
  113.    }
  114. /*---------------------------------------------------------------------*/
  115. /* Handle special targets of BLOCK and ALL. Set default columns to be  */
  116. /* ZONE settings if not sort field(s) or BLOCK specified and it is BOX */
  117. /* BLOCK.                                                              */
  118. /*---------------------------------------------------------------------*/
  119.  if (equal((char *)"all",word[0],3))
  120.     true_line = 1L;
  121.  if (equal((char *)"block",word[0],5))
  122.    {
  123.     if (marked_block(TRUE) != RC_OK)
  124.       {
  125. #ifdef TRACE
  126.        trace_return();
  127. #endif
  128.        return(RC_INVALID_ENVIRON);
  129.       }
  130.     num_lines = MARK_VIEW->mark_end_line-MARK_VIEW->mark_start_line+1L;
  131.     true_line = MARK_VIEW->mark_start_line;
  132.    }
  133. /*---------------------------------------------------------------------*/
  134. /* If the true_line is on the top or bottom of file lines and we are   */
  135. /* searching forward or backward respectively, set the true_line to be */
  136. /* the next line in the appropriate direction and reduce the number of */
  137. /* lines to sort by 1.                                                 */
  138. /*---------------------------------------------------------------------*/
  139.  if (!equal((char *)"all",word[0],3))
  140.    {
  141.     if (CURRENT_VIEW->current_window == WINDOW_COMMAND
  142.     || in_profile)
  143.       {
  144.        if (TOF(true_line))
  145.          {
  146.           true_line++;
  147.           if (!valid_integer(word[0]))
  148.              num_lines = (num_lines == 0) ? 0 : num_lines - 1;
  149.          }
  150.        if (BOF(true_line))
  151.          {
  152.           true_line--;
  153.           if (!valid_integer(word[0]))
  154.              num_lines = (num_lines == 0) ? 0 : num_lines + 1;
  155.          }
  156.       }
  157.     else
  158.       {
  159.        if (TOF(true_line) || BOF(true_line))
  160.          {
  161.           display_error(38,(char *)"");
  162. #ifdef TRACE
  163.           trace_return();
  164. #endif
  165.           return(RC_INVALID_ENVIRON);
  166.          }
  167.       }
  168.    }
  169. /*---------------------------------------------------------------------*/
  170. /* If the number of lines is negative, adjust the true line and make   */
  171. /* the number of lines positive.                                       */
  172. /*---------------------------------------------------------------------*/
  173.  if (num_lines < 0)
  174.    {
  175.     true_line = true_line + num_lines + 1;
  176.     num_lines = -num_lines;
  177.    }
  178. /*---------------------------------------------------------------------*/
  179. /* Don't need to do anything if < 2 lines to be sorted.                */
  180. /*---------------------------------------------------------------------*/
  181.  if (num_lines < 2)
  182.    {
  183.     display_error(55,(char *)"");
  184. #ifdef TRACE
  185.     trace_return();
  186. #endif
  187.     return(RC_OK);
  188.    }
  189. /*---------------------------------------------------------------------*/
  190. /* Process parameters differently, depending on the number...          */
  191. /* 1 parameter (target only) - if BOX BLOCK, then the sort field will  */
  192. /*                             be the block columns, otherwise ZONE    */
  193. /*                             settings will be used.                  */
  194. /* 2 parameters (target & order) - same as above but also validate the */
  195. /*                                 ordering value.                     */
  196. /* > 2 parameters (target & sort fields) - validate each parameter.    */
  197. /*---------------------------------------------------------------------*/
  198.  switch(num_params)
  199.    {
  200.     case 1:
  201.     case 2:
  202.            sort_fields[0].left_col = CURRENT_VIEW->zone_start;
  203.            sort_fields[0].right_col = CURRENT_VIEW->zone_end;
  204.            sort_fields[0].order = order;
  205.            num_fields = 1;
  206.            if (equal((char *)"block",word[0],5)
  207.            &&  MARK_VIEW->mark_type == M_BOX)
  208.               {
  209.                sort_fields[0].left_col = MARK_VIEW->mark_start_col;
  210.                sort_fields[0].right_col = MARK_VIEW->mark_end_col;
  211.               }
  212. /*---------------------------------------------------------------------*/
  213. /* No more processing if only 1 parameter.                             */
  214. /*---------------------------------------------------------------------*/
  215.            if (num_params == 1)
  216.               break;
  217. /*---------------------------------------------------------------------*/
  218. /* Processing for 2 parameters; validate ordering value.               */
  219. /*---------------------------------------------------------------------*/
  220.            if (equal((char *)"ascending",word[1],1)
  221.            ||  equal((char *)"descending",word[1],1))
  222.              {
  223.               order = word[1][0];
  224.               if (islower(order))
  225.                  order = toupper(order);
  226.               sort_fields[0].order = order;
  227.               break;
  228.              }
  229. /*---------------------------------------------------------------------*/
  230. /* If the parameter is not Ascending or Descending, display error.     */
  231. /*---------------------------------------------------------------------*/
  232.            display_error(1,(char *)word[1]);
  233. #ifdef TRACE
  234.            trace_return();
  235. #endif
  236.            return(RC_INVALID_OPERAND);
  237.            break;
  238. /*---------------------------------------------------------------------*/
  239. /* More than 2 parameters; sort field(s) are being specified.          */
  240. /*---------------------------------------------------------------------*/
  241.     default:
  242.            i = 1;
  243.            num_fields = 0;
  244.            state = SF_START;
  245.            while(1)
  246.              {
  247.               switch(state)
  248.                 {
  249.                  case SF_START:
  250.                       if (equal((char *)"ascending",word[i],1)
  251.                       ||  equal((char *)"descending",word[i],1))
  252.                         {
  253.                          order = word[i][0];
  254.                          if (islower(order))
  255.                             order = toupper(order);
  256.                          sort_fields[num_fields].order = order;
  257.                          state = SF_ORDER;
  258.                          i++;
  259.                          break;
  260.                         }
  261.                       left_col = atoi(word[i]);
  262.                       if (left_col == 0)
  263.                         {
  264.                          state = SF_ERROR;
  265.                          break;
  266.                         }
  267.                       sort_fields[num_fields].order = order;
  268.                       sort_fields[num_fields].left_col = left_col;
  269.                       state = SF_LEFT;
  270.                       i++;
  271.                       break;
  272.                  case SF_ORDER:
  273.                       left_col = atoi(word[i]);
  274.                       if (left_col < 1)
  275.                         {
  276.                          state = SF_ERROR;
  277.                          break;
  278.                         }
  279.                       sort_fields[num_fields].left_col = left_col;
  280.                       state = SF_LEFT;
  281.                       i++;
  282.                       break;
  283.                  case SF_LEFT:
  284.                       right_col = atoi(word[i]);
  285.                       if (right_col < 1)
  286.                         {
  287.                          state = SF_ERROR;
  288.                          break;
  289.                         }
  290.                       sort_fields[num_fields].right_col = right_col;
  291.                       if (right_col < left_col)
  292.                         {
  293.                          state = SF_ERROR;
  294.                          break;
  295.                         }
  296.                       state = SF_START;
  297.                       i++;
  298.                       num_fields++;
  299.                       break;
  300.                  default:
  301.                       state = SF_ERROR;
  302.                       break;
  303.                 }
  304. /*---------------------------------------------------------------------*/
  305. /* If we have an error, display a message...                           */
  306. /*---------------------------------------------------------------------*/
  307.               if (state == SF_ERROR)
  308.                 {
  309.                  display_error(1,(char *)word[i]);
  310. #ifdef TRACE
  311.                  trace_return();
  312. #endif
  313.                  return(RC_INVALID_OPERAND);
  314.                 }
  315. /*---------------------------------------------------------------------*/
  316. /* If we have run out of parameters...                                 */
  317. /*---------------------------------------------------------------------*/
  318.               if (i == num_params)
  319.                 {
  320. /*---------------------------------------------------------------------*/
  321. /* ...then if we have the correct number of parameters, OK.            */
  322. /*---------------------------------------------------------------------*/
  323.                  if (state == SF_START)
  324.                     break;
  325.                  else
  326. /*---------------------------------------------------------------------*/
  327. /* ...otherwise display an error.                                      */
  328. /*---------------------------------------------------------------------*/
  329.                    {
  330.                     display_error(1,(char *)params);
  331. #ifdef TRACE
  332.                     trace_return();
  333. #endif
  334.                     return(RC_INVALID_OPERAND);
  335.                    }
  336.                 }
  337.              }
  338.            break;
  339.    }
  340. /*---------------------------------------------------------------------*/
  341. /* Determine the maximum length of a sort field.                       */
  342. /*---------------------------------------------------------------------*/
  343.  for (i=0;i<num_fields;i++)
  344.     max_column_width = max(max_column_width,
  345.                 sort_fields[i].right_col - sort_fields[i].left_col + 1);
  346. /*---------------------------------------------------------------------*/
  347. /* Allocate memory for num_lines of LINE pointers.                     */
  348. /*---------------------------------------------------------------------*/
  349.  if ((lfirst = (LINE **)calloc(num_lines,sizeof(LINE *))) == NULL)
  350.    {
  351.     display_error(30,(char *)"");
  352. #ifdef TRACE
  353.     trace_return();
  354. #endif
  355.     return(RC_OUT_OF_MEMORY);
  356.    }
  357. /*---------------------------------------------------------------------*/
  358. /* Allocate memory for each of the temporary sort fields to the length */
  359. /* of the maximum field width.                                         */
  360. /*---------------------------------------------------------------------*/
  361.  if ((sort_field_1 = (char *)malloc(max_column_width)) == NULL)
  362.    {
  363.     display_error(30,(char *)"");
  364. #ifdef TRACE
  365.     trace_return();
  366. #endif
  367.     return(RC_OUT_OF_MEMORY);
  368.    }
  369.  if ((sort_field_2 = (char *)malloc(max_column_width)) == NULL)
  370.    {
  371.     display_error(30,(char *)"");
  372. #ifdef TRACE
  373.     trace_return();
  374. #endif
  375.     return(RC_OUT_OF_MEMORY);
  376.    }
  377. /*---------------------------------------------------------------------*/
  378. /* Assign the values of the newly allocated array to the LINE pointers */
  379. /* for the target lines.                                               */
  380. /*---------------------------------------------------------------------*/
  381. #ifdef USE_VOID
  382.  first = curr = (LINE *)ll_find((void *)CURRENT_FILE->first_line,true_line);
  383. #else
  384.  first = curr = lll_find(CURRENT_FILE->first_line,true_line);
  385. #endif
  386.  lp = lfirst;
  387.  for (i=0;i<num_lines;i++)
  388.    {
  389.     lp[i] = curr;
  390.     curr = curr->next;
  391.    }
  392.  last = curr;
  393. /*---------------------------------------------------------------------*/
  394. /* Sort the target array...                                            */
  395. /*---------------------------------------------------------------------*/
  396.  qsort(lfirst,num_lines,sizeof(LINE *),cmp);
  397. /*---------------------------------------------------------------------*/
  398. /* Merge  the sorted array pointers into the linked list...            */
  399. /*---------------------------------------------------------------------*/
  400.  lp = lfirst;
  401.  first->prev->next = lp[0];
  402.  for (i=0;i<num_lines;i++)
  403.    {
  404.     if (i == 0)
  405.       {
  406.        lp[0]->prev = first->prev;
  407.        lp[0]->next = lp[1];
  408.       }
  409.     else 
  410.        if (i == num_lines - 1)
  411.          {
  412.           lp[num_lines-1]->next = last;
  413.           lp[num_lines-1]->prev = lp[num_lines-2];
  414.           last->prev = lp[num_lines-1];
  415.          }
  416.        else
  417.          {
  418.           lp[i]->next = lp[i+1];
  419.           lp[i]->prev = lp[i-1];
  420.          }
  421.    }
  422. #if 0
  423.  lp->prev = first->prev;
  424.  lp->next = lp[1];
  425.  for (i=1;i<num_lines-1;i++)
  426.    {
  427.     lp[i]->next = lp[i+1];
  428.     lp[i]->prev = lp[i-1];
  429.    }
  430.  lp[num_lines-1]->next = last;
  431.  lp[num_lines-1]->prev = lp[num_lines-2];
  432.  last->prev = lp[num_lines];
  433. #endif
  434. /*---------------------------------------------------------------------*/
  435. /* Free up the memory used for the sort fields and the target array.   */
  436. /*---------------------------------------------------------------------*/
  437.  free(sort_field_1);
  438.  free(sort_field_2);
  439.  free(lfirst);
  440. /*---------------------------------------------------------------------*/
  441. /* Increment alteration count...                                       */
  442. /*---------------------------------------------------------------------*/
  443.  if ((rc = increment_alt(CURRENT_FILE)) != RC_OK)
  444.    {
  445. #ifdef TRACE
  446.     trace_return();
  447. #endif
  448.     return(rc);
  449.    }
  450.  sprintf(temp_cmd,"%d line(s) sorted",num_lines);
  451.  display_error(0,temp_cmd);
  452. #ifdef TRACE
  453.  trace_return();
  454. #endif
  455.  return(RC_OK);
  456. }
  457. /***********************************************************************/
  458. #ifdef PROTO
  459. static int cmp(LINE **first,LINE **second)
  460. #else
  461. static int cmp(first,second)
  462. LINE **first,**second;
  463. #endif
  464. /***********************************************************************/
  465. {
  466. /*--------------------------- local data ------------------------------*/
  467.  register int i,j;
  468.  int len,rc,right_col,left_col;
  469.  LINE *one = *first;
  470.  LINE *two = *second;
  471. /*--------------------------- processing ------------------------------*/
  472. /*---------------------------------------------------------------------*/
  473. /* For each sort field defined in the array sort_fields, compare the   */
  474. /* value of both lines for the specified column range.                 */
  475. /*---------------------------------------------------------------------*/
  476.  for (i=0;i<num_fields;i++)
  477.     {
  478. /*---------------------------------------------------------------------*/
  479. /* Calculate the length of the sort field.                             */
  480. /*---------------------------------------------------------------------*/
  481.      len = sort_fields[i].right_col - sort_fields[i].left_col + 1;
  482. /*---------------------------------------------------------------------*/
  483. /* Set the two temporary fields to blanks.                             */
  484. /*---------------------------------------------------------------------*/
  485.      memset(sort_field_1,' ',len);
  486.      memset(sort_field_2,' ',len);
  487. /*---------------------------------------------------------------------*/
  488. /* For the first line to be compared, extract the portion of the line  */
  489. /* that corresponds with the current sort column...                    */
  490. /*---------------------------------------------------------------------*/
  491.      right_col = min(sort_fields[i].right_col,one->length);
  492.      left_col = min(sort_fields[i].left_col,one->length);
  493. /*---------------------------------------------------------------------*/
  494. /* If the sort column lies after the end of the line, leave the        */
  495. /* contents of the sort field blank.                                   */
  496. /*---------------------------------------------------------------------*/
  497.      if (sort_fields[i].left_col <= one->length)
  498.         memcpy(sort_field_1,one->line+left_col-1,right_col-left_col+1);
  499. /*---------------------------------------------------------------------*/
  500. /* For the next  line to be compared, extract the portion of the line  */
  501. /* that corresponds with the current sort column...                    */
  502. /*---------------------------------------------------------------------*/
  503.      right_col = min(sort_fields[i].right_col,two->length);
  504.      left_col = min(sort_fields[i].left_col,two->length);
  505. /*---------------------------------------------------------------------*/
  506. /* If the sort column lies after the end of the line, leave the        */
  507. /* contents of the sort field blank.                                   */
  508. /*---------------------------------------------------------------------*/
  509.      if (sort_fields[i].left_col <= two->length)
  510.         memcpy(sort_field_2,two->line+left_col-1,right_col-left_col+1);
  511. /*---------------------------------------------------------------------*/
  512. /* If CASE IGNORE is on for the current view, set both sort fields to  */
  513. /* uppercase for the comparison.                                       */
  514. /*---------------------------------------------------------------------*/
  515.      if (CURRENT_VIEW->case_sort == CASE_IGNORE)
  516.        {
  517.         for (j=0;j<len;j++)
  518.           {
  519.            if (islower(sort_field_1[j]))
  520.               sort_field_1[j] = toupper(sort_field_1[j]);
  521.            if (islower(sort_field_2[j]))
  522.               sort_field_2[j] = toupper(sort_field_2[j]);
  523.           }
  524.        }
  525. /*---------------------------------------------------------------------*/
  526. /* If the two sort fields are equal, continue the sort with the next   */
  527. /* sort field value. If the sort fields are different, return with the */
  528. /* the comparison value (if ASCENDING) or the comparison value negated */
  529. /* (if DESCENDING).                                                    */
  530. /*---------------------------------------------------------------------*/
  531.      if ((rc = strncmp(sort_field_1,sort_field_2,len)) != 0)
  532.         return((sort_fields[i].order == 'A') ? rc : -rc);
  533.     }
  534. /*---------------------------------------------------------------------*/
  535. /* To get to here, the result of sorting on all fields has resulted in */
  536. /* both lines being equal. Return with 0 to indicate this.             */
  537. /*---------------------------------------------------------------------*/
  538.  return(0);
  539. }
  540.