Attachment "skiplist.test" to
ticket [553980ffff]
added by
ericm
2002-05-09 10:02:05.
# skiplist.test: tests for the skiplist structure.
#
# 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) 2000 by Keith Vetter
# This software is licensed under a BSD license as described in tcl/tk
# license.txt file but with the copyright held by Keith Vetter.
if {[lsearch [namespace children] ::tcltest] == -1} {
package require tcltest
namespace import ::tcltest::*
}
#lappend auto_path [pwd]
package require struct
namespace import struct::*
# ::shuffle --
#
# creates a randomly ordered list of the integers from 0 to n-1.
#
# Arguments:
# n size of the list to shuffle
#
# Results:
# list of integers from 0 to n-1 in a random order
proc shuffle {n} {
set t [list ]
set tt [list ]
for {set i 0} {$i < $n} {incr i} {
lappend t $i
}
# Select a random item out of list t and append to list tt
for {set i [expr {$n - 1}]} {$i >= 0} {incr i -1} {
set r [expr rand()]
set x [expr {int($r * ($i + 1))}]
lappend tt [lindex $t $x]
set t [lreplace $t $x $x]
}
return $tt
}
test skiplist-0.1 {skiplist errors} {
skiplist myskiplist
catch {skiplist myskiplist} msg
myskiplist destroy
set msg
} "command \"myskiplist\" already exists, unable to create skiplist"
test skiplist-0.2 {skiplist errors} {
skiplist myskiplist
catch {myskiplist} msg
myskiplist destroy
set msg
} "wrong # args: should be \"myskiplist option ?arg arg ...?\""
test skiplist-0.3 {skiplist errors} {
skiplist myskiplist
catch {myskiplist foo} msg
myskiplist destroy
set msg
} "bad option \"foo\": must be destroy, delete, insert, search, size, or walk"
test skiplist-0.4 {skiplist errors} {
catch {skiplist set} msg
set msg
} "command \"set\" already exists, unable to create skiplist"
test skiplist-0.5 {skiplist errors} {
catch {skiplist myskiplist -foo bar} msg
set msg
} "unknown option \"-foo\": should be \"skiplist name ?-maxlevel ##? ?-probability ##?\""
test skiplist-0.6 {skiplist errors} {
catch {skiplist myskiplist -maxlevel bar} msg
set msg
} "value for the maxlevel option must be greater than 0"
test skiplist-0.7 {skiplist errors} {
catch {skiplist myskiplist -probability bar} msg
set msg
} "probability must be between 0 and 1"
test skiplist-1.0 {insert} {
skiplist myskiplist
myskiplist insert 5 value_5
set t [myskiplist search 5]
myskiplist destroy
set t
} "1 value_5"
test skiplist-1.1 {insert} {
skiplist myskiplist
myskiplist insert 5 value_5
myskiplist insert 5 value_5.2
myskiplist insert 5 value_5.3
myskiplist insert 5 value_5.4
set t [myskiplist search 5]
myskiplist destroy
set t
} "1 value_5.4"
test skiplist-1.2 {insert} {
skiplist myskiplist
foreach a [list 9 7 5 3 1 8 6 4 2] {
myskiplist insert $a value_$a
}
set t [list ]
myskiplist walk {lappend t}
myskiplist destroy
set t
} "1 value_1 2 value_2 3 value_3 4 value_4 5 value_5 6 value_6 7 value_7 8 value_8 9 value_9"
test skiplist-1.3 {insert} {
skiplist myskiplist
foreach a [shuffle 500] {
set a2 [expr {$a + 1}]
myskiplist insert $a $a2
}
set t [list ]
myskiplist walk {lappend t}
myskiplist destroy
set sum [set sum2 0]
foreach {key value} $t {
set sum [expr {$sum + $key}]
set sum2 [expr {$sum2 + $value}]
}
set sum "$sum $sum2"
} "124750 125250"
test skiplist-1.4 {insert} {
skiplist myskiplist
foreach a [shuffle 500] {
myskiplist insert $a -1
}
foreach a [shuffle 500] {
myskiplist insert $a $a
}
set t [list ]
myskiplist walk {lappend t}
myskiplist destroy
set sum 0
foreach {key value} $t {
set sum [expr {$sum + $value}]
}
set sum
} "124750"
test skiplist-1.5 {insert} {
skiplist myskiplist
foreach a [list k e i t h p o w l v r] {
myskiplist insert $a value_$a
}
set t [list ]
myskiplist walk {lappend t }
set str ""
foreach {key value} $t {
append str $key
}
myskiplist destroy
set str
} "ehikloprtvw"
test skiplist-2.0 {delete} {
skiplist myskiplist
myskiplist insert 4 value_4
set t [myskiplist delete 4]
myskiplist destroy
set t
} "1"
test skiplist-2.1 {delete} {
skiplist myskiplist
myskiplist insert 4 value_4
myskiplist delete 4
set t [myskiplist search 4]
myskiplist destroy
set t
} "0"
test skiplist-2.2 {delete} {
skiplist myskiplist
myskiplist insert 4 value_4
set t [myskiplist delete 5]
myskiplist destroy
set t
} "0"
test skiplist-2.3 {delete} {
skiplist myskiplist
myskiplist insert 8 value_8
myskiplist insert 7 value_7
myskiplist insert 6 value_6
myskiplist insert 5 value_5
myskiplist insert 4 value_4
myskiplist delete 6
myskiplist delete 5
myskiplist delete 4
set t [myskiplist search 7]
myskiplist destroy
set t
} "1 value_7"
test skiplist-2.4 {delete} {
skiplist myskiplist
set data [shuffle 100]
foreach a $data {
myskiplist insert $a value_$a
if {$a == 1} {
myskiplist insert 999 value_999
}
}
foreach a $data {
myskiplist delete $a
}
set size [myskiplist size]
set search [myskiplist search 999]
myskiplist destroy
if {$size != 1} {
return "size is $size but should be 1"
}
set search
} "1 value_999"
test skiplist-3.0 {search} {
skiplist myskiplist
myskiplist insert 5 value_5
myskiplist insert 4 value_4
myskiplist insert 3 value_3
set t [myskiplist search 4]
myskiplist destroy
set t
} "1 value_4"
test skiplist-3.1 {search} {
skiplist myskiplist
myskiplist insert 5 value_5
myskiplist insert 4 value_4
myskiplist insert 3 value_3
set t [myskiplist search 14]
myskiplist destroy
set t
} "0"
test skiplist-4.0 {size} {
skiplist myskiplist
myskiplist insert 5 value_5
myskiplist insert 4 value_4
myskiplist insert 3 value_3
set t [myskiplist size]
myskiplist destroy
set t
} "3"
test skiplist-4.1 {size} {
skiplist myskiplist
for {set i 0} {$i < 500} {incr i} {
myskiplist insert $i value_$i
}
set t [myskiplist size]
myskiplist destroy
set t
} "500"
test skiplist-5.0 {walk} {
skiplist myskiplist
myskiplist insert 5 value_5
myskiplist insert 4 value_4
myskiplist insert 3 value_3
set t [list ]
myskiplist walk {lappend t }
myskiplist destroy
set t
} "3 value_3 4 value_4 5 value_5"
test skiplist-5.1 {walk} {
skiplist myskiplist
foreach a [shuffle 500] {
set a2 [expr {$a + 1}]
myskiplist insert $a $a2
}
set t [list ]
myskiplist walk {lappend t}
myskiplist destroy
set sum 0
set sum2 0
foreach {key value} $t {
set sum [expr {$sum + $key}]
set sum2 [expr {$sum2 + $value}]
}
set sum "$sum $sum2"
} "124750 125250"
test skiplist-5.2 {walk} {
skiplist myskiplist1
skiplist myskiplist2
foreach a [shuffle 500] {
myskiplist1 insert $a value_$a
}
myskiplist1 walk {myskiplist2 insert }
set size [myskiplist2 size]
myskiplist1 destroy
myskiplist2 destroy
set size
} "500"
::tcltest::cleanupTests
