Subscribe to The Madman Scribblings        RSS Feed
-----

INode(Of T) and Traversal

Icon Leave Comment
INode(Of T) Interface
Public Interface INode(Of T)
  Property LHS As INode(Of T)
  Property RHS As INode(Of T)
  Property Value As T
End Interface


A simple implementation of it.

Public Class Node(Of T)
  Implements INode(Of T)
  Public Sub New()

  End Sub
  Public Sub New(Value As T)
    Me.Value = Value
  End Sub
  Public Property LHS As INode(Of T) Implements INode(Of T).LHS
  Public Property RHS As INode(Of T) Implements INode(Of T).RHS
  Public Property Value As T Implements INode(Of T).Value
End Class



The examples use the following extension methods, to make adding things to them the same and enable collection initialisors to work also.
Spoiler


Traversals

Depth First (Recursive)

Public Class DepthFirst_Recursive(Of T)
  Public Event UpdateCurrent(ThisNode As INode(Of T))
  Public Event FoundMatch(ThisNode As INode(Of T))
  Public Sub Filter(ByVal current As INode(Of T),
                    ByVal FilterPred As Func(Of INode(Of T), Boolean))
    If current Is Nothing Then Exit Sub
    If current.LHS IsNot Nothing Then Filter(current.LHS, FilterPred)
    RaiseEvent UpdateCurrent(current)
    If FilterPred(current) Then RaiseEvent FoundMatch(current)
    If current.RHS IsNot Nothing Then Filter(current.RHS, FilterPred)
  End Sub
End Class



Depth First (Recursive)

Public Class DepthFirst_Iterative(Of T)
  Public Event UpdateCurrent(ThisNode As INode(Of T))
  Public Event FoundMatch(ThisNode As INode(Of T))
  Public Sub Filter(ByVal StartNode As INode(Of T),
                    ByVal Filter As Func(Of INode(Of T), Boolean))
    Dim nodeQ As New Stack(Of INode(Of T)) From {StartNode}
    Dim current As INode(Of T) = Nothing
    While nodeQ.Any
      '   nodeQ.Pop()
      While nodeQ.Peek.LHS IsNot Nothing : nodeQ.Push(nodeQ.Peek.LHS)
      End While
      current = nodeQ.Pop
      RaiseEvent UpdateCurrent(current)
      If Filter(current) Then RaiseEvent FoundMatch(current)
      If current.RHS IsNot Nothing Then nodeQ.Push(current.RHS)
    End While
  End Sub
End Class



Breadth First (Iterative)

Public Class BreadthFirst_Iterative(Of T)
  Public Event UpdateCurrent(ThisNode As INode(Of T))
  Public Event FoundMatch(ThisNode As INode(Of T))
  Public Sub Filter(ByVal StartNode As INode(Of T),
                    ByVal Filter As Func(Of INode(Of T), Boolean))
    Dim nodeQ As New Queue(Of INode(Of T)) From {StartNode}
    While nodeQ.Any
      Dim current = nodeQ.Dequeue
      RaiseEvent UpdateCurrent(current)
      If Filter(current) Then RaiseEvent FoundMatch(current)
      If current.LHS IsNot Nothing Then nodeQ.Enqueue(current.LHS)
      If current.RHS IsNot Nothing Then nodeQ.Enqueue(current.RHS)
    End While
  End Sub
End Class




Usage Example
Imports System.Runtime.CompilerServices
Imports ConsoleApplication1.CollectionExts
Module Module1

  Sub Main()
    Dim nodes = New Node(Of Integer)(1) With {.LHS = New Node(Of Integer)(2) With {.LHS = New Node(Of Integer)(4),
                                                                                   .RHS = New Node(Of Integer)(5)},
                                              .RHS = New Node(Of Integer)(3) With {.LHS = New Node(Of Integer)(6),
                                                                                   .RHS = New Node(Of Integer)(7)}
                                             }
    Console.WriteLine("Breadth First (Iterative)")
    Dim b As New BreadthFirst_Iterative(Of Integer)
    AddHandler b.UpdateCurrent, Sub(n As INode(Of Integer)) Console.Write("{0} ", n.Value)
    AddHandler b.FoundMatch, Sub(n As INode(Of Integer)) Console.Write("[{0}] ", n.Value)
    b.Filter(nodes, Function(x As INode(Of Integer)) x.Value Mod 2 = 1)
    Console.WriteLine()
    Console.WriteLine("DepthFirst (Recursive)")
    Dim rdg As New DepthFirst_Recursive(Of Integer)
    AddHandler rdg.UpdateCurrent, Sub(n As INode(Of Integer)) Console.Write("{0} ", n.Value)
    AddHandler rdg.FoundMatch, Sub(n As INode(Of Integer)) Console.Write("[{0}] ", n.Value)
    rdg.Filter(nodes, Function(x As INode(Of Integer)) x.Value Mod 2 = 1)
    Console.WriteLine()
    Console.WriteLine("DepthFirst (Iterative)")
    Dim ndg As New DepthFirst_Recursive(Of Integer)
    AddHandler ndg.UpdateCurrent, Sub(n As INode(Of Integer)) Console.Write("{0} ", n.Value)
    AddHandler ndg.FoundMatch, Sub(n As INode(Of Integer)) Console.Write("[{0}] ", n.Value)
    ndg.Filter(nodes, Function(x As INode(Of Integer)) x.Value Mod 2 = 1)

  End Sub

End Module

0 Comments On This Entry

 

Search My Blog

Recent Entries

Recent Comments