284. Invertible dictionary

ראינו לפני פעמיים מימוש למיפוי חד חד ערכי בין מפתחות לערכים.

למרבה הצער, רוב המיפויים בעולם הם דווקא לא חח”ע. במקום זאת אפשר להשתמש במיפוי קצת אחר:

public class InvertibleDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>,ILookup<TValue, TKey>
{
}

איך נממש את זה?

נחזיק שני Dictionaryים – אחד מהKey לValue, השני מהValueלאוסף של Key, ונדאג שכל הפונקציות של IDictionaryיעברו דרך שני הDictionaryים:

public class InvertibleDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, ILookup<TValue, TKey>
{
    private class KeyValuePairGrouping : IGrouping<TValue, TKey>
    {
        private readonly KeyValuePair<TValue, ICollection<TKey>> mPair;

        public KeyValuePairGrouping(KeyValuePair<TValue, ICollection<TKey>> pair)
        {
            mPair = pair;
        }

        public IEnumerator<TKey> GetEnumerator()
        {
            return mPair.Value.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public TValue Key
        {
            get
            {
                return mPair.Key;
            }
        }
    }

    private IDictionary<TKey, TValue> mKeyToValue = new Dictionary<TKey, TValue>();
    private IDictionary<TValue, ICollection<TKey>> mValueToKeys = new Dictionary<TValue, ICollection<TKey>>();

    IEnumerator<IGrouping<TValue, TKey>> IEnumerable<IGrouping<TValue, TKey>>.GetEnumerator()
    {
        return mValueToKeys
            .Select(x => new KeyValuePairGrouping(x))
            .Cast<IGrouping<TValue, TKey>>()
            .GetEnumerator();
    }

    public void Add(TKey key, TValue value)
    {
        mKeyToValue.Add(key, value);

        ICollection<TKey> valueToKeys;

        if (!mValueToKeys.TryGetValue(value, out valueToKeys))
        {
            valueToKeys = new List<TKey>();

            mValueToKeys[value] = valueToKeys;
        }

        valueToKeys.Add(key);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        if (mKeyToValue.Remove(item.Key))
        {
            ICollection<TKey> valueToKey = mValueToKeys[item.Value];

            valueToKey.Remove(item.Key);

            if (!valueToKey.Any())
            {
                mValueToKeys.Remove(item.Value);
            }

            return true;
        }

        return false;
    }

    public bool Remove(TKey key)
    {
        TValue value;
        
        if (!mKeyToValue.TryGetValue(key, out value))
        {
            return false;
        }

        return Remove(new KeyValuePair<TKey, TValue>(key, value));
    }

    public TValue this[TKey key]
    {
        get
        {
            return mKeyToValue[key];
        }
        set
        {
            TValue keyValue;
            
            if (mKeyToValue.TryGetValue(key, out keyValue))
            {
                Remove(new KeyValuePair<TKey, TValue>(key, keyValue));
            }

            Add(key, value);
        }
    }

    #region Dummy Implementation

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        Add(item.Key, item.Value);
    }

    public void Clear()
    {
        mKeyToValue.Clear();
        mValueToKeys.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        return mKeyToValue.Contains(item);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        mKeyToValue.CopyTo(array, arrayIndex);
    }

    public bool Contains(TValue key)
    {
        return mValueToKeys.ContainsKey(key);
    }

    public bool ContainsKey(TKey key)
    {
        return mKeyToValue.ContainsKey(key);
    }

    int ILookup<TValue, TKey>.Count
    {
        get
        {
            return mValueToKeys.Count;
        }
    }

    IEnumerable<TKey> ILookup<TValue, TKey>.this[TValue key]
    {
        get
        {
            return mValueToKeys[key];
        }
    }

    int ICollection<KeyValuePair<TKey, TValue>>.Count
    {
        get
        {
            return mKeyToValue.Count;
        }
    }

    public IEnumerator GetEnumerator()
    {
        IDictionary<TKey, TValue> dictionary = this;
        return dictionary.GetEnumerator();
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        return mKeyToValue.TryGetValue(key, out value);
    }

    IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
    {
        return mKeyToValue.GetEnumerator();
    }

    public ICollection<TKey> Keys
    {
        get
        {
            return mKeyToValue.Keys;
        }
    }

    public ICollection<TValue> Values
    {
        get
        {
            return mValueToKeys.Keys;
        }
    }

    #endregion
}

כמה דברים שאפשר לראות מכאן:

• יש הרבה מאוד מתודות לממשק IDictionary. לא הייתי ממליץ לאף אחד לממש אותו בעצמו (למרות שרוב המימושים הם שורה אחת-שתיים בעטיפה שכתובה פה)
• המימושים הכבדים, באופן לא מפתיע, הם של הפונקציות Add, Remove והIndexer, שמבצעים מניפולציות על הDictionaryים הפנימיים
• זה גם משהו שעלה בפעם הקודמת שכתבתי על המפה החד חד ערכית – מאחר ויש פה שני Indexerים, יש שתי אפשרויות:
  • הראשונה היא לממש את הממשקים Implicitly, ואז אם שני הטיפוסים שווים, אי אפשר לקרוא לIndexer ישירות (אלא רק דרך הכנסה למשתנה מסוג הממשק המתאים, ראו גם טיפ מספר 82)
  • השנייה, היא לממש לפחות את אחד הממשקיםExplicitly, ואז תמיד אפשר לקרוא לIndexerהנותר ישירות. לIndexer שמימשנו Explicitlyניתן יהיה לקרוא רק דרך הכנס למשתנה מהסוג המתאים. כאן בחרתי בדרך זו, כי נראה לי שיותר חשוב לגשת לערך לפי מפתח, לעומת הכיוון השני
• שימו לב שיש פה כמה מימושים לGetEnumerator, למעשה יש את המימוש הלא גנרי של IEnumerable שמפנה למימוש של הDictionary, יש מימוש של הLookup שמפנה לDictionary ההפוך. היה אפשר לחשוב שאם נבצע מעבר על הCollection עם הטיפוס המתאים, הקומפיילר יפנה אותנו לפרמטר הגנרי, למשל שהקוד הבא יעבוד:

  foreach (IGrouping<string, int> group in invertible)
  {
      // ...
  }

למעשה, זה לא קורה, והקוד לא עובד, מאחר ונקראת הפונקציה הלא גנרית של IEnumerable. הדרך לפתור את הבעיה היא לעשות משהו כזה:

IEnumerable<IGrouping<string,int>> invertibleEnumerable = invertible;

foreach (IGrouping<string, int> group in invertibleEnumerable)
{
    // ...
}

• שימו לב שכדי לממשIEnumerable<IGrouping<TValue, TKey>>, נאלצנו לכתוב מחלקת IGrouping משלנו, מאחר ואין כזאת שהיא public בFramework. בנוסף, היינו צריכים לעשות Select במימוש של GetEnumerator כדי שיחזרו טיפוסים מהסוג המתאים.

כעקרון זה לא הכי שימושי, אבל לדעתי זה מלמד כמה דברים.

המשך יום הפיך טוב!