5
\$\begingroup\$

This is not meant to solve any insane real world problems. I just want to make sure my Set logic is right and the code looks okay. It feels weird implementing it with a Dictionary of dummy values but it seems that's how most languages do it anyway. What do you think?

public class Set : IEnumerable
    {
        private readonly Dictionary<object, bool> _items;

        public Set()
        {
            _items = new Dictionary<object, bool>();
        }

        public void Add(object item)
        {
            if (!_items.ContainsKey(item))
            {
                _items.Add(item, true);
            }
        }

        public void Remove(object item)
        {
            if (_items.ContainsKey(item))
            {
                _items.Remove(item);
            }
        }

        public bool Contains(object item)
        {
            return _items.ContainsKey(item);
        }

        public int Count()
        {
            return _items.Keys.Count;
        }

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

        public void UnionWith(Set input)
        {
            foreach (var item in input.Cast<object>().Where(item => !_items.ContainsKey(item)))
            {
                _items.Add(item, true);
            }
        }

        public void IntersectWith(Set input)
        {
            var newSet = new Set();
            foreach (var item in _items.Keys.Where(input.Contains))
            {
                newSet.Add(item);
            }
            Clear();
            foreach (var item in newSet)
            {
                _items.Add(item, true);
            }
        }

        public void DifferenceWith(Set input)
        {
            var newSet = new Set();
            foreach (var item in _items.Keys.Where(item => !input.Contains(item)))
            {
                newSet.Add(item);
            }
            Clear();
            foreach (var item in newSet)
            {
                _items.Add(item, true);
            }
        }

        public bool IsSubsetOf(Set input)
        {
            return _items.Keys.All(input.Contains);
        }

        public IEnumerator GetEnumerator()
        {
            return _items.Keys.GetEnumerator();
        }
    }
\$\endgroup\$
  • \$\begingroup\$ You are aware that System.Collections.Generic.HashSet<T> contains exactly the same methods you have defined, except DifferenceWith() is called ExceptWith()? \$\endgroup\$ – Mattias Åslund Apr 20 '16 at 19:00
  • \$\begingroup\$ Yup! This was just to see if I could re-implement more or less the same thing as practice. \$\endgroup\$ – user103053 Apr 20 '16 at 19:10
  • 3
    \$\begingroup\$ Nothing wrong with trying to reinvent the wheel but it seems like cheating to create a HashSet based on a more advanced feature like Dictionary. \$\endgroup\$ – Rick Davin Apr 20 '16 at 19:47
  • \$\begingroup\$ referencesource.microsoft.com/#System.Core/System/Collections/… \$\endgroup\$ – Rick Davin Apr 20 '16 at 19:47
  • \$\begingroup\$ Heh, fair enough @RickDavin, I totally agree :) \$\endgroup\$ – user103053 Apr 29 '16 at 22:44
5
\$\begingroup\$

I'm going to assume that you already know about HashSet and ISet in the following review and are just missing the reinventing-the-wheel tag.

ICollection

You've got Add, Remove, Clear, Count, and Contains. If you add a CopyTo(T[] array, int arrayIndex) and bool IsReadOnly { get { return false; } } to your implementation then you can implement ICollection.

Why Dictionary?

Perhaps you'd be better suited with a HashSet<T> implementation? Correct me if I'm wrong but it doesn't appear you're actually using the boolean value of the dictionary, so you'd be better suited with a Hashset<T>.

Generics

You could create a generic implementation Set<T> fairly easily. And if you wanted to still allow your existing functionality then you'd use Set<object>.

Set Operations

Perhaps consider having your operator functions return the new set from their actions?

For example,

public Set UnionWith(Set input)
{
    var unionedSet = new Set(_items); // See suggestion below.
    foreach (var item in input.Where(x => _items.ContainsKey(item)))
    {
        unionedSet.Add(item, true);
    }

    return unionedSet;
}

Constructor

Adding the ability to give IEnumerable or ICollection of items in a constructor could be really helpful, especially if you have your set operations return new sets as suggested above.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Just trying to re-invent the wheel as practice, so you are correct :) Good notes about the Dictionary. I guess writing this, I was almost trying to pretend HashSet was not an option (or else I could just use that in the first place), so I went with a Dictionary that used dummy values. I guess you're right about the generic version. Set's (at least in mathematics), are not strictly the same type, they can be anything, so that's what I was going for there. I thought the same about the operations, I think I'll fool around with that. Thank you! \$\endgroup\$ – user103053 Apr 20 '16 at 19:12
  • \$\begingroup\$ @Scott I figured that was the case which is why I mentioned the Set<object> usage. Reduces the casting and increases performance as a result which is usually important for data-structures. \$\endgroup\$ – Shelby115 Apr 20 '16 at 19:22
  • 4
    \$\begingroup\$ @Scott As for reinventing the wheel, it might be a decent idea to just create a set data-structure that implements the ISet<T> interface. Then look into ways the ISet<T> interface is used and test or make use of it that way. \$\endgroup\$ – Shelby115 Apr 20 '16 at 19:24

Your Answer

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