4
\$\begingroup\$

The following data structure is meant for manipulating algebraic/mathematical sets.

I want Set<T> to be compatible and interchangeable with any similar data structure available in .NET. I didn't use HashSet<T> because I don't like the fact that HashSet<T> is unordered.

Kindly review it for design and efficiency.

What is your comment on the inheritance hierarchy? Do you think ISet<T> and Set<T> inherited or implemented proper interfaces?


Source code:

public interface ISet<T>:  ICloneable, IEnumerable<T>, IList<T>
{
    IEnumerable<T> Union(IEnumerable<T> set2);
    IEnumerable<T> Difference(IEnumerable<T> set2);
    IEnumerable<T> Intersection(IEnumerable<T> set2);
    IEnumerable<T> Complement(IEnumerable<T> universalSet);
    bool Disjoint(IEnumerable<T> set2);
    void AddRange(IEnumerable<T> set);
    IEnumerable<T> ToEnumerable();
}

public class Set<T> : ISet<T>, ICloneable, IEnumerable<T>, IList<T>, IList, ICollection, IEnumerable
{
    private List<T> m_ListContainer = null;

    public Set()
    {
        m_ListContainer = new List<T>();
    }

    public Set(IEnumerable<T> collection)
    {
        m_ListContainer = new List<T>(collection);
    }

