1 #Region "Microsoft.VisualBasic::68b048fd5e6efadf7dd7cf304d168f50, Microsoft.VisualBasic.Core\ComponentModel\System.Collections.Generic\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: (+3 Overloads) Sub 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         Sub New(buckets As IEnumerable(Of Dictionary(Of K, V)))
79             __buckets = buckets.AsList
80         End Sub
81
82         ''' <summary>
83         ''' 获取这个超大的字典集合之中的对象的数量总数
84         ''' </summary>
85         ''' <returns></returns>
86         Public ReadOnly Property Count As Integer Implements IReadOnlyCollection(Of KeyValuePair(Of K, V)).Count
87             <MethodImpl(MethodImplOptions.AggressiveInlining)>
88             Get
89                 Return __buckets.Sum(Function(x) x.Count)
90             End Get
91         End Property
92
93         ''' <summary>
94         ''' 注意，不要直接使用这个方法来添加新的数据，使用<see cref="BucketDictionaryExtensions"/>的方法会更加高效
95         ''' </summary>
96         ''' <param name="key"></param>
97         ''' <returns></returns>
98         Default Public Property Item(key As K) As V Implements IReadOnlyDictionary(Of K, V).Item
99             Get
100                 For Each hash In __buckets
101                     If hash.ContainsKey(key) Then
102                         Return hash(key)
103                     End If
104                 Next
105
106                 Return Nothing
107             End Get
108             Set(value As V)
109                 If __buckets.Count = 0 Then
110                     Call __buckets.Add(New Dictionary(Of K, V) From {{key, value}})
111                 Else
112                     For Each hash In __buckets
113                         If hash.ContainsKey(key) Then
114                             hash(key) = value
115                             Return
116                         End If
117                     Next
118
119                     Dim min = LinqAPI.DefaultFirst(Of Dictionary(Of K, V)) _
120  _
121                         () <= From x As Dictionary(Of K, V)
122                               In __buckets
123                               Select x
124                               Order By x.Count Ascending
125
126                     min(key) = value
127
128                     If min.Count >= bucketSize Then
129                         Call __buckets.Add(New Dictionary(Of K, V))
130                     End If
131                 End If
132             End Set
133         End Property
134
135         Public ReadOnly Property Keys As IEnumerable(Of K) Implements IReadOnlyDictionary(Of K, V).Keys
136             <MethodImpl(MethodImplOptions.AggressiveInlining)>
137             Get
138                 Return __buckets.Select(Function(x) x.Keys).IteratesALL
139             End Get
140         End Property
141
142         Public ReadOnly Property Values As IEnumerable(Of V) Implements IReadOnlyDictionary(Of K, V).Values
143             <MethodImpl(MethodImplOptions.AggressiveInlining)>
144             Get
145                 Return __buckets.Select(Function(x) x.Values).IteratesALL
146             End Get
147         End Property
148
149         Public Overrides Function ToString() As String
150             Return $"Tuple of [{GetType(K).Name}, {GetType(V).Name}] with {__buckets.Count} buckets."
151         End Function
152
153         Public Function ContainsKey(key As K) As Boolean Implements IReadOnlyDictionary(Of K, V).ContainsKey
154             For Each hash In __buckets
155                 If hash.ContainsKey(key) Then
156                     Return True
157                 End If
158             Next
159
160             Return False
161         End Function
162
163         Public Iterator Function GetEnumerator() As IEnumerator(Of KeyValuePair(Of K, V)) Implements IEnumerable(Of KeyValuePair(Of K, V)).GetEnumerator
164             For Each hash In __buckets
165                 For Each x In hash
166                     Yield x
167                 Next
168             Next
169         End Function
170
171         Public Function TryGetValue(key As K, ByRef value As V) As Boolean Implements IReadOnlyDictionary(Of K, V).TryGetValue
172             For Each hash In __buckets
173                 If hash.ContainsKey(key) Then
174                     value = hash(key)
175                     Return True
176                 End If
177             Next
178
179             Return False
180         End Function
181
182         Private Iterator Function IEnumerable_GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
183             Yield GetEnumerator()
184         End Function
185     End Class
186
187     Public Module BucketDictionaryExtensions
188
189         <Extension>
190         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)
191             Dim table As New BucketDictionary(Of K, V)(size)
192             Dim bucket As New Dictionary(Of K, V)
193
194             For Each x As T In source
195                 Dim key As K = getKey(x)
196                 Dim value As V = getValue(x)
197
198                 Call bucket.Add(key, value)
199
200                 If bucket.Count >= size Then
201                     table.__buckets.Add(bucket)
202                     bucket = New Dictionary(Of K, V)
203                 End If
204             Next
205
206             table.__buckets.Add(bucket)
207
208             Return table
209         End Function
210
211         <MethodImpl(MethodImplOptions.AggressiveInlining)>
212         <Extension>
213         Public Function CreateBuckets(Of K, V)(source As IEnumerable(Of (K, V)), Optional size% = Short.MaxValue * 10) As BucketDictionary(Of K, V)
214             Return source.CreateBuckets(Function(t) t.Item1, Function(t) t.Item2, size:=size)
215         End Function
216     End Module
217 End Namespace