|
'/<summary>
'/ The TreapEnumerator class returns the keys or objects of the treap in
'/ sorted order.
'/</summary>
Imports System.Collections
Namespace TreapVB
Public Class TreapEnumerator
' the treap uses the stack to order the nodes
Private stack As Stack
' return the keys
Private keys As Boolean
' return in ascending order (true) or descending (false)
Private ascending As Boolean
' key
Private Dim ordKey As IComparable
' the data or value associated with the key
Private Dim objValue As Object
'/<summary>
'/Key
'/</summary>
Public Property Key() As IComparable
Get
Return ordKey
End Get
Set (ByVal Value As IComparable)
ordKey = value
End Set
End Property
'/<summary>
'/Data
'/</summary>
Public Property Value() As Object
Get
Return objValue
End Get
Set (ByVal Value As Object)
objValue = value
End Set
End Property
Public Sub New()
End Sub
'/<summary>
'/ Determine order, walk the tree and push the nodes onto the stack
'/</summary>
Public Sub New (ByVal tnode As TreapNode, _
ByVal keys As Boolean, _
ByVal ascending As Boolean )
stack = New Stack()
Me.keys = keys
Me.ascending = ascending
' find the lowest node
If(ascending)
While Not (tnode Is Nothing)
stack.Push(tnode)
tnode = tnode.Left
End While
Else
' find the highest or greatest node
While Not (tnode Is Nothing)
stack.Push(tnode)
tnode = tnode.Right
End While
End If
End Sub
'/<summary>
'/ HasMoreElements
'/</summary>
Public Function HasMoreElements() As Boolean
Return (stack.Count() > 0)
End Function
'/<summary>
'/ NextElement
'/</summary>
Public Function NextElement() As Object
If(stack.Count = 0)
Throw New TreapException("Element not found")
End If
' the top of stack will always have the next item
' get top of stack but don't remove it as the next nodes in sequence
' may be pushed onto the top
' the stack will be popped after all the nodes have been returned
Dim node As TreapNode = CType(stack.Peek(), TreapNode)
If ascending
' if right node is nothing, the stack top is the lowest node
' if left node is nothing, the stack top is the highest node
If node.Right Is Nothing
' walk the tree
Dim tn As TreapNode = CType(stack.Pop(), TreapNode)
While (HasMoreElements()) AndAlso _
((CType(stack.Peek(), TreapNode)).Right Is tn)
tn = CType(stack.Pop(), TreapNode)
End While
Else
' find the next items in the sequence
' traverse to left; find lowest and push onto stack
Dim tn As TreapNode = node.Right
While Not (tn Is Nothing)
stack.Push(tn )
tn = tn.Left
End While
End If
' descending
Else _
If node.Left Is Nothing
' walk the tree
Dim tn As TreapNode = CType(stack.Pop(), TreapNode)
While (HasMoreElements()) AndAlso _
((CType(stack.Peek(), TreapNode)).left Is tn)
tn = CType(stack.Pop(), TreapNode)
End While
Else
' find the next items in the sequence
' traverse to right; find highest and push onto stack
Dim tn As TreapNode = node.Left
While Not (tn Is Nothing)
stack.Push(tn )
tn = tn.Right
End While
End If
' the following is for .NET compatibility (see MoveNext())
Key = node.Key
Value = node.Data
Dim objValue As Object = IIf(keys = True, node.Key, node.Data)
Return objValue
End Function
'/<summary>
'/ MoveNext
'/ For .NET compatibility
'/</summary>
Public Function MoveNext() As Boolean
If HasMoreElements()
NextElement()
Return True
Else
Return False
End If
End Function
End Class
End Namespace
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
Roy is a software developer who digs all aspects of software development, from design and architecture to implementation.