* tests/lsearch.test:

* doc/lsearch.n:
* generic/tclCmdIL.c (Tcl_LsearchObjCmd): Extended [lsearch] to
support sorted list searching and typed list searching. [RFE: 4098].

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