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

In this blog, you will learn how to create “Double Linked Dictionary” (DLD) by Wrapping Dictionary Generic.

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.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace MappingTech
{
    public enum MapperMode { byKey, byValue };
    public enum MapStrategy { fitToFirst, fitToSecond, makeBalanced, removeUnbalanced };
    public enum DictionarySet { first, second};

    public class DLD<K, V> // Double Linked Dictionary
    {
        private Dictionary<K, V> map = new Dictionary<K, V>();
        private Dictionary<V, K> reverseMap = new Dictionary<V, K>();
        private Object Locker = new Object();
        private bool accessed = false; // Direct acces to Dictionaries

        public V GetValue(K key)
        {
            lock (Locker)
            {
                try
                {
                    return map[key];
                }
                catch
                {
                    return default(V);
                }
            }
        }

        public K GetKey(V value)
        {
            lock (Locker)
            {
                try
                {
                    return reverseMap[value];
                }
                catch
                {
                    return default(K);
                }
            }
        }


        public void AddToInner(DictionarySet D, K DKey,V DValue )
        {
            if (D == DictionarySet.first)
            {
                lock (Locker)
                {
                    map.Add(DKey, DValue);
                    accessed = true;
                }
            }
            else
                if (D == DictionarySet.second)
            {
                lock (Locker)
                {
                    reverseMap.Add(DValue, DKey);
                    accessed = true;
                }
            }
        }

        public void RemoveFromInner<T>(DictionarySet D ,T pointer) where T: K,V
        {
            if(D == DictionarySet.first && typeof(T) == typeof(K))
            {
                lock (Locker)
                {
                    map.Remove(pointer);
                    accessed = true;
                }
            }
            else
                if(D == DictionarySet.second && typeof(T) == typeof(V))
            {
                lock (Locker)
                {
                    reverseMap.Remove(pointer);
                    accessed = true;
                }
            }
        }

        public int CountInner(DictionarySet D )
        {
            lock (Locker)
            {
                if (D == DictionarySet.first)
                    return map.Count;
                else
                    if (D == DictionarySet.second)
                    return reverseMap.Count;
                else
                    return 0;
            }
        }

        public bool GetConsistencyStatus()
        {  // Key <-> Value

            bool disbalanced = false;
            if (accessed)
            {
                if (map.Count != reverseMap.Count)
                    disbalanced = true;
                else
                {
                    lock (Locker)
                    {
                        foreach (KeyValuePair<K, V> entry in map)
                        {
                            if (EqualityComparer<K>.Default.Equals(entry.Key, reverseMap[entry.Value]))
                            {
                                continue;
                            }
                            else
                            {
                                disbalanced = true;
                                break;
                            }
                        }
                    }
                }
            }
            else
                disbalanced = false;

            if (disbalanced)
                return false;
            else
                return true;
        }

        public void Add(K key, V value)
        {
            lock (Locker)
            {
                map.Add(key, value);
                reverseMap.Add(value, key);
            }
        }

        public void Remove<GenType>(GenType data, MapperMode mode) where GenType : K, V
        {
            if (mode == MapperMode.byKey && typeof(GenType) == typeof(K))
            {
                lock (Locker)
                {
                    var tempValue = map[data];
                    map.Remove(data);
                    reverseMap.Remove(tempValue);
                }
            }
            else
            if (mode == MapperMode.byValue && typeof(GenType) == typeof(V))
            {
                lock (Locker)
                {
                    var tempKey = reverseMap[data];
                    reverseMap.Remove(data);
                    map.Remove(tempKey);
                }
            }
        }

       public void DLDMapping(MapStrategy mStrategy)
        {
            if (!GetConsistencyStatus())
            {
                switch (mStrategy)
                {
                    case MapStrategy.fitToFirst: //  1 -> 2
                        lock (Locker)
                        {
                            {
                                foreach (KeyValuePair<V, K> entry in reverseMap)
                                {
                                    if (reverseMap.ContainsKey(entry.Key) &&
                                           !(map.ContainsKey(entry.Value)))

                                        map.Add(entry.Value, entry.Key);
                                }

                            }
                        }
                        break;

                    case MapStrategy.fitToSecond: // 1 <- 2
                        {
                            lock (Locker)
                            {
                                foreach (KeyValuePair<K, V> entry in map)
                                {
                                    if (map.ContainsKey(entry.Key) &&
                                          !(reverseMap.ContainsKey(entry.Value)))

                                        reverseMap.Add(entry.Value, entry.Key);
                                }
                            }
                            break;
                        }

                    case MapStrategy.makeBalanced: //  1 <-> 2

                        {
                            lock (Locker)
                            {
                                foreach (KeyValuePair<K, V> entry in map)
                                {
                                    if (map.ContainsKey(entry.Key) &&
                                         !(reverseMap.ContainsKey(entry.Value)))

                                        reverseMap.Add(entry.Value, entry.Key);
                                }
                                foreach (KeyValuePair<V, K> entry in reverseMap)
                                {
                                    if (reverseMap.ContainsKey(entry.Key) &&
                                          !(map.ContainsKey(entry.Value)))

                                        map.Add(entry.Value, entry.Key);
                                }
                            }
                        }
                        break;

                    case MapStrategy.removeUnbalanced:// 1 >-< 2
                        {
                            lock (Locker)
                            {
                                foreach (KeyValuePair<K, V> entry in map)
                                {
                                    if (map.ContainsKey(entry.Key) &&
                                         !(reverseMap.ContainsKey(entry.Value)))
                                        reverseMap.Remove(entry.Value);
                                }
                                foreach (KeyValuePair<V, K> entry in reverseMap)
                                {
                                    if (reverseMap.ContainsKey(entry.Key) &&
                                          !(map.ContainsKey(entry.Value)))

                                        map.Remove(entry.Value);
                                }

                            }
                        }
                        break;
                    default:
                        break;
                }

            }
            if (GetConsistencyStatus())
                accessed = false;

        }

    }
}

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. 

dldMap.Add(“A1”,”B1”);
dldMap.Add(“A2”,”B2”);
dldMap.AddToInner(DictionarySet.first,“Y1”,”Y2”); // accessed only from first dictionary
dldMap.AddToInner(DictionarySet.second,“X1”,”X2”);//accessed only from second dictionary
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.