    #region IList<T> implementations
    public T this[int index]
    {
        get
        {
            return m_ListContainer[index];
        }
        set
        {
            m_ListContainer[index] = value;
        }
    }
    object IList.this[int index]
    {
        get
        {
            return m_ListContainer[index];
        }
        set
        {
            m_ListContainer[index] = (T)value;
        }
    }
    public int Count
    {
        get
        {
            return m_ListContainer.Count;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public void Add(T item)
    {
        m_ListContainer.Add(item);
    }

    public void Clear()
    {
        m_ListContainer.Clear();
    }

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

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

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

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

    public void Insert(int index, T item)
    {
        m_ListContainer.Insert(index, item);
    }

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

    public void RemoveAt(int index)
    {
        m_ListContainer.RemoveAt(index);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return m_ListContainer.GetEnumerator();
    }
    #endregion

    /// <summary>
    /// complement the current list on the basis of universalset
    /// </summary>
    /// <param name="universalSet"></param>
    public IEnumerable<T> Complement(IEnumerable<T> universalSet)
    {
        // create a copy of the universalSet
        List<T> list = new List<T>(universalSet);

        foreach (T item in m_ListContainer)
        {
            list.Remove(item);
        }

        return list;
    }

    /// <summary>
    /// return [this - set2]
    /// </summary>
    /// <param name="set2"></param>
    /// <returns></returns>
    public IEnumerable<T> Difference(IEnumerable<T> set2)
    {
        List<T> newSet = new List<T>(m_ListContainer.ToArray());

        foreach (T item in m_ListContainer)
        {
            if (((ISet<T>) set2).Contains(item))
            {
                newSet.Remove(item);
            }
        }

        return newSet;
    }

    /// <summary>
    /// Two sets A and B are mutually exclusive or disjoint if they 
    /// do not have any shared elements; i.e., their intersection is 
    /// the empty set, A∩B=∅.
    /// </summary>
    /// <param name="set1"></param>
    /// <param name="set2"></param>
    /// <returns></returns>
    public bool Disjoint(IEnumerable<T> set2)
    {
        foreach (T item in m_ListContainer)
        {
            if (((ISet<T>)set2).Contains(item))
            {
                return false; 
            }
        }

        return true;
    }
    /// <summary>
    /// The intersection of two sets A and B, denoted by A∩B, consists of all elements 
    /// that are both in A and B. For example, {1,2}∩{2,3}={2}.
    /// </summary>
    /// <param name="set1"></param>
    /// <param name="set2"></param>
    /// <returns></returns>
    public IEnumerable<T> Intersection(IEnumerable<T> set2)
    {
        List<T> newSet = new List<T>(m_ListContainer.ToArray());

        foreach (T item in m_ListContainer)
        {
            if(!((ISet<T>) set2).Contains(item))
            {
                newSet.Remove(item);
            }
        }

        return newSet;
    }
    /// <summary>
    /// return Union [this, set2]
    /// </summary>
    /// <param name="set2"></param>
    /// <returns></returns>
    public IEnumerable<T> Union(IEnumerable<T> set2)
    {
        IEnumerable<T> unionList = m_ListContainer.ToArray();//clone the currect data

        List<T> list = new List<T>(unionList);

        list.AddRange(set2);

        return list.ToArray();
    }

    /// <summary>
    /// Implementing IClonable.
    /// </summary>
    /// <returns></returns>
    public object Clone()
    {
        T [] objects = new T[m_ListContainer.Count];

        int i = 0;
        foreach (T item in m_ListContainer)
        {
            objects[i] = item;
            i++;
        }

        return objects;
    }

    public void AddRange(IEnumerable<T> set)
    {
        m_ListContainer.AddRange(set);
    }

    public IEnumerable<T> ToEnumerable()
    {
        return m_ListContainer.ToArray();
    }

    public void Show()
    {
        foreach (var item in m_ListContainer)
        {
            Console.Write(item + ", ");
        }

        Console.ReadLine();
    }

    public int Add(object value)
    {
        this.Add((T)value);

        return m_ListContainer.Count - 1;
    }

    public bool Contains(object value)
    {
        T item = (T)value;

        return this.Contains(item);
    }

    public int IndexOf(object value)
    {
        T item = (T)value;

        return this.IndexOf(item);
    }

    public void Insert(int index, object value)
    {
        T item = (T)value;

        this.Insert(index, item);
    }

    public void Remove(object value)
    {
        T item = (T)value;

        this.Remove(item);
    }

    public void CopyTo(Array array, int index)
    {
        T[] arr = (T[])array.Clone();

        this.CopyTo(arr, index);
    }

    public bool IsFixedSize
    {
        get
        {
            return false;
        }
    }

    private Object _syncRoot;
    public object SyncRoot
    {
        get
        {
            if (_syncRoot == null)
            {
                System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
            }
            return _syncRoot;
        }
    }

    public bool IsSynchronized
    {
        get
        {
            return true;
        }
    }
}

Note: Each element must be unique. I missed that in my implementation.

Edit: replace Add() with the following to add the missing "unique" functionality:

public void Add(T item)
{
    if(!m_ListContainer.Contains(item))
    {
        m_ListContainer.Add(item);
    }
}
\$\endgroup\$
  • \$\begingroup\$ I am confused. Do you want to allow duplicate elements in your collection? Use a List<T>. If you don't want duplicate elements: firstly, your collection doesn't do that; but secondly, why not use a HashSet<T>? \$\endgroup\$ – Zev Spitz Jun 21 at 10:00
  • \$\begingroup\$ But please clarify -- is this collection allowed to have unique (either by value equality, or at least by reference equality) values, or not? \$\endgroup\$ – Zev Spitz Jun 21 at 12:55
  • \$\begingroup\$ I missed that in my implementation I don't know if it's possible to review for efficiency without an implementation. \$\endgroup\$ – Zev Spitz Jun 21 at 21:36
  • \$\begingroup\$ @ZevSpitz, done. check public void Add(T item). \$\endgroup\$ – user366312 Jun 21 at 22:43
  • 2
    \$\begingroup\$ Please don't change your code after the question has been answered. The code needs to stay the same for all readers and reviewers after an answer has been posted. See What should I do after someone answers. \$\endgroup\$ – pacmaninbw Jun 21 at 22:51
1
\$\begingroup\$

The data structure

List<T> is great most of the time. What it is not great at, is this:

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

Which unfortunately is an important operation for a set.

There are different ways to set up a set that maintains insertion order that have different trade offs. For example:

  • A hash set (for contains queries, and to avoid inserting duplicates) plus a List<T> (just to remember the insertion order). Removing an item still requires searching in/removing from the list, so remove stays linear time. Adding items and indexing are constant time. Iterating over the data in insertion order is fast. IndexOf stays slow.
  • The LinkedHashSet: it's based on a hash set, but every item also acts as node in a doubly-linked list which remembers the insertion order. Using a doubly-linked list here enables constant time removal of arbitary items. However, indexing takes linear time this way, and maybe shouldn't even be offered. An iterator that yields the items in insertion order can certainly be offered. IndexOf stays slow.
  • A Dictionary<T, int>, where the int indicates the current index of the corresponding key. Good for Add and Contains and even IndexOf, but Remove has to decrement the indexes of all the items that come after the removed item, indexing is slow, and even iterating in the proper order is slow.
  • A Dictionary<T, int> plus an other Dictionary<int, T> (or list), based on the previous data structure, but also with a "reverse dictionary". Add, Contains and IndexOf stay fast, Remove stays slow (gets slower practically, now there are two dictionaries to fix up), but now indexing and iterating in order become efficient (at a significant cost in size).

Set operations, algorithm

Starting off with a copy and then conditionally removing from it works, but since the items are being removed from a List<T>, that's a O(n m) algorithm (for sets of sizes n and m). One there is a set implementation that has a constant time Contains, the quadratic time is avoidable by switching the logic around to: start with an empty list/set, add an item if it should be in the result.

Set operations, interface

The set operations take an IEnumerable<T> and then sometimes cast it with ((ISet<T>)set2). That's not nice, you can pass something to those methods that isn't an ISet<T>, reasonably expect it to work, and then it fails at runtime.

There are two good solutions, either make it work without the cast, or change the type of parameter so the cast is unnecessary. For example Disjoint could easily work by iterating over the IEnumerable<T> and calling Contains on this, then it doesn't matter whether the second set is an ISet<T> or maybe just a T[].

Returning IEnumerable<T> is strange because it limits how the operations can be "chained". For example that makes it impossible to do a.Complement(b).Union(b.Complement(a)), which would be a way to implement the symmetric difference, which the ISet<T> interface does not offer.

Redundant ToArray

new List<T>(m_ListContainer.ToArray())

There is no need for ToArray, a copy of the list is made either way but that temporary array does not need to exist.

public IEnumerable<T> Union(IEnumerable<T> set2)
{
    IEnumerable<T> unionList = m_ListContainer.ToArray();
    List<T> list = new List<T>(unionList);
    list.AddRange(set2);
    return list.ToArray();
}

Neither of these ToArray calls are necessary. new List<T>(m_ListContainer) would do the trick, and the resulting list itself can be returned.

Interestingly, Clone() could have been implemented equivalently with ToArray, though it is unexpected that Clone returns something so different than the cloned-from object.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Wrap ISet<T> in a namespace to avoid conflicts

I presume you're already doing this, but there already exists an incompatible ISet<T>; you should wrap your interface with a namespace to avoid a collision.

Replace your internal List<T> with a HashSet<T>

You noted in the comments that elements should be unique; a trivial way to do this would be for your internal container to be a HashSet<T> instead of List<T>, which would enforce uniqueness.

But this causes another issue.

Using a HashSet<T> renders the indexers meaningless

With a HashSet<T>, there is no guaranteed order, and you cannot set an item at a particular index; I believe this is intentional, as the order of elements within the HashSet<T> is arbitrary. In that case, the getter index is also meaningless.

A SortedIndex<T> maintains the sort order even while elements are added and removed, but it still doesn't make sense to place an item at a particular index, because the SortedSet<T> will in any case reorder as needed; and thus also not to read an element from a particular index.

Consider removing overloads that take object only to cast to T and pass to other overloads

If the object is of T, the T-accepting overload will be called and succeed.

If the object is not of T, an exception will be thrown on the cast. I feel this is out of the responsibility of the collection class.

And if the only point of these overloads is to implement the non-generic IList and ICollection, perhaps you don't need to implement these interfaces. I don't think IList and ICollection add much over IList<object> and ICollection<object>.

Implement Show as an extension method on IEnumerable

Better yet, implement a Joined extension method like this. That way you have an extension method that you could use for any IEnumerable<T>, and use the resultant produced string in other contexts as well.

IClonable is deprecated

There are a number of issues with implementing IClonable<T>:

  1. It's not clear whether a deep or shallow copy is being made
  2. What is supposed to happen if the base class implements IClonable<T>? How does that relate to the derived class? link

From the docs:

The ICloneable interface simply requires that your implementation of the Clone() method return a copy of the current object instance. It does not specify whether the cloning operation performs a deep copy, a shallow copy, or something in between. Nor does it require all property values of the original instance to be copied to the new instance. For example, the Clone() method performs a shallow copy of all properties except the IsReadOnly property; it always sets this property value to false in the cloned object. Because callers of Clone() cannot depend on the method performing a predictable cloning operation, we recommend that ICloneable not be implemented in public APIs.

Use method-bodied members

This will make your class definition much easier to read and parse. Readonly properties can be written like this:

 public int Count => m_ListContainer.Count;

while your indexers (and read/write properties) can be written like this:

public T this[int index] {
    get => m_ListContainer[index];
    set => m_ListContainer[index] = value;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What is your comment on the inheritance hierarchy? Do you think ISet<T> and Set<T> inherited or implemented proper interfaces? \$\endgroup\$ – user366312 Jun 21 at 17:43
  • \$\begingroup\$ Secondly, Why must I use HashSet<T> when I can just add a filter in the Add() method to check to see if the element is already there? Or, why not use Dictionary<TKey, TVal>? \$\endgroup\$ – user366312 Jun 21 at 17:44
  • \$\begingroup\$ @user366312 RE: filter in Add -- Let's turn the question around. What do you think HashSet<T>.Add does, if not precisely that? So what do you gain by reinventing the wheel? And Dictionary<TKey, TVal> is indeed unique in its' keys; presumably you would use the dictionary keys as the elements of your collection; but how is that any better than HashSet<T>? \$\endgroup\$ – Zev Spitz Jun 21 at 17:50
  • \$\begingroup\$ @user366312 RE: inheritance hierarchy -- You may have a valid use case for implementing all these interfaces, but I wouldn't implement them until I had a specific use case for them. \$\endgroup\$ – Zev Spitz Jun 21 at 17:52
  • \$\begingroup\$ You may have a valid use case for implementing all these interfaces --- I want Set to be compatible and interchangeable with any similar data structure available in .NET. \$\endgroup\$ – user366312 Jun 21 at 17:54

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.