Peter Golde's Blog

Hidden powers of OrderedSet/OrderedBag

pgolde — Tue, 03 Jan 2006 21:16:00 GMT

In a comment, Stuart Ballard wrote:

The general idea of a class that is usable both as a List and a Dictionary, maintaining an order and providing efficient access by both index and key, is a very useful one.

Althought it's not immediately obvious, the OrderedSet and OrderedBag collections can be used to do just that with just a small amount of work. An OrderedSet can be efficiently indexed just by using the indexer provided on the class. In addition, it can be used as an arbitrary (read-only) IList by simply calling the AsList method.

Now, it is true that an OrderedSet isn't really a dictionary. But, it can be used effectively as a dictionary by instantiating an OrderedSet>, and passing a Comparison delegate that compares keys only.

In retrospect, this could perhaps have been made even simpler by having an AsList method on OrderedDictionary that returned an IList>. I considered similar ideas but decided that they seemed too complicated and obscure. Maybe I was wrong.

Power Collections 1.0 for .NET 2.0 RTM

pgolde — Sat, 12 Nov 2005 00:30:00 GMT

I've posted an updated Power Collections 1.0 that has been recompiled (with slight source changes to address some base class library changes) for the released version of .NET 2.0. No new functionality has been added, nor has the documentation changed.

As usual, the download is available here.

Power Collections 1.0 released

pgolde — Tue, 21 Jun 2005 05:49:00 GMT

The release of Power Collections 1.0 is complete. There aren't many changes since the beta release a few weeks ago; mainly some updates to the tests and OrderedDictionary had a method renamed (Merge to AddMany).

As soon as I have more information and thoughts about what happens next with Power Collections, I'll post some more information. But this is where development will stop at least for a little while. I'll still be around to answer questions in the forums and so forth.

The download is available here, and the documentation can be browsed here. Enjoy!

Other minor changes in the last drop

pgolde — Wed, 08 Jun 2005 22:21:00 GMT

A few other minor changes were in the latest drop that I didn't cover in my other posts:

1. Added a CLSCompliant attribute to the assembly.

2. The Pair struct added explicit conversions to and from KeyValuePair.

3. Set, Bag, OrderedSet, and OrderedBag added an IsDisjointFrom method.

4. Deque added a Clone method.

5. Deque and BigList added a CloneContents method.

Nomenclature and new methods in Algorithms

pgolde — Wed, 08 Jun 2005 22:18:00 GMT

As I looked over all the methods in Algorithms, it seemed like I needed to be more disciplined in naming conventions so that the operations of methods would be more consistent and easy to understand. So I developed a nomenclature that I could attempt to use consistently across all the methods in Algorithms. Here's what I came up with:

First: Indicates that a method returns the first item of some subset of items.

Last: Indicates that a method returns the last item of some subset of items.

Index (plural: Indices): Indicates that a method returns the index in a list.

At: Indicates that a method operates at a particular index in a list.

Is: Indicates that a method returns a boolean value.

Try: Indicates that a method returns a boolean value, indicating if the operation was successful or not. Uses an out parameter to return the value upon success.

Where: Indicates that a method takes a Predicate to restrict an operation to items where the predicate is true.

Many: Indicates that a method operates on a (non-consecutive) collection of items passed as a parameter.

Range: Indicates that method operates on a consecutive range of items in the collection.

Set: Indicates that method operates on the item without regard to order.

All: Used SPARINGLY, since it is confusing what it refers to. When used, indicates all of the items currently in the collection.

There are a number of renamings in Algorithms in the latest drop to conform to this nomenclature.

Also, I added two new methods that return IEqualityComparer instances: GetCollectionEqualityComparer and GetSetEqualityComparer. These methods create IEqualityComparer instances that compare entire collections as single items. These are useful, for example, if you want a collection of items to be a key for a Dictionary. GetCollectionEqualityComparer compares collections with order to items being significant, GetSetEqualityComparer compares collections as insignificant to order.

Unsealing of collection classes

