1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
// (c) Microsoft Corporation 2005-2009.
namespace Microsoft.FSharp.Collections
open System
open System.Collections.Generic
open Microsoft.FSharp.Collections
// Each entry in the HashMultiMap dictionary has at least one entry. Under normal usage each entry has _only_
// one entry. So use two hash tables: one for the main entries and one for the overflow.
[<Sealed>]
type HashMultiMap<'Key,'Value>(n: int, hasheq: IEqualityComparer<'Key>) =
let firstEntries = new Dictionary<_,_>(n,hasheq);
let rest = new Dictionary<_,_>(3,hasheq);
new (hasheq : IEqualityComparer<'Key>) = new HashMultiMap<'Key,'Value>(11, hasheq)
new (seq : seq<'Key * 'Value>, hasheq : IEqualityComparer<'Key>) as x =
new HashMultiMap<'Key,'Value>(11, hasheq)
then seq |> Seq.iter (fun (k,v) -> x.Add(k,v))
new (seq : seq<'Key * 'Value>) = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
new (n:int) = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
new () = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
static member Create (seq : seq<'Key * 'Value>) = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
static member Create (n:int) = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
static member Create () = failwith "unreachable: obsolete and error"; new HashMultiMap<'Key,'Value>()
member x.GetRest(k) =
let mutable res = []
let ok = rest.TryGetValue(k,&res)
if ok then res else []
member x.Add(y,z) =
let mutable res = Unchecked.defaultof<'Value>
let ok = firstEntries.TryGetValue(y,&res)
if ok then
rest.[y] <- res :: x.GetRest(y)
firstEntries.[y] <- z
member x.Clear() =
firstEntries.Clear()
rest.Clear()
member x.FirstEntries = firstEntries
member x.Rest = rest
member x.Copy() =
let res = new HashMultiMap<'Key,'Value>(firstEntries.Count,firstEntries.Comparer)
for kvp in firstEntries do
res.FirstEntries.Add(kvp.Key,kvp.Value)
for kvp in rest do
res.Rest.Add(kvp.Key,kvp.Value)
res
member x.Item
with get(y : 'Key) =
let mutable res = Unchecked.defaultof<'Value>
let ok = firstEntries.TryGetValue(y,&res)
if ok then res else raise (new System.Collections.Generic.KeyNotFoundException("The item was not found in collection"))
and set (y:'Key) (z:'Value) =
x.Replace(y,z)
member x.FindAll(y) =
let mutable res = Unchecked.defaultof<'Value>
let ok = firstEntries.TryGetValue(y,&res)
if ok then res :: x.GetRest(y) else []
member x.Fold f acc =
let mutable res = acc
for kvp in firstEntries do
res <- f kvp.Key kvp.Value res
match x.GetRest(kvp.Key) with
| [] -> ()
| rest ->
for z in rest do
res <- f kvp.Key z res
res
member x.Iterate(f) =
for kvp in firstEntries do
f kvp.Key kvp.Value
match x.GetRest(kvp.Key) with
| [] -> ()
| rest ->
for z in rest do
f kvp.Key z
member x.Contains(y) = firstEntries.ContainsKey(y)
member x.ContainsKey(y) = firstEntries.ContainsKey(y)
member x.Remove(y) =
let mutable res = Unchecked.defaultof<'Value>
let ok = firstEntries.TryGetValue(y,&res)
// Note, if not ok then nothing to remove - nop
if ok then
// We drop the FirstEntry. Here we compute the new FirstEntry and residue MoreEntries
let mutable res = []
let ok = rest.TryGetValue(y,&res)
if ok then
match res with
| [h] ->
firstEntries.[y] <- h;
rest.Remove(y) |> ignore
| (h::t) ->
firstEntries.[y] <- h
rest.[y] <- t
| _ ->
// note: broken invariant
()
else
firstEntries.Remove(y) |> ignore
member x.Replace(y,z) =
firstEntries.[y] <- z
member x.TryFind(y) =
let mutable res = Unchecked.defaultof<'Value>
let ok = firstEntries.TryGetValue(y,&res)
if ok then Some(res) else None
member x.Count = firstEntries.Count
interface IEnumerable<KeyValuePair<'Key, 'Value>> with
member s.GetEnumerator() =
let elems = new System.Collections.Generic.List<_>(firstEntries.Count + rest.Count)
for kvp in firstEntries do
elems.Add(kvp)
for z in s.GetRest(kvp.Key) do
elems.Add(KeyValuePair(kvp.Key, z))
(elems.GetEnumerator() :> IEnumerator<_>)
interface System.Collections.IEnumerable with
member s.GetEnumerator() = ((s :> seq<_>).GetEnumerator() :> System.Collections.IEnumerator)
interface IDictionary<'Key, 'Value> with
member s.Item
with get x = s.[x]
and set x v = s.[x] <- v
member s.Keys = ([| for kvp in s -> kvp.Key |] :> ICollection<'Key>)
member s.Values = ([| for kvp in s -> kvp.Value |] :> ICollection<'Value>)
member s.Add(k,v) = s.[k] <- v
member s.ContainsKey(k) = s.ContainsKey(k)
member s.TryGetValue(k,r) = if s.ContainsKey(k) then (r <- s.[k]; true) else false
member s.Remove(k:'Key) =
let res = s.ContainsKey(k) in
s.Remove(k); res
interface ICollection<KeyValuePair<'Key, 'Value>> with
member s.Add(x) = s.[x.Key] <- x.Value
member s.Clear() = s.Clear()
member s.Remove(x) =
let res = s.ContainsKey(x.Key)
if res && Unchecked.equals s.[x.Key] x.Value then
s.Remove(x.Key);
res
member s.Contains(x) =
s.ContainsKey(x.Key) &&
Unchecked.equals s.[x.Key] x.Value
member s.CopyTo(arr,arrIndex) = s |> Seq.iteri (fun j x -> arr.[arrIndex+j] <- x)
member s.IsReadOnly = false
member s.Count = s.Count
|
