1# stack.tcl -- 2# 3# Stack implementation for Tcl. 4# 5# Copyright (c) 1998-2000 by Ajuba Solutions. 6# 7# See the file "license.terms" for information on usage and redistribution 8# of this file, and for a DISCLAIMER OF ALL WARRANTIES. 9# 10# RCS: @(#) $Id: stack_tcl.tcl,v 1.3 2010/03/15 17:17:38 andreas_kupries Exp $ 11 12namespace eval ::struct::stack { 13 # counter is used to give a unique name for unnamed stacks 14 variable counter 0 15 16 # Only export one command, the one used to instantiate a new stack 17 namespace export stack_tcl 18} 19 20# ::struct::stack::stack_tcl -- 21# 22# Create a new stack with a given name; if no name is given, use 23# stackX, where X is a number. 24# 25# Arguments: 26# name name of the stack; if null, generate one. 27# 28# Results: 29# name name of the stack created 30 31proc ::struct::stack::stack_tcl {args} { 32 variable I::stacks 33 variable counter 34 35 switch -exact -- [llength [info level 0]] { 36 1 { 37 # Missing name, generate one. 38 incr counter 39 set name "stack${counter}" 40 } 41 2 { 42 # Standard call. New empty stack. 43 set name [lindex $args 0] 44 } 45 default { 46 # Error. 47 return -code error \ 48 "wrong # args: should be \"stack ?name?\"" 49 } 50 } 51 52 # FIRST, qualify the name. 53 if {![string match "::*" $name]} { 54 # Get caller's namespace; append :: if not global namespace. 55 set ns [uplevel 1 [list namespace current]] 56 if {"::" != $ns} { 57 append ns "::" 58 } 59 60 set name "$ns$name" 61 } 62 if {[llength [info commands $name]]} { 63 return -code error \ 64 "command \"$name\" already exists, unable to create stack" 65 } 66 67 set stacks($name) [list ] 68 69 # Create the command to manipulate the stack 70 interp alias {} $name {} ::struct::stack::StackProc $name 71 72 return $name 73} 74 75########################## 76# Private functions follow 77 78# ::struct::stack::StackProc -- 79# 80# Command that processes all stack object commands. 81# 82# Arguments: 83# name name of the stack object to manipulate. 84# args command name and args for the command 85# 86# Results: 87# Varies based on command to perform 88 89if {[package vsatisfies [package provide Tcl] 8.5]} { 90 # In 8.5+ we can do an ensemble for fast dispatch. 91 92 proc ::struct::stack::StackProc {name cmd args} { 93 # Shuffle method to front and then simply run the ensemble. 94 # Dispatch, argument checking, and error message generation 95 # are all done in the C-level. 96 97 I $cmd $name {*}$args 98 } 99 100 namespace eval ::struct::stack::I { 101 namespace export clear destroy get getr peek peekr \ 102 trim trim* pop push rotate size 103 namespace ensemble create 104 } 105 106} else { 107 # Before 8.5 we have to code our own dispatch, including error 108 # checking. 109 110 proc ::struct::stack::StackProc {name cmd args} { 111 # Do minimal args checks here 112 if { [llength [info level 0]] == 2 } { 113 return -code error "wrong # args: should be \"$name option ?arg arg ...?\"" 114 } 115 116 # Split the args into command and args components 117 if {![llength [info commands ::struct::stack::I::$cmd]]} { 118 set optlist [lsort [info commands ::struct::stack::I::*]] 119 set xlist {} 120 foreach p $optlist { 121 set p [namespace tail $p] 122 if {($p eq "K") || ($p eq "lreverse")} continue 123 lappend xlist $p 124 } 125 set optlist [linsert [join $xlist ", "] "end-1" "or"] 126 return -code error \ 127 "bad option \"$cmd\": must be $optlist" 128 } 129 130 uplevel 1 [linsert $args 0 ::struct::stack::I::$cmd $name] 131 } 132} 133 134# ### ### ### ######### ######### ######### 135 136namespace eval ::struct::stack::I { 137 # The stacks array holds all of the stacks you've made 138 variable stacks 139} 140 141# ### ### ### ######### ######### ######### 142 143# ::struct::stack::I::clear -- 144# 145# Clear a stack. 146# 147# Arguments: 148# name name of the stack object. 149# 150# Results: 151# None. 152 153proc ::struct::stack::I::clear {name} { 154 variable stacks 155 set stacks($name) {} 156 return 157} 158 159# ::struct::stack::I::destroy -- 160# 161# Destroy a stack object by removing it's storage space and 162# eliminating it's proc. 163# 164# Arguments: 165# name name of the stack object. 166# 167# Results: 168# None. 169 170proc ::struct::stack::I::destroy {name} { 171 variable stacks 172 unset stacks($name) 173 interp alias {} $name {} 174 return 175} 176 177# ::struct::stack::I::get -- 178# 179# Retrieve the whole contents of the stack. 180# 181# Arguments: 182# name name of the stack object. 183# 184# Results: 185# items list of all items in the stack. 186 187proc ::struct::stack::I::get {name} { 188 variable stacks 189 return [lreverse $stacks($name)] 190} 191 192proc ::struct::stack::I::getr {name} { 193 variable stacks 194 return $stacks($name) 195} 196 197# ::struct::stack::I::peek -- 198# 199# Retrieve the value of an item on the stack without popping it. 200# 201# Arguments: 202# name name of the stack object. 203# count number of items to pop; defaults to 1 204# 205# Results: 206# items top count items from the stack; if there are not enough items 207# to fulfill the request, throws an error. 208 209proc ::struct::stack::I::peek {name {count 1}} { 210 variable stacks 211 upvar 0 stacks($name) mystack 212 213 if { $count < 1 } { 214 return -code error "invalid item count $count" 215 } elseif { $count > [llength $mystack] } { 216 return -code error "insufficient items on stack to fill request" 217 } 218 219 if { $count == 1 } { 220 # Handle this as a special case, so single item peeks are not 221 # listified 222 return [lindex $mystack end] 223 } 224 225 # Otherwise, return a list of items 226 incr count -1 227 return [lreverse [lrange $mystack end-$count end]] 228} 229 230proc ::struct::stack::I::peekr {name {count 1}} { 231 variable stacks 232 upvar 0 stacks($name) mystack 233 234 if { $count < 1 } { 235 return -code error "invalid item count $count" 236 } elseif { $count > [llength $mystack] } { 237 return -code error "insufficient items on stack to fill request" 238 } 239 240 if { $count == 1 } { 241 # Handle this as a special case, so single item peeks are not 242 # listified 243 return [lindex $mystack end] 244 } 245 246 # Otherwise, return a list of items, in reversed order. 247 incr count -1 248 return [lrange $mystack end-$count end] 249} 250 251# ::struct::stack::I::trim -- 252# 253# Pop items off a stack until a maximum size is reached. 254# 255# Arguments: 256# name name of the stack object. 257# count requested size of the stack. 258# 259# Results: 260# item List of items trimmed, may be empty. 261 262proc ::struct::stack::I::trim {name newsize} { 263 variable stacks 264 upvar 0 stacks($name) mystack 265 266 if { ![string is integer -strict $newsize]} { 267 return -code error "expected integer but got \"$newsize\"" 268 } elseif { $newsize < 0 } { 269 return -code error "invalid size $newsize" 270 } elseif { $newsize >= [llength $mystack] } { 271 # Stack is smaller than requested, do nothing. 272 return {} 273 } 274 275 # newsize < [llength $mystack] 276 # pop '[llength $mystack]' - newsize elements. 277 278 if {!$newsize} { 279 set result [lreverse [K $mystack [unset mystack]]] 280 set mystack {} 281 } else { 282 set result [lreverse [lrange $mystack $newsize end]] 283 set mystack [lreplace [K $mystack [unset mystack]] $newsize end] 284 } 285 286 return $result 287} 288 289proc ::struct::stack::I::trim* {name newsize} { 290 if { ![string is integer -strict $newsize]} { 291 return -code error "expected integer but got \"$newsize\"" 292 } elseif { $newsize < 0 } { 293 return -code error "invalid size $newsize" 294 } 295 296 variable stacks 297 upvar 0 stacks($name) mystack 298 299 if { $newsize >= [llength $mystack] } { 300 # Stack is smaller than requested, do nothing. 301 return 302 } 303 304 # newsize < [llength $mystack] 305 # pop '[llength $mystack]' - newsize elements. 306 307 # No results, compared to trim. 308 309 if {!$newsize} { 310 set mystack {} 311 } else { 312 set mystack [lreplace [K $mystack [unset mystack]] $newsize end] 313 } 314 315 return 316} 317 318# ::struct::stack::I::pop -- 319# 320# Pop an item off a stack. 321# 322# Arguments: 323# name name of the stack object. 324# count number of items to pop; defaults to 1 325# 326# Results: 327# item top count items from the stack; if the stack is empty, 328# returns a list of count nulls. 329 330proc ::struct::stack::I::pop {name {count 1}} { 331 variable stacks 332 upvar 0 stacks($name) mystack 333 334 if { $count < 1 } { 335 return -code error "invalid item count $count" 336 } 337 set ssize [llength $mystack] 338 if { $count > $ssize } { 339 return -code error "insufficient items on stack to fill request" 340 } 341 342 if { $count == 1 } { 343 # Handle this as a special case, so single item pops are not 344 # listified 345 set item [lindex $mystack end] 346 if {$count == $ssize} { 347 set mystack [list] 348 } else { 349 set mystack [lreplace [K $mystack [unset mystack]] end end] 350 } 351 return $item 352 } 353 354 # Otherwise, return a list of items, and remove the items from the 355 # stack. 356 if {$count == $ssize} { 357 set result [lreverse [K $mystack [unset mystack]]] 358 set mystack [list] 359 } else { 360 incr count -1 361 set result [lreverse [lrange $mystack end-$count end]] 362 set mystack [lreplace [K $mystack [unset mystack]] end-$count end] 363 } 364 return $result 365 366 # ------------------------------------------------------- 367 368 set newsize [expr {[llength $mystack] - $count}] 369 370 if {!$newsize} { 371 set result [lreverse [K $mystack [unset mystack]]] 372 set mystack {} 373 } else { 374 set result [lreverse [lrange $mystack $newsize end]] 375 set mystack [lreplace [K $mystack [unset mystack]] $newsize end] 376 } 377 378 if {$count == 1} { 379 set result [lindex $result 0] 380 } 381 382 return $result 383} 384 385# ::struct::stack::I::push -- 386# 387# Push an item onto a stack. 388# 389# Arguments: 390# name name of the stack object 391# args items to push. 392# 393# Results: 394# None. 395 396if {[package vsatisfies [package provide Tcl] 8.5]} { 397 398 proc ::struct::stack::I::push {name args} { 399 if {![llength $args]} { 400 return -code error "wrong # args: should be \"$name push item ?item ...?\"" 401 } 402 403 variable stacks 404 upvar 0 stacks($name) mystack 405 406 lappend mystack {*}$args 407 return 408 } 409} else { 410 proc ::struct::stack::I::push {name args} { 411 if {![llength $args]} { 412 return -code error "wrong # args: should be \"$name push item ?item ...?\"" 413 } 414 415 variable stacks 416 upvar 0 stacks($name) mystack 417 418 if {[llength $args] == 1} { 419 lappend mystack [lindex $args 0] 420 } else { 421 eval [linsert $args 0 lappend mystack] 422 } 423 return 424 } 425} 426 427# ::struct::stack::I::rotate -- 428# 429# Rotate the top count number of items by step number of steps. 430# 431# Arguments: 432# name name of the stack object. 433# count number of items to rotate. 434# steps number of steps to rotate. 435# 436# Results: 437# None. 438 439proc ::struct::stack::I::rotate {name count steps} { 440 variable stacks 441 upvar 0 stacks($name) mystack 442 set len [llength $mystack] 443 if { $count > $len } { 444 return -code error "insufficient items on stack to fill request" 445 } 446 447 # Rotation algorithm: 448 # do 449 # Find the insertion point in the stack 450 # Move the end item to the insertion point 451 # repeat $steps times 452 453 set start [expr {$len - $count}] 454 set steps [expr {$steps % $count}] 455 456 if {$steps == 0} return 457 458 for {set i 0} {$i < $steps} {incr i} { 459 set item [lindex $mystack end] 460 set mystack [linsert \ 461 [lreplace \ 462 [K $mystack [unset mystack]] \ 463 end end] $start $item] 464 } 465 return 466} 467 468# ::struct::stack::I::size -- 469# 470# Return the number of objects on a stack. 471# 472# Arguments: 473# name name of the stack object. 474# 475# Results: 476# count number of items on the stack. 477 478proc ::struct::stack::I::size {name} { 479 variable stacks 480 return [llength $stacks($name)] 481} 482 483# ### ### ### ######### ######### ######### 484 485proc ::struct::stack::I::K {x y} { set x } 486 487if {![llength [info commands lreverse]]} { 488 proc ::struct::stack::I::lreverse {x} { 489 # assert (llength(x) > 1) 490 set l [llength $x] 491 if {$l <= 1} { return $x } 492 set r [list] 493 while {$l} { lappend r [lindex $x [incr l -1]] } 494 return $r 495 } 496} 497 498# ### ### ### ######### ######### ######### 499## Ready 500 501namespace eval ::struct { 502 # Get 'stack::stack' into the general structure namespace for 503 # pickup by the main management. 504 namespace import -force stack::stack_tcl 505} 506