pgolde — Wed, 08 Jun 2005 22:07:00 GMT

In prior releases, all the collection classes were sealed, which prevent people from deriving from them. Although I still don't think that there are many good scenarios where it make sense to derive from Set, Bag, BigList, etc., I have unsealed them in the latest drop.

This allows people to derive from them and add new methods; perhaps some specific new algorithm or some such.

However, most methods on these classes remain non-virtual. Why? Basically, because the implementation of these methods is very specific, and it is not possible to override them and change functionality without breaking the core class. Even if the overriding method calls the base, you could find that functionalitybreaks in subtle ways.

For example, suppose you could override Set.Remove, so that you could do something special whenever an item is removed from a set. This override will be called when people remove items from a Set with the Remove method, but there are lots of other methods that remove items from a Set. Some of these ways (like RemoveMany) internally call Remove, others (like IntersectionWith or Clear) do not. You can't predict, and it might even change in future versions of the library.

If you need a specialized kind of collection, the “right” way to do it is to derive from CollectionBase, ListBase, or DictionaryBase, and override the appropriate methods. This can then delegate to a private instance of some collection as needed.

More methods in CollectionBase, ListBase, etc

pgolde — Wed, 08 Jun 2005 21:56:00 GMT

I did a review on CollectionBase, ListBase, DictionaryBase (and their read-only equivalents), and realized that a lot of the delegate-based methods that were added to List<T> really made sense on these classes. If you used these classes as bases to create your own collections, you now get a bunch more functionality “for free”.

I decided that it was best to use the exact same names that Microsoft used, even though I don't think that are the best possible names. This should easy the learning curve and make things more consistent for the user.

Doing this also allow removal of a lot of equivalent methods from the specific collection classes like Set, Bag, etc.

The new methods added are:

CollectionBase.AsReadOnly
CollectionBase.Exists
CollectionBase.TrueForAll
CollectionBase.FindAll
CollectionBase.RemoveAll
CollectionBase.ForEach
CollectionBase.ConvertAll
CollectionBase.CountWhere
DictionaryBase.AsReadOnly
ListBase.AsReadOnly
ListBase.CopyTo
ListBase.FindFirst
ListBase.FindLast
ListBase.TryFindFirst
ListBase.TryFindLast
ListBase.FindAll
ListBase.FindIndex
ListBase.FindLastIndex
ListBase.IndexOf
ListBase.LastIndexOf

(and read-only equivalents, where applicable).

Indexer on OrderedSet and OrderedBag

pgolde — Mon, 06 Jun 2005 19:13:00 GMT

One interesting feature that was added in the latest drop is the support for accessing OrderedSet and OrderedBag by integer index. Recall that OrderedSet and OrderedBag maintain all the items in order, where order is defined by an IComparer or Comparison. When you could always iterate over the items in order, you can now get at any item by its integer index in the order. This operation takes time O(log N). You can also go this other way; you get do an IndexOf operation on an item to get its index in O(log N) time also.

The implementation of this is primary in the RedBlackTree class, and it's a little bit interesting and tricky. Each node in the tree stores the number of items in that sub-tree. As items as added or deleted, the counts are updated. One annoying part has to do with adds and deletes that don't complete as expected. For example, consider that operation of deleting an item. As we go down the tree searching for the item to delete, we update the counts in the nodes to reflect the deletion. However, if the item to delete is not found, we have to restore those counts back to where they were. This means that we have to keep a record of what counts were updated, so that they can be restored.

Beta of PowerCollections 1.0 now available

pgolde — Fri, 03 Jun 2005 23:05:00 GMT

I've uploaded a new drop of Power Collections. This is quite close to what will be released as the 1.0 release of Power Collections, there are just a few more things to do (mainly making the classes serializable). You can consider this the “Beta“ release of PowerCollection 1.0. Any feedback that can be provided will be very useful to getting the final 1.0 release as good as possible. I'm aiming toward the 1.0 release at the end of June. I'm short of time right this minute; I'll post more details soon on the changes since the last drop.

