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