1 #Region "Microsoft.VisualBasic::42aa90d57a9c12fb5abb3f794d617c0a, 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 NothingNothing, 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 NothingNothing, max.Key)
141         End Function
142     End Module
143 End Namespace