| 1 | '\" |
| 2 | '\" Copyright (c) 1993 The Regents of the University of California. |
| 3 | '\" Copyright (c) 1994-1996 Sun Microsystems, Inc. |
| 4 | '\" Copyright (c) 1999 Scriptics Corporation |
| 5 | '\" Copyright (c) 2001 Kevin B. Kenny. All rights reserved. |
| 6 | '\" |
| 7 | '\" See the file "license.terms" for information on usage and redistribution |
| 8 | '\" of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
| 9 | '\" |
| 10 | '\" RCS: @(#) $Id: lsort.n,v 1.12.4.2 2004/10/27 12:52:40 dkf Exp $ |
| 11 | '\" |
| 12 | '\" The definitions below are for supplemental macros used in Tcl/Tk |
| 13 | '\" manual entries. |
| 14 | '\" |
| 15 | '\" .AP type name in/out ?indent? |
| 16 | '\" Start paragraph describing an argument to a library procedure. |
| 17 | '\" type is type of argument (int, etc.), in/out is either "in", "out", |
| 18 | '\" or "in/out" to describe whether procedure reads or modifies arg, |
| 19 | '\" and indent is equivalent to second arg of .IP (shouldn't ever be |
| 20 | '\" needed; use .AS below instead) |
| 21 | '\" |
| 22 | '\" .AS ?type? ?name? |
| 23 | '\" Give maximum sizes of arguments for setting tab stops. Type and |
| 24 | '\" name are examples of largest possible arguments that will be passed |
| 25 | '\" to .AP later. If args are omitted, default tab stops are used. |
| 26 | '\" |
| 27 | '\" .BS |
| 28 | '\" Start box enclosure. From here until next .BE, everything will be |
| 29 | '\" enclosed in one large box. |
| 30 | '\" |
| 31 | '\" .BE |
| 32 | '\" End of box enclosure. |
| 33 | '\" |
| 34 | '\" .CS |
| 35 | '\" Begin code excerpt. |
| 36 | '\" |
| 37 | '\" .CE |
| 38 | '\" End code excerpt. |
| 39 | '\" |
| 40 | '\" .VS ?version? ?br? |
| 41 | '\" Begin vertical sidebar, for use in marking newly-changed parts |
| 42 | '\" of man pages. The first argument is ignored and used for recording |
| 43 | '\" the version when the .VS was added, so that the sidebars can be |
| 44 | '\" found and removed when they reach a certain age. If another argument |
| 45 | '\" is present, then a line break is forced before starting the sidebar. |
| 46 | '\" |
| 47 | '\" .VE |
| 48 | '\" End of vertical sidebar. |
| 49 | '\" |
| 50 | '\" .DS |
| 51 | '\" Begin an indented unfilled display. |
| 52 | '\" |
| 53 | '\" .DE |
| 54 | '\" End of indented unfilled display. |
| 55 | '\" |
| 56 | '\" .SO |
| 57 | '\" Start of list of standard options for a Tk widget. The |
| 58 | '\" options follow on successive lines, in four columns separated |
| 59 | '\" by tabs. |
| 60 | '\" |
| 61 | '\" .SE |
| 62 | '\" End of list of standard options for a Tk widget. |
| 63 | '\" |
| 64 | '\" .OP cmdName dbName dbClass |
| 65 | '\" Start of description of a specific option. cmdName gives the |
| 66 | '\" option's name as specified in the class command, dbName gives |
| 67 | '\" the option's name in the option database, and dbClass gives |
| 68 | '\" the option's class in the option database. |
| 69 | '\" |
| 70 | '\" .UL arg1 arg2 |
| 71 | '\" Print arg1 underlined, then print arg2 normally. |
| 72 | '\" |
| 73 | '\" RCS: @(#) $Id: man.macros,v 1.4 2000/08/25 06:18:32 ericm Exp $ |
| 74 | '\" |
| 75 | '\" # Set up traps and other miscellaneous stuff for Tcl/Tk man pages. |
| 76 | .if t .wh -1.3i ^B |
| 77 | .nr ^l \n(.l |
| 78 | .ad b |
| 79 | '\" # Start an argument description |
| 80 | .de AP |
| 81 | .ie !"\\$4"" .TP \\$4 |
| 82 | .el \{\ |
| 83 | . ie !"\\$2"" .TP \\n()Cu |
| 84 | . el .TP 15 |
| 85 | .\} |
| 86 | .ta \\n()Au \\n()Bu |
| 87 | .ie !"\\$3"" \{\ |
| 88 | \&\\$1 \\fI\\$2\\fP (\\$3) |
| 89 | .\".b |
| 90 | .\} |
| 91 | .el \{\ |
| 92 | .br |
| 93 | .ie !"\\$2"" \{\ |
| 94 | \&\\$1 \\fI\\$2\\fP |
| 95 | .\} |
| 96 | .el \{\ |
| 97 | \&\\fI\\$1\\fP |
| 98 | .\} |
| 99 | .\} |
| 100 | .. |
| 101 | '\" # define tabbing values for .AP |
| 102 | .de AS |
| 103 | .nr )A 10n |
| 104 | .if !"\\$1"" .nr )A \\w'\\$1'u+3n |
| 105 | .nr )B \\n()Au+15n |
| 106 | .\" |
| 107 | .if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n |
| 108 | .nr )C \\n()Bu+\\w'(in/out)'u+2n |
| 109 | .. |
| 110 | .AS Tcl_Interp Tcl_CreateInterp in/out |
| 111 | '\" # BS - start boxed text |
| 112 | '\" # ^y = starting y location |
| 113 | '\" # ^b = 1 |
| 114 | .de BS |
| 115 | .br |
| 116 | .mk ^y |
| 117 | .nr ^b 1u |
| 118 | .if n .nf |
| 119 | .if n .ti 0 |
| 120 | .if n \l'\\n(.lu\(ul' |
| 121 | .if n .fi |
| 122 | .. |
| 123 | '\" # BE - end boxed text (draw box now) |
| 124 | .de BE |
| 125 | .nf |
| 126 | .ti 0 |
| 127 | .mk ^t |
| 128 | .ie n \l'\\n(^lu\(ul' |
| 129 | .el \{\ |
| 130 | .\" Draw four-sided box normally, but don't draw top of |
| 131 | .\" box if the box started on an earlier page. |
| 132 | .ie !\\n(^b-1 \{\ |
| 133 | \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul' |
| 134 | .\} |
| 135 | .el \}\ |
| 136 | \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul' |
| 137 | .\} |
| 138 | .\} |
| 139 | .fi |
| 140 | .br |
| 141 | .nr ^b 0 |
| 142 | .. |
| 143 | '\" # VS - start vertical sidebar |
| 144 | '\" # ^Y = starting y location |
| 145 | '\" # ^v = 1 (for troff; for nroff this doesn't matter) |
| 146 | .de VS |
| 147 | .if !"\\$2"" .br |
| 148 | .mk ^Y |
| 149 | .ie n 'mc \s12\(br\s0 |
| 150 | .el .nr ^v 1u |
| 151 | .. |
| 152 | '\" # VE - end of vertical sidebar |
| 153 | .de VE |
| 154 | .ie n 'mc |
| 155 | .el \{\ |
| 156 | .ev 2 |
| 157 | .nf |
| 158 | .ti 0 |
| 159 | .mk ^t |
| 160 | \h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n' |
| 161 | .sp -1 |
| 162 | .fi |
| 163 | .ev |
| 164 | .\} |
| 165 | .nr ^v 0 |
| 166 | .. |
| 167 | '\" # Special macro to handle page bottom: finish off current |
| 168 | '\" # box/sidebar if in box/sidebar mode, then invoked standard |
| 169 | '\" # page bottom macro. |
| 170 | .de ^B |
| 171 | .ev 2 |
| 172 | 'ti 0 |
| 173 | 'nf |
| 174 | .mk ^t |
| 175 | .if \\n(^b \{\ |
| 176 | .\" Draw three-sided box if this is the box's first page, |
| 177 | .\" draw two sides but no top otherwise. |
| 178 | .ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c |
| 179 | .el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c |
| 180 | .\} |
| 181 | .if \\n(^v \{\ |
| 182 | .nr ^x \\n(^tu+1v-\\n(^Yu |
| 183 | \kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c |
| 184 | .\} |
| 185 | .bp |
| 186 | 'fi |
| 187 | .ev |
| 188 | .if \\n(^b \{\ |
| 189 | .mk ^y |
| 190 | .nr ^b 2 |
| 191 | .\} |
| 192 | .if \\n(^v \{\ |
| 193 | .mk ^Y |
| 194 | .\} |
| 195 | .. |
| 196 | '\" # DS - begin display |
| 197 | .de DS |
| 198 | .RS |
| 199 | .nf |
| 200 | .sp |
| 201 | .. |
| 202 | '\" # DE - end display |
| 203 | .de DE |
| 204 | .fi |
| 205 | .RE |
| 206 | .sp |
| 207 | .. |
| 208 | '\" # SO - start of list of standard options |
| 209 | .de SO |
| 210 | .SH "STANDARD OPTIONS" |
| 211 | .LP |
| 212 | .nf |
| 213 | .ta 5.5c 11c |
| 214 | .ft B |
| 215 | .. |
| 216 | '\" # SE - end of list of standard options |
| 217 | .de SE |
| 218 | .fi |
| 219 | .ft R |
| 220 | .LP |
| 221 | See the \\fBoptions\\fR manual entry for details on the standard options. |
| 222 | .. |
| 223 | '\" # OP - start of full description for a single option |
| 224 | .de OP |
| 225 | .LP |
| 226 | .nf |
| 227 | .ta 4c |
| 228 | Command-Line Name: \\fB\\$1\\fR |
| 229 | Database Name: \\fB\\$2\\fR |
| 230 | Database Class: \\fB\\$3\\fR |
| 231 | .fi |
| 232 | .IP |
| 233 | .. |
| 234 | '\" # CS - begin code excerpt |
| 235 | .de CS |
| 236 | .RS |
| 237 | .nf |
| 238 | .ta .25i .5i .75i 1i |
| 239 | .. |
| 240 | '\" # CE - end code excerpt |
| 241 | .de CE |
| 242 | .fi |
| 243 | .RE |
| 244 | .. |
| 245 | .de UL |
| 246 | \\$1\l'|0\(ul'\\$2 |
| 247 | .. |
| 248 | .TH lsort n 8.3 Tcl "Tcl Built-In Commands" |
| 249 | .BS |
| 250 | '\" Note: do not modify the .SH NAME line immediately below! |
| 251 | .SH NAME |
| 252 | lsort \- Sort the elements of a list |
| 253 | .SH SYNOPSIS |
| 254 | \fBlsort \fR?\fIoptions\fR? \fIlist\fR |
| 255 | .BE |
| 256 | |
| 257 | .SH DESCRIPTION |
| 258 | .PP |
| 259 | This command sorts the elements of \fIlist\fR, returning a new |
| 260 | list in sorted order. The implementation of the \fBlsort\fR command |
| 261 | uses the merge\-sort algorithm which is a stable sort that has O(n log |
| 262 | n) performance characteristics. |
| 263 | .PP |
| 264 | By default ASCII sorting is used with the result returned in |
| 265 | increasing order. However, any of the following options may be |
| 266 | specified before \fIlist\fR to control the sorting process (unique |
| 267 | abbreviations are accepted): |
| 268 | .TP 20 |
| 269 | \fB\-ascii\fR |
| 270 | Use string comparison with Unicode code-point collation order (the |
| 271 | name is for backward-compatibility reasons.) This is the default. |
| 272 | .TP 20 |
| 273 | \fB\-dictionary\fR |
| 274 | Use dictionary-style comparison. This is the same as \fB\-ascii\fR |
| 275 | except (a) case is ignored except as a tie-breaker and (b) if two |
| 276 | strings contain embedded numbers, the numbers compare as integers, |
| 277 | not characters. For example, in \fB\-dictionary\fR mode, \fBbigBoy\fR |
| 278 | sorts between \fBbigbang\fR and \fBbigboy\fR, and \fBx10y\fR |
| 279 | sorts between \fBx9y\fR and \fBx11y\fR. |
| 280 | .TP 20 |
| 281 | \fB\-integer\fR |
| 282 | Convert list elements to integers and use integer comparison. |
| 283 | .TP 20 |
| 284 | \fB\-real\fR |
| 285 | Convert list elements to floating-point values and use floating comparison. |
| 286 | .TP 20 |
| 287 | \fB\-command\0\fIcommand\fR |
| 288 | Use \fIcommand\fR as a comparison command. |
| 289 | To compare two elements, evaluate a Tcl script consisting of |
| 290 | \fIcommand\fR with the two elements appended as additional |
| 291 | arguments. The script should return an integer less than, |
| 292 | equal to, or greater than zero if the first element is to |
| 293 | be considered less than, equal to, or greater than the second, |
| 294 | respectively. |
| 295 | .TP 20 |
| 296 | \fB\-increasing\fR |
| 297 | Sort the list in increasing order (``smallest'' items first). |
| 298 | This is the default. |
| 299 | .TP 20 |
| 300 | \fB\-decreasing\fR |
| 301 | Sort the list in decreasing order (``largest'' items first). |
| 302 | .TP 20 |
| 303 | \fB\-index\0\fIindex\fR |
| 304 | If this option is specified, each of the elements of \fIlist\fR must |
| 305 | itself be a proper Tcl sublist. Instead of sorting based on whole |
| 306 | sublists, \fBlsort\fR will extract the \fIindex\fR'th element from |
| 307 | each sublist and sort based on the given element. The keyword |
| 308 | \fBend\fP is allowed for the \fIindex\fP to sort on the last sublist |
| 309 | element, |
| 310 | .VS 8.4 |
| 311 | and \fBend-\fIindex\fR sorts on a sublist element offset from |
| 312 | the end. |
| 313 | .VE |
| 314 | For example, |
| 315 | .RS |
| 316 | .CS |
| 317 | lsort -integer -index 1 {{First 24} {Second 18} {Third 30}} |
| 318 | .CE |
| 319 | returns \fB{Second 18} {First 24} {Third 30}\fR, and |
| 320 | .VS 8.4 |
| 321 | '\" |
| 322 | '\" This example is from the test suite! |
| 323 | '\" |
| 324 | .CS |
| 325 | lsort -index end-1 {{a 1 e i} {b 2 3 f g} {c 4 5 6 d h}} |
| 326 | .CE |
| 327 | returns \fB{c 4 5 6 d h} {a 1 e i} {b 2 3 f g}\fR. |
| 328 | .VE |
| 329 | This option is much more efficient than using \fB\-command\fR |
| 330 | to achieve the same effect. |
| 331 | .RE |
| 332 | .TP 20 |
| 333 | \fB\-unique\fR |
| 334 | If this option is specified, then only the last set of duplicate |
| 335 | elements found in the list will be retained. Note that duplicates are |
| 336 | determined relative to the comparison used in the sort. Thus if |
| 337 | \fI-index 0\fR is used, \fB{1 a}\fR and \fB{1 b}\fR would be |
| 338 | considered duplicates and only the second element, \fB{1 b}\fR, would |
| 339 | be retained. |
| 340 | .SH "NOTES" |
| 341 | .PP |
| 342 | The options to \fBlsort\fR only control what sort of comparison is |
| 343 | used, and do not necessarily constrain what the values themselves |
| 344 | actually are. This distinction is only noticeable when the list to be |
| 345 | sorted has fewer than two elements. |
| 346 | .PP |
| 347 | The \fBlsort\fR command is reentrant, meaning it is safe to use as |
| 348 | part of the implementation of a command used in the \fB\-command\fR |
| 349 | option. |
| 350 | .SH "EXAMPLES" |
| 351 | .PP |
| 352 | Sorting a list using ASCII sorting: |
| 353 | .CS |
| 354 | % \fBlsort\fR {a10 B2 b1 a1 a2} |
| 355 | B2 a1 a10 a2 b1 |
| 356 | .CE |
| 357 | .PP |
| 358 | Sorting a list using Dictionary sorting: |
| 359 | .CS |
| 360 | % \fBlsort\fR -dictionary {a10 B2 b1 a1 a2} |
| 361 | a1 a2 a10 b1 B2 |
| 362 | .CE |
| 363 | .PP |
| 364 | Sorting lists of integers: |
| 365 | .CS |
| 366 | % \fBlsort\fR -integer {5 3 1 2 11 4} |
| 367 | 1 2 3 4 5 11 |
| 368 | % \fBlsort\fR -integer {1 2 0x5 7 0 4 -1} |
| 369 | -1 0 1 2 4 0x5 7 |
| 370 | .CE |
| 371 | .PP |
| 372 | Sorting lists of floating-point numbers: |
| 373 | .CS |
| 374 | % \fBlsort\fR -real {5 3 1 2 11 4} |
| 375 | 1 2 3 4 5 11 |
| 376 | % \fBlsort\fR -real {.5 0.07e1 0.4 6e-1} |
| 377 | 0.4 .5 6e-1 0.07e1 |
| 378 | .CE |
| 379 | .PP |
| 380 | Sorting using indices: |
| 381 | .CS |
| 382 | % # Note the space character before the c |
| 383 | % \fBlsort\fR {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| 384 | { c 3} {a 5} {b 4} {d 2} {e 1} |
| 385 | % \fBlsort\fR -index 0 {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| 386 | {a 5} {b 4} { c 3} {d 2} {e 1} |
| 387 | % \fBlsort\fR -index 1 {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| 388 | {e 1} {d 2} { c 3} {b 4} {a 5} |
| 389 | .CE |
| 390 | .PP |
| 391 | Stripping duplicate values using sorting: |
| 392 | .CS |
| 393 | % \fBlsort\fR -unique {a b c a b c a b c} |
| 394 | a b c |
| 395 | .CE |
| 396 | .PP |
| 397 | More complex sorting using a comparison function: |
| 398 | .CS |
| 399 | % proc compare {a b} { |
| 400 | set a0 [lindex $a 0] |
| 401 | set b0 [lindex $b 0] |
| 402 | if {$a0 < $b0} { |
| 403 | return -1 |
| 404 | } elseif {$a0 > $b0} { |
| 405 | return 1 |
| 406 | } |
| 407 | return [string compare [lindex $a 1] [lindex $b 1]] |
| 408 | } |
| 409 | % \fBlsort\fR -command compare \\ |
| 410 | {{3 apple} {0x2 carrot} {1 dingo} {2 banana}} |
| 411 | {1 dingo} {2 banana} {0x2 carrot} {3 apple} |
| 412 | .CE |
| 413 | |
| 414 | .SH "SEE ALSO" |
| 415 | .VS 8.4 |
| 416 | list(n), lappend(n), lindex(n), linsert(n), llength(n), lsearch(n), |
| 417 | lset(n), lrange(n), lreplace(n) |
| 418 | .VE |
| 419 | |
| 420 | .SH KEYWORDS |
| 421 | element, list, order, sort |