1 //
2 // Copyright (c) 2010-2018 Antmicro
3 // Copyright (c) 2011-2015 Realtime Embedded
4 //
5 // This file is licensed under the MIT License.
6 // Full license text is available in 'licenses/MIT.txt'.
7 //
8 using System;
9 using System.Collections.Generic;
10 using System.Linq;
11 
12 namespace Antmicro.Renode.Utilities.Collections
13 {
14     /// <summary>
15     /// This is an implementation of MultiValueDictionary which is memory effictient at expense of sligthly
16     /// more logic. It holds key-value  associations for singular values in plain dictionary, and moves them to
17     /// a key-list of values dictionary when more than one value gets associated to the same key.
18     ///
19     /// This way, the overhead of keeping lists is limited only to keys that actually need it.
20     ///
21     /// Semantically it behaves as Dictionary<TKey, IReadOnlyCollection<TValue>>. So Get methods
22     /// always return a collection, even in cases when there are no elements or one element to return.
23     /// </summary>
24     public class MultiValueDictionary<TKey, TValue> : IEnumerable<TValue> where TValue : IEquatable<TValue>
25     {
MultiValueDictionary()26         public MultiValueDictionary()
27         {
28             multiple = new Dictionary<TKey,List<TValue>>();
29             single = new Dictionary<TKey,TValue>();
30         }
31 
GetEnumerator()32         public IEnumerator<TValue> GetEnumerator()
33         {
34             return single.Values.Concat(multiple.Values.SelectMany(list => list)).GetEnumerator();
35         }
36 
System.Collections.IEnumerable.GetEnumerator()37         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
38         {
39             return GetEnumerator();
40         }
41 
Add(TKey key, TValue value)42         public void Add(TKey key, TValue value)
43         {
44             TValue existingSingle;
45             if(single.TryGetValue(key, out existingSingle))
46             {
47                 single.Remove(key);
48                 multiple.Add(key, new List<TValue>{ existingSingle, value });
49                 return;
50             }
51 
52             List<TValue> existingMultiple;
53             if(multiple.TryGetValue(key, out existingMultiple))
54             {
55                 existingMultiple.Add(value);
56                 return;
57             }
58 
59             single.Add(key, value);
60         }
61 
AddRange(TKey key, IEnumerable<TValue> values)62         public void AddRange(TKey key, IEnumerable<TValue> values)
63         {
64             TValue existingSingle;
65             if(single.TryGetValue(key, out existingSingle))
66             {
67                 single.Remove(key);
68                 var list = new List<TValue>{ existingSingle };
69                 list.AddRange(values);
70                 multiple.Add(key, list);
71                 return;
72             }
73 
74             List<TValue> existingMultiple;
75             if(multiple.TryGetValue(key, out existingMultiple))
76             {
77                 existingMultiple.AddRange(values);
78             }
79             else
80             {
81                 multiple.Add(key, new List<TValue>(values));
82             }
83         }
84 
85         /// <summary>
86         /// Removes all values associated with the key.
87         /// </summary>
88         /// <param name="key">Key.</param>
Remove(TKey key)89         public bool Remove(TKey key)
90         {
91             return single.Remove(key) || multiple.Remove(key);
92         }
93 
94         /// <summary>
95         /// Removes particular key, value association.
96         /// </summary>
97         /// <param name="key">Key.</param>
98         /// <param name="value">Value.</param>
Remove(TKey key, TValue value)99         public bool Remove(TKey key, TValue value)
100         {
101             TValue existingSingle;
102             if(single.TryGetValue(key, out existingSingle) && existingSingle.Equals(value))
103             {
104                 return single.Remove(key);
105             }
106             List<TValue> existingMultipleValues;
107             if(multiple.TryGetValue(key, out existingMultipleValues) && existingMultipleValues.Remove(value))
108             {
109                 //if there is one element left in list, move it to the single values
110                 if(existingMultipleValues.Count == 1)
111                 {
112                     single.Add(key, existingMultipleValues.First());
113                     multiple.Remove(key);
114                 }
115             }
116             return true;
117         }
118 
119         /// <summary>
120         /// Tries to get the collection of values associated with the key.
121         /// </summary>
122         /// <returns><c>true</c>, if collection is not empty, <c>false</c> otherwise.</returns>
123         /// <param name="key">Key.</param>
124         /// <param name="values">Values.</param>
TryGetValue(TKey key, out IReadOnlyCollection<TValue> values)125         public bool TryGetValue(TKey key, out IReadOnlyCollection<TValue> values)
126         {
127             TValue existingSingle;
128             if(single.TryGetValue(key, out existingSingle))
129             {
130                 values = new List<TValue> { existingSingle };
131                 return true;
132             }
133 
134             List<TValue> existingMultiple;
135             var ret = multiple.TryGetValue(key, out existingMultiple);
136             if(ret)
137             {
138                 values = existingMultiple.AsReadOnly();
139             }
140             else
141             {
142                 values = new List<TValue>();
143             }
144             return ret;
145         }
146 
ContainsKey(TKey key)147         public bool ContainsKey(TKey key)
148         {
149             return single.ContainsKey(key) || multiple.ContainsKey(key);
150         }
151 
ContainsValue(TValue value)152         public bool ContainsValue(TValue value)
153         {
154             return this.Contains(value);
155         }
156 
Contains(TKey key)157         public bool Contains(TKey key)
158         {
159             return ContainsKey(key);
160         }
161 
Contains(TKey key, TValue value)162         public bool Contains(TKey key, TValue value)
163         {
164             IReadOnlyCollection<TValue> values;
165             return TryGetValue(key, out values) && values.Contains(value);
166         }
167 
Clear()168         public void Clear()
169         {
170             single.Clear();
171             multiple.Clear();
172         }
173 
174         /// <summary>
175         /// Contains dictionary of keys associated with one value.
176         /// </summary>
177         private readonly Dictionary<TKey, TValue> single;
178 
179         /// <summary>
180         /// Contains dictionary of keys associated with more than one value.
181         /// </summary>
182         private readonly Dictionary<TKey, List<TValue>> multiple;
183     }
184 }
185 
186