Repository files navigation

Download the NuGet package.

Provides robust map collections for C# with high compatibility with core collection interfaces.

In almost every place you could use a normal Dictionary, you can also use a map from this repository due to them implementing all the relevant interfaces.

An important goal of this repository is to have extensive unit testing that can confirm a class correctly implements a map interface. This goal has been largely achieved and the structure of the testing suite is explained inTesting.

• Styles
• Implementations
• Features & Complexity
• Testing
• Contributing
• Roadmap

There are three "styles" of maps available, represented by their respective interfaces:

• IBiMap<T, K> is like a dictionary where keys can also be retrieved by their associated value.
• IMultiMap<T, K> is like a dictionary where each key may be associated with multiple values. No duplicate values may exist on the same key.
• IMultiBiMap<T, K> combines the properties of the previous two at the cost of additional space.

Note that BiMaps and MultiBiMaps are not bijections because they are not injective, only surjective. In other words, they are not one-to-one mappings of keys to values because several keys might have the same value. If having strict one to one mappings is important, these interfaces will not satisfy that specific requirement.

So far the only implementation is the composite "family". Named thusly because the backing store uses regular dictionaries.

• CompositeBiMap<T, K>. Uses two dictionaries, one for forward lookup and one for reverse lookup.
• CompositeMultiMap<T, K>. Uses a dictionary that maps keys to value hashsets.
• CompositeMultiBiMap<T, K>. Uses three dictionaries. One that maps keys to value hashsets, a second that maps value hashsets to keys, and a third dictionary that maps unique values to key hashsets.

Note: values to the left of the slash indicate the "average" case, generally signifying the absence of hash collisions. The value to the right indicates the actual worst case time complexity.

• n => generic item count.
• k => number of keys.
• v => number of values.
• vu => number of unique values.

(Relevant only to contributors)

Anvoker.Maps contains a heavy-duty unit testing suite that confirms almost every single interface, including standard library ones, is implemented correctly in the concrete collections. The design pattern used in the testing suite allows the same test logic and data to be reused for new implementations. No additional test logic has to be written for interfaces that already have an interface tester fixture defined. New test logic is required only for completely new interfaces or for methods belonging directly to the concrete class.

The testing suite is separated into two different projects.

Contains all the actual test logic and interfaces.

Test fixtures for every relevant interface are defined here inAnvoker.Maps.Tests.Common\InterfaceTesters.

Interfaces for the test data are defined inAnvoker.Maps.Tests.Common\Interfaces which allow the same test data to be adapted for more than one "kind" of test fixture.

MapData<TK, TV> andMultiMap<TK, TV> are data classes used for fixtures that test maps/dictionaries and multimaps respectively.

MapDataConcrete<TK, TV> andMultiMapConcrete<TK, TV> are refinements whose most important feature is containing aFunc pointing to the concrete implementation's constructor. This allows test fixtures to freely create instances of the implementation despite having access only to one of its interfaces.

MapFixtureParamConstructor andMultiMapFixtureParamConstructor are constructors of fixture parameters which allow us to specify the type arguments of the fixtures. This is important because without them NUnit would fail to correctly infer the type arguments.

Contains all the data and boilerplate that determines what tests will ultimately be created.

MapDataSource andMultiMapDataSource are static classes that each define 4 data sets - IntDecimal, StringStringInsensitive, StringStringSensitive and ArrayIntType.

MapDataSourceValidator andMultiMapDataSourceValidator run unit tests on the defined data to make sure it's correct, running null checks, verifying key uniqueness etc.

Each 'family' of maps gets its own directory. The directory contains a number of FixtureSources classes. Each FixtureSource contains a static property that returns an array ofITestFixtureData. This can be used byTestFixtureSource to instantiate a test fixture to test a specific implementation with a specific data set. Every family in part needs one FixtureSource class per interface being tested. The FixtureSource class calls a method inMapFixtureParamConstructor orMultiMapFixtureParamConstructor to obtain the constructed test fixture parameters.

