| '\" |
| '\" Copyright (c) 1993 The Regents of the University of California. |
| '\" Copyright (c) 1994-1996 Sun Microsystems, Inc. |
| '\" Copyright (c) 1999 Scriptics Corporation |
| '\" Copyright (c) 2001 Kevin B. Kenny. All rights reserved. |
| '\" |
| '\" See the file "license.terms" for information on usage and redistribution |
| '\" of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
| '\" |
| '\" RCS: @(#) $Id: lsort.n,v 1.12 2001/11/14 23:38:39 hobbs Exp $ |
| '\" |
| '\" The definitions below are for supplemental macros used in Tcl/Tk |
| '\" manual entries. |
| '\" |
| '\" .AP type name in/out ?indent? |
| '\" Start paragraph describing an argument to a library procedure. |
| '\" type is type of argument (int, etc.), in/out is either "in", "out", |
| '\" or "in/out" to describe whether procedure reads or modifies arg, |
| '\" and indent is equivalent to second arg of .IP (shouldn't ever be |
| '\" needed; use .AS below instead) |
| '\" |
| '\" .AS ?type? ?name? |
| '\" Give maximum sizes of arguments for setting tab stops. Type and |
| '\" name are examples of largest possible arguments that will be passed |
| '\" to .AP later. If args are omitted, default tab stops are used. |
| '\" |
| '\" .BS |
| '\" Start box enclosure. From here until next .BE, everything will be |
| '\" enclosed in one large box. |
| '\" |
| '\" .BE |
| '\" End of box enclosure. |
| '\" |
| '\" .CS |
| '\" Begin code excerpt. |
| '\" |
| '\" .CE |
| '\" End code excerpt. |
| '\" |
| '\" .VS ?version? ?br? |
| '\" Begin vertical sidebar, for use in marking newly-changed parts |
| '\" of man pages. The first argument is ignored and used for recording |
| '\" the version when the .VS was added, so that the sidebars can be |
| '\" found and removed when they reach a certain age. If another argument |
| '\" is present, then a line break is forced before starting the sidebar. |
| '\" |
| '\" .VE |
| '\" End of vertical sidebar. |
| '\" |
| '\" .DS |
| '\" Begin an indented unfilled display. |
| '\" |
| '\" .DE |
| '\" End of indented unfilled display. |
| '\" |
| '\" .SO |
| '\" Start of list of standard options for a Tk widget. The |
| '\" options follow on successive lines, in four columns separated |
| '\" by tabs. |
| '\" |
| '\" .SE |
| '\" End of list of standard options for a Tk widget. |
| '\" |
| '\" .OP cmdName dbName dbClass |
| '\" Start of description of a specific option. cmdName gives the |
| '\" option's name as specified in the class command, dbName gives |
| '\" the option's name in the option database, and dbClass gives |
| '\" the option's class in the option database. |
| '\" |
| '\" .UL arg1 arg2 |
| '\" Print arg1 underlined, then print arg2 normally. |
| '\" |
| '\" RCS: @(#) $Id: man.macros,v 1.4 2000/08/25 06:18:32 ericm Exp $ |
| '\" |
| '\" # Set up traps and other miscellaneous stuff for Tcl/Tk man pages. |
| .if t .wh -1.3i ^B |
| .nr ^l \n(.l |
| .ad b |
| '\" # Start an argument description |
| .de AP |
| .ie !"\\$4"" .TP \\$4 |
| .el \{\ |
| . ie !"\\$2"" .TP \\n()Cu |
| . el .TP 15 |
| .\} |
| .ta \\n()Au \\n()Bu |
| .ie !"\\$3"" \{\ |
| \&\\$1 \\fI\\$2\\fP (\\$3) |
| .\".b |
| .\} |
| .el \{\ |
| .br |
| .ie !"\\$2"" \{\ |
| \&\\$1 \\fI\\$2\\fP |
| .\} |
| .el \{\ |
| \&\\fI\\$1\\fP |
| .\} |
| .\} |
| .. |
| '\" # define tabbing values for .AP |
| .de AS |
| .nr )A 10n |
| .if !"\\$1"" .nr )A \\w'\\$1'u+3n |
| .nr )B \\n()Au+15n |
| .\" |
| .if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n |
| .nr )C \\n()Bu+\\w'(in/out)'u+2n |
| .. |
| .AS Tcl_Interp Tcl_CreateInterp in/out |
| '\" # BS - start boxed text |
| '\" # ^y = starting y location |
| '\" # ^b = 1 |
| .de BS |
| .br |
| .mk ^y |
| .nr ^b 1u |
| .if n .nf |
| .if n .ti 0 |
| .if n \l'\\n(.lu\(ul' |
| .if n .fi |
| .. |
| '\" # BE - end boxed text (draw box now) |
| .de BE |
| .nf |
| .ti 0 |
| .mk ^t |
| .ie n \l'\\n(^lu\(ul' |
| .el \{\ |
| .\" Draw four-sided box normally, but don't draw top of |
| .\" box if the box started on an earlier page. |
| .ie !\\n(^b-1 \{\ |
| \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul' |
| .\} |
| .el \}\ |
| \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul' |
| .\} |
| .\} |
| .fi |
| .br |
| .nr ^b 0 |
| .. |
| '\" # VS - start vertical sidebar |
| '\" # ^Y = starting y location |
| '\" # ^v = 1 (for troff; for nroff this doesn't matter) |
| .de VS |
| .if !"\\$2"" .br |
| .mk ^Y |
| .ie n 'mc \s12\(br\s0 |
| .el .nr ^v 1u |
| .. |
| '\" # VE - end of vertical sidebar |
| .de VE |
| .ie n 'mc |
| .el \{\ |
| .ev 2 |
| .nf |
| .ti 0 |
| .mk ^t |
| \h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n' |
| .sp -1 |
| .fi |
| .ev |
| .\} |
| .nr ^v 0 |
| .. |
| '\" # Special macro to handle page bottom: finish off current |
| '\" # box/sidebar if in box/sidebar mode, then invoked standard |
| '\" # page bottom macro. |
| .de ^B |
| .ev 2 |
| 'ti 0 |
| 'nf |
| .mk ^t |
| .if \\n(^b \{\ |
| .\" Draw three-sided box if this is the box's first page, |
| .\" draw two sides but no top otherwise. |
| .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 |
| .el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c |
| .\} |
| .if \\n(^v \{\ |
| .nr ^x \\n(^tu+1v-\\n(^Yu |
| \kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c |
| .\} |
| .bp |
| 'fi |
| .ev |
| .if \\n(^b \{\ |
| .mk ^y |
| .nr ^b 2 |
| .\} |
| .if \\n(^v \{\ |
| .mk ^Y |
| .\} |
| .. |
| '\" # DS - begin display |
| .de DS |
| .RS |
| .nf |
| .sp |
| .. |
| '\" # DE - end display |
| .de DE |
| .fi |
| .RE |
| .sp |
| .. |
| '\" # SO - start of list of standard options |
| .de SO |
| .SH "STANDARD OPTIONS" |
| .LP |
| .nf |
| .ta 5.5c 11c |
| .ft B |
| .. |
| '\" # SE - end of list of standard options |
| .de SE |
| .fi |
| .ft R |
| .LP |
| See the \\fBoptions\\fR manual entry for details on the standard options. |
| .. |
| '\" # OP - start of full description for a single option |
| .de OP |
| .LP |
| .nf |
| .ta 4c |
| Command-Line Name: \\fB\\$1\\fR |
| Database Name: \\fB\\$2\\fR |
| Database Class: \\fB\\$3\\fR |
| .fi |
| .IP |
| .. |
| '\" # CS - begin code excerpt |
| .de CS |
| .RS |
| .nf |
| .ta .25i .5i .75i 1i |
| .. |
| '\" # CE - end code excerpt |
| .de CE |
| .fi |
| .RE |
| .. |
| .de UL |
| \\$1\l'|0\(ul'\\$2 |
| .. |
| .TH lsort n 8.3 Tcl "Tcl Built-In Commands" |
| .BS |
| '\" Note: do not modify the .SH NAME line immediately below! |
| .SH NAME |
| lsort \- Sort the elements of a list |
| .SH SYNOPSIS |
| \fBlsort \fR?\fIoptions\fR? \fIlist\fR |
| .BE |
| |
| .SH DESCRIPTION |
| .PP |
| This command sorts the elements of \fIlist\fR, returning a new |
| list in sorted order. The implementation of the \fBlsort\fR command |
| uses the merge\-sort algorithm which is a stable sort that has O(n log |
| n) performance characteristics. |
| .PP |
| By default ASCII sorting is used with the result returned in |
| increasing order. However, any of the following options may be |
| specified before \fIlist\fR to control the sorting process (unique |
| abbreviations are accepted): |
| .TP 20 |
| \fB\-ascii\fR |
| Use string comparison with ASCII collation order. This is the default. |
| .TP 20 |
| \fB\-dictionary\fR |
| Use dictionary-style comparison. This is the same as \fB\-ascii\fR |
| except (a) case is ignored except as a tie-breaker and (b) if two |
| strings contain embedded numbers, the numbers compare as integers, |
| not characters. For example, in \fB\-dictionary\fR mode, \fBbigBoy\fR |
| sorts between \fBbigbang\fR and \fBbigboy\fR, and \fBx10y\fR |
| sorts between \fBx9y\fR and \fBx11y\fR. |
| .TP 20 |
| \fB\-integer\fR |
| Convert list elements to integers and use integer comparison. |
| .TP 20 |
| \fB\-real\fR |
| Convert list elements to floating-point values and use floating comparison. |
| .TP 20 |
| \fB\-command\0\fIcommand\fR |
| Use \fIcommand\fR as a comparison command. |
| To compare two elements, evaluate a Tcl script consisting of |
| \fIcommand\fR with the two elements appended as additional |
| arguments. The script should return an integer less than, |
| equal to, or greater than zero if the first element is to |
| be considered less than, equal to, or greater than the second, |
| respectively. |
| .TP 20 |
| \fB\-increasing\fR |
| Sort the list in increasing order (``smallest'' items first). |
| This is the default. |
| .TP 20 |
| \fB\-decreasing\fR |
| Sort the list in decreasing order (``largest'' items first). |
| .TP 20 |
| \fB\-index\0\fIindex\fR |
| If this option is specified, each of the elements of \fIlist\fR must |
| itself be a proper Tcl sublist. Instead of sorting based on whole |
| sublists, \fBlsort\fR will extract the \fIindex\fR'th element from |
| each sublist and sort based on the given element. The keyword |
| \fBend\fP is allowed for the \fIindex\fP to sort on the last sublist |
| element, |
| .VS 8.4 |
| and \fBend-\fIindex\fR sorts on a sublist element offset from |
| the end. |
| .VE |
| For example, |
| .RS |
| .CS |
| lsort -integer -index 1 {{First 24} {Second 18} {Third 30}} |
| .CE |
| returns \fB{Second 18} {First 24} {Third 30}\fR, and |
| .VS 8.4 |
| '\" |
| '\" This example is from the test suite! |
| '\" |
| .CS |
| lsort -index end-1 {{a 1 e i} {b 2 3 f g} {c 4 5 6 d h}} |
| .CE |
| returns \fB{c 4 5 6 d h} {a 1 e i} {b 2 3 f g}\fR. |
| .VE |
| This option is much more efficient than using \fB\-command\fR |
| to achieve the same effect. |
| .RE |
| .TP 20 |
| \fB\-unique\fR |
| If this option is specified, then only the last set of duplicate |
| elements found in the list will be retained. Note that duplicates are |
| determined relative to the comparison used in the sort. Thus if |
| \fI-index 0\fR is used, \fB{1 a}\fR and \fB{1 b}\fR would be |
| considered duplicates and only the second element, \fB{1 b}\fR, would |
| be retained. |
| |
| .SH "NOTES" |
| .PP |
| The options to \fBlsort\fR only control what sort of comparison is |
| used, and do not necessarily constrain what the values themselves |
| actually are. This distinction is only noticeable when the list to be |
| sorted has fewer than two elements. |
| .PP |
| The \fBlsort\fR command is reentrant, meaning it is safe to use as |
| part of the implementation of a command used in the \fB\-command\fR |
| option. |
| |
| .SH "EXAMPLES" |
| |
| .PP |
| Sorting a list using ASCII sorting: |
| .CS |
| % lsort {a10 B2 b1 a1 a2} |
| B2 a1 a10 a2 b1 |
| .CE |
| |
| .PP |
| Sorting a list using Dictionary sorting: |
| .CS |
| % lsort -dictionary {a10 B2 b1 a1 a2} |
| a1 a2 a10 b1 B2 |
| .CE |
| |
| .PP |
| Sorting lists of integers: |
| .CS |
| % lsort -integer {5 3 1 2 11 4} |
| 1 2 3 4 5 11 |
| % lsort -integer {1 2 0x5 7 0 4 -1} |
| -1 0 1 2 4 0x5 7 |
| .CE |
| |
| .PP |
| Sorting lists of floating-point numbers: |
| .CS |
| % lsort -real {5 3 1 2 11 4} |
| 1 2 3 4 5 11 |
| % lsort -real {.5 0.07e1 0.4 6e-1} |
| 0.4 .5 6e-1 0.07e1 |
| .CE |
| |
| .PP |
| Sorting using indices: |
| .CS |
| % # Note the space character before the c |
| % lsort {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| { c 3} {a 5} {b 4} {d 2} {e 1} |
| % lsort -index 0 {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| {a 5} {b 4} { c 3} {d 2} {e 1} |
| % lsort -index 1 {{a 5} { c 3} {b 4} {e 1} {d 2}} |
| {e 1} {d 2} { c 3} {b 4} {a 5} |
| .CE |
| |
| .PP |
| Stripping duplicate values using sorting: |
| .CS |
| % lsort -unique {a b c a b c a b c} |
| a b c |
| .CE |
| |
| .PP |
| More complex sorting using a comparison function: |
| .CS |
| % proc compare {a b} { |
| set a0 [lindex $a 0] |
| set b0 [lindex $b 0] |
| if {$a0 < $b0} { |
| return -1 |
| } elseif {$a0 > $b0} { |
| return 1 |
| } |
| return [string compare [lindex $a 1] [lindex $b 1]] |
| } |
| % lsort -command compare \\ |
| {{3 apple} {0x2 carrot} {1 dingo} {2 banana}} |
| {1 dingo} {2 banana} {0x2 carrot} {3 apple} |
| .CE |
| |
| .SH "SEE ALSO" |
| .VS 8.4 |
| list(n), lappend(n), lindex(n), linsert(n), llength(n), lsearch(n), |
| lset(n), lrange(n), lreplace(n) |
| .VE |
| |
| .SH KEYWORDS |
| element, list, order, sort |