Databases
StackOverflow2013
Postsdbo
POImplementing a content-hashable HashSet in C# (like python's `frozenset`)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImplementing a content-hashable HashSet in C# (like python's `frozenset`)
    primarykey
    data
    text
    <p><strong>Brief summary</strong></p> <p>I want to build a set of sets of items in C#. The inner sets of items have a <code>GetHashCode</code> and <code>Equals</code> method defined by their <em>contents</em>. In mathematical notation:</p> <pre><code>x = { } x.Add( { A, B, C } ) x.Add( { A, D } ) x.Add( { B, C, A } ) now x should be{ { A, B, C }, { A, D } } </code></pre> <p>In python, this could be accomplished with <code>frozenset</code>:</p> <pre><code>x = set() x.add( frozenset(['A','B','C']) ) x.add( frozenset(['A','D']) ) x.add( frozenset(['B','C','A']) ) </code></pre> <p><strong>/BriefSummary</strong> <br><br></p> <p>I would like to have a hashable HashSet in C#. This would allow me to do:</p> <pre><code>HashSet&lt;ContentHashableHashSet&lt;int&gt;&gt; setOfSets; </code></pre> <p>Although there are more sophisticated ways to accomplish this, This can be trivially achieved in practice (although not in the most efficient manner) by adding overriding <code>ContentHashableHashSet.ToString()</code> (outputing the strings of the elements contained in sorted order) and then using then using <code>ContentHashableHashSet.ToString().GetHashCode()</code> as the hash code.</p> <p>However, if an object is modified after placement in <code>setOfSets</code>, it could result in multiple copies:</p> <pre><code>var setA = new ContentHashableHashSet&lt;int&gt;(); setA.Add(1); setA.Add(2); var setB = new ContentHashableHashSet&lt;int&gt;(); setB.Add(1); setOfSets.Add(setA); setOfSets.Add(setB); setB.Add(2); // now there are duplicate members! </code></pre> <p>As far as I can see, I have two options: I can derive <code>ContentHashableHashSet</code> from <code>HashSet</code>, but then I will need to make it so that all modifiers throw an exception. Missing one modifier could cause an insidious bug.</p> <p>Alternatively, I can use encapsulation and class <code>ContentHashableHashSet</code> can contain a <code>readonly HashSet</code>. But then I would need to reimplement all set methods (except modifiers) so that the <code>ContentHashableHashSet</code> can behave like a <code>HashSet</code>. As far as I know, extensions would not apply.</p> <p>Lastly, I could encapsulate as above and then all set-like functionality will occur by returning the const (or readonly?) HashSet member.</p> <p>In hindsight, this is reminiscent of python's <code>frozenset</code>. Does anyone know of a well-designed way to implement this in C#?</p> <p>If I was able to lose <code>ISet</code> functionality, then I would simply create a sorted <code>ImmutableList</code>, but then I would lose functionality like fast union, fast intersection, and sub-linear ( roughly O(log(n)) ) set membership with <code>Contains</code>.</p> <p><strong>EDIT:</strong> The base class HashSet does <em>not</em> have virtual <code>Add</code> and <code>Remove</code> methods, so overriding them will work within the derived class, but will <em>not</em> work if you perform <code>HashSet&lt;int&gt; set = new ContentHashableHashSet&lt;int&gt;();</code>. Casting to the base class will allow editing.</p> <p><strong>EDIT 2:</strong> Thanks to @xanatos for recommending a simple <code>GetHashCode</code> implementation: </p> <blockquote> <p>The easiest way to calculate the GetHashCode is to simply xor (^) all the gethashcodes of the elements. The xor operator is commutative, so the ordering is irrelevant. For the comparison you can use the SetEquals</p> </blockquote> <p><strong>EDIT 3:</strong> Someone recently shared information about <a href="http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx" rel="nofollow">ImmutableHashSet</a>, but because this class is sealed, it is not possible to derive from it and override <code>GetHashCode</code>.</p> <p>I was also told that <code>HashSet</code> takes an <code>IEqualityComparer</code> as an argument, and so this can be used to provide an immutable, content-hashable set without deriving from ImmutableHashSet; however, this is not a very object oriented solution: every time I want to use a <code>ContentHashableHashSet</code>, I will need to pass the same (non-trivial) argument. As I'm sure you know, this can really wreak havoc with your coding zen, and where I would be flying along in python with <code>myDictionary[ frozenset(mySet) ] = myValue</code>, I will be stuck doing the same thing <a href="http://en.wikipedia.org/wiki/Sisyphus" rel="nofollow">again and again and again</a>. </p> <p>Thanks for any help you can provide. I have a temporary workaround (whose problems are mentioned in <strong>EDIT 1</strong> above), but I'd mostly like to learn about the best way to design something like this.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser
    1. USuser
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COWhat I did in such situation was to create `IReadOnlySet<T> : IReadOnlyCollection<T>` interface, where I would re-declare non-mutating set methods, as well as changing the contract on some of the methods to not modify the set, but return a new one (e.g. `IReadOnlySet<T> SymmetricExceptWith(IEnumerable<T> other); `). It's not exactly 'backwards-compatible' and there's a lot of delegation, but the interface is simple.
      singulars
      1. POImplementing a content-hashable HashSet in C# (like python's `frozenset`)
      1. USPatryk Ćwiek
    2. COWow. Probably worth re-checking your architecture to see if you can find a simpler and cleaner way to do whatever you need to do. However in this case I am not even sure what the question is exactly. Are you not just struggling with hash key generation?
      singulars
      1. POImplementing a content-hashable HashSet in C# (like python's `frozenset`)
      1. USdr.mo
    3. CO@dr.mo It isn't `GetHashCode` that's the problem (that's easy-- use `ToString().GetHashCode()`), it's the fact that the set of items can change after insertion into the set of sets of items, and this change may result in duplicate sets of items.
      singulars
      1. POImplementing a content-hashable HashSet in C# (like python's `frozenset`)
      1. USuser
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload