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 |