8
\$\begingroup\$

I need a generic data structure that ensures that its elements are unique. C# has HashSet<T>, great!

As it turns out, the elements have to stay in the order in which they were added, too. This sounds more like List<T>.

I tried to create my own:

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

namespace Collections.Generic
{
    public class HashSetList<T> : IList<T>
    {
        private List<T> _list;
        private HashSet<T> _set;

        public HashSetList()
        {
            _list = new List<T>();
            _set = new HashSet<T>();
        }

        public int IndexOf(T item)
        {
            return _list.IndexOf(item);
        }

        public void Insert(int index, T item)
        {
            if (_set.Add(item))
            {
                _list.Insert(index, item);
            }
        }

        public void RemoveAt(int index)
        {
            _set.Remove(_list[index]);

            _list.RemoveAt(index);
        }

        public T this[int index]
        {
            get
            {
                return _list[index];
            }
            set
            {
                if (_set.Add(value))
                {
                    _list[index] = value;
                };
            }
        }

        public void Add(T item)
        {
            if (_set.Add(item))
            {
                _list.Add(item);
            }
        }

        public void Clear()
        {
            _list.Clear();
            _set.Clear();
        }

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

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

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

        public bool IsReadOnly
        {
            get 
            {
                return false;
            }
        }

        public bool Remove(T item)
        {
            _set.Remove(item);
            return _list.Remove(item);
        }

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


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

It's an IList<T> wrapper that delegates method calls of the interface to a List<T> member with an additional HashSet<T> to ensure the uniqueness.

One problem is that it somewhat breaks the IList<T> interface. It's always possible to successfully call Add(T item) on a IList<T>, which is why that method returns void. But my HashSetList<T> rejects elements it already contains. In this regard, it's more like a ISet<T>, which returns bool if the operation was successful or not.

Then why implement IList<T> only? It's an ISet<T> after all, right? Well, yes and no. This is where the problem lies: The two interfaces IList<T> and ISet<T> are incompatible because their Add(T item) methods have incompatible "signatures".

By "signatures" I mean that their signatures are actually the same, because afaik in C# land the return type is not part of the signature. However, the interfaces demand different return types, which means they both have to be implemented, which in turn creates an invalidly overloaded Add(T item) method that is not distinguishable from each other. (singular/plural pun intended)

Should HashSetList<T> implement ISet<T> instead of IList<T>? (I omit its code for brevity)

That would allow code to branch based on the success of the Add(T item) method like so:

 if (orderedSet.Add(foo))
 {
     //added now
 }

vs

