MapBase

Below is the code, with comments, of a 4 key map. You are welcome to copy this into your project if you need a 4 key map. This code follows the principals and design patterns used in the other 3 map types. There are 2 reasons this 4 key is not included with the BeanMap library.
  1. It has not proven reasonable to use a 4 key map in real world cases.
  2. The 4 key map is a proof of concept demonstrating the extensibility of the BeanMap library to more complex map types. The commenting herein should help direct those that need to know.
    • Note that it is clear that creating a 4 key map (i.e. extending MapBase) is not very practical and that in fact this code is complex. Due to the efforts to maintain strong typing and type integrity (for performance reasons) throughout the Maps and the base types, some extensibility was lost.

using System;
using System.Collections.Generic;
using System.Linq;
using BeanboxSoftware.BeanMap;

// I'm using an external namespace to demonstrate that the namespace doesn't have to
// match that of the other Map classes
namespace CustomMaps
{
  // All current and future maps implement their own IMap interface. Not all of the API
  // can be inherited while preserving type integrity
  // Thus, the IMap interface is designed to provide a contract of distinct methods
  // (while still following a design)
  public interface IMap<K1, K2, K3, K4, V> : IDictionary<K1, IDictionary<K2, IDictionary<K3, IDictionary<K4, V>>>>
  {
    new IMap<K2, K3, K4, V> this[K1 k1] { get; }
    IMap<K3, K4, V> this[K1 k1, K2 k2] { get; }
    IMap<K4, V> this[K1 k1, K2 k2, K3 k3] { get; }
    V this[K1 k1, K2 k2, K3 k3, K4 k4] { get; set; }

    new IEnumerator<KeyValuePair<Tuple<K1, K2, K3, K4>, V>> GetEnumerator(); //foreach
    IEnumerable<KeyValuePair<Tuple<K1, K2, K3, K4>, V>> KeyValues { get; }
    new IEnumerable<Tuple<K1, K2, K3, K4>> Keys { get; }
    new IEnumerable<V> Values { get; }

    bool Remove(K1 k1, K2 k2);
    bool Remove(K1 k1, K2 k2, K3 k3);
    bool Remove(K1 k1, K2 k2, K3 k3, K4 k4);

    //bool ContainsKey(K1 k1); // promised with IDictionary
    bool ContainsKey(K1 k1, K2 k2);
    bool ContainsKey(K1 k1, K2 k2, K3 k3);
    bool ContainsKey(K1 k1, K2 k2, K3 k3, K4 k4);
  }

  public partial class Map<K1, K2, K3, K4, V> : 
    // All current and future maps should inherit MapBase
    // The generic parameters to MapBase are
    // TGen:          Declare a Func<$types> where $types == the map class's generic
    //                arguments. This type is used for DefaultGeneration
    // TValue:        Declare the value type (last generic argument of the class)
    //                Typically called V for Maps
    // TPrimaryKey:   Declare the first key type (first generic argument of the class)
    //                Typically called K or K1 for Maps
    // TPrimaryValue: Declare the top most value type of the class. In other words, the
    //                Type contained within each first key value. For multiple key maps
    //                this is expected to be an IDictionary<K2, ...> where `...` here
    //                implies a recursive declaration of each subsequent layer of
    //                values using this same rule.
    BeanboxSoftware.BeanMap.Internal.MapBase<
      Func<K1, K2, K3, K4, V>, 
      V, 
      K1, 
      IDictionary<K2, IDictionary<K3, IDictionary<K4, V>>>>, 

