Introduction

The Dictionary class (map in C++) is the data structure, which makes possible to create associative pairs of a different object. Such association allows to get value by knowing a key [Figure 1].


Figure 1: Dictionary association
Sometimes, it becomes necessary to get the key from the value [Figure 2]. The most common way to get the value from the key is to iterate through all the elements till the necessary key will be found. Another solution (that is presented here) based on idea of creating a wrapper class for two independent dictionaries, where the key parameter in first dictionary represents the value in the second dictionary and vice versa respectively.

Figure 2 Double Linked Dictionary (DLD)

Such approach allows not to iterate through all elements inside the structure, but it will take an additional memory, because of storing the two independent dictionaries.

Implementation

In this implementation of DLD (double linked dictionary) class, only some methods from standard Dictionary class have been implemented and adapted for the double liked distribution.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  8. namespace MappingTech
  9. {
  10. public enum MapperMode { byKey, byValue };
  11. public enum MapStrategy { fitToFirst, fitToSecond, makeBalanced, removeUnbalanced };
  12. public enum DictionarySet { first, second};
  14. public class DLD<K, V> // Double Linked Dictionary
  15. {
  16. private Dictionary<K, V> map = new Dictionary<K, V>();
  17. private Dictionary<V, K> reverseMap = new Dictionary<V, K>();
  18. private Object Locker = new Object();
  19. private bool accessed = false; // Direct acces to Dictionaries
  21. public V GetValue(K key)
  22. {
  23. lock (Locker)
  24. {
  25. try
  26. {
  27. return map[key];
  28. }
  29. catch
  30. {
  31. return default(V);
  32. }
  33. }
  34. }
  36. public K GetKey(V value)
  37. {
  38. lock (Locker)
  39. {
  40. try
  41. {
  42. return reverseMap[value];
  43. }
  44. catch
  45. {
  46. return default(K);
  47. }
  48. }
  49. }
  52. public void AddToInner(DictionarySet D, K DKey,V DValue )
  53. {
  54. if (D == DictionarySet.first)
  55. {
  56. lock (Locker)
  57. {
  58. map.Add(DKey, DValue);
  59. accessed = true;
  60. }
  61. }
  62. else
  63. if (D == DictionarySet.second)
  64. {
  65. lock (Locker)
  66. {
  67. reverseMap.Add(DValue, DKey);
  68. accessed = true;
  69. }
  70. }
  71. }
  73. public void RemoveFromInner<T>(DictionarySet D ,T pointer) where T: K,V
  74. {
  75. if(D == DictionarySet.first && typeof(T) == typeof(K))
  76. {
  77. lock (Locker)
  78. {
  79. map.Remove(pointer);
  80. accessed = true;
  81. }
  82. }
  83. else
  84. if(D == DictionarySet.second && typeof(T) == typeof(V))
  85. {
  86. lock (Locker)
  87. {
  88. reverseMap.Remove(pointer);
  89. accessed = true;
  90. }
  91. }
  92. }
  94. public int CountInner(DictionarySet D )
  95. {
  96. lock (Locker)
  97. {
  98. if (D == DictionarySet.first)
  99. return map.Count;
  100. else
  101. if (D == DictionarySet.second)
  102. return reverseMap.Count;
  103. else
  104. return 0;
  105. }
  106. }
  108. public bool GetConsistencyStatus()
  109. { // Key <-> Value
  111. bool disbalanced = false;
  112. if (accessed)
  113. {
  114. if (map.Count != reverseMap.Count)
  115. disbalanced = true;
  116. else
  117. {
  118. lock (Locker)
  119. {
  120. foreach (KeyValuePair<K, V> entry in map)
  121. {
  122. if (EqualityComparer<K>.Default.Equals(entry.Key, reverseMap[entry.Value]))
  123. {
  124. continue;
  125. }
  126. else
  127. {
  128. disbalanced = true;
  129. break;
  130. }
  131. }
  132. }
  133. }
  134. }
  135. else
  136. disbalanced = false;
  138. if (disbalanced)
  139. return false;
  140. else
  141. return true;
  142. }
  144. public void Add(K key, V value)
  145. {
  146. lock (Locker)
  147. {
  148. map.Add(key, value);
  149. reverseMap.Add(value, key);
  150. }
  151. }
  153. public void Remove<GenType>(GenType data, MapperMode mode) where GenType : K, V
  154. {
  155. if (mode == MapperMode.byKey && typeof(GenType) == typeof(K))
  156. {
  157. lock (Locker)
  158. {
  159. var tempValue = map[data];
  160. map.Remove(data);
  161. reverseMap.Remove(tempValue);
  162. }
  163. }
  164. else
  165. if (mode == MapperMode.byValue && typeof(GenType) == typeof(V))
  166. {
  167. lock (Locker)
  168. {
  169. var tempKey = reverseMap[data];
  170. reverseMap.Remove(data);
  171. map.Remove(tempKey);
  172. }
  173. }
  174. }
  176. public void DLDMapping(MapStrategy mStrategy)
  177. {
  178. if (!GetConsistencyStatus())
  179. {
  180. switch (mStrategy)
  181. {
  182. case MapStrategy.fitToFirst: // 1 -> 2
  183. lock (Locker)
  184. {
  185. {
  186. foreach (KeyValuePair<V, K> entry in reverseMap)
  187. {
  188. if (reverseMap.ContainsKey(entry.Key) &&
  189. !(map.ContainsKey(entry.Value)))
  191. map.Add(entry.Value, entry.Key);
  192. }
  194. }
  195. }
  196. break;
  198. case MapStrategy.fitToSecond: // 1 <- 2
  199. {
  200. lock (Locker)
  201. {
  202. foreach (KeyValuePair<K, V> entry in map)
  203. {
  204. if (map.ContainsKey(entry.Key) &&
  205. !(reverseMap.ContainsKey(entry.Value)))
  207. reverseMap.Add(entry.Value, entry.Key);
  208. }
  209. }
  210. break;
  211. }
  213. case MapStrategy.makeBalanced: // 1 <-> 2
  215. {
  216. lock (Locker)
  217. {
  218. foreach (KeyValuePair<K, V> entry in map)
  219. {
  220. if (map.ContainsKey(entry.Key) &&
  221. !(reverseMap.ContainsKey(entry.Value)))
  223. reverseMap.Add(entry.Value, entry.Key);
  224. }
  225. foreach (KeyValuePair<V, K> entry in reverseMap)
  226. {
  227. if (reverseMap.ContainsKey(entry.Key) &&
  228. !(map.ContainsKey(entry.Value)))
  230. map.Add(entry.Value, entry.Key);
  231. }
  232. }
  233. }
  234. break;
  236. case MapStrategy.removeUnbalanced:// 1 >-< 2
  237. {
  238. lock (Locker)
  239. {
  240. foreach (KeyValuePair<K, V> entry in map)
  241. {
  242. if (map.ContainsKey(entry.Key) &&
  243. !(reverseMap.ContainsKey(entry.Value)))
  244. reverseMap.Remove(entry.Value);
  245. }
  246. foreach (KeyValuePair<V, K> entry in reverseMap)
  247. {
  248. if (reverseMap.ContainsKey(entry.Key) &&
  249. !(map.ContainsKey(entry.Value)))
  251. map.Remove(entry.Value);
  252. }
  254. }
  255. }
  256. break;
  257. default:
  258. break;
  259. }
  261. }
  262. if (GetConsistencyStatus())
  263. accessed = false;
  265. }
  267. }
  268. }

