Unlike Dictionary
, you cannot construct a Lookup
by adding elements one by one. Do you happen to know the reason?
Lookup
is just like multimap
in C++; why can't we modify it in C#? If we really can't, how can we construct a multimap
data structure in C#?
Lookup
and ILookup
were introduced as part of LINQ, which generally takes a more functional approach than other aspects of the framework. Personally I like the fact that Lookup
is (at least publicly) immutable - and I'm looking forward to more immutable collections being available.
If you want to create your own multimap data structure, just maintain a Dictionary<TKey, List<TValue>>
or something similar. You might want to look at my Edulinq implementation of Lookup
for some sample code.
Here is an implementation I wrote
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class MultiLookup<Key, Value> : ILookup<Key, Value>
{
Dictionary<Key, HashSet<Value>> Contents = new Dictionary<Key, HashSet<Value>>();
public void Add(Key key, Value value)
{
if (!Contains(key))
{
Contents[key]=new HashSet<Value>();
}
Contents[key].Add(value);
}
public void Add(IEnumerable<Tuple<Key, Value>> items)
{
foreach (var item in items)
{
Add(item.Item1, item.Item2);
}
}
public void Remove(Key key, Value value)
{
if (!Contains(key))
{
return;
}
Contents[key].Remove(value);
if (Contents[key].Count==0)
{
Contents.Remove(key);
}
}
public void RemoveKey(Key key)
{
Contents.Remove(key);
}
public IEnumerable<Key> Keys
{
get
{
return Contents.Keys;
}
}
public int Count
{
get
{
return Contents.Count;
}
}
public bool Contains(Key key)
{
return Contents.ContainsKey(key);
}
private class Grouping : IGrouping<Key, Value>
{
public MultiLookup<Key, Value> _source;
public Key _key;
public Key Key
{
get { return _key; }
}
public static HashSet<Value> Empty = new HashSet<Value>();
public IEnumerator<Value> GetEnumerator()
{
if (!_source.Contains(_key))
{
yield break;
}
else
{
foreach (var item in _source[_key])
{
yield return item;
}
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
public IEnumerator<IGrouping<Key, Value>> GetEnumerator()
{
return (from p in Contents
select new Grouping() { _key = p.Key, _source = this }).GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public IEnumerable<Value> this[Key key]
{
get { return Contents[key]; }
}
}
and a test case ( probably not exhaustive ) for you
using FluentAssertions;
using System.Linq;
using Xunit;
public class MultiLookupSpec
{
MultiLookup<int, string> Fixture = new MultiLookup<int,string>();
[Fact]
public void NewLookupShouldBeEmpty()
{
Fixture.Count.Should().Be(0);
}
[Fact]
public void AddingANewValueToANonExistentKeyShouldCreateKeyAndAddValue()
{
Fixture.Add(0, "hello");
Fixture.Count.Should().Be(1);
}
[Fact]
public void AddingMultipleValuesToAKeyShouldGenerateMultipleValues()
{
Fixture.Add(0, "hello");
Fixture.Add(0, "cat");
Fixture.Add(0, "dog");
Fixture[0].Should().BeEquivalentTo(new []{"hello", "cat", "dog"});
}
[Fact]
public void RemovingAllElementsOfKeyWillAlsoRemoveKey()
{
Fixture.Add(0, "hello");
Fixture.Add(0, "cat");
Fixture.Add(0, "dog");
Fixture.Remove(0, "dog");
Fixture.Remove(0, "cat");
Fixture.Remove(0, "hello");
Fixture.Contains(0).Should().Be(false);
}
[Fact]
public void EnumerationShouldWork()
{
Fixture.Add(0, "hello");
Fixture.Add(0, "cat");
Fixture.Add(0, "dog");
Fixture.Add(1, "house");
Fixture.Add(2, "pool");
Fixture.Add(2, "office");
Fixture.Select(s => s.Key).Should().Contain(new[] { 0, 1, 2 });
Fixture.SelectMany(s => s).Should().Contain(new[] { "hello", "cat", "dog", "house", "pool", "office" });
}
}
I had this same problem and question. Why is Lookup immutable? I solved it with some extension methods to IDictionary
public static void Add<TKey,TList,TItem>(this IDictionary<TKey,TList> dict,TKey key,TItem item)
where TList : ICollection<TItem>,new()
{
if(!dict.ContainsKey(key))
{
dict.Add(key, new TList());
}
dict[key].Add(item);
}
public static void Remove<TKey, TList, TItem>(this IDictionary<TKey, TList> dict, TKey key)
where TList : IEnumerable<TItem>, new()
{
if (dict.ContainsKey(key))
{
dict.Remove(key);
}
}
public static TList Items<TKey, TList, TItem>(this IDictionary<TKey, TList> dict, TKey key)
where TList : IEnumerable<TItem>, new()
{
if (dict.ContainsKey(key))
{
return dict[key];
}
return default(TList);
}