For each interface tester fixture defined in Tests.Common, there is corresponding ForwardingFixture class here. A ForwardingFixture class is nothing more than an empty test fixture that inherits from its respective interface tester fixture. This is done firstly so that we can specify new implementations to test without modifying the interface tester fixture in Tests.Common, and secondly so that we can specify some concrete types if needed.

In the case of testingCompositeBiMap's implementation ofIReadOnlyDictionary, the FixtureSource would look like this:

usingstaticAnvoker.Maps.Tests.BiMap.BiMapHelpers;usingstaticAnvoker.Maps.Tests.MapDataSource;namespaceAnvoker.Maps.Tests.BiMap{publicstaticclassFixtureSource_IReadOnlyDictionary{privatestaticreadonlystringfixtureName=typeof(IReadOnlyDictionary<,>).Name;publicstaticITestFixtureData[]GetArgs{get;}=newITestFixtureData[]{MapFixtureParamConstructor<int,decimal,IReadOnlyBiMap<int,decimal>>.Construct(CompositeCtor,IntDecimal,Name,fixtureName),MapFixtureParamConstructor<string,string,IReadOnlyBiMap<string,string>>.Construct(CompositeCtor,StringStringInsensitive,Name,fixtureName),MapFixtureParamConstructor<string,string,IReadOnlyBiMap<string,string>>.Construct(CompositeCtor,StringStringSensitive,Name,fixtureName),MapFixtureParamConstructor<int[],Type,IReadOnlyBiMap<int[],Type>>.Construct(CompositeCtor,ArrayIntType,Name,fixtureName),};}}

This construct method takes aFunc delegate in its first parameter, in this case CompositeCtor, which later allows the test fixture to make new instances of the implementation without knowing what the implementation is. The delegate is implictly created simply by using the name of the method defined inAnvoker.Maps.Tests.BiMap.BiMapHelpers. All this method does is take keys and values from aMapData instance and construct a newCompositeBiMap instance with them.

public static CompositeBiMap<TKey, TVal> CompositeCtor<TKey, TVal>(MapData<TKey, TVal> d){    var m = new CompositeBiMap<TKey, TVal>(d.ComparerKey, d.ComparerValue);    for (int i = 0; i < d.KeysInitial.Length; i++)    {        m.Add(d.KeysInitial[i], d.ValuesInitial[i]);    }    return m;}

If we wanted to test an entirely new implementation we would just add another such constructor method toBiMapHelpers.cs and use it in calls toMapFixtureParamConstructor to assemble our test data as seen inFixtureSource_IReadOnlyDictionary.

Finally we need to reference this test data in the appropriate ForwardingFixture through NUnit'sTestFixtureSource attribute.

[TestFixtureSource(typeof(BiMap.FixtureSource_IReadOnlyDictionary),nameof(BiMap.FixtureSource_IReadOnlyDictionary.GetArgs))]publicclassFF_IReadOnlyDictionary<TKey,TVal,TCollection>:IReadOnlyDictionaryTester<TKey,TVal,TCollection>whereTCollection:IReadOnlyDictionary<TKey,TVal>{publicFF_IReadOnlyDictionary(MapDataConcrete<TKey,TVal,TCollection>args):base(args){}}

This is all that's needed in order to have generated 80 test cases that will confirmIReadOnlyDictionary is implemented correctly forCompositeBiMap. It's a lot of boilerplate, but it allows a lot of sharing code of logic, vastly reducing the need to ever write new test logic.

Submitting pull requests for new implementations, bug fixes or additional test coverage is welcome, but new implementations will be accepted based on their quality, usefulness and lack of overlap with existing implementations. Basically don't make an implementation that achieves what another implementation has already achieved.

Download StyleCop and use theSettings.StyleCop file in the respective project to respect the overall style of the repository. In large, the most important parts are:

• Allman style indentation with 4 spaces.
• Respecting 80 col limit. Minor exceptions for summaries or ridiculously long nested generic types.
• Preference for => notation where ever it can be used instead of a block.
• PascalCase for everything except private variables, local variables and parameters which are camelCase and constants which are ALL_CAPS.

• Adding a red-black tree implementation of IMultiMap.
• Adding benchmarks to test implementation performance.
• Adding integration tests to confirm that combinations of successive method calls don't mess up an implementation.