1	#Region "Microsoft.VisualBasic::bacdc2924f8376fed143f63f8a9cee5d, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\BinaryTree\BinaryTree.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	'     Module Extensions
35	'
36	'         Function: Find, HasKey, Max, MaxKey, Min
37	'                   MinKey, TakeRange
38	'
39	'
40	' /********************************************************************************/
41
42	#End Region
43
44	Imports System.Runtime.CompilerServices
45
46	Namespace ComponentModel.Algorithm.BinaryTree
47
48	Public Module Extensions
49
50	''' <summary>
51	''' 查找失败会返回空值
52	''' </summary>
53	''' <typeparam name="K"></typeparam>
54	''' <typeparam name="V"></typeparam>
55	''' <param name="tree"></param>
56	''' <param name="key"></param>
57	''' <param name="compares"></param>
58	''' <returns></returns>
59	<Extension>
60	Public Function Find(Of K, V)(tree As BinaryTree(Of K, V), key As K, compares As Comparison(Of K)) As BinaryTree(Of K, V)
61	Do While Not tree Is Nothing
62	Select Case compares(key, tree.Key)
63	Case < 0 : tree = tree.Left
64	Case > 0 : tree = tree.Right
65	Case = 0
66	Return tree
67	End Select
68	Loop
69
70	Return Nothing
71	End Function
72
73	<MethodImpl(MethodImplOptions.AggressiveInlining)>
74	<Extension>
75	Public Function HasKey(Of K, V)(tree As BinaryTree(Of K, V), key As K, compares As Comparison(Of K)) As Boolean
76	Return Not tree.Find(key, compares) Is Nothing
77	End Function
78
79	<Extension>
80	Public Iterator Function TakeRange(Of K, V)(tree As BinaryTree(Of K, V), min As K, max As K, compares As Comparison(Of K)) As IEnumerable(Of Map(Of K, V))
81	Do While Not tree Is Nothing
82	Dim compare = (
83	min:=compares(min, tree.Key),
84	max:=compares(max, tree.Key)
85	)
86
87	If compare.min < 0 Then
88	tree = tree.Left
89	ElseIf compare.min <= 0 AndAlso compare.max >= 0 Then
90	Yield New Map(Of K, V)(tree.Key, tree.Value)
91
92	For Each map In tree.Left.TakeRange(min, max, compares)
93	Yield map
94	Next
95	For Each map In tree.Right.TakeRange(min, max, compares)
96	Yield map
97	Next
98
99	ElseIf compare.min > 0 OrElse compare.max > 0 Then
100	tree = tree.Right
101	End If
102	Loop
103	End Function
104
105	<Extension>
106	Public Function Min(Of K, V)(tree As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
107	Do While Not tree Is Nothing
108	If tree.Left Is Nothing Then
109	Return tree
110	Else
111	tree = tree.Left
112	End If
113	Loop
114
115	Return Nothing
116	End Function
117
118	<Extension>
119	Public Function Max(Of K, V)(tree As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
120	Do While Not tree Is Nothing
121	If tree.Right Is Nothing Then
122	Return tree
123	Else
124	tree = tree.Right
125	End If
126	Loop
127
128	Return Nothing
129	End Function
130
131	<Extension>
132	Public Function MinKey(Of K, V)(tree As BinaryTree(Of K, V)) As K
133	Dim min = tree.Min
134	Return If(min Is Nothing, Nothing, min.Key)
135	End Function
136
137	<Extension>
138	Public Function MaxKey(Of K, V)(tree As BinaryTree(Of K, V)) As K
139	Dim max = tree.Max
140	Return If(max Is Nothing, Nothing, max.Key)
141	End Function
142	End Module
143	End Namespace