(untagged)

Generic Sparse Array and Sparse Matrices in C#

Bill_Hallahan

0.00/5 (No votes)

25 Oct 2013

Generic Sparse Collection Containers

Download source code - 40.5 KB

Introduction

This article presents a generic sparse array class in C#, and generic sparse matrix classes that take from 2 to 8 key values. The sparse array class is named SparseArray and the sparse matrix classes are named Sparse2DMatrix through Sparse8DMatrix respectively.

A simple program named SparseCollectionTest is provided to demonstrate the use of these classes.

Because these are all generic types, almost any type can be used either for the keys or the item that is stored in the sparse container. The only special requirement is that the key types must implement the IComparable interface.

These sparse containers are not as efficient as a fixed size array or a fixed size matrix, and so should only be used when necessary.

A sparse array or a sparse matrix is useful when most of an array or a matrix will not be written. This is often the case in mathematics, so if the item type and key types are numeric types, these containers can be very useful for solutions in linear algebra. The containers can also be used to implement simple associative memories.

Background

I originally wrote a C# SparseArray class in April 2010. I also wanted a sparse matrix class for a linear equation solver. I created Sparse2DMatrix through Sparse8DMatrix long before Microsoft had added Tuple classes to .NET.

Because Tuples were not available back then, I created classes Group2 through Group8. Based on feedback from a CodeProject user, I have renamed these ComparableTuple2 through ComparableTuple8. These classes are used internally in the Sparse2DMatrix through Sparse8DMatrix respectively. ComparableTuple2 through ComparableTuple8 class instances are immutable by design, because the hash code for a comparable tuple instance depends on key values, and the hash code for a type instance should not be changed.

I cannot currently develop with .NET 4.x, but it probably would be easy to modify these classes to use the Tuple classes, although since I don't have access to those classes, I'm not sure whether they implement the IComparable interface, or if there isn't some other limitation. I did see from reading the documentation that those classes provide a Create method that makes it unnecessary to declare the generic type using angle brackets when instantiating an instance. This is nice feature that my sparse collection types don't provide. In any event, these work just fine as is.

List of Files

Program.cs - The main program
SparseCollectionTest.csproj - The Visual Studio C# project file
SparseCollectionTest.sln - The Visual Studio C# solution file
AssemblyInfo.cs - Contains information about the program
ComparableTuple2.cs - Stores 2 keys, and is used in the Sparse2DMatrix class
ComparableTuple3.cs - Stores 2 keys, and is used in the Sparse3DMatrix class
ComparableTuple4.cs - Stores 2 keys, and is used in the Sparse4DMatrix class
ComparableTuple5.cs - Stores 2 keys, and is used in the Sparse5DMatrix class
ComparableTuple6.cs - Stores 2 keys, and is used in the Sparse6DMatrix class
ComparableTuple7.cs - Stores 2 keys, and is used in the Sparse7DMatrix class
ComparableTuple8.cs - Stores 2 keys, and is used in the Sparse8DMatrix class
SparseArray.cs - An associative array that takes 1 key to access an item
Sparse2DMatrix.cs - An associative array that takes 2 keys to access an item
Sparse3DMatrix.cs - An associative array that takes 3 keys to access an item
Sparse4DMatrix.cs - An associative array that takes 4 keys to access an item
Sparse5DMatrix.cs - An associative array that takes 5 keys to access an item
Sparse6DMatrix.cs - An associative array that takes 6 keys to access an item
Sparse7DMatrix.cs - An associative array that takes 7 keys to access an item
Sparse8DMatrix.cs - An associative array that takes 8 keys to access an item

Using a Sparse Array

Creating and using a SparseArray instance is very easy. Below shows a SparseArray instance with a key-type of int and a item-type of double. Then a value of 100.0 is stored at key value 10, and a value of 12345.0 is stored at key value 20.

SparseArray<int, double> vector = new SparseArray<int, double>(0.0);
vector[10] = 100.0;
vector[20] = 12345.0;

Any value in the SparseArray can be obtained. The following line of code gets the value at key item 15.

double value = vector[15];;

The following code prints all the key-value pairs in the sparse array.