The download is available here, and the documentation can be browsed here.

IList, ICollection and IsReadOnly

pgolde — Thu, 12 May 2005 19:18:00 GMT

An interesting discussion has been occurring in comments, and in this bug report, about the problems with IList and arrays that I discussed earlier.

I think the discussion has correctly focussed in on a key problem: that the IsReadOnly property on ICollection<T> is too general to take into account the different kinds of changes that can be made to a list. Having identified this problem, however, does not necessarily mean that we need to proliferate into a huge number of different “Is/Can” properties. Instead, we should look at the implementations that actually make sense and put in enough properties to handle the realistic cases.

In the case of ICollection<T> and IList<T>, my feeling is that two properties would handle all the interesting cases easily:

1. ICollection<T> should change IsReadOnly to CanAddRemove. If true, this would indicate that items can be added to or removed from the collection using the “Add”, “Remove”, and “Clear” methods on ICollection. If false, this would indicate that Add, Remove, and Clear should not be called (however, other methods of changing the collection might work).

2. IList<T> should add CanChangeValues to indicate that values in the list can be changed using the indexer. If true, the set accessor on the indexer can be used to change the value at a particular index. If false, the set accessor on the indexer should not be used. If both CanAddRemove and CanChangeValues are true, then Insert and RemoveAt can be used to insert or remove values at a particular place.

These two properties allow all of the interesting cases that I can think of:

read/write List<T>: CanAddRemove=true, CanChangeValues=true

read/write array: CannAddRemove=false, CanChangeValues=true

read-only List<T>: CanAddRemove=false, CanChangeValues=false

OrderedSet<T>: CanAddRemove=true, CanChangeValues=false (This is the case where items can be added to the collection, but the order in the collection is fixed by the values. Thus, you cannot change the value at a particular index, or insert at a particular index, but you can add or remove values at an unspecified location).

[For similar reasons, IDictionary<K,V> should include a CanChangeValues that indicates whether the value associated with a key can be changed. This allows the case where a dictionary as a fixed set of keys, but the values associated with the keys can be changed.]

Beta 2 drop is now available

pgolde — Mon, 09 May 2005 20:49:00 GMT

I've finally completed a drop of Power Collections for Visual Studio 2005 Beta 2. The download is available here, and the documentation can be browsed here. Sorry this took so long to get posted; I was delayed first by the IList problem with arrays, then by some technical problems with the Wintellect FTP server.

This drop has all the changes needed to work with Beta 2. All of the algorithms that want to change IList<T> contents have been updated to special case arrays to still work, either internally or through overloads.

Additionally, the MultiCollections have been updated to implement IDictionary<TKey, ICollection<TValue>> instead of IDictionary<TKey, IEnumerable<TValue>>. This was a suggestion I received through the comments on this weblog, and it made these collections significantly better.

Please give it a try and let me know what you think!

Arrays and IList

pgolde — Wed, 20 Apr 2005 18:41:00 GMT

As I was updating Power Collections to use Beta 2, I found an somewhat unfortunate change that had been made since Beta 1. Arrays in .NET have always implemented the IList interface, so you have always been able to convert an int[], say, to an IList, and use that IList to read and write the elements of the array. This is very useful, because you can write algorithms that take an IList, and use that IList without knowing whether they are using an array of object, an array of string, an array of ints, an ArrayList, or any other kind of object that implements IList.

With the advent of generics, there is now a generic IList<T> interface, which can be specialized to describe lists of any specific type. For example, IList<int> allows reading and writing a list-like object that can only contains ints. Now, it makes total sense that int[] should implement IList<int>, string[] should implement IList<string>, etc. And, in fact, this is the case in both Beta 1 and in Beta 2. This is great, because it means that all of the algorithms in Algorithms that take a parameter of IList<T> can be used on arrays, as well as other collections.

