Ordered tree are tree where the elements of a same parent are in a specific order
Elements of the trees are added with the add
method that takes a parent and
a sub-element.
If the parent is null
, then the element is considered a root.
var t = new OrderedTree[String]
t.add(null, "root")
t.add("root", "child1")
t.add("root", "child2")
t.add("child1", "grand-child")
assert t.length == 4
By default, the elements with a same parent are visited in the order they are added.
assert t.to_a == ["root", "child1", "grand-child", "child2"]
assert t.write_to_string == """
root
|--child1
| `--grand-child
`--child2
"""
The sort_with
method can be used reorder elements
t.add("root", "aaa")
assert t.to_a == ["root", "child1", "grand-child", "child2", "aaa"]
t.sort_with(alpha_comparator)
assert t.to_a == ["root", "aaa", "child1", "grand-child", "child2"]
This class can be used as it to work with generic trees but can also be specialized to provide more specific behavior or display. It is why the internal attributes are mutable.
ordered_tree :: OrderedTree :: add_all
Append all nodeses
as children of p
.
ordered_tree :: OrderedTree :: display
How to display a specific element of the treeordered_tree :: OrderedTree :: roots=
The roots of the tree (in sequence)ordered_tree :: OrderedTree :: sort_with
Sort roots and other elements using a comparator methodordered_tree :: OrderedTree :: sub=
The branches of the trees.ordered_tree :: OrderedTree :: write_line
Write the full line for the elemente
in o
.
ordered_tree $ OrderedTree :: ==
Two trees are equal if they have the same nodes in the same orderordered_tree $ OrderedTree :: SELF
Type of this instance, automatically specialized in every classordered_tree $ OrderedTree :: has
Isitem
in the collection ?
ordered_tree $ OrderedTree :: iterator
var tree = new OrderedTree[Int]
core :: Collection :: CONCURRENT
Type of the concurrent variant of this collectionordered_tree :: OrderedTree :: add_all
Append all nodeses
as children of p
.
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Collection :: combinations
Allr
-length combinations on self (in same order) without repeated elements.
core :: Collection :: combinations_with_replacement
Allr
-length combination on self (in same order) with repeated elements.
core :: Cloneable :: defaultinit
core :: Collection :: defaultinit
core :: Writable :: defaultinit
core :: Object :: defaultinit
ordered_tree :: OrderedTree :: display
How to display a specific element of the treecore :: Collection :: has_all
Does the collection contain at least each element ofother
?
core :: Collection :: has_any
Does the collection contain at least one element ofother
?
core :: Collection :: has_exactly
Does the collection contain exactly all the elements ofother
?
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: Object :: output_class_name
Display class name on stdout (debug only).core :: Collection :: permutations
Allr
-length permutations on self (all possible ordering) without repeated elements.
core :: Collection :: product
Cartesian product, overr
times self
.
ordered_tree :: OrderedTree :: roots=
The roots of the tree (in sequence)ordered_tree :: OrderedTree :: sort_with
Sort roots and other elements using a comparator methodordered_tree :: OrderedTree :: sub=
The branches of the trees.core :: Collection :: to_concurrent
Wrapsself
in a thread-safe collection
core :: Collection :: to_counter
Create and fill up a counter with the elements of `self.core :: Collection :: to_curlslist
Convert Collection[String] to CURLSListcore :: Collection :: to_shuffle
Return a new array made of elements in a random order.ordered_tree :: OrderedTree :: write_line
Write the full line for the elemente
in o
.
core :: Writable :: write_to_bytes
Likewrite_to
but return a new Bytes (may be quite large)
core :: Writable :: write_to_file
Likewrite_to
but take care of creating the file
core :: Writable :: write_to_string
Likewrite_to
but return a new String (may be quite large).
# Generic structure to manage and display an ordered tree
#
# Ordered tree are tree where the elements of a same parent are in a specific order
#
# Elements of the trees are added with the `add` method that takes a parent and
# a sub-element.
# If the parent is `null`, then the element is considered a root.
#
# ~~~~
# var t = new OrderedTree[String]
# t.add(null, "root")
# t.add("root", "child1")
# t.add("root", "child2")
# t.add("child1", "grand-child")
# assert t.length == 4
# ~~~~
#
# By default, the elements with a same parent
# are visited in the order they are added.
#
# ~~~
# assert t.to_a == ["root", "child1", "grand-child", "child2"]
# assert t.write_to_string == """
# root
# |--child1
# | `--grand-child
# `--child2
# """
# ~~~
#
# The `sort_with` method can be used reorder elements
#
# ~~~
# t.add("root", "aaa")
# assert t.to_a == ["root", "child1", "grand-child", "child2", "aaa"]
# t.sort_with(alpha_comparator)
# assert t.to_a == ["root", "aaa", "child1", "grand-child", "child2"]
# ~~~
#
# This class can be used as it to work with generic trees but can also be specialized to provide more specific
# behavior or display. It is why the internal attributes are mutable.
class OrderedTree[E: Object]
super Writable
super Collection[E]
super Cloneable
# The roots of the tree (in sequence)
var roots = new Array[E]
# The branches of the trees.
# For each element, the ordered array of its direct sub-elements.
var sub = new HashMap[E, Array[E]]
# The parent of each element.
#
# Roots have `null` as parent.
private var parents = new HashMap[E, nullable E]
redef fun length do return parents.length
redef fun has(e) do return parents.has_key(e)
# The parent of the element `e`
#
# Roots have `null` as parent.
#
# ~~~
# var tree = new OrderedTree[Int]
# tree.add(1, 2)
# assert tree.parent(2) == 1
# assert tree.parent(1) == null
# ~~~
fun parent(e: E): nullable E do return parents[e]
# Add a new element `e` in the tree.
#
# `p` is the parent of `e`.
# If `p` is null, then `e` is a root element.
#
# If `e` is already in the tree, it is detached from its old
# parent and attached to the new parent `p`.
fun add(p: nullable E, e: E)
do
detach(e)
parents[e] = p
if p == null then
roots.add(e)
else
if not has(p) then add(null, p)
if sub.has_key(p) then
sub[p].add(e)
else
sub[p] = [e]
end
end
end
# Append all nodes `es` as children of `p`.
fun add_all(p: nullable E, es: Collection[E])
do
for e in es do add(p, e)
end
# Temporary remove `e`.
#
# Children of `e` are left untouched in the tree.
# This make the tree inconstant until `e` is added back.
private fun detach(e: E)
do
var old_parent = parents.get_or_null(e)
if old_parent != null then
var subs = sub[old_parent]
subs.remove(e)
if subs.is_empty then
# remove the sub when all children are detached
# so that `==` and `hash` are sane
# Otherwise an empty array will be considered
# differently than no array.
sub.keys.remove(old_parent)
end
else if roots.has(e) then
roots.remove(e)
end
end
# print the full tree on `o`
# Write a ASCII-style tree and use the `display` method to label elements
redef fun write_to(stream: Writer)
do
for r in roots do
write_line(stream, r, "")
sub_write_to(stream, r, "")
end
end
private fun sub_write_to(o: Writer, e: E, prefix: String)
do
if not sub.has_key(e) then return
var subs = sub[e]
if subs.is_empty then return
var last = subs.last
for e2 in subs do
if e2 != last then
write_line(o, e2, prefix+"|--")
sub_write_to(o, e2, prefix+"| ")
else
write_line(o, e2, prefix+"`--")
sub_write_to(o, e2, prefix+" ")
end
end
end
# Write the full line for the element `e` in `o`.
#
# Basically it does:
#
# ~~~nitish
# o.write "{prefix}{display(e)}\n"
# ~~~
#
# Usually, you should redefine `display` to change the display of an element.
protected fun write_line(o: Writer, e: E, prefix: String)
do
o.write "{prefix}{display(e)}\n"
end
# Sort roots and other elements using a comparator method
# This method basically sorts roots then each group of children
fun sort_with(comparator: Comparator)
do
comparator.sort(roots)
for a in sub.values do
comparator.sort(a)
end
end
# How to display a specific element of the tree
# By defaut, uses `to_s`
#
# Subclasses should redefine this method to provide a specific output
fun display(e: E): String do return e.to_s
# Get an array of the contained elements
# Order is preserved
#
# var tree = new OrderedTree[Int]
# tree.add_all(null, [1, 2])
# tree.add_all(1, [11, 12])
# tree.add_all(11, [111, 112])
# tree.add_all(12, [121, 122])
# tree.add_all(2, [21, 22])
# assert tree.to_a == [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
redef fun to_a: Array[E] do
var res = new Array[E]
for r in roots do sub_to_a(r, res)
return res
end
private fun sub_to_a(e: E, res: Array[E]) do
res.add e
if sub.has_key(e) then for e2 in sub[e] do sub_to_a(e2, res)
end
# var tree = new OrderedTree[Int]
# assert tree.is_empty
# tree.add(null, 1)
# assert not tree.is_empty
redef fun is_empty: Bool do return roots.is_empty
# var tree = new OrderedTree[Int]
# tree.add(null, 1)
# tree.add(1, 11)
# assert tree.first == 1
redef fun first do return roots.first
# var tree = new OrderedTree[Int]
# tree.add_all(null, [1, 2])
# tree.add_all(1, [11, 12])
# tree.add_all(11, [111, 112])
# tree.add_all(12, [121, 122])
# tree.add_all(2, [21, 22])
# var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
# assert tree.iterator.to_a == order
redef fun iterator do return new OrderedTreeIterator[E](self)
# Two trees are equal if they have the same nodes in the same order
#
# ~~~
# var t1 = new OrderedTree[Int]
# t1.add_all(null, [1, 2])
# t1.add_all(1, [11, 12])
#
# var t2 = new OrderedTree[Int]
# t2.add_all(null, [1, 2])
#
# assert t1 != t2
#
# t2.add_all(1, [11, 12])
#
# assert t1 == t2
# ~~~
redef fun ==(other)
do
if not other isa OrderedTree[Object] then return false
return roots == other.roots and sub == other.sub
end
redef fun hash
do
return roots.hash + sub.hash
end
# Shallow clone of the tree.
#
# ~~~
# var t = new OrderedTree[Int]
# t.add_all(null, [1, 2])
# t.add_all(1, [11, 12])
#
# assert t.clone == t
# ~~~
redef fun clone
do
var res = new OrderedTree[E]
res.add_all(null, roots)
for p, es in sub do
res.add_all(p, es)
end
return res
end
end
lib/ordered_tree/ordered_tree.nit:20,1--290,3