1 vote for Algorithms

<br>

<br>If it gets too long I'll just write snippet expansions for the algorithms I use frequently.

<br>

<br>Collection seems like it should be an actual collection, not methods that act on a collection.

<br>

<br>Collections would be my second choice, although I assume that some of the algorithms will work on IEnumerable&lt;T&gt; rather than ICollection&lt;T&gt; or IList&lt;T&gt;, so I think Algorithms is the best name.  Plus, it would fit right in with the algorithms header file in the STL (Just, please name them better than the STL did.  There are inconsistancies...such as find vs search).

I also vote for Algorithms.

Algorithms ist OK. If this name seems too long one could always write:

<br>

<br>using Algo=TheNamespace.Algorithms;

<br>

<br>at the top of a file where Algorithms is often used...

I dislike Collections (because it's unlikely that most methods will be applied to more than one collection at a time, the plural sounds wrong) and I agree with the rationale given by others for choosing between Collection and Algorithm.

&quot;In Power Collections, we are going to want to provide a bunch of static methods that implement useful algorithms on collection interfaces (sort of STL-like). Stuff like “LargestElement“, “Sort“, “Shuffle“, and so forth. (By the way, feel free to proposed ideas for these in the forums or in feedback).&quot;

<br>

<br>Why?  Shouldn't these be methods on the interface?  How are you going to implement LargestElement?  By iterating over the passed in collection until you find it?  What if it's a heap, or a treee structure?  Are we going to incur a O(N) traversal to find something that can be O(1) or O(log n).

<br>

<br>It would be nice to hear the justification for why these static methods are a good thing from a design, implementation, or performance perspective.

<br>

<br>I blogged on this before and would be happy to link to that.

Cyrus: I kind of like most of the signatures because the input requirement is only something like IEnumerable&lt;T&gt; and IList&lt;T&gt; - those interfaces are a very simple requirement, so people can use the same methods on lots of different kinds of data structures.  Putting the methods on types restrictions their usage to said types and subclasses - the ideas of these methods (IMHO) is that they work on the largest variety of input collections and as such are the least restrictive to input values.  That promotes their usage in a much larger set of scenarios, and enables reuse of the same methods (leading to smaller footprints, we'd hope).  Yes, it does mean that some things are slower than they necessarily have to be, but the alternative seems to be bifurcating the coding into the &quot;interface-based statics&quot; and then &quot;type-based methods&quot;, with mixes and matches depending on scenario.

<br>

<br>I wouldn't mind overloads of more specific interfaces that could behavior better (as needed), but since we can't modify IEnumerable&lt;T&gt; or IList&lt;T&gt; (and don't want to) with these methods, the statics seem like a good choice IMHO.

<br>

<br>Peter: on the naming front (well, method-level), these 3 seem odd to me:

<br>

<br>4.25 T Smallest(IComparable&lt;T&gt; list, int n, optional Comparer&lt;T&gt;)

<br>Finds the smallest item of a list.

<br>4.26 T Largest(IComparable&lt;T&gt; list, int n, optional Comparer&lt;T&gt;)

<br>Finds the Nth largest item of a list.

<br>4.27 T NthLargest(IList&lt;T&gt; list, int n, optional Comparer&lt;T&gt;)

<br>Finds the Nth largest item of a list.

<br>

<br>-          IComparable isn’t a list interface AFAICT, it’s implemented by a type and “IComparable&lt;T&gt; list” doesn’t make sense to me at the moment – seems like lists should be passed as IList&lt;T&gt; or IEnumerable&lt;T&gt; (those make sense to me) and not IComparable&lt;T&gt;?

<br>-          I like NthLargest as a method name – it makes the “int n” parameter obvious, but the first two don't have that name - should they drop the &quot;int n&quot;? If not, what does it mean?  Is the description for 4.26 wrong?

<br>-          there should be an NthSmallest if there's NthLargest, of course.

<br>-          Smallest and Largest being basically NthLargest(list, 1, comparer) makes sense (n has to be 1 based to make sense, unfortunately), but the “int n” doesn’t make sense (at least in a discoverable way) for them – it seem like they should be 2 params of IList&lt;T&gt; and optional Comparer&lt;T&gt;

<br>-          I’m still more in favor of IComparer&lt;T&gt; for comparison rather than Comparer&lt;T&gt;, but that’s approaching a religious war these days.  IComparer&lt;T&gt; is sufficient for the methods and presents less of a constraint on the inputs, etc. etc. - I can't just have one ComparisonHelper class that implements 3 different IComparer&lt;X&gt; for X being 3 different types if the restriction is on Comparer&lt;T&gt; - now I need 3 different classes.

Algorithms seems to be a fine name for a static class.  We came up with some similar ideas, but they all seemed rather horrible.  &quot;Enumerable&quot; was one of them, &quot;Functional&quot; was another (I think), and surprisingly there's a file called Functor.cs in our tree (but it just defines four delegates, neither of them use &quot;functor&quot; in their name).  &quot;Collection&quot; would be misleading, as we may be shipping a class called Collection&lt;T&gt;.  A static class with a surprisingly similar name but rather different purpose would be a bad idea.

<br>

<br>You're going to need a dumping ground for all your generic programming methods.  Algorithms sounds like the best name put forward so far.  Otherwise you're stuck with some variant of &quot;collection utils&quot; or &quot;collection helper&quot;.  I also tried our fallback approach for naming ideas - using a thesaurus - but it came up blank.

<br>

James:  Sorry... i didn't understand that :(

<br>

<br>You said: &quot;I kind of like most of the signatures because the input requirement is only something like IEnumerable&lt;T&gt; and IList&lt;T&gt; - those interfaces are a very simple requirement, so people can use the same methods on lots of different kinds of data structures&quot;

<br>

<br>Well... if the input is only an IList&lt;T&gt;... then why not put the method on IList&lt;T&gt; itself where it belongs?

<br>

<br>I might be missing something though...

Cyrus: Because he's not Microsoft, and he can't modify IList&lt;T&gt;.

<br>

<br>However, this project is supposed to extend the existing Microsoft implementation, so he can't write his own IList&lt;T&gt; unless it in turn inherited from Microsoft's IList&lt;T&gt;, and even then that wouldn't exactly be extending Microsoft's design.

<br>

<br>Besides, Microsoft stated that their collections should cover most people's needs (was it 80 or 90% or something?).  For everyone else, this project will fill the gaps (hopefully---*grin*).

<br>

<br>Now, what he COULD do is specialize a bit.  For example, if the implementation of any particular algorithm for dictionaries may have significantly better performance on say, a BinaryTree-based IDictionary&lt;K,V&gt;, he could write an interface called IBinaryTreeDictionary&lt;K,V&gt; which moved the responsibility of the algorithm to the collection class itself.  The Algorithms class could have overloads on each of such methods taking an IBinaryTreeDictionary&lt;K,V&gt; which called the appropriate method on the collection class.  The overload for IDictionary&lt;K, V&gt; could fist check to see if the dictionary was an IBinaryTreeDictionary&lt;K,V&gt;, and if it wasn't fall back on default behavior.  This would add the overhead of an &quot;as&quot; operation on the general version of the method for every call, which may or may not be for the best.

<br>

<br>In a simpler case, a single algorithm may work differently on IEnumerable&lt;T&gt;, ICollection&lt;T&gt;, and IList&lt;T&gt;, and contain three overloads.  The algorithm could take advantage of an ICollection&lt;T&gt;'s ability to return a Count, or perhaps IList&lt;T&gt;'s ability to access by index.

<br>

<br>Besides, I don't think that the STL puts very many algorithms on their container classes.  This isn't as much of a problem as it is in C#, however, as their containers can often add or remove items while iterating.  Cluttering the IList interface with several methods that may be hard to implement in every case is not a good solution.

Matthew: Ahh.  That makes more sense.  Well... pity.

<br>

<br>As to the 80%-90%.  I find that very surprising.  I find the collections are unable to cover my needs 100% of the time.  I.e. it is a rare occurrance when a built in collection will suffice for the work i do (and I'm not doign anything complicated!)

<br>

<br>&quot;Besides, I don't think that the STL puts very many algorithms on their container classes. This isn't as much of a problem as it is in C#, however, as their containers can often add or remove items while iterating.&quot;

<br>

<br>Yup.  I don't know why iterators can't modify the underlying collection.  It kills me that to do so I end up having to copy to temporary structures.  All my perf bugs eventually come down to design decisions in the frameworks getting in my way.  Rather than designing it so that it was flexible and extendible and would solve all needs, (with a thin wrapper around it to dumb it down to look like the current api) they went with a design that has no positive points at all.  it's clutttered, inneficient and unextendible.  Well, guess that's why people write their own (including Peter).  

<br>

<br>I which we wouldn't have to keep reimplementing the wheel though.  It's incredibly tedious.

Great feedback!

<br>

<br>Looks like a pretty good consensus on &quot;Algorithms&quot;.

<br>

<br>James: You are correct. The signature and naming on those three methods are messed up! Insufficient proof reading on my part.

<br>

<br>--Peter

Somewhat unrelated, but going through the spec again I ran across 4.19:

<br>

<br>void RemoveIf(IEnumerable&lt;T&gt; collection, Predicate&lt;T&gt; func)

<br>

<br>I'm kind of at a loss on how that's supposed to work.  It seems like it needs to change in one of two ways:  either 1) return back an IEnumerable&lt;T&gt; that's the input &quot;stream&quot; with the func==true items removed from said stream or 2) operate on IList&lt;T&gt; instead.  

<br>

<br>Obviously #2 is less useful, only because List&lt;T&gt; (although not IList&lt;T&gt; of course) has RemoveAll which does &quot;remove based on predicate func&quot; already.  Because of that, changing the return type to IEnumerable&lt;T&gt; seems like the better choice.

<br>

<br>As-is, it sure seems like (maybe I'm missing something) that the method will take the stream (being an IEnumerable&lt;T&gt;, I like to thing of them as strongly-typed streams of objects, although I do realize the GetEnumerator indirection layer) and then foreach (T t in collection) { if (!func(t)) yield return t; } - that's the only kind of implementation that makes sense to me at the moment, because otherwise the passed-in collection has to be something more like a real collection (IList&lt;T&gt; or similar) instead of something more stream-like.

<br>

<br>Apologies if I'm just being daft and missing something obvious :)

Matthew: I actually work for Microsoft, but even if I was the owner of IList&lt;T&gt; (I'm not :) I wouldn't add anything to it.  It would cease to serve it's purposes, which to me should continue to be the minimal set of things a class needs to implement to be capable of being treated as a strongly-type list of objects.

<br>

<br>Peter: not overly relevant, but in case you haven't already, make sure to skim around the Commons Collections of the Jakarta Project.

<br>

<br><a target="_new" href="http://jakarta.apache.org/commons/collections/">http://jakarta.apache.org/commons/collections/</a>

<br><a target="_new" href="http://jakarta.apache.org/commons/collections/">http://jakarta.apache.org/commons/collections/</a>apidocs-COLLECTIONS_3_1/index.html

<br>

<br>The size of their API is kinda unwieldy (not being generic) and nothing jumps out at me as being in their API and useful and missing in the Power Collections spec at a quick glance outside of maybe their BidiMap support, something that supports fast lookup from key to value or value to key.  Could be useful in situations where you know both key and value are unique and it could be a little nicer than people having to keep Dictionary&lt;&gt;'s in both directions.  Since the Power Collections has MultiDictionary going on anyway, the unique requirements could be dropped, of course, for a MultiBidiDictionary or whatever :)

Where's this spec that you guys keep talking about?

<br>

<br>Is it something internal to Microsoft at the moment?

<br>

<br>Sorry if I'm being too nosy.  I'd like to know what will be supported so I don't waste my time porting some of my non-generic collections to Whidbey,

Nevermind.  I visited the non-blog part of the Wintellect site for the first time today and found it myself.

<br>

<br>Excuse me for jumping the gun.

James -- you are right again. Return type should be IEnumerable&lt;T&gt;.

<br>

<br>It's so much easier to get things right when you actually have to code them up!

I think Algo is good!