C5 icon indicating copy to clipboard operation
C5 copied to clipboard
verified publisher icon sestoft

System.Collections.Generic `ISet<T>` and `IDictionary<T>` (Fixes #53)

Open NightOwl888 opened this issue 6 years ago • 10 comments

This PR addresses #53:

  • Implements SCG.ISet<T> on TreeSet<T>
  • Implements SCG.IDictionary<K, V> on DictionaryBase<K, V>

I also attempted to implement SCG.ISet<T> on HashSet<T>, but since it seems to be missing a way to get and delete items by index, I am not sure how to proceed. Here is the (non compiling) attempt, in case you want to try to complete it:

Redundant Behavior

Do note that the AddAll, ContainsAll RetainAll, and RemoveAll methods are now redundant with UnionWith, IsSupersetOf, IntersectWith, and ExceptWith, respectively.

Options

  1. Leave the redundant methods in place
  2. Break C5 backward compatibility, but follow .NET conventions by removing (or making internal) AddAll, ContainsAll RetainAll, and RemoveAll
  3. Preserve C5 backward compatibility, and hide UnionWith, IsSupersetOf, IntersectWith, and ExceptWith by using explicit interface declarations

Performance

Most of the ISet<T> methods were reverse engineered from SCG.HashSet<T>, but it may be possible to implement some of the methods at a lower level for better performance - I didn't look into it.

NightOwl888 avatar Dec 31 '19 20:12 NightOwl888

On 31 Dec 2019, at 21.22, Shad Storhaug <[email protected]mailto:[email protected]> wrote:

This PR addresses #53https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fsestoft%2FC5%2Fissues%2F53&data=02%7C01%7Csestoft%40itu.dk%7C1949ec5c619544d6d56708d78e2f2188%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637134205403253096&sdata=TLkMrgyvS8AjM4fUFtoYIhuoSEwgxNDzBqOejbjB%2Bu8%3D&reserved=0:

  • Implements SCG.ISet<T> on TreeSet<T>
  • Implements SCG.IDictionary<K, V> on DictionaryBase<K, V>

I also attempted to implement SCG.ISet<T> on HashSet<T>, but since it seems to be missing a way to get and delete items by index, I am not sure how to proceed.

You mean, using the indexer set[i] = … where i is an integer?

Having this indexer on ISet<T> is an abominable design mistake in the .Net library, and I think it should throw an exception on HashSet<T> and similar. What does it do on SCG.HashSet<T>?

Peter

Here is the (non compiling) attempt, in case you want to try to complete it:

Redundant Behavior

Do note that the AddAll, ContainsAll RetainAll, and RemoveAll methods are now redundant with UnionWith, IsSupersetOf, IntersectWith, and ExceptWith, respectively.

Options

  1. Leave the redundant methods in place
  2. Break C5 backward compatibility, but follow .NET conventions by removing (or making internal) AddAll, ContainsAll RetainAll, and RemoveAll
  3. Preserve C5 backward compatibility, and hide UnionWith, IsSupersetOf, IntersectWith, and ExceptWith by using explicit interface declarations

Performance

Most of the ISet<T> methods were reverse engineered from SCG.HashSet<T>, but it may be possible to implement some of the methods at a lower level for better performance - I didn't look into it.

You can view, comment on, or merge this pull request online at:

https://github.com/sestoft/C5/pull/93https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fsestoft%2FC5%2Fpull%2F93&data=02%7C01%7Csestoft%40itu.dk%7C1949ec5c619544d6d56708d78e2f2188%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637134205403263093&sdata=Vtj6HLcnNHE6jMbrXFCWcIoaPCaET5Ff8gdQOH52I%2Fs%3D&reserved=0

Commit Summary

  • Implemented SCG.IEqualityComparer<T> on C5.Tests.SC class
  • Added SCG.ISet<T> to TreeSet<T> (fixes #53)
  • Added SCG.IDictionary<K, V> to DictionaryBase<K, V> (#53)

File Changes

Patch Links:

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fsestoft%2FC5%2Fpull%2F93%3Femail_source%3Dnotifications%26email_token%3DAAFSQECR24RJ3KH2DAOAKW3Q3OSXRA5CNFSM4KBXZWF2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IDQZ6EA&data=02%7C01%7Csestoft%40itu.dk%7C1949ec5c619544d6d56708d78e2f2188%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637134205403443013&sdata=w1NdapeWHBCzcmHxmGdUqtfDVutdjQyaJdWsys9u9FI%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAAFSQEDQS4RKNDFVEWPADUDQ3OSXRANCNFSM4KBXZWFQ&data=02%7C01%7Csestoft%40itu.dk%7C1949ec5c619544d6d56708d78e2f2188%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637134205403453008&sdata=sRoOrEIQx0b5C9Mmh6VxauRY1ZoR860iDSoTqKBLOqo%3D&reserved=0.

sestoft avatar Jan 02 '20 06:01 sestoft

You mean, using the indexer set[i] = … where i is an integer?

Having this indexer on ISet<T> is an abominable design mistake in the .Net library, and I think it should throw an exception on HashSet<T> and similar. What does it do on SCG.HashSet<T>?

No, what I meant was that the SCG.HashSet<T> has an IndexOfInternal(TKey) method and a way to delete an item internally by index. Since TreeSet<T> has an external IndexOf(TKey) and RemoveAt(int) methods, it was easy to translate. However, the C5 HashSet<T> doesn't seem to expose this functionality, so it is not as straightforward to implement ISet<T>.

NightOwl888 avatar Jan 04 '20 15:01 NightOwl888

On 4 Jan 2020, at 16.55, Shad Storhaug <[email protected]mailto:[email protected]> wrote:

You mean, using the indexer set[i] = … where i is an integer?

Having this indexer on ISet is an abominable design mistake in the .Net library, and I think it should throw an exception on HashSet and similar. What does it do on SCG.HashSet?

No, what I meant was that the SCG.HashSet<T> has an IndexOfInternal(TKey) method and a way to delete an item internally by index.

Strange, I don’t see any (documentation of) such a method on either SCG.HashSet<T> or SCG.ISet<T>.

In any case I believe the best way to implement it is by a method that throws a suitable exception, with a message such as “Not implemented”.

Peter

sestoft avatar Jan 04 '20 20:01 sestoft

Strange, I don’t see any (documentation of) such a method on either SCG.HashSet<T> or SCG.ISet<T>.

You won't find any documentation, because as I mentioned, the method is intenal:

https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs#L1423

There is also an internal way to delete a slot by index after determining which indices need removal:

https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs#L1310

In any case I believe the best way to implement it is by a method that throws a suitable exception, with a message such as “Not implemented”.

Since this is the slow path that happens whenever the equality comparers don't match (which is probably 70-80% of the time), it would mean that all of the set operations would throw an exception 70-80% of the time.

Of course, if there is no way to get the index of an item or delete an item by index, this could be implemented by wrapping each item in a structure with a bit to track the items, but that would be a lot slower than using a BitArray to track the indicies.

I was hoping you had a more clever lower-level way to complete this than what Microsoft did.

But whatever the case, to me it makes more sense to provide the basic tests and a direction to go than to provide a broken implementation or one that is unreasonably slow. Since it is not part of the PR, you can either use your knowledge of the inner workings of C5's HashSet to complete it the right way or completely leave it out.

NightOwl888 avatar Jan 05 '20 03:01 NightOwl888

Sorry, I failed to notice this about the method being internal. This makes more sense.

Peter

On 5 Jan 2020, at 04.59, Shad Storhaug <[email protected]mailto:[email protected]> wrote:

Strange, I don’t see any (documentation of) such a method on either SCG.HashSet or SCG.ISet.

You won't find any documentation, because as I mentioned, the method is intenal:

https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs#L1423https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmicrosoft%2Freferencesource%2Fblob%2Fmaster%2FSystem.Core%2FSystem%2FCollections%2FGeneric%2FHashSet.cs%23L1423&data=02%7C01%7Csestoft%40itu.dk%7C0fef879490874276411d08d79193aa75%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637137935734167066&sdata=vdPRJLYZmhoiTi4SfoaTvaY9gsZNnnPazVJKli%2BkESk%3D&reserved=0

There is also an internal way to delete a slot by index after determining which indices need removal:

https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs#L1310https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmicrosoft%2Freferencesource%2Fblob%2Fmaster%2FSystem.Core%2FSystem%2FCollections%2FGeneric%2FHashSet.cs%23L1310&data=02%7C01%7Csestoft%40itu.dk%7C0fef879490874276411d08d79193aa75%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637137935734167066&sdata=FEkgzJKZmn14yRGB3ORKFrc5ddxzTXsWJg75tYFo7Y4%3D&reserved=0

In any case I believe the best way to implement it is by a method that throws a suitable exception, with a message such as “Not implemented”.

Since this is the slow path that happens whenever the equality comparers don't match (which is probably 70-80% of the time), it would mean that all of the set operations would throw an exception 70-80% of the time.

Of course, if there is no way to get the index of an item or delete an item by index, this could be implemented by wrapping each item in a structure with a bit to track the items, but that would be a lot slower than using a BitArray to track the indicies.

I was hoping you had a more clever lower-level way to complete this than what Microsoft did.

But whatever the case, to me it makes more sense to provide the basic tests and a direction to go than to provide a broken implementation or one that is unreasonably slow. Since it is not part of the PR, you can either use your knowledge of the inner workings of C5's HashSet to complete it the right way or completely leave it out.

— You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fsestoft%2FC5%2Fpull%2F93%3Femail_source%3Dnotifications%26email_token%3DAAFSQEF2H23VVVKEXAA44ATQ4FLKBA5CNFSM4KBXZWF2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEIDIFJA%23issuecomment-570852004&data=02%7C01%7Csestoft%40itu.dk%7C0fef879490874276411d08d79193aa75%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637137935734172058&sdata=J1mpccU63mYcO2AHMbnkjOR60X%2BP1NEEjUL%2BaIyES%2FY%3D&reserved=0, or unsubscribehttps://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAAFSQEGWBQTAUPW4UQJH7S3Q4FLKBANCNFSM4KBXZWFQ&data=02%7C01%7Csestoft%40itu.dk%7C0fef879490874276411d08d79193aa75%7Cbea229b67a084086b44c71f57f716bdb%7C1%7C0%7C637137935734177049&sdata=fqUhetkY9dk9Ru0JRNeq71WmIwIYG1cKp8AD%2FzxAt8M%3D&reserved=0.

sestoft avatar Jan 05 '20 11:01 sestoft

AddAll, ContainsAll, RetainAll, and RemoveAll come from ICollection or IExtensible. They should maybe be called *Range to match the naming in .NET. My thinking would be to rename *All to *Range and then go with option 3: hide by using explicit interface declarations. This is in line with how SCG.LinkedList<T> implements SCG.ICollection<T>. WRT HashSet<T> I think we should provide a crude implementation of ISet<T> to allow it to be used and possibly not the the perf is not optimal for ISet<T> operations.

ondfisk avatar Jan 05 '20 11:01 ondfisk

AddAll, ContainsAll, RetainAll, and RemoveAll come from ICollection or IExtensible. They should maybe be called *Range to match the naming in .NET. My thinking would be to rename *All to *Range and then go with option 3: hide by using explicit interface declarations. This is in line with how SCG.LinkedList<T> implements SCG.ICollection<T>. WRT HashSet<T> I think we should provide a crude implementation of ISet<T> to allow it to be used and possibly not the the perf is not optimal for ISet<T> operations.

Do you mean hide all of the ISet<T> set operations, or just the redundant ones?

It would be useful to provide the rest of the set operations (IsSubsetOf, IsProperSubsetOf, IsProperSupersetOf, and Overlaps) as top-level methods. However, it feels like a crime to provide IsSubsetOf, IsProperSubsetOf, IsProperSupersetOf and name the remaining one ContainsRange instead of IsSupersetOf.

Either way it feels like Overlaps should definitely be on the top level, but IsSubsetOf, IsProperSubsetOf, IsProperSupersetOf and IsSupersetOf should be all public or all hidden.

NightOwl888 avatar Jan 05 '20 14:01 NightOwl888

No I mean hide the IExtensible methods so HashSet and TreeSet looks and behaves like SCG.ISet. That’s a breaking change but I think it’ll make more sense than hiding the ISet methods. We just need to ensure the C5 event stuff is implemented also.

ondfisk avatar Jan 05 '20 15:01 ondfisk

@NightOwl888: are you working on the changes mentioned above?

ondfisk avatar Jan 14 '20 22:01 ondfisk

I haven't had a chance to get to it yet, and it might be awhile until I have the time. No objections if you want to jump ahead and do it yourself.

NightOwl888 avatar Jan 15 '20 10:01 NightOwl888