1	#Region "Microsoft.VisualBasic::6abf7be1188e9cce30e4aa8d6f07be60, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\BinaryTree\NaiveBinaryTree.vb"
2
3	' Author:
4	'
5	'       asuka (amethyst.asuka@gcmodeller.org)
6	'       xie (genetics@smrucc.org)
7	'       xieguigang (xie.guigang@live.com)
8	'
9	' Copyright (c) 2018 GPL3 Licensed
10	'
11	'
12	' GNU GENERAL PUBLIC LICENSE (GPL3)
13	'
14	'
15	' This program is free software: you can redistribute it and/or modify
16	' it under the terms of the GNU General Public License as published by
17	' the Free Software Foundation, either version 3 of the License, or
18	' (at your option) any later version.
19	'
20	' This program is distributed in the hope that it will be useful,
21	' but WITHOUT ANY WARRANTY; without even the implied warranty of
22	' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23	' GNU General Public License for more details.
24	'
25	' You should have received a copy of the GNU General Public License
26	' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30	' /********************************************************************************/
31
32	' Summaries:
33
34	'     Class NaiveBinaryTree
35	'
36	'         Properties: Length
37	'
38	'         Constructor: (+2 Overloads) Sub New
39	'
40	'         Function: add, drawNode, findSuccessor, FindSymbol, insert
41	'                   ToString
42	'
43	'         Sub: clear, delete, KillTree
44	'
45	'
46	' /********************************************************************************/
47
48	#End Region
49
50	Imports System.Runtime.CompilerServices
51
52	' Software License Agreement (BSD License)
53	'*
54	'* Copyright (c) 2003, Herbert M Sauro
55	'* All rights reserved.
56	'*
57	'* Redistribution and use in source and binary forms, with or without
58	'* modification, are permitted provided that the following conditions are met:
59	'*     * Redistributions of source code must retain the above copyright
60	'*       notice, this list of conditions and the following disclaimer.
61	'*     * Redistributions in binary form must reproduce the above copyright
62	'*       notice, this list of conditions and the following disclaimer in the
63	'*       documentation and/or other materials provided with the distribution.
64	'*     * Neither the name of Herbert M Sauro nor the
65	'*       names of its contributors may be used to endorse or promote products
66	'*       derived from this software without specific prior written permission.
67	'*
68	'* THIS SOFTWARE IS PROVIDED BY <copyright holder> ``AS IS'' AND ANY
69	'* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
70	'* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
71	'* DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
72	'* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
73	'* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
74	'* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
75	'* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
76	'* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
77	'* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
78	'
79
80	Namespace ComponentModel.Algorithm.BinaryTree
81
82	''' <summary>
83	''' The Binary tree itself. 朴素二叉树
84	'''
85	''' A very basic Binary Search Tree. Not generalized, stores
86	''' name/value pairs in the tree nodes. name is the node key.
87	''' The advantage of a binary tree is its fast insert and lookup
88	''' characteristics. This version does not deal with tree balancing.
89	''' (二叉搜索树，用于建立对repository的索引文件)
90	''' </summary>
91	''' <remarks></remarks>
92	Public Class NaiveBinaryTree(Of K, V) : Inherits TreeBase(Of K, V)
93
94	''' <summary>
95	''' Returns the number of nodes in the tree
96	''' </summary>
97	''' <returns>Number of nodes in the tree</returns>
98	Public ReadOnly Property Length As Integer
99	<MethodImpl(MethodImplOptions.AggressiveInlining)>
100	Get
101	Return stack.Count
102	End Get
103	End Property
104
105	Public Sub New(key As K, value As V, compares As Comparison(Of K), Optional views As Func(Of K, String) = Nothing)
106	Call MyBase.New(compares, views)
107	Call Me.insert(key, value)
108	End Sub
109
110	Public Sub New(compares As Comparison(Of K), Optional views As Func(Of K, String) = Nothing)
111	MyBase.New(compares, views)
112	End Sub
113
114	' Recursive destruction of binary search tree, called by method clear
115	' and destroy. Can be used to kill a sub-tree of a larger tree.
116	' This is a hanger on from its Delphi origins, it might be dispensable
117	' given the garbage collection abilities of .NET
118	Private Sub KillTree(ByRef p As BinaryTree(Of K, V))
119	If p IsNot Nothing Then
120	KillTree(p.Left)
121	KillTree(p.Right)
122	p = Nothing
123	End If
124	End Sub
125
126	''' <summary>
127	''' Clear the binary tree.
128	''' </summary>
129	Public Sub clear()
130	Call KillTree(root)
131	Call stack.Clear()
132	End Sub
133
134	''' <summary>
135	''' Find name in tree. Return a reference to the node
136	''' if symbol found else return null to indicate failure.
137	''' </summary>
138	''' <param name="key">Name of node to locate</param>
139	''' <returns>Returns null if it fails to find the node, else returns reference to node</returns>
140	Public Function FindSymbol(key As K, Optional ByRef parent As BinaryTree(Of K, V) = Nothing) As BinaryTree(Of K, V)
141	Dim np As BinaryTree(Of K, V) = root
142	Dim cmp As Integer
143
144	parent = Nothing
145
146	While np IsNot Nothing
147	cmp = compares(key, np.Key)
148
149	If cmp = 0 Then
150	' found !
151	Return np
152	Else
153	parent = np
154	End If
155
156	If cmp < 0 Then
157	np = np.Left
158	Else
159	np = np.Right
160	End If
161	End While
162
163	' Return null to indicate failure to find name
164	Return Nothing
165	End Function
166
167	''' <summary>
168	''' Recursively locates an empty slot in the binary tree and inserts the node
169	''' </summary>
170	''' <param name="node"></param>
171	''' <param name="tree"></param>
172	''' <returns>
173	''' 当处于append模式下，append值的时候不会返回节点，而是返回nothing
174	''' </returns>
175	Private Function add(node As BinaryTree(Of K, V), ByRef tree As BinaryTree(Of K, V), append As Boolean) As BinaryTree(Of K, V)
176	Do While True
177	' If we find a node with the same name then it's
178	' a duplicate and we can't continue
179	Dim comparison As Integer = compares(node.Key, tree.Key)
180
181	If comparison = 0 Then
182	' Duplicated node was found!
183	If append Then
184	' clustering
185	DirectCast(tree!values, List(Of V)).Add(node.Value)
186	Return Nothing
187	Else
188	' Value replace when not append
189	tree.Value = node.Value
190	Return node
191	End If
192	ElseIf comparison < 0 Then
193	If Not tree.Left Is Nothing Then
194	tree = tree.Left
195	Else
196	tree.Left = node
197	Return node
198	End If
199	Else
200	If Not tree.Right Is Nothing Then
201	tree = tree.Right
202	Else
203	tree.Right = node
204	Return node
205	End If
206	End If
207	Loop
208
209	Throw New NotImplementedException("This exception will never happends!")
210	End Function
211
212	''' <summary>
213	''' Add a symbol to the tree if it's a new one. Returns reference to the new
214	''' node if a new node inserted, else returns null to indicate node already present.
215	''' </summary>
216	''' <returns> Returns reference to the new node is the node was inserted.
217	''' If a duplicate node (same name was located then returns null</returns>
218	Public Function insert(key As K, obj As V, Optional append As Boolean = True) As BinaryTree(Of K, V)
219	Dim node As New BinaryTree(Of K, V)(key, obj, toString:=views)
220
221	Try
222	If root Is Nothing Then
223	_root = node
224	Else
225	node = add(node, root, append)
226	End If
227
228	If Not node Is Nothing Then
229	Call stack.Add(node)
230	End If
231
232	Return node
233	Catch generatedExceptionName As Exception
234	Dim ex = New Exception(node.ToString, generatedExceptionName)
235	Return App.LogException(ex)
236	End Try
237	End Function
238
239	''' <summary>
240	''' Find the next ordinal node starting at node startNode.
241	''' Due to the structure of a binary search tree, the
242	''' successor node is simply the left most node on the right branch.
243	''' </summary>
244	''' <param name="startNode">Name key to use for searching</param>
245	''' <param name="parent">Returns the parent node if search successful</param>
246	''' <returns>Returns a reference to the node if successful, else null</returns>
247	Public Function findSuccessor(startNode As BinaryTree(Of K, V), ByRef parent As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
248	parent = startNode
249	' Look for the left-most node on the right side
250	startNode = startNode.Right
251	While startNode.Left IsNot Nothing
252	parent = startNode
253	startNode = startNode.Left
254	End While
255	Return startNode
256	End Function
257
258	''' <summary>
259	''' Delete a given node. This is the more complex method in the binary search
260	''' class. The method considers three senarios, 1) the deleted node has no
261	''' children; 2) the deleted node as one child; 3) the deleted node has two
262	''' children. Case one and two are relatively simple to handle, the only
263	''' unusual considerations are when the node is the root node. Case 3) is
264	''' much more complicated. It requires the location of the successor node.
265	''' The node to be deleted is then replaced by the sucessor node and the
266	''' successor node itself deleted. Throws an exception if the method fails
267	''' to locate the node for deletion.
268	''' </summary>
269	''' <param name="key">Name key of node to delete</param>
270	Public Sub delete(key As K)
271	Dim parent As BinaryTree(Of K, V) = Nothing
272	' First find the node to delete and its parent
273	Dim nodeToDelete As BinaryTree(Of K, V) = FindSymbol(key, parent)
274
275	If nodeToDelete Is Nothing Then
276	Throw New Exception("Unable to delete node: " & key.ToString())
277	End If
278	' can't find node, then say so
279	' Three cases to consider, leaf, one child, two children
280
281	' If it is a simple leaf then just null what the parent is pointing to
282	If (nodeToDelete.Left Is Nothing) AndAlso (nodeToDelete.Right Is Nothing) Then
283	If parent Is Nothing Then
284	_root = Nothing
285	Return
286	End If
287
288	' find out whether left or right is associated
289	' with the parent and null as appropriate
290	If parent.Left Is nodeToDelete Then
291	parent.Left = Nothing
292	Else
293	parent.Right = Nothing
294	End If
295
296	Call stack.Remove(nodeToDelete)
297
298	Return
299	End If
300
301	' One of the children is null, in this case
302	' delete the node and move child up
303	If nodeToDelete.Left Is Nothing Then
304	' Special case if we're at the root
305	If parent Is Nothing Then
306	_root = nodeToDelete.Right
307	Return
308	End If
309
310	' Identify the child and point the parent at the child
311	If parent.Left Is nodeToDelete Then
312	parent.Right = nodeToDelete.Right
313	Else
314	parent.Left = nodeToDelete.Right
315	End If
316	nodeToDelete = Nothing
317	' Clean up the deleted node
318	Call stack.Remove(nodeToDelete)
319
320	Return
321	End If
322
323	' One of the children is null, in this case
324	' delete the node and move child up
325	If nodeToDelete.Right Is Nothing Then
326	' Special case if we're at the root
327	If parent Is Nothing Then
328	_root = nodeToDelete.Left
329	Return
330	End If
331
332	' Identify the child and point the parent at the child
333	If parent.Left Is nodeToDelete Then
334	parent.Left = nodeToDelete.Left
335	Else
336	parent.Right = nodeToDelete.Left
337	End If
338	nodeToDelete = Nothing
339	' Clean up the deleted node
340	Call stack.Remove(nodeToDelete)
341
342	Return
343	End If
344
345	' Both children have nodes, therefore find the successor,
346	' replace deleted node with successor and remove successor
347	' The parent argument becomes the parent of the successor
348	Dim successor As BinaryTree(Of K, V) = findSuccessor(nodeToDelete, parent)
349	' Make a copy of the successor node
350	Dim tmp As New BinaryTree(Of K, V)(successor.Key, successor.Value)
351	' Find out which side the successor parent is pointing to the
352	' successor and remove the successor
353	If parent.Left Is successor Then
354	parent.Left = Nothing
355	Else
356	parent.Right = Nothing
357	End If
358
359	' Copy over the successor values to the deleted node position
360	Call nodeToDelete.Copy(tmp)
361	Call stack.Remove(nodeToDelete)
362	End Sub
363
364	' Simple 'drawing' routines
365	Private Function drawNode(node As BinaryTree(Of K, V)) As String
366	If node Is Nothing Then
367	Return "empty"
368	End If
369
370	If (node.Left Is Nothing) AndAlso (node.Right Is Nothing) Then
371	Return views(node.Key)
372	End If
373	If (node.Left IsNot Nothing) AndAlso (node.Right Is Nothing) Then
374	Return views(node.Key) & "(" & drawNode(node.Left) & ", _)"
375	End If
376
377	If (node.Right IsNot Nothing) AndAlso (node.Left Is Nothing) Then
378	Return views(node.Key) & "(_, " & drawNode(node.Right) & ")"
379	End If
380
381	Return views(node.Key) & "(" & drawNode(node.Left) & ", " & drawNode(node.Right) & ")"
382	End Function
383
384	''' <summary>
385	''' Return the tree depicted as a simple string, useful for debugging, eg
386	''' 50(40(30(20, 35), 45(44, 46)), 60)
387	''' </summary>
388	''' <returns>Returns the tree</returns>
389	Public Overrides Function ToString() As String
390	Return drawNode(root)
391	End Function
392	End Class
393	End Namespace