Introduction
Look at this:
Public Class Tree(Of T) : Inherits List(Of Tree(Of T))
Public Value As T
End Class
I don't know, whether it's real new, but I think, this could be the base for a lot of hierarchical data-structures. Since it's a generic Tree, Value can be anything.
Let's do a small extension and see it running:
Public Class Tree(Of T) : Inherits List(Of Tree(Of T))
Public Value As T
Public Sub New(ByVal Value As T)
Me.Value = Value
End Sub
Public Function AddNew(ByVal Value As T) As Tree(Of T)
Dim Node As New Tree(Of T)(Value)
MyBase.Add(Node)
Return Node
End Function
End Class
Sub EnumerateTree(Of T)(ByVal Parent As Tree(Of T))
WriteLine(Parent.Value)
Indent += 2
For Each Child In Parent
EnumerateTree(Child)
Next
Indent -= 2
End Sub
Sub Main()
Dim Vehicles As New Tree(Of String)("Vehicle")
With Vehicles
With .AddNew("OnWater")
.AddNew("SurfBoard")
With .AddNew("Ship")
With .AddNew("Motorboat")
.AddNew("Steamboat")
.AddNew("Submarine")
.AddNew("Tanker").AddNew("Tanker2").AddNew("Tanker3")
.AddNew("Speedboat")
End With
With .AddNew("Sailboat")
.AddNew("Cog")
.AddNew("Frigate")
.AddNew("Catamaran")
End With
End With
End With
With .AddNew("OnAir")
.AddNew("Plane")
With .AddNew("Rocket")
.AddNew("Challenger")
.AddNew("Apollo 13")
End With
.AddNew("Balloon")
End With
With .AddNew("OnEarth")
.AddNew("Horse")
With .AddNew("Car")
.AddNew("Trabant")
End With
.AddNew("Bike")
.AddNew("Foot")
End With
End With
EnumerateTree(Vehicles)
End Sub
Actually I'm finished now, but I'd like to append some stuff about iterating trees. You're right, I said "iterating", not "recursing". (Was that a pun?).
Some More
Recursion has the principle lack, that you need to create a special function for each kind of all-element-access.
How nice it would be, to loop all nodes with simple ForEach
!
Jepp, and here we go:
Public Class HEnumerating : Implements IEnumerable
Protected _Enrt As New Enumerator
Public Sub New(ByVal Roots As IEnumerable)
_Enrt.Roots = Roots.GetEnumerator
End Sub
Public Function GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
_Enrt.Reset()
Return _Enrt
End Function
Public Sub SkipChildren()
_Enrt._ParentEnumerators.Pop()
End Sub
Public ReadOnly Property CurrentDepth() As Integer
Get
Return _Enrt._ParentEnumerators.Count - 2
End Get
End Property
Protected Class Enumerator : Implements IEnumerator
Friend Roots As IEnumerator
Friend _ParentEnumerators As New Stack(Of IEnumerator)
Private _EnrtCurr As IEnumerator
Public Sub Reset() Implements IEnumerator.Reset
_ParentEnumerators.Clear()
Roots.Reset()
_ParentEnumerators.Push(Roots)
End Sub
Private Function MoveNext() As Boolean Implements IEnumerator.MoveNext
While _ParentEnumerators.Count > 0
_EnrtCurr = _ParentEnumerators.Peek
If _EnrtCurr.MoveNext Then
_ParentEnumerators.Push( _
DirectCast(_EnrtCurr.Current, IEnumerable).GetEnumerator)
Return True
Else
_ParentEnumerators.Pop()
End If
End While
Return False
End Function
Private ReadOnly Property Current() As Object Implements IEnumerator.Current
Get
Return _EnrtCurr.Current
End Get
End Property
End Class
End Class
Of course our tree wants one of this fabulous class - ah, be generous - give him two. One to iterate his children, and one to get iterated, including himself.
Public Class Tree(Of T) : Inherits List(Of Tree(Of T))
Public Value As T
Public Sub New(ByVal Value As T)
Me.Value = Value
End Sub
Public Function AddNew(ByVal Value As T) As Tree(Of T)
Dim Node As New Tree(Of T)(Value)
MyBase.Add(Node)
Return Node
End Function
Public Function ChildEnumerating() As HEnumerating
Static ChildRetVal As New HEnumerating(Me)
Return ChildRetVal
End Function
Public Function RootEnumerating() As HEnumerating
Static RetVal As New HEnumerating(New Tree(Of T)() {Me})
Return RetVal
End Function
Public Function GetNodeCount() As Integer
For Each Nd As Tree(Of T) In Me
GetNodeCount += 1 + Nd.GetNodeCount
Next
End Function
End Class
The HEnumerating
- objects are encapsulated in the Root-/Child-Enumerating()
-function. In effect most nodes never need to instantiate them.
Now we can do different selections without any effort.
For Each Nd As Tree(Of String) In Vehicles.RootEnumerating()
If Nd.Value.StartsWith("S") Then WriteLine(Nd.Value)
Next
WriteLine()
Dim RootEnumerating = Vehicles.RootEnumerating()
For Each Nd As Tree(Of String) In RootEnumerating
If RootEnumerating.CurrentDepth > 2 Then WriteLine(Nd.Value)
Next
WriteLine()
For Each Nd As Tree(Of String) In RootEnumerating
If RootEnumerating.CurrentDepth > 2 Then
RootEnumerating.SkipChildren()
Else
WriteLine(Nd.Value)
End If
Next
Try write these three searches using usual recursion!
Also note the benefit of .CurrentDepth()
and .SkipChildren()
.
Postscript
The given code is quite dirty, I know (booh, no Properties!!). But it shows the Ideas behind quite clearly, I hope.
History
- 15th January, 2008: Initial post