 orderedSet.Add(foo);
 if (orderedSet.Contains(foo))
 {
     //added now or already present before
 }

The disadvantage would be that operations one would expect from an ordered data structure, especially those with read/write access via index would be gone. At least in terms of an implemented interface.

Which interface should I choose? Or should I create two classes OrderedSet and UniqueList each implementing either one?

\$\endgroup\$
  • \$\begingroup\$ IList really is a very broad interface. It's often impractical to fulfill it's entire contract. Make a practical decision. API users likely want to use your class as an IList so give it to them and document where the abstraction leaks. \$\endgroup\$ – usr Jun 15 '16 at 20:45
6
\$\begingroup\$

From the technical point of view you could implement both interfaces at the same time but you'd have to implement the Add method explicitly and without repeating yourself it would go like this:

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

bool ISet<T>.Add(T item)
{
    if (_set.Add(item))
    {
        _list.Add(item);
        return true;
    }
    return false;
}

Which leads to one issue in your code namely the indexer repeats the insertion. You should use the insert method here:

public T this[int index]
{
    get
    {
        return _list[index];
    }
    set
    {
        Insert(index, value);
    }
}
\$\endgroup\$
5
\$\begingroup\$

You can always add more guarantees, but you should never take them away. This is much better as a Set with the additional property of maintaining insertion order, rather than a List that breaks the spec.

\$\endgroup\$
4
\$\begingroup\$

Should HashSetList implement ISet instead of IList?

In my eyes definitely YES!

Some of the IList members doesn't make sense in combinations with a set.

For example:

IList<int> set = new HashSetList<int>();
set.Add(1);
set[0] = 2;
// set[0] remains 1!

I am fine with a set that preserves the order of insertion by implementing ISet with a customized IEnumerable-implementation (something like OrderedSet). Whereas, an UniqueList doesn't make sense for me because it would not behave like a list (see also Liskov Substitution Principle).

\$\endgroup\$
  • \$\begingroup\$ Good example, but I guess the access via brackets can be modified to work for cases like that. The question is if things like set[0] = 2 should always modify the data or if they are allowed to fail. \$\endgroup\$ – I'll add comments tomorrow Jun 15 '16 at 17:54
  • \$\begingroup\$ @I'lladdcommentstomorrow: Which behavior would you suggest? I could imagine something like: set[0] = 2 removes the '1' from the setlist and adds the '2' at index 0, but if the setlist already contains a '2' an exception is thrown!? That is not the behavior that i would expect from an object of type IList. \$\endgroup\$ – JanDotNet Jun 15 '16 at 18:05
  • \$\begingroup\$ I guess the general idea of a set is that every operation that would cause a duplicated element should fail. Attempting any such operation should never cause an exception. Just like Add() on HashSet fails almost silently and merely returns false, something like set[0] = 2 would fail entirely silently (and not remove anything either), if 2 is already in the set. \$\endgroup\$ – I'll add comments tomorrow Jun 15 '16 at 18:22
4
\$\begingroup\$

Because you don't validate method parameters of your public methods you are leaking implementation details of your class. The user of your class shouldn't know which kind of underlaying datastructure you are using.

Let's take e.g RemoveAt(int):

Calling this method with an index > _list.Count will result in an ArgumentOutOfRangeException with the stacktrace

StackTrace:
at System.ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument argument, ExceptionResource resource)
at System.Collections.Generic.List`1.get_Item(Int32 index)

hence its exposing that you are using aList<T>.

Sure you can say, hey I implement IList<T> that is what expected to be seen here. But if you, like correctly suggested, implement a ISet<T> then it wouldn't be that good if you are leaking the usage of the List<T>.


private List<T> _list;
  private HashSet<T> _set;  

does this need to be a List<T> and a HashSet<T> ? I don't think so because you aren't using specific methods of this objects. You should declare them as IList<T> and ISet<T>. You should code against interfaces not implementations.

In addition, by making these variables readonly your code will become more robust.


\$\endgroup\$
  • \$\begingroup\$ ah, this is what you mean by leaking implimentation ;-) I'll be more careful too. \$\endgroup\$ – t3chb0t Jun 16 '16 at 7:38
  • \$\begingroup\$ I worked with a library before that had stacktraces going down to the bare metal (the call to the C code that the library was wrapping) and thus wasn't aware that this is a problem. Instead of checking the input, I could also just try to make the call and then re-throw any occurring exception in a non-leaking way. Is that a worse solution? \$\endgroup\$ – I'll add comments tomorrow Jun 16 '16 at 8:30
  • \$\begingroup\$ In a case like this (OP's question) I would validate the arguments and throw the exceptions right away. Throwing the exception in a non leaking way would mean loosing the stacktrace. You should consider this option only if you have a possibility to first log the inital exception including the stacktrace. \$\endgroup\$ – Heslacher Jun 16 '16 at 8:56
2
\$\begingroup\$

I like the idea of adding guaranteers instead of taking them away.

But to chicane a little bit to the current solution:

public bool Remove(T item)
{
    _set.Remove(item);
    return _list.Remove(item);
}

Looks like you can make it faster if you only remove an item from the list when you successfully remove this item from the set:

public bool Remove(T item)
{
    return _set.Remove(item)
        ? _list.Remove(item)
        : false;    
}

Also,

if (_set.Add(value))
{
    _list[index] = value;
};

You do not need a semicolon here.

\$\endgroup\$
1
\$\begingroup\$

I think there's a worthwhile compromise where you implement ISet<T> and IReadOnlyList<T>. This exposes the ordering efficiently (a caller can get the nth item in constant time rather than time linear in n) without committing you to the mutating methods of List<T>.

\$\endgroup\$
1
\$\begingroup\$

I believe requirements around the contract should be more specific as well. Is there a reason why you expose all the members defined in IList or ISet or both?

How about defining an interface as below assuming these members are what your caller will need:

public interface IOrderedSet<T> : IEnumerable<T> where T : IEquatable<T>
{
    long Count { get; }

    void Add(T item);

    void AddRange(IEnumerable<T> items);

    bool Remove(T item);
}

As you can see the implementation of above will offer the caller LINQ capabilities. I've added the IEquatable constraint for a better control over items' "uniqueness", however, it's a minor detail for now.

Following is the implementation:

public class OrderedSet<T> : IOrderedSet<T> where T : IEquatable<T>
{
    private readonly HashSet<T> _lookup = new HashSet<T>();
    private readonly LinkedList<T> _elements = new LinkedList<T>();

    public long Count => _lookup.Count;

    public OrderedSet(IEnumerable<T> collection = null)
    {
        if (collection != null)
        {
            AddRange(collection);
        }
    }

    public void Add(T item)
    {
        if (_lookup.Contains(item)) return;

        _elements.AddLast(item);
        _lookup.Add(item);
    }

    public void AddRange(IEnumerable<T> items)
    {
        foreach(var item in items)
        {
            Add(item);
        }
    }

    public bool Remove(T item)
    {            
        if (_lookup.Contains(item))
        {
            _lookup.Remove(item);
            _elements.Remove(item);

            return true;
        }

        return false;
    }

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

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

The choice of the underlying collection depends on the use case which your contract should reflect. For instance if you need an item by an index than List is a better fit. However, LinkedList semantics makes more sense keeping the initial assumption around the contract in mind.

Here are some tests covering a few cases:

[TestFixture]
public class OrderedSetTests
{
    [Test]
    public void AddRange_InsertsItem()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };

        list.AddRange(items);

        Assert.AreEqual(7, list.Count);
        CollectionAssert.AreEqual(items, list);
    }

    [Test]
    public void AddRange_IgnoresDuplicateInput()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        var items2 = new List<int> { 1, 2, 3, 4, 5, 6, 7, 7, 6, 6, 3 };            

        list.AddRange(items2);

        CollectionAssert.AreEqual(items, list);
    }

    [Test]
    public void Remove_RemovesItemIfItemExists()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        list.AddRange(items);
        var removed = list.Remove(3);
        Assert.IsTrue(removed);
        removed = list.Remove(1);
        Assert.IsTrue(removed);

        Assert.AreEqual(5, list.Count);
        CollectionAssert.AreEqual(new[] { 2, 4, 5, 6, 7 }, list);
    }

    [Test]
    public void Remove_IgnoresItemIfItemDoesNotExist()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        list.AddRange(items);
        var removed = list.Remove(9);
        Assert.IsFalse(removed);
        removed = list.Remove(11);
        Assert.IsFalse(removed);

        Assert.AreEqual(7, list.Count);
        CollectionAssert.AreEqual(items, list);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.