HashSet that preserves insertion order or .NET implementation of LinkedHashSet

A_README.md

HashSet that preserves insertion order or .NET implementation of LinkedHashSet

Many people naively assume an ordinary .NET HashSet preserves insertion order. Indeed HashSet accidentally preserves insertion order until you remove and re-add some elements. There is such a data structure in Java - LinkedHashSet which respects order and has O(1) RW times.

No, I did not find a (working) corresponding implementation in .NET. That's I wrote this one.

The implementation uses linked list in combination with dictionary to define the iteration, ordering and at the same time allow O(1) removal.

The order is not affected if an element is re-inserted into the set it retains it's old position.

This code is distributed under MIT license. Copyright (c) 2013 George Mamaladze See license.txt or http://opensource.org/licenses/mit-license.php

OrderedSet.cs

// This code is distributed under MIT license. Copyright (c) 2013 George Mamaladze
// See license.txt or http://opensource.org/licenses/mit-license.php

using System.Collections;
using System.Collections.Generic;

namespace Gma.DataStructures
{
    public class OrderedSet<T> : ICollection<T>
    {
        private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
        private readonly LinkedList<T> m_LinkedList;

        public OrderedSet()
            : this(EqualityComparer<T>.Default)
        {
        }

        public OrderedSet(IEqualityComparer<T> comparer)
        {
            m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
            m_LinkedList = new LinkedList<T>();
        }

        public int Count
        {
            get { return m_Dictionary.Count; }
        }

        public virtual bool IsReadOnly
        {
            get { return m_Dictionary.IsReadOnly; }
        }

        void ICollection<T>.Add(T item)
        {
            Add(item);
        }

        public void Clear()
        {
            m_LinkedList.Clear();
            m_Dictionary.Clear();
        }

        public bool Remove(T item)
        {
            LinkedListNode<T> node;
            bool found = m_Dictionary.TryGetValue(item, out node);
            if (!found) return false;
            m_Dictionary.Remove(item);
            m_LinkedList.Remove(node);
            return true;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return m_LinkedList.GetEnumerator();
        }

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

        public bool Contains(T item)
        {
            return m_Dictionary.ContainsKey(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            m_LinkedList.CopyTo(array, arrayIndex);
        }

        public bool Add(T item)
        {
            if (m_Dictionary.ContainsKey(item)) return false;
            LinkedListNode<T> node = m_LinkedList.AddLast(item);
            m_Dictionary.Add(item, node);
            return true;
        }
    }
}

OrderedSetExt.cs

// This code is distributed under MIT license. Copyright (c) 2013 George Mamaladze
// See license.txt or http://opensource.org/licenses/mit-license.php

using System;
using System.Collections.Generic;
using System.Linq;

namespace Gma.DataStructures
{
    public class OrderedSetExt<T> : OrderedSet<T>, ISet<T>
    {
        public OrderedSetExt()
        {
        }

        public OrderedSetExt(IEqualityComparer<T> comparer)
            : base(comparer)
        {
        }

        public OrderedSetExt(IEnumerable<T> collection)
            : this(collection, EqualityComparer<T>.Default)
        {
        }

        public OrderedSetExt(IEnumerable<T> collection, IEqualityComparer<T> comparer)
            : this(comparer)
        {
            foreach (T item in collection)
            {
                Add(item);
            }
        }

        /// <summary>
        ///     Modifies the current set so that it contains all elements that are present in both the current set and in the
        ///     specified collection.
        /// </summary>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public void UnionWith(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            foreach (T element in other)
            {
                Add(element);
            }
        }

        /// <summary>
        ///     Modifies the current set so that it contains only elements that are also in a specified collection.
        /// </summary>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public void IntersectWith(IEnumerable<T> other)
        {
            foreach (T element in other)
            {
                if (Contains(element)) continue;
                Remove(element);
            }
        }

        /// <summary>
        ///     Removes all elements in the specified collection from the current set.
        /// </summary>
        /// <param name="other">The collection of items to remove from the set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public void ExceptWith(IEnumerable<T> other)
        {
            foreach (T element in other)
            {
                Remove(element);
            }
        }

        /// <summary>
        ///     Modifies the current set so that it contains only elements that are present either in the current set or in the
        ///     specified collection, but not both.
        /// </summary>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public void SymmetricExceptWith(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            foreach (T element in other)
            {
                if (Contains(element))
                {
                    Remove(element);
                }
                else
                {
                    Add(element);
                }
            }
        }

