diff options
author | ericm <ericm@noemail.net> | 2000-05-09 17:50:37 (GMT) |
---|---|---|
committer | ericm <ericm@noemail.net> | 2000-05-09 17:50:37 (GMT) |
commit | 44d3a07a8273c026cd4e061f89151fc8a13b55eb (patch) | |
tree | 4f7c1988a264961da2e766d9c6fbc70cddb7627c /tests/lsearch.test | |
parent | 040618a8dabf810f5a28a56e494fdf9802b6f87b (diff) | |
download | tcl-44d3a07a8273c026cd4e061f89151fc8a13b55eb.zip tcl-44d3a07a8273c026cd4e061f89151fc8a13b55eb.tar.gz tcl-44d3a07a8273c026cd4e061f89151fc8a13b55eb.tar.bz2 |
* tests/lsearch.test:
* doc/lsearch.n:
* generic/tclCmdIL.c (Tcl_LsearchObjCmd): Extended [lsearch] to
support sorted list searching and typed list searching. [RFE: 4098].
FossilOrigin-Name: 51a0b967fd7cec90a883e24e2e8605cab526ecea
Diffstat (limited to 'tests/lsearch.test')
-rw-r--r-- | tests/lsearch.test | 192 |
1 files changed, 186 insertions, 6 deletions
diff --git a/tests/lsearch.test b/tests/lsearch.test index a5ba1b7..275a569 100644 --- a/tests/lsearch.test +++ b/tests/lsearch.test @@ -11,7 +11,7 @@ # See the file "license.terms" for information on usage and redistribution # of this file, and for a DISCLAIMER OF ALL WARRANTIES. # -# RCS: @(#) $Id: lsearch.test,v 1.5 2000/04/10 17:19:01 ericm Exp $ +# RCS: @(#) $Id: lsearch.test,v 1.6 2000/05/09 17:50:39 ericm Exp $ if {[lsearch [namespace children] ::tcltest] == -1} { package require tcltest @@ -61,20 +61,20 @@ test lsearch-2.9 {search modes} { } 1 test lsearch-2.10 {search modes} { list [catch {lsearch -glib {b.x bx xy bcx} b.x} msg] $msg -} {1 {bad search mode "-glib": must be -exact, -glob, or -regexp}} +} {1 {bad option "-glib": must be -ascii, -decreasing, -dictionary, -exact, -increasing, -integer, -glob, -real, -regexp, or -sorted}} test lsearch-3.1 {lsearch errors} { list [catch lsearch msg] $msg -} {1 {wrong # args: should be "lsearch ?mode? list pattern"}} +} {1 {wrong # args: should be "lsearch ?options? list pattern"}} test lsearch-3.2 {lsearch errors} { list [catch {lsearch a} msg] $msg -} {1 {wrong # args: should be "lsearch ?mode? list pattern"}} +} {1 {wrong # args: should be "lsearch ?options? list pattern"}} test lsearch-3.3 {lsearch errors} { list [catch {lsearch a b c} msg] $msg -} {1 {bad search mode "a": must be -exact, -glob, or -regexp}} +} {1 {bad option "a": must be -ascii, -decreasing, -dictionary, -exact, -increasing, -integer, -glob, -real, -regexp, or -sorted}} test lsearch-3.4 {lsearch errors} { list [catch {lsearch a b c d} msg] $msg -} {1 {wrong # args: should be "lsearch ?mode? list pattern"}} +} {1 {bad option "a": must be -ascii, -decreasing, -dictionary, -exact, -increasing, -integer, -glob, -real, -regexp, or -sorted}} test lsearch-3.5 {lsearch errors} { list [catch {lsearch "\{" b} msg] $msg } {1 {unmatched open brace in list}} @@ -89,6 +89,186 @@ test lsearch-4.2 {binary data} { lsearch -exact [list foo one\000two bar] $x } 1 +# Make a sorted list +set l {} +set l2 {} +for {set i 0} {$i < 100} {incr i} { + lappend l $i + lappend l2 [expr {double($i)/2}] +} +set increasingIntegers [lsort -integer $l] +set decreasingIntegers [lsort -decreasing -integer $l] +set increasingDoubles [lsort -real $l2] +set decreasingDoubles [lsort -decreasing -real $l2] +set increasingStrings [lsort {48 6a 18b 22a 21aa 35 36}] +set decreasingStrings [lsort -decreasing {48 6a 18b 22a 21aa 35 36}] +set increasingDictionary [lsort -dictionary {48 6a 18b 22a 21aa 35 36}] +set decreasingDictionary [lsort -dictionary -decreasing $increasingDictionary] + +set l {} +for {set i 0} {$i < 10} {incr i} { + lappend l $i $i $i $i $i +} +set repeatingIncreasingIntegers [lsort -integer $l] +set repeatingDecreasingIntegers [lsort -integer -decreasing $l] + +test lsearch-5.1 {binary search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -integer -sorted $increasingIntegers $i] + } + set res +} $increasingIntegers +test lsearch-5.2 {binary search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -integer -decreasing -sorted \ + $decreasingIntegers $i] + } + set res +} $decreasingIntegers +test lsearch-5.3 {binary search finds leftmost occurances} { + set res {} + for {set i 0} {$i < 10} {incr i} { + lappend res [lsearch -integer -sorted $repeatingIncreasingIntegers $i] + } + set res +} [list 0 5 10 15 20 25 30 35 40 45] +test lsearch-5.4 {binary search -decreasing finds leftmost occurances} { + set res {} + for {set i 9} {$i >= 0} {incr i -1} { + lappend res [lsearch -sorted -integer -decreasing \ + $repeatingDecreasingIntegers $i] + } + set res +} [list 0 5 10 15 20 25 30 35 40 45] + +test lsearch-6.1 {integer search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -exact -integer $increasingIntegers $i] + } + set res +} [lrange $increasingIntegers 0 99] +test lsearch-6.2 {decreasing integer search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -exact -integer -decreasing \ + $decreasingIntegers $i] + } + set res +} [lrange $decreasingIntegers 0 99] +test lsearch-6.3 {sorted integer search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -sorted -integer $increasingIntegers $i] + } + set res +} [lrange $increasingIntegers 0 99] +test lsearch-6.4 {sorted decreasing integer search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -integer -sorted -decreasing \ + $decreasingIntegers $i] + } + set res +} [lrange $decreasingIntegers 0 99] + +test lsearch-7.1 {double search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -exact -real $increasingDoubles \ + [expr {double($i)/2}]] + } + set res +} [lrange $increasingIntegers 0 99] +test lsearch-7.2 {decreasing double search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -exact -real -decreasing \ + $decreasingDoubles [expr {double($i)/2}]] + } + set res +} [lrange $decreasingIntegers 0 99] +test lsearch-7.3 {sorted double search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -sorted -real \ + $increasingDoubles [expr {double($i)/2}]] + } + set res +} [lrange $increasingIntegers 0 99] +test lsearch-7.4 {sorted decreasing double search} { + set res {} + for {set i 0} {$i < 100} {incr i} { + lappend res [lsearch -sorted -real -decreasing \ + $decreasingDoubles [expr {double($i)/2}]] + } + set res +} [lrange $decreasingIntegers 0 99] + +test lsearch-8.1 {dictionary search} { + set res {} + foreach val {6a 18b 21aa 22a 35 36 48} { + lappend res [lsearch -exact -dictionary $increasingDictionary $val] + } + set res +} [list 0 1 2 3 4 5 6] +test lsearch-8.2 {decreasing dictionary search} { + set res {} + foreach val {6a 18b 21aa 22a 35 36 48} { + lappend res [lsearch -exact -dictionary $decreasingDictionary $val] + } + set res +} [list 6 5 4 3 2 1 0] +test lsearch-8.3 {sorted dictionary search} { + set res {} + foreach val {6a 18b 21aa 22a 35 36 48} { + lappend res [lsearch -sorted -dictionary $increasingDictionary $val] + } + set res +} [list 0 1 2 3 4 5 6] +test lsearch-8.4 {decreasing sorted dictionary search} { + set res {} + foreach val {6a 18b 21aa 22a 35 36 48} { + lappend res [lsearch -decreasing -sorted -dictionary \ + $decreasingDictionary $val] + } + set res +} [list 6 5 4 3 2 1 0] + +test lsearch-9.1 {ascii search} { + set res {} + foreach val {18b 21aa 22a 35 36 48 6a} { + lappend res [lsearch -exact -ascii $increasingStrings $val] + } + set res +} [list 0 1 2 3 4 5 6] +test lsearch-9.2 {decreasing ascii search} { + set res {} + foreach val {18b 21aa 22a 35 36 48 6a} { + lappend res [lsearch -exact -ascii $decreasingStrings $val] + } + set res +} [list 6 5 4 3 2 1 0] +test lsearch-9.3 {sorted ascii search} { + set res {} + foreach val {18b 21aa 22a 35 36 48 6a} { + lappend res [lsearch -sorted -ascii $increasingStrings $val] + } + set res +} [list 0 1 2 3 4 5 6] +test lsearch-9.4 {decreasing sorted ascii search} { + set res {} + foreach val {18b 21aa 22a 35 36 48 6a} { + lappend res [lsearch -decreasing -sorted -ascii \ + $decreasingStrings $val] + } + set res +} [list 6 5 4 3 2 1 0] + + + # cleanup ::tcltest::cleanupTests return |