However, this support was made more limited in Beta 2. In Beta 2, when you get the IList<T> interface on an array, it is a read-only list. This means that you can read items in the array, but you cannot change the array via the IList<T> interface. The IList<T>.ReadOnly property returns true to indicate this, and using the indexer to change an item throws an NotSupportedException. After some searching around, I found a posting from the BCL team that described this limitation.

The upshot is that you can stiill use non-modifying generic algorithms on an array (for example, Algorithms.LastIndexOf). However, a generic algorithm that modifies the list (for example, Algorithms.StableSortInPlace) cannot be used directly on an array. An annoying limitation, to be sure.

My current thinking is to provide a method on Algorithms that creates a read-write IList<T> wrapper on an array. Something like:

IList<T> AsReadWriteList(T[] array);

Other ideas (or a better name) welcome.

VS Beta 2 is released

pgolde — Tue, 19 Apr 2005 17:02:00 GMT

Visual Studio Beta 2 and Visual C# Express Beta 2 are finally available. I'm downloading and installing now, and will be posting an updated Power Collections as soon as I am able.

ToString() on collections

pgolde — Tue, 12 Apr 2005 18:50:00 GMT

I got a lot of great feedback on ToString and how it should work on collections. Based on that feedback, I've modified my implementation some and made it significantly better, I think:

1) Several people raised concerns that having ToString return a representation of the collection contents could drastically slow debugging for large collections, because the debugger internally calls ToString to display the value. For small collections, this is a huge plus, because you can see the collection contents directly in the debugger. For large collections, though, the returned string is too long to usefully look at, and the debugger might become very slow having to deal with all that data.What I did was use the new DebuggerDisplay attribute to specify a custom debugger display function. The returned format is similar to how ToString() looks ({1,2,3}), but is limited to around 250 characters. After this, it just puts a “...“ in the returned string. This gives the advantages of the ToString functionality in debugging, but doesn't negatively impact debugging in large collections.

2) Several people indicated the desire to customize the look of the returned string, possible by using a different separator than comma, or different string and end character other than braces. To address this, I added an static method to Algorithms:

string ToString<T>(IEnumerable<T> collection, bool recursive, string start, string separator, string end)

This method converts any enumerable collection to a string, and allows complete control over the separator string, as well as the start and end strings. The boolean recursive parameters determines whether contained collections are converted to a string via a recursive call or not.

Thanks to everyone for their feedback!

Feature complete drop

pgolde — Fri, 08 Apr 2005 06:57:00 GMT

Sorry that the project has been so slow the last two months, but it is has not come to a complete stop. There's been some good discussion in the forums; I'll be working on replying to more of the posts over the next two days.

Today I've posted a new drop of PowerCollections in the usual place. You can download the zip to get the source, binaries, and documentation. If you just want to browse documentation, just go here. This drop still uses the November tech preview of Visual C#. Rumor is that Beta 2 of Visual Studio will be released soon; as soon as that is publicly available, I'll be posting a version for Beta 2.

This version has a two new important classes: MultiDictionary and OrderedMultiDictionary, which map a key to multiple values. I'll post a description of these classes and the design thinking behind them in a subsequent posting.

This version also has a number of smaller changes:

1. The BigList class has been updated with many utility methods, to make it much closer to a replacement for the BCL List class.

2. Most collection classes now have a Comparer property to return the IComparer that the classes was constructed with.

3. Several renamings of methods to be better: AddAll became AddMany, RemoveAll become RemoveMany, SubsetOf became IsSubsetOf (and several similar renamings), AddTyping became TypedAs, RemoveTyping became Untyped, UniqueItems became DistinctItems.

4. The Range, RangeFrom, and RangeTo methods on the ordered collections now take additional boolean parameters indicating whether the endpoints of the range should be treated inclusively or exclusively.

With this drop, Power Collections version 1.0 is feature complete. From now on, I'm not planning to add any new collection types or major new features. Instead, I'm going to polish, fix, and get what is there ready for a final release. In the source, you will we a number of comments marked “UNDONE” and “CONSIDER”, which list a lot of the items that need to be addressed. I'll also be looking over the comments in the forums one more time to look at suggestions that have been made.