Creating "Double Linked Dictionary" (DLD) By Wrapping Dictionary Generics

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;  
  6.   
  7.   
  8. namespace MappingTech  
  9. {  
  10.     public enum MapperMode { byKey, byValue };  
  11.     public enum MapStrategy { fitToFirst, fitToSecond, makeBalanced, removeUnbalanced };  
  12.     public enum DictionarySet { first, second};  
  13.   
  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            
  20.   
  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.         }  
  35.   
  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.         }  
  50.   
  51.   
  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.         }  
  72.   
  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.         }  
  93.   
  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.         }  
  107.   
  108.         public bool GetConsistencyStatus()  
  109.         {  // Key <-> Value  
  110.   
  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;  
  137.   
  138.             if (disbalanced)  
  139.                 return false;  
  140.             else  
  141.                 return true;  
  142.         }  
  143.   
  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.         }  
  152.   
  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.         }  
  175.   
  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)))  
  190.   
  191.                                         map.Add(entry.Value, entry.Key);  
  192.                                 }  
  193.   
  194.                             }  
  195.                         }  
  196.                         break;  
  197.   
  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)))  
  206.   
  207.                                         reverseMap.Add(entry.Value, entry.Key);  
  208.                                 }  
  209.                             }  
  210.                             break;  
  211.                         }  
  212.   
  213.                     case MapStrategy.makeBalanced: //  1 <-> 2  
  214.   
  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)))  
  222.   
  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)))  
  229.   
  230.                                         map.Add(entry.Value, entry.Key);  
  231.                                 }  
  232.                             }  
  233.                         }  
  234.                         break;  
  235.   
  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)))  
  250.   
  251.                                         map.Remove(entry.Value);  
  252.                                 }  
  253.   
  254.                             }  
  255.                         }  
  256.                         break;  
  257.                     default:  
  258.                         break;  
  259.                 }  
  260.   
  261.             }  
  262.             if (GetConsistencyStatus())  
  263.                 accessed = false;  
  264.   
  265.         }  
  266.   
  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. 
X

Build smarter apps with Machine Learning, Bots, Cognitive Services - Start free.

Start Learning Now