    // contract of distinct 4-key API
    IMap<K1, K2, K3, K4, V>
  {
    public Map()
    {
    }

    // Value list constructor, see
    // http://beanmap.codeplex.com/wikipage?title=List%20to%20Map%20conversion
    public Map(IEnumerable<V> list, Func<V, K1> key1Gen, Func<V, K2> key2Gen, Func<V, K3> key3Gen, Func<V, K4> key4Gen)
    {
      foreach (var item in list)
      {
        this[key1Gen(item), key2Gen(item), key3Gen(item), key4Gen(item)] = item;
      }
    }

    public Map(Map<K1, K2, K3, K4, V> copy)
    {
      foreach (var kv in copy.KeyValues)
      {
        this[kv.Key.Item1, kv.Key.Item2, kv.Key.Item3, kv.Key.Item4] = kv.Value;
      }
    }

    #region Child Maps
    // Index requests on a Map<K1, K2, ... KN, V> with M keys were M >= 1 and <N, such
    // as map[k1, k2, ... kM], will result in a "Child Map". Child Maps do not hold any
    // key-values, but instead act as a proxy to the parent map. Internally, this proxy
    // process is referred to as 'passthrough'. Declaring passthrough maps is completely
    // nonintuitve; the complexity was necessary in order to preserve generic type
    // information and maximize code reuse at the same time. The outward benefit
    // for the user is the ability to use jagged notation; e.g. map[k1][k2][...kn]

    public IMap<K2, K3, K4, V> this[K1 k1]
    {
      get
      {
        return 
          // Passthrough map generation is kept internal using the _PassthroughFactory
          // The _PassthroughFactory is a nested protected class in MapBase
          // The current MapBase in context (i.e. this->base) is for
          // Map<K1, K2, ... KN, V>. However, the child map that we want to return will
          // be of fewer keys, and thus an explicit and fully qualified name of the
          // correct MapBase is necessary
          new BeanboxSoftware.BeanMap.Internal.MapBase<Func<K2, K3, K4, V>, V, K2, IDictionary<K3, IDictionary<K4, V>>>._PassthroughFactory()

          // The only purpose of the factory is to create (new up) a child map
          // The Map classes can double as child maps via clever shared code from base
          // types (MapBase and DictionaryCommonBase). The class type for the child
          // map is declared as a generic argument to CreatePassthrough. The
          // constraints on the type used are where TMap : MapBase<...>, new()
          // For this example, the indexer here is taking just K1, thus the child map
          // returned should be <K2, K3, K4, V>
          .CreatePassthrough<Map<K2, K3, K4, V>>(

          // Passthrough code; gives the proper data handle in child map context
          build => ContainsKey(k1) ? RetrieveDataHandle()[k1] : build ? Prepare(k1) : null,

          // Used to tell the parent to remove potentially empty keys
          () => RemovalCleanup(k1),

          // Used to read value from the parent map using the parent's configured
          // KeyNotFoundBehavior
          (k2, k3, k4) => this[k1, k2, k3, k4]);
      }
    }

    public IMap<K3, K4, V> this[K1 k1, K2 k2]
    {
      get
      {
        return new BeanboxSoftware.BeanMap.Internal.MapBase<Func<K3, K4, V>, V, K3, IDictionary<K4, V>>._PassthroughFactory().CreatePassthrough<Map<K3, K4, V>>(
          build => ContainsKey(k1, k2) ? RetrieveDataHandle()[k1][k2] : build ? Prepare(k1, k2) : null,
          () => RemovalCleanup(k1, k2),
          (k3, k4) => this[k1, k2, k3, k4]);
      }
    }

    public IMap<K4, V> this[K1 k1, K2 k2, K3 k3]
    {
      get
      {
        return new BeanboxSoftware.BeanMap.Internal.MapBase<Func<K4, V>, V, K4, V>._PassthroughFactory().CreatePassthrough<Map<K4, V>>(
          build => ContainsKey(k1, k2, k3) ? RetrieveDataHandle()[k1][k2][k3] : build ? Prepare(k1, k2, k3) : null,
          () => RemovalCleanup(k1, k2, k3),
          (k4) => this[k1, k2, k3, k4]);
      }
    }

    #endregion

    // Prepare methods make first time writes safe and hide the process from
    // the user. Example: a new map<K1, K2, V> is allowed to say `map[k1, k2] = v`
    // 
    // In addition, Prepare methods cannot be shared through inheritance from
    // less specific types (fewer generic type information), and thus each
    // map type must define N-1 Prepare methods
    protected IDictionary<K2, IDictionary<K3, IDictionary<K4, V>>> Prepare(K1 k1)
    {
      // SafeGet supports child maps
      var data = SafeGet();

      if (!data.ContainsKey(k1))
      {
        // The type you use to contain the _actual_ data storage does not have to
        // be a Dictionary<,> as used here. It only must be an IDictionary<,>.
        // Keep in mind that the actual data structure is hidden from the user
        data[k1] = new Dictionary<K2, IDictionary<K3, IDictionary<K4, V>>>();
      }

      return data[k1];
    }

    protected IDictionary<K3, IDictionary<K4, V>> Prepare(K1 k1, K2 k2)
    {
      // Reuse 1 key prepare
      var data = Prepare(k1);

      if (!data.ContainsKey(k2))
      {
        data[k2] = new Dictionary<K3, IDictionary<K4, V>>();
      }

      return data[k2];
    }

    protected IDictionary<K4, V> Prepare(K1 k1, K2 k2, K3 k3)
    {
      // Reuse 2 key prepare
      var data = Prepare(k1, k2);

      if (!data.ContainsKey(k3))
      {
        data[k3] = new Dictionary<K4, V>();
      }

      return data[k3];
    }

    protected void SafeSet(K1 k1, K2 k2, K3 k3, K4 k4, V value)
    {
      var data = Prepare(k1, k2, k3);
      data[k4] = value;
    }

    // A 4 key request will not need child maps; this method is much more straight
    // forward than the previous indexers
    public V this[K1 k1, K2 k2, K3 k3, K4 k4]
    {
      get
      {
        if (!ContainsKey(k1, k2, k3, k4))
        {
          // The complexity in the parameters to the HandleKeyNotFound method
          // (defined in MapBase) is due to generic type preservation
          return HandleKeyNotFound(gen => gen(k1, k2, k3, k4), v => this[k1, k2, k3, k4] = v, () => new object[] { k1, k2, k3, k4 });
        }

        // Note this call must be jagged as the data handle is not an IMap, but an
        // IDictionary
        return RetrieveDataHandle()[k1][k2][k3][k4];
      }
      set
      {
        SafeSet(k1, k2, k3, k4, value);
      }
    }

    public bool ContainsKey(K1 k1, K2 k2, K3 k3, K4 k4)
    {
      // For performance, minimize the number of calls to RetrieveDataHandle
      var data = RetrieveDataHandle();

      return
        data.ContainsKey(k1) &&
        data[k1].ContainsKey(k2) &&
        data[k1][k2].ContainsKey(k3) &&
        data[k1][k2][k3].ContainsKey(k4);
    }

    public bool ContainsKey(K1 k1, K2 k2, K3 k3)
    {
      // For performance, minimize the number of calls to RetrieveDataHandle
      var data = RetrieveDataHandle();

      return
        data.ContainsKey(k1) &&
        data[k1].ContainsKey(k2) &&
        data[k1][k2].ContainsKey(k3);
    }

    public bool ContainsKey(K1 k1, K2 k2)
    {
      // For performance, minimize the number of calls to RetrieveDataHandle
      var data = RetrieveDataHandle();

      return
        data.ContainsKey(k1) &&
        data[k1].ContainsKey(k2);
    }

    // Count is the number of values, not top level keys
    public override int Count
    {
      get { return RetrieveDataHandle().Sum(kvp => kvp.Value.Sum(kkvp => kkvp.Value.Sum(kkkvp => kkkvp.Value.Count))); }
    }

    public IEnumerator<KeyValuePair<Tuple<K1, K2, K3, K4>, V>> GetEnumerator()
    {
      return KeyValues.GetEnumerator();
    }

    public IEnumerable<KeyValuePair<Tuple<K1, K2, K3, K4>, V>> KeyValues
    {
      get
      {
        // For performance, minimize the number of calls to RetrieveDataHandle
        var data = RetrieveDataHandle();

        foreach (var k1 in data.Keys)
        {
          foreach (var k2 in data[k1].Keys)
          {
            foreach (var k3 in data[k1][k2].Keys)
            {
              foreach (var k4 in data[k1][k2][k3].Keys)
              {
                yield return new KeyValuePair<Tuple<K1, K2, K3, K4>, V>(Tuple.Create(k1, k2, k3, k4), data[k1][k2][k3][k4]);
              }
            }
          }
        }
      }
    }

    public IEnumerable<Tuple<K1, K2, K3, K4>> Keys
    {
      get
      {
        return KeyValues.Select(kvs => kvs.Key);
      }
    }

    public IEnumerable<V> Values
    {
      get
      {
        return KeyValues.Select(kvs => kvs.Value);
      }
    }

    public override bool TryGetValue(K1 key, out IDictionary<K2, IDictionary<K3, IDictionary<K4, V>>> value)
    {
      // A TryGet always works to child maps
      value = this[key];
      return true;
    }

    protected override IDictionary<K2, IDictionary<K3, IDictionary<K4, V>>> IndexerGet(K1 key)
    {
      // Due to some IDictionary method hiding, a special IndexerGet is necessary for
      // internal calls
      return this[key];
    }

    #region Remove
    // Keys should not exist that have no values
    // This is not an issue with 1 key maps because the key and value are stored
    // together. But with multiple keys a lower order key (K2, ... KN) could be
    // removed and no siblings below the higher order keys remain. In such a scenario
    // the higher order keys should be removed. This is done via RemovalCleanup

    public bool Remove(K1 k1, K2 k2)
    {
      if (!ContainsKey(k1))
      {
        return false;
      }

      var data = RetrieveDataHandle();
      if (data[k1].Remove(k2))
      {
        RemovalCleanup(k1);
        return true;
      }

      return false;
    }

    public bool Remove(K1 k1, K2 k2, K3 k3)
    {
      if (!ContainsKey(k1, k2))
      {
        return false;
      }

      var data = RetrieveDataHandle();

      if (data[k1][k2].Remove(k3))
      {
        RemovalCleanup(k1, k2);
        return true;
      }

      return false;
    }

    public bool Remove(K1 k1, K2 k2, K3 k3, K4 k4)
    {
      if (!ContainsKey(k1, k2, k3))
      {
        return false;
      }

      var data = RetrieveDataHandle();

      if (data[k1][k2][k3].Remove(k4))
      {
        RemovalCleanup(k1, k2, k3);
        return true;
      }

      return false;
    }

    protected void RemovalCleanup(K1 k1)
    {
      var data = RetrieveDataHandle();
      if (data.ContainsKey(k1) && data[k1].Count == 0)
      {
        data.Remove(k1);
      }

      RemovalCleanup();
    }

    protected void RemovalCleanup(K1 k1, K2 k2)
    {
      var data = RetrieveDataHandle();
      if (data.ContainsKey(k1) && data[k1].ContainsKey(k2) && data[k1][k2].Count == 0)
      {
        data[k1].Remove(k2);
      }

      RemovalCleanup(k1);
    }

    protected void RemovalCleanup(K1 k1, K2 k2, K3 k3)
    {
      var data = RetrieveDataHandle();
      if (data.ContainsKey(k1) && data[k1].ContainsKey(k2) && data[k1][k2].ContainsKey(k3) && data[k1][k2][k3].Count == 0)
      {
        data[k1][k2].Remove(k3);
      }

      RemovalCleanup(k1, k2);
    }
    #endregion
  }
}

Last edited Feb 3, 2012 at 9:27 PM by payonel, version 12

Comments

No comments yet.