1 #Region "Microsoft.VisualBasic::f75d2f33ac4ac1a36e313aad67ca0b54, Microsoft.VisualBasic.Core\ComponentModel\DataStructures\BucketDictionary.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 BucketDictionary
35     
36     '         Properties: Count, Keys, Values
37     
38     '         Constructor: (+2 OverloadsSub New
39     '         Function: ContainsKey, GetEnumerator, IEnumerable_GetEnumerator, ToString, TryGetValue
40     
41     '     Module BucketDictionaryExtensions
42     
43     '         Function: (+2 Overloads) CreateBuckets
44     
45     
46     ' /********************************************************************************/
47
48 #End Region
49
50 Imports System.Runtime.CompilerServices
51 Imports Microsoft.VisualBasic.Language
52 Imports Microsoft.VisualBasic.Linq
53
54 Namespace ComponentModel.Collection
55
56     ''' <summary>
57     ''' An ultralarge size dictionary object.
58     ''' (当你发现一个数据集合非常的大的时候,一个字典会出现溢出,则这个时候就需要这个超大容量的Bucket字典容器了)
59     ''' </summary>
60     ''' <typeparam name="K"></typeparam>
61     ''' <typeparam name="V"></typeparam>
62     Public Class BucketDictionary(Of K, V) : Implements IReadOnlyDictionary(Of K, V)
63
64         Friend ReadOnly __buckets As New List(Of Dictionary(Of K, V))
65         ''' <summary>
66         ''' 每一个字典之中的最大的元素数目
67         ''' </summary>
68         ReadOnly bucketSize As Integer
69
70         Sub New(bucketSize As Integer)
71             Me.bucketSize = bucketSize
72         End Sub
73
74         Sub New()
75             Call Me.New(Short.MaxValue * 10)
76         End Sub
77
78         ''' <summary>
79         ''' 获取这个超大的字典集合之中的对象的数量总数
80         ''' </summary>
81         ''' <returns></returns>
82         Public ReadOnly Property Count As Integer Implements IReadOnlyCollection(Of KeyValuePair(Of K, V)).Count
83             <MethodImpl(MethodImplOptions.AggressiveInlining)>
84             Get
85                 Return __buckets.Sum(Function(x) x.Count)
86             End Get
87         End Property
88
89         ''' <summary>
90         ''' 注意,不要直接使用这个方法来添加新的数据,使用<see cref="BucketDictionaryExtensions"/>的方法会更加高效
91         ''' </summary>
92         ''' <param name="key"></param>
93         ''' <returns></returns>
94         Default Public Property Item(key As K) As V Implements IReadOnlyDictionary(Of K, V).Item
95             Get
96                 For Each hash In __buckets
97                     If hash.ContainsKey(key) Then
98                         Return hash(key)
99                     End If
100                 Next
101
102                 Return Nothing
103             End Get
104             Set(value As V)
105                 If __buckets.Count = 0 Then
106                     Call __buckets.Add(New Dictionary(Of K, V) From {{key, value}})
107                 Else
108                     For Each hash In __buckets
109                         If hash.ContainsKey(key) Then
110                             hash(key) = value
111                             Return
112                         End If
113                     Next
114
115                     Dim min = LinqAPI.DefaultFirst(Of Dictionary(Of K, V)) _
116  _
117                         () <= From x As Dictionary(Of K, V)
118                               In __buckets
119                               Select x
120                               Order By x.Count Ascending
121
122                     min(key) = value
123
124                     If min.Count >= bucketSize Then
125                         Call __buckets.Add(New Dictionary(Of K, V))
126                     End If
127                 End If
128             End Set
129         End Property
130
131         Public ReadOnly Property Keys As IEnumerable(Of K) Implements IReadOnlyDictionary(Of K, V).Keys
132             <MethodImpl(MethodImplOptions.AggressiveInlining)>
133             Get
134                 Return __buckets.Select(Function(x) x.Keys).IteratesALL
135             End Get
136         End Property
137
138         Public ReadOnly Property Values As IEnumerable(Of V) Implements IReadOnlyDictionary(Of K, V).Values
139             <MethodImpl(MethodImplOptions.AggressiveInlining)>
140             Get
141                 Return __buckets.Select(Function(x) x.Values).IteratesALL
142             End Get
143         End Property
144
145         Public Overrides Function ToString() As String
146             Return $"Tuple of [{GetType(K).Name}, {GetType(V).Name}] with {__buckets.Count} buckets."
147         End Function
148
149         Public Function ContainsKey(key As K) As Boolean Implements IReadOnlyDictionary(Of K, V).ContainsKey
150             For Each hash In __buckets
151                 If hash.ContainsKey(key) Then
152                     Return True
153                 End If
154             Next
155
156             Return False
157         End Function
158
159         Public Iterator Function GetEnumerator() As IEnumerator(Of KeyValuePair(Of K, V)) Implements IEnumerable(Of KeyValuePair(Of K, V)).GetEnumerator
160             For Each hash In __buckets
161                 For Each x In hash
162                     Yield x
163                 Next
164             Next
165         End Function
166
167         Public Function TryGetValue(key As K, ByRef value As V) As Boolean Implements IReadOnlyDictionary(Of K, V).TryGetValue
168             For Each hash In __buckets
169                 If hash.ContainsKey(key) Then
170                     value = hash(key)
171                     Return True
172                 End If
173             Next
174
175             Return False
176         End Function
177
178         Private Iterator Function IEnumerable_GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
179             Yield GetEnumerator()
180         End Function
181     End Class
182
183     Public Module BucketDictionaryExtensions
184
185         <Extension>
186         Public Function CreateBuckets(Of T, K, V)(source As IEnumerable(Of T), getKey As Func(Of T, K), getValue As Func(Of T, V), Optional size% = Short.MaxValue * 10) As BucketDictionary(Of K, V)
187             Dim table As New BucketDictionary(Of K, V)(size)
188             Dim bucket As New Dictionary(Of K, V)
189
190             For Each x As T In source
191                 Dim key As K = getKey(x)
192                 Dim value As V = getValue(x)
193
194                 Call bucket.Add(key, value)
195
196                 If bucket.Count >= size Then
197                     table.__buckets.Add(bucket)
198                     bucket = New Dictionary(Of K, V)
199                 End If
200             Next
201
202             table.__buckets.Add(bucket)
203
204             Return table
205         End Function
206
207         <MethodImpl(MethodImplOptions.AggressiveInlining)>
208         <Extension>
209         Public Function CreateBuckets(Of K, V)(source As IEnumerable(Of (K, V)), Optional size% = Short.MaxValue * 10) As BucketDictionary(Of K, V)
210             Return source.CreateBuckets(Function(t) t.Item1, Function(t) t.Item2, size:=size)
211         End Function
212     End Module
213 End Namespace