Lines Matching defs:tree
0 # tree.tcl --
3 # Implementation of a tree data structure for Tcl.
16 namespace eval ::struct::tree {
17 # Data storage in the tree module
20 # There's a lot of bits to keep track of for each tree:
26 # within the tree namespace itself. Instead, each tree structure will get
35 # Only export one command, the one used to instantiate a new tree
36 namespace export tree
39 # ::struct::tree::tree --
41 # Create a new tree with a given name; if no name is given, use
45 # name Optional name of the tree; if null or not given, generate one.
48 # name Name of the tree created
50 proc ::struct::tree::tree {{name ""}} {
55 set name "tree${counter}"
69 "command \"$name\" already exists, unable to create tree"
96 # Create the command to manipulate the tree
97 interp alias {} ::$name {} ::struct::tree::TreeProc $name
105 # ::struct::tree::TreeProc --
107 # Command that processes all tree object commands.
110 # name Name of the tree object to manipulate.
117 proc ::struct::tree::TreeProc {name {cmd ""} args} {
125 if { [llength [info commands ::struct::tree::$sub]] == 0 } {
126 set optlist [lsort [info commands ::struct::tree::_*]]
136 return [uplevel 1 [linsert $args 0 ::struct::tree::$sub $name]]
139 # ::struct::tree::_children --
141 # Return the child list for a given node of a tree.
144 # name Name of the tree object.
150 proc ::struct::tree::_children {name node} {
152 return -code error "node \"$node\" does not exist in tree \"$name\""
159 # ::struct::tree::_cut --
161 # Destroys the specified node of a tree, but not its children.
166 # name Name of the tree object.
172 proc ::struct::tree::_cut {name node} {
179 return -code error "node \"$node\" does not exist in tree \"$name\""
207 # ::struct::tree::_delete --
209 # Remove a node from a tree, including all of its values. Recursively
213 # name Name of the tree.
219 proc ::struct::tree::_delete {name node} {
225 return -code error "node \"$node\" does not exist in tree \"$name\""
258 # ::struct::tree::_depth --
263 # name Name of the tree.
269 proc ::struct::tree::_depth {name node} {
271 return -code error "node \"$node\" does not exist in tree \"$name\""
282 # ::struct::tree::_destroy --
284 # Destroy a tree, including its associated command and data storage.
287 # name Name of the tree to destroy.
292 proc ::struct::tree::_destroy {name} {
297 # ::struct::tree::_exists --
299 # Test for existance of a given node in a tree.
302 # name Name of the tree to query.
308 proc ::struct::tree::_exists {name node} {
312 # ::struct::tree::_get --
314 # Get a keyed value from a node in a tree.
317 # name Name of the tree.
325 proc ::struct::tree::_get {name node {flag -key} {key data}} {
327 return -code error "node \"$node\" does not exist in tree \"$name\""
348 # ::struct::tree::_getall --
350 # Get a serialized list of key/value pairs from a node in a tree.
353 # name Name of the tree.
359 proc ::struct::tree::_getall {name node args} {
361 return -code error "node \"$node\" does not exist in tree \"$name\""
377 # ::struct::tree::_keys --
379 # Get a list of keys from a node in a tree.
382 # name Name of the tree.
388 proc ::struct::tree::_keys {name node args} {
390 return -code error "node \"$node\" does not exist in tree \"$name\""
407 # ::struct::tree::_keyexists --
409 # Test for existance of a given key for a node in a tree.
412 # name Name of the tree.
420 proc ::struct::tree::_keyexists {name node {flag -key} {key data}} {
422 return -code error "node \"$node\" does not exist in tree \"$name\""
440 # ::struct::tree::_index --
445 # name Name of the tree.
451 proc ::struct::tree::_index {name node} {
458 return -code error "node \"$node\" does not exist in tree \"$name\""
470 # ::struct::tree::_insert --
472 # Add a node to a tree; if the node(s) specified already exist, they
476 # name Name of the tree.
485 proc ::struct::tree::_insert {name parentNode index args} {
491 return -code error "parent node \"$parentNode\" does not exist in tree \"$name\""
548 # ::struct::tree::_isleaf --
550 # Return whether the given node of a tree is a leaf or not.
553 # name Name of the tree object.
559 proc ::struct::tree::_isleaf {name node} {
561 return -code error "node \"$node\" does not exist in tree \"$name\""
568 # ::struct::tree::_move --
571 # location in the tree.
574 # name Name of the tree
577 # node Node to move; the node must exist in the tree.
579 # in the tree.
584 proc ::struct::tree::_move {name parentNode index node args} {
587 # Can only move a node to a real location in the tree
589 return -code error "parent node \"$parentNode\" does not exist in tree \"$name\""
612 return -code error "node \"$node\" does not exist in tree \"$name\""
643 # ::struct::tree::_next --
645 # Return the right sibling for a given node of a tree.
648 # name Name of the tree object.
655 proc ::struct::tree::_next {name node} {
662 return -code error "node \"$node\" does not exist in tree \"$name\""
676 # ::struct::tree::_numchildren --
678 # Return the number of immediate children for a given node of a tree.
681 # name Name of the tree object.
687 proc ::struct::tree::_numchildren {name node} {
689 return -code error "node \"$node\" does not exist in tree \"$name\""
696 # ::struct::tree::_parent --
698 # Return the name of the parent node of a node in a tree.
701 # name Name of the tree.
707 proc ::struct::tree::_parent {name node} {
709 return -code error "node \"$node\" does not exist in tree \"$name\""
715 # ::struct::tree::_previous --
717 # Return the left sibling for a given node of a tree.
720 # name Name of the tree object.
727 proc ::struct::tree::_previous {name node} {
734 return -code error "node \"$node\" does not exist in tree \"$name\""
748 # ::struct::tree::_serialize --
750 # Serialize a tree object (partially) into a transportable value.
753 # name Name of the tree.
754 # node Root node of the serialized tree.
757 # A list structure describing the part of the tree which was serialized.
759 proc ::struct::tree::_serialize {name {node root}} {
761 return -code error "node \"$node\" does not exist in tree \"$name\""
763 Serialize $name $node tree attr
764 return [list $tree [array get attr]]
767 # ::struct::tree::_set --
769 # Set or get a value for a node in a tree.
772 # name Name of the tree.
781 proc ::struct::tree::_set {name node args} {
783 return -code error "node \"$node\" does not exist in tree \"$name\""
829 # ::struct::tree::_append --
831 # Append a value for a node in a tree.
834 # name Name of the tree.
843 proc ::struct::tree::_append {name node args} {
845 return -code error "node \"$node\" does not exist in tree \"$name\""
876 # ::struct::tree::_lappend --
878 # lappend a value for a node in a tree.
881 # name Name of the tree.
890 proc ::struct::tree::_lappend {name node args} {
892 return -code error "node \"$node\" does not exist in tree \"$name\""
923 # ::struct::tree::_size --
929 # name Name of the tree.
935 proc ::struct::tree::_size {name {node root}} {
937 return -code error "node \"$node\" does not exist in tree \"$name\""
941 # number of nodes (excluding the root node) that we have in the tree with
948 # Otherwise we have to do it the hard way and do a full tree search
966 # ::struct::tree::_splice --
968 # Add a node to a tree, making a range of children from the given
972 # name Name of the tree.
981 # node Name of the node added to the tree.
983 proc ::struct::tree::_splice {name parentNode from {to end} args} {
992 return -code error "node \"$node\" already exists in tree \"$name\""
1016 # ::struct::tree::_swap --
1018 # Swap two nodes in a tree.
1021 # name Name of the tree.
1028 proc ::struct::tree::_swap {name node1 node2} {
1036 return -code error "node \"$node1\" does not exist in tree \"$name\""
1039 return -code error "node \"$node2\" does not exist in tree \"$name\""
1118 # ::struct::tree::_unset --
1123 # name Name of the tree.
1132 proc ::struct::tree::_unset {name node {flag -key} {key data}} {
1134 return -code error "node \"$node\" does not exist in tree \"$name\""
1153 # ::struct::tree::_walk --
1155 # Walk a tree using a pre-order depth or breadth first
1157 # a command will be called with the name of the tree and the node.
1160 # name Name of the tree.
1163 # the tree walk, and the command to execute at each node.
1170 proc ::struct::tree::_walk {name node args} {
1178 return -code error "node \"$node\" does not exist in tree \"$name\""
1351 # ::struct::tree::WalkCall --
1355 # the tree, node and current action are substituted
1359 # tree Tree we are walking
1367 proc ::struct::tree::WalkCall {tree node action cmd} {
1368 set subs [list %n [list $node] %a [list $action] %t [list $tree] %% %]
1373 # ::struct::tree::GenerateUniqueNodeName --
1375 # Generate a unique node name for the given tree.
1378 # name Name of the tree to generate a unique node name for.
1381 # node Name of a node guaranteed to not exist in the tree.
1383 proc ::struct::tree::GenerateUniqueNodeName {name} {
1391 # ::struct::tree::KillNode --
1396 # name Name of the tree containing the node
1402 proc ::struct::tree::KillNode {name node} {
1419 # ::struct::tree::GenAttributeStorage --
1424 # name Name of the tree containing the node
1430 proc ::struct::tree::GenAttributeStorage {name node} {
1441 # ::struct::tree::Serialize --
1443 # Serialize a tree object (partially) into a transportable value.
1446 # name Name of the tree.
1447 # node Root node of the serialized tree.
1452 proc ::struct::tree::Serialize {name node tvar avar} {
1453 upvar 1 $tvar tree $avar attr
1465 # Build tree structure as nested list.
1473 set tree [list $node $subtrees]
1481 # Get 'tree::tree' into the general structure namespace.
1482 namespace import -force tree::tree
1483 namespace export tree
1485 package provide struct::tree 1.2.2