Package components.tree

Class Tree1<T>

java.lang.Object
components.tree.TreeSecondary<T>
components.tree.Tree1<T>
Type Parameters:
T - type of Tree labels
All Implemented Interfaces:
Standard<Tree<T>>, Tree<T>, TreeKernel<T>, Iterable<T>
public class Tree1<T> extends TreeSecondary<T>
Tree represented as a recursive data structure, done "bare-handed", with implementations of primary methods.
Mathematical Subtypes:
TREE_REP is  (
  size: integer,
  height: integer,
  rootLabel: T,
  subtrees: string of TREE_REP
 )
Mathematical Definitions:
IS_LEGAL_REP (
  tr: TREE_REP
 ): boolean is
 0 <= tr.height <= tr.size  and
 (if tr.size > 0 then
  [tr.size = 1 + sum of the sizes of the TREE_REP in tr.subtrees]  and
  [tr.height = 1 + max of the heights of the TREE_REP in tr.subtrees]  and
  [tr.rootLabel is not null]  and
  [tr.subtrees is not null]  and
  STRING_IS_LEGAL_REP(tr.subtrees)
 else
  [tr.rootLabel is null]  and
  [tr.subtrees is null])

STRING_IS_LEGAL_REP (
  s: string of TREE_REP
 ): string of tree of T satisfies
 if s = <> then
  STRING_IS_LEGAL_REP(s) = true
 else
  there exists t: TREE_REP, rest: string of TREE_REP
   (s = <t> * rest  and
    [t is not null]  and
    [t is not aliased to any of the TREE_REP in rest]  and
    STRING_IS_LEGAL_REP(s) = IS_LEGAL_REP(t) and STRING_IS_LEGAL_REP(rest))

ABSTRACT_TREE (
  tr: TREE_REP
 ): tree of T satisfies
 if IS_LEGAL_REP(tr) then
  (if tr.size = 0 then
    ABSTRACT_TREE(tr) = empty_tree
   else
    ABSTRACT_TREE(tr) =
     compose(tr.rootLabel, STRING_ABSTRACT_TREE(tr.subtrees)))

STRING_ABSTRACT_TREE (
  s: string of TREE_REP
 ): string of tree of T satisfies
 if STRING_IS_LEGAL_REP(s) then
  (if s = <> then
    STRING_ABSTRACT_TREE(s) = <>
   else
    there exists t: TREE_REP, rest: string of TREE_REP
     (s = <t> * rest and
      STRING_ABSTRACT_TREE(s) =
       ABSTRACT_TREE(t) * STRING_ABSTRACT_TREE(rest)))
Representation Invariant (concrete invariant of $this):
IS_LEGAL_REP($this)
Abstraction Relation (interpretation mapping between $this and this):
this = ABSTRACT_TREE($this)

  • Constructor Summary

    Constructors
    Constructor
    Description
    Tree1()
    No-argument constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    final void
    assemble(T root, Sequence<Tree<T>> children)
    Assembles in this a tree with root label root and subtrees children; the declaration notwithstanding, the dynamic type of each entry of children must be the same as the dynamic type of this and the dynamic type of children must be the same as that returned by newSequenceOfTree.
    final void
    clear()
    Resets this to an initial value.
    final T
    disassemble(Sequence<Tree<T>> children)
    Disassembles this into its root label, which is returned as the value of the function, and subtrees in children; the declaration notwithstanding, the dynamic type of children must be the same as that returned by newSequenceOfTree.
    final int
    height()
    Reports the height of this.
    final Iterator<T>
    iterator()
     
    final Tree<T>
    newInstance()
    Returns a new object with the same dynamic type as this, having an initial value.
    final Sequence<Tree<T>>
    newSequenceOfTree()
    Creates and returns an empty Sequence<Tree<T>> of the dynamic type needed in assemble and disassemble.
    final int
    numberOfSubtrees()
    Returns the number of subtrees of the root of this.
    final T
    replaceRoot(T x)
    Replaces the root of this with x, and returns the old root.
    final T
    root()
    Reports the root of this.
    final int
    size()
    Reports the size of this.
    final void
    transferFrom(Tree<T> source)
    Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this.

    Methods inherited from class components.tree.TreeSecondary

    addSubtree, equals, hashCode, removeSubtree, toString

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • Tree1

      public Tree1()
      No-argument constructor.

  • Method Details

    • newInstance

      public final Tree<T> newInstance()
      Description copied from interface: Standard
      Returns a new object with the same dynamic type as this, having an initial value. If the type T has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then the value of the new returned object satisfies the contract of the constructor call that was used to initialize this .
      Returns:
      new object "like" this with an initial value

    • clear

      public final void clear()
      Description copied from interface: Standard
      Resets this to an initial value. If the type T has a no-argument constructor, then this satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then this satisfies the contract of the constructor call that was used to initialize #this.

    • transferFrom

      public final void transferFrom(Tree<T> source)
      Description copied from interface: Standard
      Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this. If the type T has a no-argument constructor, then source satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then source satisfies the contract of the constructor call that was used to initialize #source.
      Parameters:
      source - object whose value is to be transferred

    • newSequenceOfTree

      public final Sequence<Tree<T>> newSequenceOfTree()
      Description copied from interface: TreeKernel
      Creates and returns an empty Sequence<Tree<T>> of the dynamic type needed in assemble and disassemble.
      Returns:
      a new empty Sequence<Tree<T>>

    • assemble

      public final void assemble(T root, Sequence<Tree<T>> children)
      Description copied from interface: TreeKernel
      Assembles in this a tree with root label root and subtrees children; the declaration notwithstanding, the dynamic type of each entry of children must be the same as the dynamic type of this and the dynamic type of children must be the same as that returned by newSequenceOfTree.
      Parameters:
      root - the root label
      children - the subtrees

    • disassemble

      public final T disassemble(Sequence<Tree<T>> children)
      Description copied from interface: TreeKernel
      Disassembles this into its root label, which is returned as the value of the function, and subtrees in children; the declaration notwithstanding, the dynamic type of children must be the same as that returned by newSequenceOfTree.
      Parameters:
      children - the subtrees
      Returns:
      the root label

    • size

      public final int size()
      Description copied from interface: TreeKernel
      Reports the size of this.
      Returns:
      the size

    • iterator

      public final Iterator<T> iterator()

    • root

      public final T root()
      Description copied from interface: Tree
      Reports the root of this.
      Specified by:
      root in interface Tree<T>
      Overrides:
      root in class TreeSecondary<T>
      Returns:
      the root entry of this

    • replaceRoot

      public final T replaceRoot(T x)
      Description copied from interface: Tree
      Replaces the root of this with x, and returns the old root.
      Specified by:
      replaceRoot in interface Tree<T>
      Overrides:
      replaceRoot in class TreeSecondary<T>
      Parameters:
      x - the new root
      Returns:
      the old root

    • height

      public final int height()
      Description copied from interface: Tree
      Reports the height of this.
      Specified by:
      height in interface Tree<T>
      Overrides:
      height in class TreeSecondary<T>
      Returns:
      the height

    • numberOfSubtrees

      public final int numberOfSubtrees()
      Description copied from interface: Tree
      Returns the number of subtrees of the root of this.
      Specified by:
      numberOfSubtrees in interface Tree<T>
      Overrides:
      numberOfSubtrees in class TreeSecondary<T>
      Returns:
      the number of subtrees of the root of this