Thursday, November 10, 2011

Creating LINQ UnorderedEqual


Background
A colleague of mine asked me for some help with writing a LINQ query to check if two lists contained the same contents, order-insensitive. I was surprised to find that LINQ has built-in extension methods for a similar order-sensitive check (SequenceEqual) but not an order-insensitive check.

So, after searching StackOverflow, I wrote the following extension method and tests. Use them as you see fit!

The Code
// 2011 © Team Gunmetal, Inc.
// Available for reuse under the MIT License: http://www.opensource.org/licenses/mit-license.php
using System.Collections.Generic;
using System.Linq;

namespace TeamGunmetal.Extensions
{
    /// <summary>
    /// A place to put IEnumerable extension methods
    /// </summary>
    public static class IEnumerableExtension
    {
        /// <summary>
        /// Determines whether two unordered sequences are equal by comparing the elements
        /// using the default equality comparer for their type.
        /// </summary>
        /// <typeparam name="T">The type of the elements of the input sequences.</typeparam>
        /// <param name="first">
        /// An IEnumerable<<typeparamref name="T"/>> to compare to <paramref name="second"/>.
        /// </param>
        /// <param name="second">
        /// An IEnumerable<<typeparamref name="T"/>> to compare to the <paramref name="first"/> sequence.
        /// </param>
        /// <returns>
        /// true if the two source sequences are of equal length and their elements are equal
        /// according to the default equality comparer for their type, irrespective of order;
        /// otherwise, false.
        /// </returns>
        public static bool UnorderedEqual<T>(this IEnumerable<T> first, IEnumerable<T> second)
        {
            var firstCount = first.Count();
            return firstCount == second.Count() && firstCount == first.Intersect(second).Count();
        }
    }
}


The Tests
// 2011 © Team Gunmetal, Inc.
// Available for reuse under the MIT License: http://www.opensource.org/licenses/mit-license.php
using System.Collections.Generic;
using TeamGunmetal.Extensions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TeamGunmetal.Tests.Extensions
{
    [TestClass]
    public class IEnumerableExtensionTest
    {
        [TestMethod]
        public void UnorderedEqual_IEnumerablesWithSameContentsInSameOrderAreEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 1, 2, 3 };
            Assert.IsTrue(list1.UnorderedEqual(list2));
        }

        [TestMethod]
        public void UnorderedEqual_IEnumerablesWithSameContentsInOppositeOrderAreEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 3, 2, 1 };
            Assert.IsTrue(list1.UnorderedEqual(list2));
        }

        [TestMethod]
        public void UnorderedEqual_IEnumerablesWithSameContentsInRandomOrderAreEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 2, 3, 1 };
            Assert.IsTrue(list1.UnorderedEqual(list2));
        }

        [TestMethod]
        public void UnorderedEqual_IEnumerablesWithoutContentsAreEqual()
        {
            IEnumerable<int> list1 = new List<int>();
            IEnumerable<int> list2 = new List<int>();
            Assert.IsTrue(list1.UnorderedEqual(list2));
        }

        [TestMethod]
        public void UnorderedEqual_IEnumerablesWithSameContentsButDifferentFrequenciesAreNotEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3, 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 1, 2, 3 };
            Assert.IsFalse(list1.UnorderedEqual(list2));
        }
 
        [TestMethod]
        public void UnorderedEqual_IEnumerablesOfSameLengthButWithMutuallyExclusiveContentsAreNotEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 4, 5, 6 };
            Assert.IsFalse(list1.UnorderedEqual(list2));
        }
 
        [TestMethod]
        public void UnorderedEqual_IEnumerablesOfDifferentLengthAndWithMutuallyExclusiveContentsAreNotEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 4, 5, 6, 7, 8 };
            Assert.IsFalse(list1.UnorderedEqual(list2));
        }
 
        [TestMethod]
        public void UnorderedEqual_IEnumerablesOfDifferentLengthsButThatHaveAnIntersectionEqualToOnlyTheFirstAreNotEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3 };
            IEnumerable<int> list2 = new List<int>() { 1, 2, 3, 4, 5 };
            Assert.IsFalse(list1.UnorderedEqual(list2));
        }

        [TestMethod]
        public void UnorderedEqual_IEnumerablesOfDifferentLengthsButThatHaveAnIntersectionEqualToOnlyTheSecondAreNotEqual()
        {
            IEnumerable<int> list1 = new List<int>() { 1, 2, 3, 4, 5 };
            IEnumerable<int> list2 = new List<int>() { 1, 2, 3 };
            Assert.IsFalse(list1.UnorderedEqual(list2));
        }
    }
}

