| Paste number 52218: | Generic tree classes |
| Pasted by: | |Agent |
| 8 months, 2 weeks ago | |
| #dylan | Context in IRC logs | |
| Paste contents: |
| // The general tree is n-ary; a node may have an arbitrary number of children. // Subclasses may limit this. A mutable tree allows node values to change. // A stretchy tree allows nodes to be moved around, pruned, or grafted, and could theoretically be // empty (lacking even a root node). define abstract open class <tree> (<explicit-key-collection>) end class; // A <tree-key> is an absolute location within a tree. If the tree is stretchy, the key may or // may not exist in the tree; this is a requirement for <stretchy-collection>. // This is not an instantiable class. Tree locations only exist in the context of a tree. define abstract open class <tree-key> end class; // Every tree has one root. Stretchy trees might want to allow an element to be added, superior // to the root. This element would become the new root. Even empty trees return a root node // key; there just isn't an element at that key. define open generic root-key (tree :: <tree>) => (root :: <tree-key>); // Each <tree> implementation provides its own <tree-key> class. define open generic key-class (tree-type :: subclass(<tree>)) => (class :: subclass(<tree-key>)) // Returns the superior (parent) of a key, or #f if none is present or allowed. define open generic superior-key (key :: <tree-key>) => (superior :: false-or(<tree-key>)); // Returns inferior (child) keys that have elements. define open generic inferior-key-sequence (key :: <tree-key>) => (inferiors :: <sequence>); // Returns the next inferior key that doesn't have an element, or #f if none remain. // Non-stretchy trees always return #f. define open generic next-inferior-key (key :: <tree-key>) => (inferior :: false-or(<tree-key>)); // Returns the next or previous sibling key. May be #f if the tree is, e.g. a binary tree. define open generic successor-key (key :: <tree-key>) => (succ :: false-or(<tree-key>)); define open generic predecessor-key (key :: <tree-key>) => (pred :: false-or(<tree-key>)); // The tree key has to be valid for the instance of tree. If not, an error is signaled. // Because <tree-key> is only instantiable through the x-key methods, all elements can // only be placed in known relation to existing keys. define method element (tree :: <tree>, key :: <tree-key>, #key default:); define method element-setter (value, tree :: <mutable-tree>, key :: <tree-key>); // Copies contents of tree rooted at from:. define open generic copy-tree (tree :: <tree>, #key from: :: <tree-key> = root-key(<tree>)) => (tree :: <tree>); // Replaces contents of tree at from:, including the element at from: itself. define open generic replace-subtree! (target :: <stretchy-tree>, insert :: <tree>, #key from: :: <tree-key>) => (tree :: <tree>); // The forward iteration protocol can be pre-order, breadth-first, whatever is convenient. define method forward-iteration-protocol (tree :: <tree>) => (...); // These other iteration protocols return values analogous to forward-iteration-protocol, // and are all optional. define open generic pre-order-iteration-protocol (tree :: <tree>) => (...); define open generic post-order-iteration-protocol (tree :: <tree>) => (...); define open generic breadth-first-iteration-protocol (tree :: <tree>) => (...); |
This paste has no annotations.