struct::tree_v1(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

✨ NAME ✨

struct::tree_v1 — Create and manipulate tree objects

This is from the Tcl Data Structures manual, section 3tcl. Hey bestie, we're about to get into it. 💅

🦋 SYNOPSIS 🦋

package require Tcl 8.5 9

package require struct::tree ?1.2.3?

treeName option ?arg arg ...?

treeName append node ?-key key? value

treeName children node

treeName cut node

treeName delete node ?node ...?

treeName depth node

treeName destroy

treeName exists node

treeName get node ?-key key?

treeName getall node

treeName keys node

treeName keyexists node ?-key key?

treeName index node

treeName insert parent index ?child ?child ...??

treeName isleaf node

treeName lappend node ?-key key? value

treeName move parent index node ?node ...?

treeName next node

treeName numchildren node

treeName parent node

treeName previous node

treeName set node ?-key key? ?value?

treeName size ?node?

treeName splice parent from ?to? ?child?

treeName swap node1 node2

treeName unset node ?-key key?

treeName walk node ?-order order? ?-type type? -command cmd

💖 DESCRIPTION 💖

The ::struct::tree command creates a new tree object with an associated global Tcl command whose name is treeName. This command may be used to invoke various operations on the tree. It has the following general form:

treeName option ?arg arg ...?

Option and the args determine the exact behavior of the command.

A tree is a collection of named elements, called nodes, one of which is distinguished as a root, along with a relation ("parenthood") that places a hierarchical structure on the nodes. (Data Structures and Algorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987). In addition to maintaining the node relationships, this tree implementation allows any number of keyed values to be associated with each node.

The element names can be arbitrary strings.

A tree is thus similar to an array, but with three important differences:

  1. Trees are accessed through an object command, whereas arrays are accessed as variables. (This means trees cannot be local to a procedure.)
  2. Trees have a hierarchical structure, whereas an array is just an unordered collection.
  3. Each node of a tree has a separate collection of attributes and values. This is like an array where every value is a dictionary.

The following commands are possible for tree objects:

  • treeName append node ?-key key? value — Glues value onto the end of one of the keyed values hanging off node. If you don't pass -key, the key data is assumed. ✨
  • treeName children node — Gives you back a list of the children of node. Like a little headcount of the immediate fam. 🫶
  • treeName cut node — Takes node out of the tree, but not its children. Those children get rehomed as children of node's parent, at the exact index where node used to sit. No orphan vibes. 💅
  • treeName delete node ?node ...? — Yeets the specified nodes out of the tree. All of those nodes' children get removed too, so nobody ends up orphaned. 💀
  • treeName depth node — Tells you how many steps it takes to get from node up to the root node. 🌈
  • treeName destroy — Destroys the tree, including its storage space and associated command. It's giving full cleanup, no crumbs. 🧚
  • treeName exists node — Returns true if node exists in the tree. Vibe check: present or not? ⭐
  • treeName get node ?-key key? — Returns the value associated with the key key for node. No -key? Then the key data is assumed. 👑
  • treeName getall node — Returns a serialized list of key/value pairs (suitable for use with [array set]) for node. It's the whole dictionary moment. 💖
  • treeName keys node — Returns a list of keys for node. Just the keys, bestie. 🔑
  • treeName keyexists node ?-key key? — Returns true if the specified key exists for node. No -key? The key data is assumed. ✅
  • treeName index node — Returns the index of node in its parent's list of children. For example, if a node has nodeFoo, nodeBar, and nodeBaz as children, in that order, the index of nodeBar is 1. Math is math. 🧮
  • treeName insert parent index ?child ?child ...?? — Inserts one or more nodes into the tree as children of parent. They go in the order you give them. If parent is root, it refers to the root of the tree. The new nodes get added to parent's child list at index. index can be end, in which case the new nodes go after the current last child. If any of the specified children already exist in treeName, those nodes will be moved from their original location to the new location indicated by this command. If no child is specified, a single node is added and a name is generated for it. The generated name is of the form nodex, where x is a number. If names are specified, they must neither contain whitespace nor colons (":"). The return result from this command is a list of nodes added. Big slay. 🎀
  • treeName isleaf node — Returns true if node is a leaf of the tree (if node has no children), false otherwise. Leaf = no kids, just vibes. 🍃
  • treeName lappend node ?-key key? value — Appends value (as a list) to one of the keyed values associated with a node. No -key? The key data is assumed. 📝
  • treeName move parent index node ?node ...? — Makes the specified nodes children of parent, inserting them into parent's child list at index. Important: the command takes all nodes out of the tree before inserting them under the new parent, and it determines the position to place them into after the removal, before the re-insertion. This behaviour is important when moving one or more nodes to a different index without changing their parent node. 🚚
  • treeName next node — Returns the right sibling of node, or the empty string if node was the last child of its parent. Right-side neighbor check. 👉
  • treeName numchildren node — Returns the number of immediate children of node. Not the whole bloodline, just the direct kids. 👶
  • treeName parent node — Returns the parent of node. Who's your mother? 💅
  • treeName previous node — Returns the left sibling of node, or the empty string if node was the first child of its parent. Left-side neighbor check. 👈
  • treeName set node ?-key key? ?value? — Sets or gets one of the keyed values associated with a node. No -key? The key data is assumed. Every node added to a tree automatically gets the value "" assigned to the key data. A node may have any number of keyed values associated with it. If value is not specified, this command returns the current value assigned to the key; if value is specified, this command assigns that value to the key. ✨
  • treeName size ?node? — Returns a count of the number of descendants of the node node; if no node is specified, root is assumed. It's the whole downstream tree count. 🌳
  • treeName splice parent from ?to? ?child? — Inserts a node named child into the tree as a child of parent. If parent is root, it refers to the root of the tree. The new node is added to parent's child list at the index given by from. The children of parent which are in the range of the indices from and to are made children of child. If to is not specified it defaults to end. If no name is given for child, a name is generated for the new node. The generated name is of the form nodex, where x is a number. The return result from this command is the name of the new node. 🪄
  • treeName swap node1 node2 — Swaps the position of node1 and node2 in the tree. Trading places, iconic. 🔄
  • treeName unset node ?-key key? — Removes a keyed value from the node node. No -key? The key data is assumed. Bye key. 👋
  • treeName walk node ?-order order? ?-type type? -command cmd — Performs a breadth-first or depth-first walk of the tree starting at node. The type of walk, breadth-first or depth-first, is determined by the value of type; bfs indicates breadth-first, dfs indicates depth-first. Depth-first is the default. The order of the walk, pre-, post-, both- or in-order, is determined by the value of order; pre indicates pre-order, post indicates post-order, both indicates both-order and in indicates in-order. Pre-order is the default. 🚶‍♀️

Pre-order walking means that a parent node is visited before any of its children. For example, a breadth-first search starting from the root will visit the root, followed by all of the root's children, followed by all of the root's grandchildren. Post-order walking means that a parent node is visited after any of its children. Both-order walking means that a parent node is visited before and after any of its children. In-order walking means that a parent node is visited after its first child and before the second. This is a generalization of in-order walking for binary trees and will do the right thing if a binary is walked. The combination of a breadth-first walk with in-order is illegal.

⚠️ Not me warning you: breadth-first + in-order? Illegal. Don't do it. 🙅‍♀️

As the walk progresses, the command cmd will be evaluated at each node. Percent substitution will be performed on cmd before evaluation, just as in a bind script. The following substitutions are recognized:

  • %% — Insert the literal % character.
  • %t — Name of the tree object.
  • %n — Name of the current node.
  • %a — Name of the action occurring; one of enter, leave, or visit. enter actions occur during pre-order walks; leave actions occur during post-order walks; visit actions occur during in-order walks. In a both-order walk, the command will be evaluated twice for each node; the action is enter for the first evaluation, and leave for the second.

💖 BUGS, IDEAS, FEEDBACK 💖

okay bestie, real talk: this doc? and the whole package it's describing? they will undoubtedly have bugs and other problems. like, not maybe. undoubtedly. so please don't come for me, come for the tracker instead 💅

🌸 proposing code changes? read this first 🌸

When proposing code changes, please provide unified diffs, i.e. the output of diff -u.

and one more thing that is super important, no cap:

Note further that attachments are strongly preferred over inlined patches.

the way to attach stuff: go to the Edit form of the ticket immediately after its creation, and then use the left-most button in the secondary navigation bar. that's the whole move, iykyk 💫

🎀 KEYWORDS 🎀

tree

🦋 CATEGORY 🦋

Data structures

Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>

and that's the page, bestie!! 🫶 this was struct::tree_v1(3tcl) from tcllib, version 1.2.3 — go forth and build ur trees, u absolute icon 💖🌳✨

📦 where this page comes from