path: root/tests/lsearch.test

# Commands covered:  lsearch
#
# This file contains a collection of tests for one or more of the Tcl
# built-in commands.  Sourcing this file into Tcl runs the tests and
# generates output for errors.  No output means no errors were found.
#
# Copyright (c) 1991-1993 The Regents of the University of California.
# Copyright (c) 1994 Sun Microsystems, Inc.
# Copyright (c) 1998-1999 by Scriptics Corporation.
#
# 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.6 2000/05/09 17:50:39 ericm Exp $

if {[lsearch [namespace children] ::tcltest] == -1} {
    package require tcltest
    namespace import -force ::tcltest::*
}

set x {abcd bbcd 123 234 345}
test lsearch-1.1 {lsearch command} {
    lsearch $x 123
} 2
test lsearch-1.2 {lsearch command} {
    lsearch $x 3456
} -1
test lsearch-1.3 {lsearch command} {
    lsearch $x *5
} 4
test lsearch-1.4 {lsearch command} {
    lsearch $x *bc*
} 0

test lsearch-2.1 {search modes} {
    lsearch -exact {xyz bbcc *bc*} *bc*
} 2
test lsearch-2.2 {search modes} {
    lsearch -exact {b.x ^bc xy bcx} ^bc
} 1
test lsearch-2.3 {search modes} {
    lsearch -exact {foo bar cat} ba
} -1
test lsearch-2.4 {search modes} {
    lsearch -exact {foo bar cat} bart
} -1
test lsearch-2.5 {search modes} {
    lsearch -exact {foo bar cat} bar
} 1
test lsearch-2.6 {search modes} {
    list [catch {lsearch -regexp {xyz bbcc *bc*} *bc*} msg] $msg
} {1 {couldn't compile regular expression pattern: quantifier operand invalid}}
test lsearch-2.7 {search modes} {
    lsearch -regexp {b.x ^bc xy bcx} ^bc
} 3
test lsearch-2.8 {search modes} {
    lsearch -glob {xyz bbcc *bc*} *bc*
} 1
test lsearch-2.9 {search modes} {
    lsearch -glob {b.x ^bc xy bcx} ^bc
} 1
test lsearch-2.10 {search modes} {
    list [catch {lsearch -glib {b.x bx xy bcx} b.x} msg] $msg
} {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 ?options? list pattern"}}
test lsearch-3.2 {lsearch errors} {
    list [catch {lsearch a} msg] $msg
} {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 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 {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}}

test lsearch-4.1 {binary data} {
    lsearch -exact [list foo one\000two bar] bar
} 2
test lsearch-4.2 {binary data} {
    set x one
    append x \x00
    append x two
    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