foreach(KeyValuePair<int, double> pair in vector)
{
    Console.WriteLine("pair vector[{0}] = {1}", pair.Key, pair.Value);

Using A Sparse Matrix

Below shows a Sparse3DMatrix instance with three key-types of int and a item-type of double. A value of 1111.0 is stored at the key set (11, 22, 33). This example shows keys that are the same type, but this is not necessary. They key types can be different. One key could be a string, one an int, and the other a float.

Sparse3DMatrix<int, int, int, double> matrix = new Sparse3DMatrix<int, int, double>();
matrix[11, 22, 33] = 1111.0;

To iterate over sparse matrix keys and the value, use the following code. The code takes advantage of the matrix instances SeparateCombinedKeys method. All of the sparse matrix classes provide this method. The correct comparable tuple class, which is ComparableTuple3 for a Sparse3DMatrix, must have the correct key types, the same types used to instantiate the Sparse3DMatrix instance.

foreach (KeyValuePair<ComparableTuple3<int, int, int>, double> pair3D in matrix3D)
{
    int key0 = 0;
    int key1 = 0;
    int key2 = 0;
    matrix3D.SeparateCombinedKeys(pair3D.Key, ref key0, ref key1, ref key2);
    Console.WriteLine("pair matrix[{0}, {1}, {2}] = {3}", key0, key1, key2, pair3D.Value);
}

The Main Program - File Program.cs

The main program creates each type of sparse container, stores data in the container, and then dumps the data in the container.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using SparseCollections;

namespace SparseCollectionTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //----------------------------------------------------------
            // One dimensional vector.
            //----------------------------------------------------------

            SparseArray<int, double> vector = new SparseArray<int, double>(0.0);
            vector[0] = 100.0;

            Console.WriteLine("vector[{0}] = {1}", 0, vector[0]);
            Console.WriteLine("vector[{0}] = {1}", 1, vector[1]);
            vector[0] = 90.0;
            Console.WriteLine("vector[{0}] = {1}", 0, vector[0]);

            foreach(KeyValuePair<int, double> pair in vector)
            {
                Console.WriteLine("pair vector[{0}] = {1}", pair.Key, pair.Value);
            }

            //----------------------------------------------------------
            // Two dimensional matrix.
            //----------------------------------------------------------

            Sparse2DMatrix<int, int, double> matrix = new Sparse2DMatrix<int, int, double>();

            matrix[0, 0] = 200.0;
            matrix[0, 1] = 201.0;
            matrix[1, 0] = 210.0;
            Console.WriteLine("matrix[{0}, {1}] = {2}", 0, 0, matrix[0, 0]);
            Console.WriteLine("matrix[{0}, {1}] = {2}", 0, 1, matrix[0, 1]);
            Console.WriteLine("matrix[{0}, {1}] = {2}", 1, 0, matrix[1, 0]);
            Console.WriteLine("matrix[{0}, {1}] = {2}", 1, 1, matrix[1, 1]);

            foreach (KeyValuePair<ComparableTuple2<int, int>, double> pair in matrix)
            {
                int key0 = 0;
                int key1 = 0;
                matrix.SeparateCombinedKeys(pair.Key, ref key0, ref key1);
                Console.WriteLine("pair matrix[{0}, {1}] = {2}", key0, key1, pair.Value);
            }

            //----------------------------------------------------------
            // Three dimensional matrix.
            //----------------------------------------------------------

            Sparse3DMatrix<int, int, int, double> matrix3D =
                new Sparse3DMatrix<int, int, int, double>();

            matrix3D[0, 0, 0] = 3000.0;
            matrix3D[0, 1, 0] = 3010.0;
            matrix3D[1, 0, 1] = 3101.0;
            Console.WriteLine("matrix3D[{0}, {1}, {2}] = {3}", 0, 0, 0, matrix3D[0, 0, 0]);
            Console.WriteLine("matrix3D[{0}, {1}, {2}] = {3}", 0, 1, 0, matrix3D[0, 1, 0]);
            Console.WriteLine("matrix3D[{0}, {1}, {2}] = {3}", 1, 0, 1, matrix3D[1, 0, 1]);
            Console.WriteLine("matrix3D[{0}, {1}, {2}] = {3}", 1, 1, 1, matrix3D[1, 1, 1]);

            foreach (KeyValuePair<ComparableTuple3<int, int, int>, double> pair3D in matrix3D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                matrix3D.SeparateCombinedKeys(pair3D.Key, ref key0, ref key1, ref key2);
                Console.WriteLine("pair matrix[{0}, {1}, {2}] = {3}", key0, key1, key2, pair3D.Value);
            }

            //----------------------------------------------------------
            // Four dimensional matrix.
            //----------------------------------------------------------

            Sparse4DMatrix<int, int, int, int, double> matrix4D =
                new Sparse4DMatrix<int, int, int, int, double>();

            matrix4D[0, 0, 0, 0] = 40000.0;
            matrix4D[0, 1, 0, 1] = 40101.0;
            matrix4D[1, 0, 1, 0] = 41010.0;

            Console.WriteLine(String.Format("matrix4D[{0}, 
            {1}, {2}, {3}] = {4}", 0, 0, 0, 0, matrix4D[0, 0, 0, 0]));
            Console.WriteLine(String.Format("matrix4D[{0}, 
            {1}, {2}, {3}] = {4}", 0, 1, 0, 1, matrix4D[0, 1, 0, 1]));
            Console.WriteLine(String.Format("matrix4D[{0}, 
            {1}, {2}, {3}] = {4}", 1, 0, 1, 0, matrix4D[1, 0, 1, 0]));
            Console.WriteLine(String.Format("matrix4D[{0}, 
            {1}, {2}, {3}] = {4}", 1, 1, 1, 1, matrix4D[1, 1, 1, 1]));

            foreach (KeyValuePair<ComparableTuple4<int, int, int, int>, double> pair4D in matrix4D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                int key3 = 0;
                matrix4D.SeparateCombinedKeys(pair4D.Key, ref key0, ref key1, ref key2, ref key3);
                Console.WriteLine("pair matrix[{0}, 
                {1}, {2}, {3}] = {4}", key0, key1, key2, key3, pair4D.Value);
            }

            //----------------------------------------------------------
            // For five dimensions and higher, all of the index
            // values are not output to reduce clutter.
            //----------------------------------------------------------

            //----------------------------------------------------------
            // Five dimensional matrix.
            //----------------------------------------------------------

            Sparse5DMatrix<int, int, int, int, int, double> matrix5D =
                new Sparse5DMatrix<int, int, int, int, int, double>();

            matrix5D[0, 0, 0, 0, 0] = 500000.0;
            matrix5D[0, 1, 0, 1, 0] = 501010.0;
            matrix5D[1, 0, 1, 0, 1] = 510101.0;

            Console.WriteLine(String.Format("{0}", matrix5D[0, 0, 0, 0, 0]));
            Console.WriteLine(String.Format("{0}", matrix5D[0, 1, 0, 1, 0]));
            Console.WriteLine(String.Format("{0}", matrix5D[1, 0, 1, 0, 1]));
            Console.WriteLine(String.Format("{0}", matrix5D[1, 1, 1, 1, 1]));

            foreach (KeyValuePair<ComparableTuple5<int, 
            int, int, int, int>, double> pair5D in matrix5D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                int key3 = 0;
                int key4 = 0;
                matrix5D.SeparateCombinedKeys(pair5D.Key,
                                              ref key0,
                                              ref key1,
                                              ref key2,
                                              ref key3,
                                              ref key4);
                Console.WriteLine("pair matrix[{0}, {1}, {2}, {3}, {4}] = {5}",
                                  key0, key1, key2, key3, key4, pair5D.Value);
            }

            //----------------------------------------------------------
            // Six dimensional matrix.
            //----------------------------------------------------------

            Sparse6DMatrix<int, int, int, int, int, int, double> matrix6D =
                new Sparse6DMatrix<int, int, int, int, int, int, double>();

            matrix6D[0, 0, 0, 0, 0, 0] = 6000000.0;
            matrix6D[0, 1, 0, 1, 0, 1] = 6010101.0;
            matrix6D[1, 0, 1, 0, 1, 0] = 6101010.0;

            Console.WriteLine(String.Format("{0}", matrix6D[0, 0, 0, 0, 0, 0]));
            Console.WriteLine(String.Format("{0}", matrix6D[0, 1, 0, 1, 0, 1]));
            Console.WriteLine(String.Format("{0}", matrix6D[1, 0, 1, 0, 1, 0]));
            Console.WriteLine(String.Format("{0}", matrix6D[1, 1, 1, 1, 1, 1]));

            foreach (KeyValuePair<ComparableTuple6<int, int, 
            int, int, int, int>, double> pair6D in matrix6D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                int key3 = 0;
                int key4 = 0;
                int key5 = 0;
                matrix6D.SeparateCombinedKeys(pair6D.Key,
                                              ref key0,
                                              ref key1,
                                              ref key2,
                                              ref key3,
                                              ref key4,
                                              ref key5);
                Console.WriteLine("pair matrix[{0}, {1}, {2}, {3}, {4}, {5}] = {6}",
                                  key0, key1, key2, key3, key4, key5, pair6D.Value);
            }

            //----------------------------------------------------------
            // Seven dimensional matrix.
            //----------------------------------------------------------

            Sparse7DMatrix<int, int, int, int, int, int, int, double> matrix7D =
                new Sparse7DMatrix<int, int, int, int, int, int, int, double>();

            matrix7D[0, 0, 0, 0, 0, 0, 0] = 70000000.0;
            matrix7D[0, 1, 0, 1, 0, 1, 0] = 70101010.0;
            matrix7D[1, 0, 1, 0, 1, 0, 1] = 71010101.0;

            Console.WriteLine(String.Format("{0}", matrix7D[0, 0, 0, 0, 0, 0, 0]));
            Console.WriteLine(String.Format("{0}", matrix7D[0, 1, 0, 1, 0, 1, 0]));
            Console.WriteLine(String.Format("{0}", matrix7D[1, 0, 1, 0, 1, 0, 1]));
            Console.WriteLine(String.Format("{0}", matrix7D[1, 1, 1, 1, 1, 1, 1]));

            foreach (KeyValuePair<ComparableTuple7<int, int, 
            int, int, int, int, int>, double> pair7D in matrix7D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                int key3 = 0;
                int key4 = 0;
                int key5 = 0;
                int key6 = 0;
                matrix7D.SeparateCombinedKeys(pair7D.Key,
                                              ref key0,
                                              ref key1,
                                              ref key2,
                                              ref key3,
                                              ref key4,
                                              ref key5,
                                              ref key6);
                Console.WriteLine("pair matrix[{0}, {1}, {2}, {3}, {4}, {5}, {6}] = {7}",
                                  key0, key1, key2, key3, key4, key5, key6, pair7D.Value);
            }

            //----------------------------------------------------------
            // Eight dimensional matrix.
            //----------------------------------------------------------

            Sparse8DMatrix<int, int, int, int, int, int, int, int, double> matrix8D =
                new Sparse8DMatrix<int, int, int, int, int, int, int, int, double>();

            matrix8D[0, 0, 0, 0, 0, 0, 0, 0] = 800000000.0;
            matrix8D[0, 1, 0, 1, 0, 1, 0, 1] = 801010101.0;
            matrix8D[1, 0, 1, 0, 1, 0, 1, 0] = 810101010.0;

            FileStream fileStream = null;

            // Serialization code.
            using (fileStream = new FileStream
            ("Matrix8.dat", FileMode.OpenOrCreate, FileAccess.Write))
            {
                BinaryFormatter binFormatter = new BinaryFormatter();
                binFormatter.Serialize(fileStream, matrix8D);
            }

            // Deserialization code.
            Sparse8DMatrix<int, int, int, int, int, int, int, int, double> newMatrix8D =
                new Sparse8DMatrix<int, int, int, int, int, int, int, int, double>();

            using (fileStream = new FileStream("Matrix8.dat", FileMode.Open, FileAccess.Read))
            {
                BinaryFormatter binFormatter = new BinaryFormatter();
                newMatrix8D =
                    (Sparse8DMatrix<int, int, int, int, int, 
                    int, int, int, double>)binFormatter.Deserialize(fileStream);
            }

            Console.WriteLine(String.Format("{0}", newMatrix8D[0, 0, 0, 0, 0, 0, 0, 0]));
            Console.WriteLine(String.Format("{0}", newMatrix8D[0, 1, 0, 1, 0, 1, 0, 1]));
            Console.WriteLine(String.Format("{0}", newMatrix8D[1, 0, 1, 0, 1, 0, 1, 0]));
            Console.WriteLine(String.Format("{0}", newMatrix8D[1, 1, 1, 1, 1, 1, 1, 1]));

            foreach (KeyValuePair<ComparableTuple8<int, int, int, 
            int, int, int, int, int>, double> pair8D in newMatrix8D)
            {
                int key0 = 0;
                int key1 = 0;
                int key2 = 0;
                int key3 = 0;
                int key4 = 0;
                int key5 = 0;
                int key6 = 0;
                int key7 = 0;
                matrix8D.SeparateCombinedKeys(pair8D.Key,
                                              ref key0,
                                              ref key1,
                                              ref key2,
                                              ref key3,
                                              ref key4,
                                              ref key5,
                                              ref key6,
                                              ref key7);
                Console.WriteLine("pair matrix[{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}] = {8}",
                                  key0, key1, key2, key3, key4, key5, key6, key7, pair8D.Value);
            }

            //----------------------------------------------------------
            // Wait for input before exiting the program.
            //----------------------------------------------------------

            Console.Write("Hit 'enter' to continue > ");
            Console.ReadLine();
        }
    }
}

The SparseArray Class in File SparseArrays.cs

//=======================================================================
// Copyright (C) 2010-2013 William Hallahan
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//=======================================================================

?//======================================================================
// Generic Class: SparseArray
// Author: Bill Hallahan
// Date: April 9, 2010
//======================================================================

using System;
using System.Collections.Generic;

namespace SparseCollections
{
    /// <summary>
    /// This class implements a sparse array.
    /// </summary>
    /// <typeparam name="TKey">The key type used to index the array items</typeparam>
    /// <typeparam name="TValue">The type of the array values</typeparam>
    [Serializable]
    public class SparseArray<TKey, TValue>  : IEnumerable<KeyValuePair<TKey, TValue>>
        where TKey : IComparable<TKey>
    {
        private Dictionary<TKey, TValue> m_dictionary;

        /// <summary>
        /// This property stores the default value that is returned if the key doesn't exist.
        /// </summary>
        public TValue DefaultValue
        {
            get;
            set;
        }

        /// <summary>
        /// Property to get the count of items in the sparse array.
        /// </summary>
        public int Count
        {
            get
            {
                return m_dictionary.Count;
            }
        }

        #region Constructors
        /// <summary>
        /// Constructor - creates an empty sparse array instance.
        /// </summary>
        public SparseArray()
        {
            m_dictionary = new Dictionary<TKey, TValue>();
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="defaultValue">
        /// A default value to return if the key is not present.</param>
        public SparseArray(TValue defaultValue)
        {
            m_dictionary = new Dictionary<TKey, TValue>();
            DefaultValue = defaultValue;
        }

        /// <summary>
        /// Copy constructor.
        /// </summary>
        /// <param name="sparseArray">
        /// The sparse array instance to be copied</param>
        public SparseArray(SparseArray<TKey, TValue> sparseArray)
        {
            m_dictionary = new Dictionary<TKey, TValue>();
            Initialize(sparseArray);
            DefaultValue = sparseArray.DefaultValue;
        }

        #endregion

        /// <summary>
        /// Method to copy the data in another SparseArray instance to this instance.
        /// </summary>
        /// <param name="sparse2DMatrix">
        /// An instance of the SparseArray class.</param>
        private void Initialize(SparseArray<TKey, TValue> sparseArray)
        {
            m_dictionary.Clear();

            // Copy each key value pair to the new dictionary.
            foreach (KeyValuePair<TKey, TValue> pair in sparseArray)
            {
                m_dictionary.Add(pair.Key, pair.Value);
            }
        }

        /// <summary>
        /// Method to copy the data in this SparseArray instance to another instance.
        /// </summary>
        /// <param name="sparse2DMatrix">
        /// An instance of the SparseArray class.</param>
        public void CopyTo(SparseArray<TKey, TValue> sparseArray)
        {
            sparseArray.m_dictionary.Clear();

            // Copy each key value pair to the new dictionary.
            foreach (KeyValuePair<TKey, TValue> pair in m_dictionary)
            {
                sparseArray.m_dictionary.Add(pair.Key, pair.Value);
            }
        }

        /// <summary>
        /// Property []
        /// </summary>
        /// <param name="key">The key used to index the value</param>
        /// <returns>The 'get' property returns the value at the current key</returns>
        public TValue this[TKey key]
        {
            get
            {
                TValue value;

                if (!m_dictionary.TryGetValue(key, out value))
                {
                    value = DefaultValue;
                }

                return value;
            }

            set
            {
                m_dictionary[key] = value;
            }
        }

        /// <summary>
        /// Determines whether this sparse array contains the specified key.
        /// </summary>
        /// <param name="key">A key</param>
        /// <returns>Returns the value 'true' 
        /// if and only if the key exists in this sparse array</returns>
        public bool ContainsKey(TKey key)
        {
            return m_dictionary.ContainsKey(key);
        }

        /// <summary>
        /// Determines whether this sparse array contains the specified value.
        /// </summary>
        /// <param name="key">A value</param>
        /// <returns>Returns the value 'true' if and only if 
        /// the value exists in this sparse array</returns>
        public bool ContainsValue(TValue value)
        {
            return m_dictionary.ContainsValue(value);
        }

        /// <summary>
        /// Gets the value for the associated key.
        /// </summary>
        /// <param name="key">The key of the value to get</param>
        /// <param name="value">An out parameter 
        /// that contains the value if the key exists</param>
        /// <returns>Returns the value 'true' if and only if 
        /// the key exists in this sparse array</returns>
        public bool TryGetValue(TKey key, out TValue value)
        {
            return m_dictionary.TryGetValue(key, out value);
        }

        /// <summary>
        /// Removes the value with the specified key from this sparse array instance.
        /// </summary>
        /// <param name="key">The key of the element to remove</param>
        /// <returns>The value 'true' if and only if the element 
        /// is successfully found and removed.</returns>
        public bool Remove(TKey key)
        {
            return m_dictionary.Remove(key);
        }

        /// <summary>
        /// Method to clear all values in the sparse array.
        /// </summary>
        public void Clear()
        {
            m_dictionary.Clear();
        }

        #region IEnumerable<KeyValuePair<TKey, TValue>> Members

        /// <summary>
        /// The Generic IEnumerator<> GetEnumerator method
        /// </summary>
        /// <returns>An enumerator to iterate over all 
        /// key-value pairs in this sparse array</returns>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return this.m_dictionary.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// The non-generic IEnumerator<> GetEnumerator method
        /// </summary>
        /// <returns>An enumerator to iterate over all 
        /// key-value pairs in this sparse array</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.m_dictionary.Values.GetEnumerator();
        }

        /// <summary>
        /// Property to get the key-value pair at the current enumerator position.
        /// </summary>
        public TValue Current
        {
            get
            {
                return m_dictionary.Values.GetEnumerator().Current;
            }
        }

        /// <summary>
        /// Method to move to the next enumerator position.
        /// </summary>
        /// <returns></returns>
        public bool MoveNext()
        {
            return m_dictionary.Values.GetEnumerator().MoveNext();
        }

        #endregion
    }

A Sparse Matrix

I chose the Sparse3DMatrix to describe all the sparse matrix classes. Shown first is the ComparableTuple3 class, which stores the key values for the Sparse3DMatrix class.

The ComparableTuple3 Class in File ComparableTuple3.cs

//=======================================================================
// Copyright (C) 2010-2013 William Hallahan
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//=======================================================================

?//======================================================================
// Generic Abstract Class: ComparableTuple3
// Author: Bill Hallahan
// Date: April 22, 2010
//======================================================================

using System;
using System.Collections.Generic;

namespace SparseCollections
{
    /// <summary>
    /// This class implements a group of 3 items.
    /// </summary>
    /// <typeparam name="TItem0">The type of the first item</typeparam>
    /// <typeparam name="TItem1">The type of the second item</typeparam>
    /// <typeparam name="TItem2">The type of the third item</typeparam>
    [Serializable]
    public class ComparableTuple3<TItem0, TItem1, TItem2>
        : IComparable<ComparableTuple3<TItem0, TItem1, TItem2>>
        where TItem0 : IComparable<TItem0>
        where TItem1 : IComparable<TItem1>
        where TItem2 : IComparable<TItem2>
    {
        /// <summary>
        /// The first item
        /// </summary>
        public TItem0 Item0
        {
            get;
            private set;
        }

        /// <summary>
        /// The second item.
        /// </summary>
        public TItem1 Item1
        {
            get;
            private set;
        }

        /// <summary>
        /// The third item.
        /// </summary>
        public TItem2 Item2
        {
            get;
            private set;
        }

        #region Constructors

        /// <summary>
        /// Constructor
        /// </summary>
        public ComparableTuple3()
        {
        }

        /// <summary>
        /// Constructs a new instance with the same item values as this instance.
        /// </summary>
        /// <param name="group">The group used to initialize this instance</param>
        public ComparableTuple3(ComparableTuple3<TItem0, TItem1, TItem2> group)
        {
            Item0 = group.Item0;
            Item1 = group.Item1;
            Item2 = group.Item2;
        }

        /// <summary>
        /// Constructs a new instance with the specified item values.
        /// </summary>
        /// <param name="item0">The first item</param>
        /// <param name="item1">The second item</param>
        /// <param name="item2">The third item</param>
        public ComparableTuple3(TItem0 item0,
                      TItem1 item1,
                      TItem2 item2)
        {
            Item0 = item0;
            Item1 = item1;
            Item2 = item2;
        }

        #endregion

        #region IComparable<ComparableTuple3> implementation
        /// <summary>
        /// This methods implements the IComparable<ComparableTuple3<TItem0, TItem1, TItem2>> interface.
        /// </summary>
        /// <param name="group">The group being compared to this group</param>
        /// <returns>
        /// The value -1 if this groups is less than the passed group.
        /// The value 1 if this group is greater than the passed group.
        /// The value 0 if this group and the passed groups are equal.
        /// </returns>
        public int CompareTo(ComparableTuple3<TItem0, TItem1, TItem2> group)
        {
            int result = this.Item0.CompareTo(group.Item0);

            if (result == 0)
            {
                result = this.Item1.CompareTo(group.Item1);

                if (result == 0)
                {
                    result = this.Item2.CompareTo(group.Item2);
                }
            }

            return result;
        }

        #endregion
    }

    /// <summary>
    /// This class implements the IEqualityComparer<ComparableTuple3<
    /// TItem0, TItem1, TItem2>> interface
    /// to allow using ComparableTuple3<ComparableTuple3<TItem0, 
    /// TItem1, TItem2> class instances as keys in a dictionary.
    /// </summary>
    /// <typeparam name="TItem0">The type of the first item</typeparam>
    /// <typeparam name="TItem1">The type of the second item</typeparam>
    /// <typeparam name="TItem2">The type of the third item</typeparam>
    [Serializable]
    public class ComparableTuple3EqualityComparer<TItem0, TItem1, TItem2>
        : IEqualityComparer<ComparableTuple3<TItem0, TItem1, TItem2>>
        where TItem0 : IComparable<TItem0>
        where TItem1 : IComparable<TItem1>
        where TItem2 : IComparable<TItem2>
    {
        #region Constructor

        /// <summary>
        /// Constructor
        /// </summary>
        public ComparableTuple3EqualityComparer()
        {
        }

        #endregion

        /// IEqualityComparer.Equals compares the items in this group for equality.
        public bool Equals(ComparableTuple3<TItem0, TItem1, TItem2> groupA,
                           ComparableTuple3<TItem0, TItem1, TItem2> groupB)
        {
            return ((groupA.Item0.Equals(groupB.Item0))
                && (groupA.Item1.Equals(groupB.Item1))
                && (groupA.Item2.Equals(groupB.Item2)));
        }

        /// <summary>
        /// Returns a hash code for an object.
        /// </summary>
        /// <param name="obj">An object of type ComparableTuple3</param>
        /// <returns>A hash code for the object.</returns>
        public int GetHashCode(ComparableTuple3<TItem0, TItem1, TItem2> group)
        {
            int hash0 = group.Item0.GetHashCode();
            int hash1 = group.Item1.GetHashCode();
            int hash2 = group.Item2.GetHashCode();

            int hash = 577 * hash0 + 599 * hash1 + 619 * hash2;
            return hash.GetHashCode();
        }
    }
}

The Sparse3DMatrix Class in File Sparse3DMatrix.cs

//=======================================================================
// Copyright (C) 2010-2013 William Hallahan
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//=======================================================================

//======================================================================
// Generic Class: Sparse3DMatrix
// Author: Bill Hallahan
// Date: April 12, 2010
//======================================================================

using System;
using System.Collections.Generic;

namespace SparseCollections
{
    /// <summary>
    /// This class implements a sparse 3 dimensional matrix.
    /// </summary>
    /// <typeparam name="TKey0">The first key type used to index the array items</typeparam>
    /// <typeparam name="TKey1">The second key type used to index the array items</typeparam>
    /// <typeparam name="TKey2">The third key type used to index the array items</typeparam>
    /// <typeparam name="TValue">The type of the array values</typeparam>
    [Serializable]
    public class Sparse3DMatrix<TKey0, TKey1, TKey2, TValue> : IEnumerable<KeyValuePair<ComparableTuple3<TKey0, TKey1, TKey2>, TValue>>
        where TKey0 : IComparable<TKey0>
        where TKey1 : IComparable<TKey1>
        where TKey2 : IComparable<TKey2>
    {
        private Dictionary<ComparableTuple3<TKey0, TKey1, TKey2>, TValue> m_dictionary;

        /// <summary>
        /// This property stores the default value that is returned if the keys don't exist in the array.
        /// </summary>
        public TValue DefaultValue
        {
            get;
            set;
        }

        /// <summary>
        /// Property to get the count of items in the sparse array.
        /// </summary>
        public int Count
        {
            get
            {
                return m_dictionary.Count;
            }
        }

        #region Constructors
        /// <summary>
        /// Constructor - creates an empty sparse array instance.
        /// </summary>
        public Sparse3DMatrix()
        {
            InitializeDictionary();
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="defaultValue">A default value to return if the key is not present.</param>
        public Sparse3DMatrix(TValue defaultValue)
        {
            InitializeDictionary();
            DefaultValue = defaultValue;
        }

        /// <summary>
        /// Copy constructor.
        /// </summary>
        /// <param name="sparse3DMatrix">The sparse array instance to be copied</param>
        public Sparse3DMatrix(Sparse3DMatrix<TKey0, TKey1, TKey2, TValue> sparse3DMatrix)
        {
            InitializeDictionary();
            Initialize(sparse3DMatrix);
            DefaultValue = sparse3DMatrix.DefaultValue;
        }

        #endregion

        /// <summary>
        /// Initialize the dictionary to compare items based on key values.
        /// </summary>
        private void InitializeDictionary()
        {
            ComparableTuple3EqualityComparer<TKey0, TKey1, TKey2> equalityComparer = new ComparableTuple3EqualityComparer<TKey0, TKey1, TKey2>();
            m_dictionary = new Dictionary<ComparableTuple3<TKey0, TKey1, TKey2>, TValue>(equalityComparer);
        }

        /// <summary>
        /// Method to copy the data in another Sparse3DMatrix instance to this instance.
        /// </summary>
        /// <param name="sparse3DMatrix">An instance of the Sparse3DMatrix class.</param>
        private void Initialize(Sparse3DMatrix<TKey0, TKey1, TKey2, TValue> sparse3DMatrix)
        {
            m_dictionary.Clear();

            // Copy each key value pair to the dictionary.
            foreach (KeyValuePair<ComparableTuple3<TKey0, TKey1, TKey2>, TValue> pair in sparse3DMatrix)
            {
                ComparableTuple3<TKey0, TKey1, TKey2> newCombinedKey = new ComparableTuple3<TKey0, TKey1, TKey2>(pair.Key);
                m_dictionary.Add(newCombinedKey, pair.Value);
            }
        }

        /// <summary>
        /// Method to copy the data in this Sparse3DMatrix instance to another instance.
        /// </summary>
        /// <param name="sparse3DMatrix">An instance of the Sparse3DMatrix class.</param>
        public void CopyTo(Sparse3DMatrix<TKey0, TKey1, TKey2, TValue> sparse3DMatrix)
        {
            sparse3DMatrix.m_dictionary.Clear();

            // Copy each key value pair to the dictionary.
            foreach (KeyValuePair<ComparableTuple3<TKey0, TKey1, TKey2>, TValue> pair in m_dictionary)
            {
                ComparableTuple3<TKey0, TKey1, TKey2> newCombinedKey = new ComparableTuple3<TKey0, TKey1, TKey2>(pair.Key);
                sparse3DMatrix.m_dictionary.Add(newCombinedKey, pair.Value);
            }
        }

        /// <summary>
        /// Property []
        /// </summary>
        /// <param name="key0">The first key used to index the value</param>
        /// <param name="key1">The second key used to index the value</param>
        /// <param name="key2">The third key used to index the value</param>
        /// <returns>The 'get' property returns the value at the current key</returns>
        public TValue this[TKey0 key0, TKey1 key1, TKey2 key2]
        {
            get
            {
                TValue value;

                if (!m_dictionary.TryGetValue(CombineKeys(key0, key1, key2), out value))
                {
                    value = DefaultValue;
                }

                return value;
            }

            set
            {
                m_dictionary[CombineKeys(key0, key1, key2)] = value;
            }
        }
        /// <summary>
        /// Determines whether this matrix contains the specified keys.
        /// </summary>
        /// <param name="key0">The first key used to index the value</param>
        /// <param name="key1">The second key used to index the value</param>
        /// <param name="key2">The third key used to index the value</param>
        /// <returns>Returns the value 'true' if and only if the keys exists in this matrix</returns>
        public bool ContainsKey(TKey0 key0, TKey1 key1, TKey2 key2)
        {
            return m_dictionary.ContainsKey(CombineKeys(key0, key1, key2));
        }

        /// <summary>
        /// Determines whether this matrix contains the specified value.
        /// </summary>
        /// <param name="value">A value</param>
        /// <returns>Returns the value 'true' if and only if the value exists in this matrix</returns>
        public bool ContainsValue(TValue value)
        {
            return m_dictionary.ContainsValue(value);
        }

        /// <summary>
        /// Gets the value for the associated keys.
        /// </summary>
        /// <param name="key0">The first key used to index the value</param>
        /// <param name="key1">The second key used to index the value</param>
        /// <param name="key2">The third key used to index the value</param>
        /// <param name="value">An out parameter that contains the value if the key exists</param>
        /// <returns>Returns the value 'true' if and only if the key exists in this matrix</returns>
        public bool TryGetValue(TKey0 key0, TKey1 key1, TKey2 key2, out TValue value)
        {
            return m_dictionary.TryGetValue(CombineKeys(key0, key1, key2), out value);
        }

        /// <summary>
        /// Removes the value with the specified key from this sparse matrix instance.
        /// </summary>
        /// <param name="key0">The first key of the element to remove</param>
        /// <param name="key1">The second key of the element to remove</param>
        /// <param name="key2">The third key used to index the value</param>
        /// <returns>The value 'true' if and only if the element is successfully found and removed.</returns>
        public bool Remove(TKey0 key0, TKey1 key1, TKey2 key2)
        {
            return m_dictionary.Remove(CombineKeys(key0, key1, key2));
        }

        /// <summary>
        /// Method to clear all values in the sparse array.
        /// </summary>
        public void Clear()
        {
            m_dictionary.Clear();
        }

        /// <summary>
        /// This method must be overridden by the caller to combine the keys.
        /// </summary>
        /// <param name="key0">The first key</param>
        /// <param name="key1">The second key</param>
        /// <param name="key2">The third key</param>
        /// <returns>A value that combines the keys in a unique fashion</returns>
        public ComparableTuple3<TKey0, TKey1, TKey2> CombineKeys(TKey0 key0, TKey1 key1, TKey2 key2)
        {
            return new ComparableTuple3<TKey0, TKey1, TKey2>(key0, key1, key2);
        }

        /// <summary>
        /// This method must be overridden by the caller to separate a combined key into the two original keys.
        /// </summary>
        /// <param name="combinedKey">A value that combines the keys in a unique fashion</param>
        /// <param name="key0">A reference to the first key</param>
        /// <param name="key1">A reference to the second key</param>
        /// <param name="key2">A reference to the third key</param>
        public void SeparateCombinedKeys(ComparableTuple3<TKey0, TKey1, TKey2> combinedKey,
                                         ref TKey0 key0,
                                         ref TKey1 key1,
                                         ref TKey2 key2)
        {
            key0 = combinedKey.Item0;
            key1 = combinedKey.Item1;
            key2 = combinedKey.Item2;
        }

        #region IEnumerable<KeyValuePair<ComparableTuple3<TKey0, TKey1, TKey2>, TValue>> Members

        /// <summary>
        /// The Generic IEnumerator<> GetEnumerator method
        /// </summary>
        /// <returns>An enumerator to iterate over all key-value pairs in this sparse array</returns>
        public IEnumerator<KeyValuePair<ComparableTuple3<TKey0, TKey1, TKey2>, TValue>> GetEnumerator()
        {
            return this.m_dictionary.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// The non-generic IEnumerator<> GetEnumerator method
        /// </summary>
        /// <returns>An enumerator to iterate over all key-value pairs in this sparse array</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.m_dictionary.GetEnumerator();
        }

        #endregion
    }
}

Points of Interest

I originally wrote the SparseArray class. When I started to write the first sparse matrix class, I noted that all the sparse matrix classes would have a similar form. So, I wrote a code generator that wrote most of the code. I implemented the SparseMatrix8D class first. Then it was easy to create the others. I still have the code generator in case I ever need a Sparse16DMatrix!

Also, when I recently looked at Microsoft's Tuple classes online, I was surprised at how similar I had made the Group classes, which again has been renamed to ComparableTuple. I named the item property starting with Item0, and Microsoft started at Item1, but we essentially have exactly the same name for a property! I guess that is not surprising - "Item" is a generic term for "something" and books describing properties often use the word "item".

History

Initial post
Based on feedback, I renamed the Group<X> classes to ComparableTuple<X>. Added a 'using' statement to the main program for the FileStream instance. Updated the article accordingly and uploaded the new code.
Based on feedback, I removed the private set property method from the Count property of the SparseXDMatrix classes.
Based on even good feeback from kornman00, I removed the incorrect and unneeded IEnumerator interface Move and Current propery methods from the sparse matrix classes. I update the article and uploaded the updated code.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here