Thursday, June 3, 2010

One feature I wish .NET offered

Know one thing that pisses me off about .NET? That you can't write design-time/compile-time exceptions, e.g. for custom attribute classes that need to verify design-time things like (1) existence of input parameter of certain name/type, (2) existence of other required attributes, etc.

Microsoft has obviously accounted for this in some way for their own attributes, e.g. AttributeUsageAttribute, but don't seem to offer any overridable method in order to provide our own design-time/compile-time errors.

Wednesday, November 25, 2009

What the hell, IE....

So last night I was bitten by a very unexpected behavior in the IE JavaScript engine (IE7, specifically, but I would suspect it's present in all the other versions).

Background
I have a function that iterates through the characters in a string trying to align them with those from another string. I was doing this with a for loop from 0 through "length - 1" and then pulling out the pertinent character from the string using the indexer, e.g.
    for (var c = 0; c < myString.length; c++)
    {
        alert("char at index " + c + " was: " + myString[c]);
    }

Problem
This seemed to work fine in all of my initial tests and works like a charm in Firefox.  However, when I flipped back to IE7 to run my JSUnit tests there as well, I saw about 7 errors in my results.  Turns out it was an error from when the string was a single character, e.g. "x".  From an object perspective, JavaScript still knows it's a string because all of the string methods are available.  However, use of the indexer, e.g. myString[c], caused it to blow up, saying that myString[c] was undefined.

My assumption here is that, in IE, the indexer syntax actually tries to retrieve the index from its internal data structure (i.e. char[]) rather than its JS representation (i.e. String).  However, it seems that when the string is only one character long, its internal representation is just a plain ole char rather than a char array.  Very odd!

Solution/Workaround
Any which way, this was easily worked around by using the string methods instead:
    for (var c = 0; c < myString.length; c++)
    {
        alert("char at index " + c + " was: " + myString.substring(c, c + 1));
    }

Thursday, October 29, 2009

TreeWalker: The ultimate DOM traversal provider

The W3C's DOM Level 2 calls for the existence of a JavaScript class by the name of TreeWalker, which all DOM Level 2-compliant browsers (amongst the modern ones, this is all but the IE browsers) have successfully provided. But wouldn't it be nice to have a TreeWalker available in IE too? This is the question that was raised at work during a story with very intense JavaScript requirements. And so, I set out to build a cross-browser TreeWalker (obviously leveraging the native TreeWalker when available). I blew through a number of methods easily (parentNode(), firstChild(), lastChild(), previousSibling(), nextSibling()), but had to call it quits for the night when I got to previousNode() and nextNode()... much too complicated to think about at the late hour. I did get some confirmation by looking at Mozile's (Mozilla In-Line Editor) TreeWalker JS (http://mozile.mozdev.org/0.8/src/dom/TreeWalker.js).

Looks like they also have some JS files in the same folder (http://mozile.mozdev.org/0.8/src/dom/InternetExplorerRange.js and http://mozile.mozdev.org/0.8/src/dom/InternetExplorerSelection.js) to give IE ranges/selections the capabilities of a W3C Range and the Mozilla Selection object, respectively, that I may have to peek at to see if I can refactor any of the RangeInformation class I put together to wrap ranges in a mostly cross-browser fashion.

Along with the Selection library I've recently created, I'd love to publish a copy of the TreeWalker to the open source world. We'll see....


Update:
Upon second inspection the next day, it turned out that parentNode, firstChild, lastChild, nextSibling, previousSibling were all actually harder methods than I had given them credit for, and nextNode and previousNode were actually the easy ones. The complications come from the whole "logical view" as defined in the W3C spec for DOM Traversal (DOM level 2) that features the TreeWalker.

Thursday, October 22, 2009

Twin Cities Code Camp 7 this weekend!

This weekend marks the 7th bi-annual (twice annually) Twin Cities Code Camp.  Unfortunately, I have class for the Masters degree all day Saturday.  Fortunately, my classes and TCCC are both at the University of Minnesota's EE/CSci Building.  Therefore, I will be skipping my morning class to attend two sessions on JavaScript but attending my afternoon class as normal.  At least the morning will be more fun than usual.... :)

Sadly, this is the first time TCCC will not be providing lunch to attendees.  While I can understand this predicament given the down economy and relatedly poor sponsorship this time around, it still sucks.  :(

Friday, October 2, 2009

My return to ActiveX

Given the good state of all things JavaScript that I've been working on, I started back in on the ActiveX control I had been working on earlier this summer.  I have already updated the few externally related field values that have changed in the time the project has been idle, but now must work on figuring out why some IE8 users have issues with running it.  Harrumph, not looking forward to it... especially without the free access to the "Add-in Express 2009 for Internet Explorer and Microsoft .NET for Visual Studio 2008 (C#)" that I so desired.  :(

Friday, September 25, 2009

No "Add-in Express 2009 for Internet Explorer and Microsoft .NET" for you!

As mentioned in my previous post "Developing IE addons is infuriating!", I was attempting to get a free copy of "Add-in Express 2009 for Internet Explorer and Microsoft .NET for Visual Studio 2008 (C#)" from Add-in Express Ltd. through their "blog review" program.  Alas, it seems that my fledgling blog did not meet any of their three criteria to qualify for such a benefit:
  1. It has not been around for over 1 year.
  2. It does not yet have a strong follower base.
  3. It does not show up with a high ranking on Google search results (for some magical search they must run to qualify this).

Guess that was just a pipe dream.  Back to being confused out of my mind on how IE Addons development in .NET works....

Thursday, September 24, 2009

Unraveling the pitfalls of JS inheritance

So with the aid of a colleague and the good ole O'Reilly "JavaScript: The Definitive Guide, Fourth Edition" book, I pinned down a previously unexplainable problem with the JS inheritance work I was doing.  Basically, I was trying to create a base widget that more complex widgets would inherit from — pretty standard inheritance idea.  Here's the basic code concept to illustrate....

MyNs.BaseWidget = function()
{
    this.parentElement = null;
    this.childWidgets = [];
};
MyNs.BaseWidget.prototype.AddChildWidget = function(childWidget)
{
    this.childWidgets.push(childWidget);
};
MyNs.BaseWidget.prototype.Draw = function()
{
    this.DrawSelf();
   
    for (var c = 0; c > this.childWidgets.length; c++)
    {
        var childWidget = this.childWidgets[c];
        childWidget.Draw(); 
    }
};

MyNs.ComplexWidget = function()
{
    // Some new properties of no consequence
};
// The next two lines chain prototypal inheritance
MyNs.ComplexWidget.prototype = new MyNs.BaseWidget();
MyNs.ComplexWidget.prototype.constructor = MyNs.ComplexWidget;


// Create objects!
var myChildWidget = new MyNs.ComplexWidget();
myChildWidget.parentElement = document.getElementById("childDiv");

var myMainWidget = new MyNs.ComplexWidget();
myMainWidget.parentElement = document.getElementById("parentDiv");
myMainWidget.AddChildWidget(myChildWidget);
myMainWidget.Draw();


Now what happened was by far the most confusing thing I've ever encountered: the "parentElement" property on each object was set correctly; however, the "childWidgets" property on myChildWidget (which should've been of length 0) was actually identical to myMainWidget's "childWidgets" property (which had a length of 1).  While confusing, the real problem here is that it spawned an infinitely recursive loop when invoking the Draw method as there was always one child widget to draw regardless of the context of "this".  I noodled on that problem for a few idle days before my colleague and I finally stumbled upon the reasoning in our quest to solve the problem today (yay for pair programming as needed and the fact that I actually asked him to look at it with me).  The scoop follows!

The prototypal inheritance model of JavaScript with regard to inherited properties operates under the following basic rules:
  1. Rule #1: If the derived class never modifies the inherited property, any "read-only" references to that property will actually use the property from the base class instead.
  2. Rule #2: If the derived class directly modifies the inherited property, it makes a copy of the base class's property for itself and masks its ties to the base class's property.  However, if the derived class's copy of the property were to be deleted (destroyed from memory), trying to access said property will again link to the base class's property.
  3. Rule #3: If the inherited property is never modified (so the derived class still points to the base class's property) and it is INDIRECTLY modified (e.g. childWidgets.push({})), the call to grab the property itself is seen as a read-only reference and therefore pulls the base class's property and then updates that.

Now knowing this, such a folly can easily be solved with some code changes in red as follows....


MyNs.BaseWidget = function()
{
    this.parentElement = null;
    this.childWidgets = null// was: = [];
};
MyNs.BaseWidget.prototype.AddChildWidget = function(childWidget)
{
    if (this.childWidgets == null)
    {
        this.childWidgets = [];
    }
    this.childWidgets.push(childWidget);
};
MyNs.BaseWidget.prototype.Draw = function()
{
    this.DrawSelf();
    if (this.childWidgets != null)
    {
        for (var c = 0; c > this.childWidgets.length; c++)
        {
            var childWidget = this.childWidgets[c];
            childWidget.Draw();
        }
    }
};

MyNs.ComplexWidget = function()
{
    // Some new properties of no consequence
};
// The next two lines chain prototypal inheritance
MyNs.ComplexWidget.prototype = new MyNs.BaseWidget();
MyNs.ComplexWidget.prototype.constructor = MyNs.ComplexWidget;


// Create objects!
var myChildWidget = new MyNs.ComplexWidget();
myChildWidget.parentElement = document.getElementById("childDiv");

var myMainWidget = new MyNs.ComplexWidget();
myMainWidget.parentElement = document.getElementById("parentDiv");
myMainWidget.AddChildWidget(myChildWidget);
myMainWidget.Draw();


Here we see that by not having the property declared in the base class's constructor (except to null, which is not its intended value), but rather instantiating it in the first call to the "AddChildWidget" method (which will be invoked an instance of the derived class), we have fallen into Rule #2 rather than Rule #3 as before: now the new derived instance is creating an instance of this array for itself.  Success!

Final word: it should be noted that, although my example here focuses on hierarchical chaining ("composite" design pattern), the problem described here would show itself just as easily when there are two derived instance objects on the page at the same time even if they had no direct relation to each other.  The only thing that makes it more evident in a hierarchical chaining example like this one is the unfortunate introduction of an infinitely recursive loop.  ;)

Friday, September 11, 2009

Aspirations of true agile practices in JavaScript development

My team regularly develops JavaScript for our piece of the application, but has struggled until recently to get decent test coverage of our JS code.  In an effort to see what the ideal state of such things could be, I've setup a website on my local IIS 7 instance with the following set of tools that I believe would satisfy the needs of doing real TDD/agile practices with JavaScript development: JSUnit, JSMock, JSCoverage, and the JSDoc Toolkit.  We'll see how it goes!

Note that for JSUnit, the download links are sadly out of date.  You must drill into the SourceForge trunk of the codebase in order to get a remotely recent version.

Wednesday, September 9, 2009

Can't wait for my inheritance!

I am busy trying to figure out the best way to do reliable class inheritance in JavaScript without importing a third party library OR extending the prototype of a core JavaScript class (e.g. function).  Amongst a great variety of blog posts, forum answers, and random articles, I am finding Douglas Crockford's Prototypal Inheritance in JavaScript and Classical Inheritance in JavaScript the most useful in terms of edification thus far.

Other interesting resources

Quick practical examples:
http://phrogz.net/JS/Classes/OOPinJS2.html


Overriding instanceOf to make it work for derived types:
http://www.webreference.com/programming/javascript/gr/column18/3.html

Poor man's "reflection" on "classes":
http://webreflection.blogspot.com/2007/01/javascript-getclass-and-isa-functions.html

Microsoft's take on the subject (related to their ASP.NET AJAX libraries):
http://msdn.microsoft.com/en-us/magazine/cc163419.aspx


Continuing the hunt....