        /// <summary>
        ///     Determines whether a set is a subset of a specified collection.
        /// </summary>
        /// <returns>
        ///     true if the current set is a subset of <paramref name="other" />; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool IsSubsetOf(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            var otherHashset = new HashSet<T>(other);
            return otherHashset.IsSupersetOf(this);
        }

        /// <summary>
        ///     Determines whether the current set is a superset of a specified collection.
        /// </summary>
        /// <returns>
        ///     true if the current set is a superset of <paramref name="other" />; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool IsSupersetOf(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            return other.All(Contains);
        }

        /// <summary>
        ///     Determines whether the current set is a correct superset of a specified collection.
        /// </summary>
        /// <returns>
        ///     true if the <see cref="T:System.Collections.Generic.ISet`1" /> object is a correct superset of
        ///     <paramref name="other" />; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set. </param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool IsProperSupersetOf(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            var otherHashset = new HashSet<T>(other);
            return otherHashset.IsProperSubsetOf(this);
        }

        /// <summary>
        ///     Determines whether the current set is a property (strict) subset of a specified collection.
        /// </summary>
        /// <returns>
        ///     true if the current set is a correct subset of <paramref name="other" />; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool IsProperSubsetOf(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            var otherHashset = new HashSet<T>(other);
            return otherHashset.IsProperSupersetOf(this);
        }

        /// <summary>
        ///     Determines whether the current set overlaps with the specified collection.
        /// </summary>
        /// <returns>
        ///     true if the current set and <paramref name="other" /> share at least one common element; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool Overlaps(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            if (Count == 0) return false;
            return other.Any(Contains);
        }

        /// <summary>
        ///     Determines whether the current set and the specified collection contain the same elements.
        /// </summary>
        /// <returns>
        ///     true if the current set is equal to <paramref name="other" />; otherwise, false.
        /// </returns>
        /// <param name="other">The collection to compare to the current set.</param>
        /// <exception cref="T:System.ArgumentNullException"><paramref name="other" /> is null.</exception>
        public bool SetEquals(IEnumerable<T> other)
        {
            if (other == null) throw new ArgumentNullException("other");
            var otherHashset = new HashSet<T>(other);
            return otherHashset.SetEquals(this);
        }
    }
}

OrderedSetTest.cs

// This code is distributed under MIT license. Copyright (c) 2013 George Mamaladze
// See license.txt or http://opensource.org/licenses/mit-license.php
#region Used namespaces

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

#endregion

namespace Gma.DataStructures.Test
{
    internal class Command<T>
    {
        public const char Separator = ';';

        private readonly Operation m_Operation;
        private readonly T m_Item;

        public Command(Operation operation, T item)
        {
            m_Operation = operation;
            m_Item = item;
        }

        public void Execute(ISet<T> set)
        {
            switch (m_Operation)
            {
                case Operation.Add:
                    set.Add(m_Item);
                    break;
                case Operation.Remove:
                    set.Remove(m_Item);
                    break;
                case Operation.Clear:
                    set.Clear();
                    break;
                default:
                    throw new NotSupportedException(String.Format("Operation [{0}] is not supported.", m_Operation));
            }
        }

        public static Command<T> Parse(string token)
        {
            var prefixChar = token[0];
            var itemText = token.Substring(1);
            var operation = CharToOperation(prefixChar);
            T item =
                !String.IsNullOrEmpty(itemText)
                    ? (T)Convert.ChangeType(itemText, typeof(T))
                    : default(T);
            return new Command<T>(operation, item);
        }

        private static Operation CharToOperation(char ch)
        {
            switch (ch)
            {
                case '+':
                    return Operation.Add;
                case '-':
                    return Operation.Remove;
                case '#':
                    return Operation.Clear;
                default:
                    throw new NotSupportedException(String.Format("Operation [{0}] is not supported.", ch));
            }
        }
    }

    internal enum Operation
    {
        Add,
        Remove,
        Clear
    }

    [TestClass]
    public class OrderedSetTest
    {
        [TestMethod]
        public void empty()
        {
            const string input = "";
            const string expected = "";
            TestX(input, expected);
        }

        [TestMethod]
        public void add_one()
        {
            const string input = "+1;";
            const string expected = "1";
            TestX(input, expected);
        }

        [TestMethod]
        public void add_many()
        {
            const string input = "+1;+2;+3;+4;+5;+6";
            const string expected = "1;2;3;4;5;6";
            TestX(input, expected);
        }

        [TestMethod]
        public void add_many_then_clear()
        {
            const string input = "+1;+2;+3;+4;+5;+6;#";
            const string expected = "";
            TestX(input, expected);
        }

        [TestMethod]
        public void add_many_then_clear_then_add()
        {
            const string input = "+1;+2;+3;+4;+5;+6;#;+4;+3;+2;";
            const string expected = "4;3;2";
            TestX(input, expected);
        }

        [TestMethod]
        public void adds_and_removes_mixed()
        {
            const string input = "+1;+2;+3;+4;-2;-3;+2;+3;+5";
            const string expected = "1;4;2;3;5";
            TestX(input, expected);
        }

        private void TestX(string input, string expected)
        {
            ISet<int> set = new OrderedSetExt<int>();
            Execute(set, input);
            AssertSet(expected, set);
        }

        private void AssertSet<T>(string expected, IEnumerable<T> actual)
        {
            var expactedArray =
                expected
                    .Split(Command<int>.Separator)
                    .Where(s => !string.IsNullOrEmpty(s))
                    .Select(token => Convert.ChangeType(token, typeof (T)))
                    .Cast<T>();

            AssertEnumerables(expactedArray, actual);
        }

        private static void AssertEnumerables<T>(IEnumerable<T> expected, IEnumerable<T> actual)
        {
            string separator = Command<T>.Separator.ToString(CultureInfo.InvariantCulture);
            string expectedText = string.Join(separator, expected.Select(item => Convert.ToString(item)));
            string actualText = string.Join(separator, actual.Select(item => Convert.ToString(item)));
            Assert.AreEqual(expectedText, actualText);
        }

        private void Execute(ISet<int> set, string program)
        {
            var commands =
                program
                    .Split(Command<int>.Separator)
                    .Where(s => !string.IsNullOrEmpty(s))
                    .Select(Command<int>.Parse);

            foreach (var command in commands)
            {
                command.Execute(set);
            }
        }
    }
}