1/*
2 * tkTableCell.c --
3 *
4 *	This module implements cell sort functions for table
5 *	widgets.  The MergeSort algorithm and other aux sorting
6 *	functions were taken from tclCmdIL.c lsort command:
7
8 * tclCmdIL.c --
9 *
10 *	This file contains the top-level command routines for most of
11 *	the Tcl built-in commands whose names begin with the letters
12 *	I through L.  It contains only commands in the generic core
13 *	(i.e. those that don't depend much upon UNIX facilities).
14 *
15 * Copyright (c) 1987-1993 The Regents of the University of California.
16 * Copyright (c) 1993-1997 Lucent Technologies.
17 * Copyright (c) 1994-1997 Sun Microsystems, Inc.
18 * Copyright (c) 1998-1999 by Scriptics Corporation.
19
20 *
21 * Copyright (c) 1998-2002 Jeffrey Hobbs
22 *
23 * See the file "license.terms" for information on usage and redistribution
24 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
25 *
26 */
27
28#include "tkTable.h"
29
30#ifndef UCHAR
31#define UCHAR(c) ((unsigned char) (c))
32#endif
33
34/*
35 * During execution of the "lsort" command, structures of the following
36 * type are used to arrange the objects being sorted into a collection
37 * of linked lists.
38 */
39
40typedef struct SortElement {
41    Tcl_Obj *objPtr;			/* Object being sorted. */
42    struct SortElement *nextPtr;        /* Next element in the list, or
43					 * NULL for end of list. */
44} SortElement;
45
46static int		TableSortCompareProc _ANSI_ARGS_((CONST VOID *first,
47							  CONST VOID *second));
48static SortElement *    MergeSort _ANSI_ARGS_((SortElement *headPt));
49static SortElement *    MergeLists _ANSI_ARGS_((SortElement *leftPtr,
50						SortElement *rightPtr));
51static int		DictionaryCompare _ANSI_ARGS_((char *left,
52						       char *right));
53
54/*
55 *----------------------------------------------------------------------
56 *
57 * TableSortCompareProc --
58 *	This procedure is invoked by qsort to determine the proper
59 *	ordering between two elements.
60 *
61 * Results:
62 *	< 0 means first is "smaller" than "second", > 0 means "first"
63 *	is larger than "second", and 0 means they should be treated
64 *	as equal.
65 *
66 * Side effects:
67 *	None, unless a user-defined comparison command does something
68 *	weird.
69 *
70 *----------------------------------------------------------------------
71 */
72static int
73TableSortCompareProc(first, second)
74    CONST VOID *first, *second;		/* Elements to be compared. */
75{
76    char *str1 = *((char **) first);
77    char *str2 = *((char **) second);
78
79    return DictionaryCompare(str1, str2);
80}
81
82/*
83 *----------------------------------------------------------------------
84 *
85 * TableCellSort --
86 *	Sort a list of table cell elements (of form row,col)
87 *
88 * Results:
89 *	Returns the sorted list of elements.  Because Tcl_Merge allocs
90 *	the space for result, it must later be Tcl_Free'd by caller.
91 *
92 * Side effects:
93 *	Behaviour undefined for ill-formed input list of elements.
94 *
95 *----------------------------------------------------------------------
96 */
97char *
98TableCellSort(Table *tablePtr, char *str)
99{
100    int listArgc;
101    CONST84 char **listArgv;
102    char *result;
103
104    if (Tcl_SplitList(tablePtr->interp, str, &listArgc, &listArgv) != TCL_OK) {
105	return str;
106    }
107    /* Thread safety: qsort is reportedly not thread-safe... */
108    qsort((VOID *) listArgv, (size_t) listArgc, sizeof (char *),
109	  TableSortCompareProc);
110    result = Tcl_Merge(listArgc, listArgv);
111    ckfree((char *) listArgv);
112    return result;
113}
114
115/*
116 *----------------------------------------------------------------------
117 *
118 * DictionaryCompare - Not the Unicode version
119 *
120 *	This function compares two strings as if they were being used in
121 *	an index or card catalog.  The case of alphabetic characters is
122 *	ignored, except to break ties.  Thus "B" comes before "b" but
123 *	after "a".  Also, integers embedded in the strings compare in
124 *	numerical order.  In other words, "x10y" comes after "x9y", not
125 *      before it as it would when using strcmp().
126 *
127 * Results:
128 *      A negative result means that the first element comes before the
129 *      second, and a positive result means that the second element
130 *      should come first.  A result of zero means the two elements
131 *      are equal and it doesn't matter which comes first.
132 *
133 * Side effects:
134 *	None.
135 *
136 *----------------------------------------------------------------------
137 */
138
139static int
140DictionaryCompare(left, right)
141    char *left, *right;          /* The strings to compare */
142{
143    int diff, zeros;
144    int secondaryDiff = 0;
145
146    while (1) {
147	if (isdigit(UCHAR(*right)) && isdigit(UCHAR(*left))) {
148	    /*
149	     * There are decimal numbers embedded in the two
150	     * strings.  Compare them as numbers, rather than
151	     * strings.  If one number has more leading zeros than
152	     * the other, the number with more leading zeros sorts
153	     * later, but only as a secondary choice.
154	     */
155
156	    zeros = 0;
157	    while ((*right == '0') && (isdigit(UCHAR(right[1])))) {
158		right++;
159		zeros--;
160	    }
161	    while ((*left == '0') && (isdigit(UCHAR(left[1])))) {
162		left++;
163		zeros++;
164	    }
165	    if (secondaryDiff == 0) {
166		secondaryDiff = zeros;
167	    }
168
169	    /*
170	     * The code below compares the numbers in the two
171	     * strings without ever converting them to integers.  It
172	     * does this by first comparing the lengths of the
173	     * numbers and then comparing the digit values.
174	     */
175
176	    diff = 0;
177	    while (1) {
178		if (diff == 0) {
179		    diff = UCHAR(*left) - UCHAR(*right);
180		}
181		right++;
182		left++;
183		if (!isdigit(UCHAR(*right))) {
184		    if (isdigit(UCHAR(*left))) {
185			return 1;
186		    } else {
187			/*
188			 * The two numbers have the same length. See
189			 * if their values are different.
190			 */
191
192			if (diff != 0) {
193			    return diff;
194			}
195			break;
196		    }
197		} else if (!isdigit(UCHAR(*left))) {
198		    return -1;
199		}
200	    }
201	    continue;
202	}
203        diff = UCHAR(*left) - UCHAR(*right);
204        if (diff) {
205            if (isupper(UCHAR(*left)) && islower(UCHAR(*right))) {
206                diff = UCHAR(tolower(*left)) - UCHAR(*right);
207                if (diff) {
208		    return diff;
209                } else if (secondaryDiff == 0) {
210		    secondaryDiff = -1;
211                }
212            } else if (isupper(UCHAR(*right)) && islower(UCHAR(*left))) {
213                diff = UCHAR(*left) - UCHAR(tolower(UCHAR(*right)));
214                if (diff) {
215		    return diff;
216                } else if (secondaryDiff == 0) {
217		    secondaryDiff = 1;
218                }
219            } else {
220                return diff;
221            }
222        }
223        if (*left == 0) {
224	    break;
225	}
226        left++;
227        right++;
228    }
229    if (diff == 0) {
230	diff = secondaryDiff;
231    }
232    return diff;
233}
234
235/*
236 *----------------------------------------------------------------------
237 *
238 * MergeLists -
239 *
240 *	This procedure combines two sorted lists of SortElement structures
241 *	into a single sorted list.
242 *
243 * Results:
244 *      The unified list of SortElement structures.
245 *
246 * Side effects:
247 *	None, unless a user-defined comparison command does something
248 *	weird.
249 *
250 *----------------------------------------------------------------------
251 */
252
253static SortElement *
254MergeLists(leftPtr, rightPtr)
255    SortElement *leftPtr;               /* First list to be merged; may be
256					 * NULL. */
257    SortElement *rightPtr;              /* Second list to be merged; may be
258					 * NULL. */
259{
260    SortElement *headPtr;
261    SortElement *tailPtr;
262
263    if (leftPtr == NULL) {
264        return rightPtr;
265    }
266    if (rightPtr == NULL) {
267        return leftPtr;
268    }
269    if (DictionaryCompare(Tcl_GetString(leftPtr->objPtr),
270			  Tcl_GetString(rightPtr->objPtr)) > 0) {
271	tailPtr = rightPtr;
272	rightPtr = rightPtr->nextPtr;
273    } else {
274	tailPtr = leftPtr;
275	leftPtr = leftPtr->nextPtr;
276    }
277    headPtr = tailPtr;
278    while ((leftPtr != NULL) && (rightPtr != NULL)) {
279	if (DictionaryCompare(Tcl_GetString(leftPtr->objPtr),
280			      Tcl_GetString(rightPtr->objPtr)) > 0) {
281	    tailPtr->nextPtr = rightPtr;
282	    tailPtr = rightPtr;
283	    rightPtr = rightPtr->nextPtr;
284	} else {
285	    tailPtr->nextPtr = leftPtr;
286	    tailPtr = leftPtr;
287	    leftPtr = leftPtr->nextPtr;
288	}
289    }
290    if (leftPtr != NULL) {
291       tailPtr->nextPtr = leftPtr;
292    } else {
293       tailPtr->nextPtr = rightPtr;
294    }
295    return headPtr;
296}
297
298/*
299 *----------------------------------------------------------------------
300 *
301 * MergeSort -
302 *
303 *	This procedure sorts a linked list of SortElement structures
304 *	use the merge-sort algorithm.
305 *
306 * Results:
307 *      A pointer to the head of the list after sorting is returned.
308 *
309 * Side effects:
310 *	None, unless a user-defined comparison command does something
311 *	weird.
312 *
313 *----------------------------------------------------------------------
314 */
315
316static SortElement *
317MergeSort(headPtr)
318    SortElement *headPtr;               /* First element on the list */
319{
320    /*
321     * The subList array below holds pointers to temporary lists built
322     * during the merge sort.  Element i of the array holds a list of
323     * length 2**i.
324     */
325
326#   define NUM_LISTS 30
327    SortElement *subList[NUM_LISTS];
328    SortElement *elementPtr;
329    int i;
330
331    for(i = 0; i < NUM_LISTS; i++){
332        subList[i] = NULL;
333    }
334    while (headPtr != NULL) {
335	elementPtr = headPtr;
336	headPtr = headPtr->nextPtr;
337	elementPtr->nextPtr = 0;
338	for (i = 0; (i < NUM_LISTS) && (subList[i] != NULL); i++){
339	    elementPtr = MergeLists(subList[i], elementPtr);
340	    subList[i] = NULL;
341	}
342	if (i >= NUM_LISTS) {
343	    i = NUM_LISTS-1;
344	}
345	subList[i] = elementPtr;
346    }
347    elementPtr = NULL;
348    for (i = 0; i < NUM_LISTS; i++){
349        elementPtr = MergeLists(subList[i], elementPtr);
350    }
351    return elementPtr;
352}
353
354#ifndef NO_SORT_CELLS
355/*
356 *----------------------------------------------------------------------
357 *
358 * TableCellSortObj --
359 *	Sorts a list of table cell elements (of form row,col) in place
360 *
361 * Results:
362 *	Sorts list of elements in place.
363 *
364 * Side effects:
365 *	Behaviour undefined for ill-formed input list of elements.
366 *
367 *----------------------------------------------------------------------
368 */
369Tcl_Obj *
370TableCellSortObj(Tcl_Interp *interp, Tcl_Obj *listObjPtr)
371{
372    int length, i;
373    Tcl_Obj *sortedObjPtr, **listObjPtrs;
374    SortElement *elementArray;
375    SortElement *elementPtr;
376
377    if (Tcl_ListObjGetElements(interp, listObjPtr,
378			       &length, &listObjPtrs) != TCL_OK) {
379	return NULL;
380    }
381    if (length <= 0) {
382	return listObjPtr;
383    }
384
385    elementArray = (SortElement *) ckalloc(length * sizeof(SortElement));
386    for (i=0; i < length; i++){
387	elementArray[i].objPtr = listObjPtrs[i];
388	elementArray[i].nextPtr = &elementArray[i+1];
389    }
390    elementArray[length-1].nextPtr = NULL;
391    elementPtr = MergeSort(elementArray);
392    sortedObjPtr = Tcl_NewObj();
393    for (; elementPtr != NULL; elementPtr = elementPtr->nextPtr){
394	Tcl_ListObjAppendElement(NULL, sortedObjPtr, elementPtr->objPtr);
395    }
396    ckfree((char*) elementArray);
397
398    return sortedObjPtr;
399}
400#endif
401