Additional advantages

AccessToInner(), RemoveFromInner<T>() methods allow to create zones in the data structure, where access is possible only in one direction [Figure 3] .
Figure 3 Mapping diagram
In the diagram, Y1 is not accessible from the second dictionary (as well as X1 is not accessible from the first). Such object distribution creates an asymmetric mapping, which might be used in the cases, where part of stored data must be private (accessible only from one Dictionary ). The code snippet, given below, shows the implementation of [Figure 3] mapping.
  1. dldMap.Add(“A1”,”B1”);
  2. dldMap.Add(“A2”,”B2”);
  3. dldMap.AddToInner(DictionarySet.first,“Y1”,”Y2”); // accessed only from first dictionary
  4. dldMap.AddToInner(DictionarySet.second,“X1”,”X2”);//accessed only from second dictionary
  5. dldMap.Add(“A3”,”B3”);
Such mapping with an asymmetric zone might be restored by using DLDMapping method, which uses four different strategies, which is shown in the diagram, given below:
Figure 4 Mapping strategies
If you consider the diagram in [Figure 3] exists in initial state, the next diagram [Figure 4] shows one of the four strategies to distribute such mapped data and it represents the data in the next state. Strategies "fitToFirst" and "fitToSecond" are used to redistribute the data in order to match it with respect to one of the Dictionaries. Nevertheless, mapping is still asymmetric. To get symmetry in DLD, there are several strategies, "makeBalanced" and "removeUnbalanced", where "makeBalanced" creates an additional Key Value pairs in the dictionary, which has no such association. The last method "removeUnbalanced" removes all the data, which does not fit to the opposite Dictionary.