Package components.tree
Class Tree1<T>
java.lang.Object
components.tree.TreeSecondary<T>
components.tree.Tree1<T>
- Type Parameters:
T
- type ofTree
labels
- All Implemented Interfaces:
Standard<Tree<T>>
,Tree<T>
,TreeKernel<T>
,Iterable<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
-
Method Summary
Modifier and TypeMethodDescriptionfinal void
Assembles inthis
a tree with root labelroot
and subtreeschildren
; the declaration notwithstanding, the dynamic type of each entry ofchildren
must be the same as the dynamic type ofthis
and the dynamic type ofchildren
must be the same as that returned bynewSequenceOfTree
.final void
clear()
Resetsthis
to an initial value.final T
disassemble
(Sequence<Tree<T>> children) Disassemblesthis
into its root label, which is returned as the value of the function, and subtrees inchildren
; the declaration notwithstanding, the dynamic type ofchildren
must be the same as that returned bynewSequenceOfTree
.final int
height()
Reports the height ofthis
.iterator()
Returns a new object with the same dynamic type asthis
, having an initial value.Creates and returns an emptySequence<Tree<T>>
of the dynamic type needed inassemble
anddisassemble
.final int
Returns the number of subtrees of the root ofthis
.final T
replaceRoot
(T x) Replaces the root ofthis
withx
, and returns the old root.final T
root()
Reports the root ofthis
.final int
size()
Reports the size ofthis
.final void
transferFrom
(Tree<T> source) Setsthis
to the incoming value ofsource
, and resetssource
to an initial value; the declaration notwithstanding, the dynamic type ofsource
must be the same as the dynamic type ofthis
.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
Description copied from interface:Standard
Returns a new object with the same dynamic type asthis
, having an initial value. If the typeT
has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor forT
. IfT
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 initializethis
.- Returns:
- new object "like"
this
with an initial value
-
clear
Description copied from interface:Standard
Resetsthis
to an initial value. If the typeT
has a no-argument constructor, thenthis
satisfies the contract of the no-argument constructor forT
. IfT
does not have a no-argument constructor, thenthis
satisfies the contract of the constructor call that was used to initialize#this
. -
transferFrom
Description copied from interface:Standard
Setsthis
to the incoming value ofsource
, and resetssource
to an initial value; the declaration notwithstanding, the dynamic type ofsource
must be the same as the dynamic type ofthis
. If the typeT
has a no-argument constructor, thensource
satisfies the contract of the no-argument constructor forT
. IfT
does not have a no-argument constructor, thensource
satisfies the contract of the constructor call that was used to initialize#source
.- Parameters:
source
- object whose value is to be transferred
-
newSequenceOfTree
Description copied from interface:TreeKernel
Creates and returns an emptySequence<Tree<T>>
of the dynamic type needed inassemble
anddisassemble
.- Returns:
- a new empty
Sequence<Tree<T>>
-
assemble
Description copied from interface:TreeKernel
Assembles inthis
a tree with root labelroot
and subtreeschildren
; the declaration notwithstanding, the dynamic type of each entry ofchildren
must be the same as the dynamic type ofthis
and the dynamic type ofchildren
must be the same as that returned bynewSequenceOfTree
.- Parameters:
root
- the root labelchildren
- the subtrees
-
disassemble
Description copied from interface:TreeKernel
Disassemblesthis
into its root label, which is returned as the value of the function, and subtrees inchildren
; the declaration notwithstanding, the dynamic type ofchildren
must be the same as that returned bynewSequenceOfTree
.- Parameters:
children
- the subtrees- Returns:
- the root label
-
size
Description copied from interface:TreeKernel
Reports the size ofthis
.- Returns:
- the size
-
iterator
-
root
Description copied from interface:Tree
Reports the root ofthis
. -
replaceRoot
Description copied from interface:Tree
Replaces the root ofthis
withx
, and returns the old root.- Specified by:
replaceRoot
in interfaceTree<T>
- Overrides:
replaceRoot
in classTreeSecondary<T>
- Parameters:
x
- the new root- Returns:
- the old root
-
height
Description copied from interface:Tree
Reports the height ofthis
. -
numberOfSubtrees
Description copied from interface:Tree
Returns the number of subtrees of the root ofthis
.- Specified by:
numberOfSubtrees
in interfaceTree<T>
- Overrides:
numberOfSubtrees
in classTreeSecondary<T>
- Returns:
- the number of subtrees of the root of
this
-