TypeScript QuadTree part 3

This is the third part of my series on implementing a QuadTree in TypeScript, the first post can be found here and the second post can be found here. This posts focuses on starting to implement the QuadTree itself since the previous post addressed the prerequisites. As mentioned previously the pseudo code is from an example of a QuadTree found here. In this post have implemented a basic foundation that is capable of being constructed and sub-dived.

///
///

// Interfaces
interface IQuadTree {
    insert(quad: IQuad);
    queryRange(quad: IQuad);
}

// Class
class QuadTree implements IQuadTree {
    private minSize = 1;
    private contents: IQuadList;
    private topLeft: IQuadTree;
    private topRight: IQuadTree;
    private bottomLeft: IQuadTree;
    private bottomRight: IQuadTree;

    constructor (private quad: IQuad) {
        this.contents = new QuadList();
    }

    isSubdivided(): bool {
        return this.topLeft !== null;
    }

    subdivide() {
        this.topLeft = new QuadTree(this.getTopLeft());
        this.topRight = new QuadTree(this.getTopRight());
        this.bottomLeft = new QuadTree(this.getBottomLeft());
        this.bottomRight = new QuadTree(this.getBottomRight());
    }

    getTopLeft(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getTopRight(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getBottomLeft(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getBottomRight(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(),this. quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    insert(quad: IQuad) {
        // To be implemented
    }

    queryRange(quad: IQuad) {
        // To be implemented
    }
}

Now I run tsc.exe over the TypeScipt and I get a whole bunch of JavaScript that isn't actually that different.

var QuadTree = (function () {
    function QuadTree(quad) {
        this.quad = quad;
        this.minSize = 1;
        this.contents = new QuadList();
    }
    QuadTree.prototype.isSubdivided = function () {
        return this.topLeft !== null;
    };
    QuadTree.prototype.subdivide = function () {
        this.topLeft = new QuadTree(this.getTopLeft());
        this.topRight = new QuadTree(this.getTopRight());
        this.bottomLeft = new QuadTree(this.getBottomLeft());
        this.bottomRight = new QuadTree(this.getBottomRight());
    };
    QuadTree.prototype.getTopLeft = function () {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getTopRight = function () {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getBottomLeft = function () {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getBottomRight = function () {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.insert = function (quad) {
    };
    QuadTree.prototype.queryRange = function (quad) {
    };
    return QuadTree;
})();

Now that we have got the basic class implemented my next post I will get down and dirty implementing the insert and queryRange methods.

TestCaseData mock verifications

It is common practice to use an the TestCaseSource attribute to specify test data and the expected result in the format of IEnumerable<TestCaseData> like the example below.

[Test, TestCaseSource("TestCases")]
public int ShouldReturnTheExpectedValueWhenCalled(int testCase)
{
 context.Setup(c => c.Number).Returns(testCase);

 return context.CalculateSomething();
}

private IEnumerable<TestCaseData> TestCases
{
 get
 {
  yield return new TestCaseData(4).Returns(16);
  yield return new TestCaseData(5).Returns(25);
  yield return new TestCaseData(-1).Throws(typeof( Exception));
 }
}

For some tests the method shown above is sufficient but what about when you are testing a method that does not return a value and executes a command? In this circumstance you will be using mocking to assert that the method is operating correctly. The only problem with this is that I could not find any documentation for using a mock verification with TestCaseData, but I was able to get the functionality required from the example below.

[Test, TestCaseSource("TestCases")]
public void ShouldAlwaysCallSaveMethod(int testCase, Action[] verifications)
{
 // Act
 context.DoSomething(testCase);

 // Assert
 foreach (var verification in verifications)
 {
  verification.Invoke();
 }
}

private IEnumerable<TestCaseData> TestCases
{
 get
 {
  yield return new TestCaseData(random.Next(), 
   new Action[] 
   {
    () =&gt; service.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Once()),
    () =&gt; service2.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Once())
   });

  yield return new TestCaseData(0,
   new Action[]
   {
    () =&gt; service.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Once()),
    () =&gt; service2.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Never())
   });

  yield return new TestCaseData(-(random.Next()), 
   new Action[]
   {
    () =&gt; service.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Never()),
    () =&gt; service2.Verify(s =&gt; s.SomeAction(It.IsAny<int>()), Times.Never())
   });
 }
}

TypeScript QuadTree part 2

This is the second part of my series on implementing a QuadTree in TypeScript, the first post can be found here. This posts focuses on another prerequisite of my QuadTree, a list of Quads (as the QuadTree itself doesn't really care about how they are stored). There is currently no generic type support in TypeScript, but they are planning it in the future. So I have made a basic list implementation that can be later modified to become a generic list like that provided by C#, this class could even potentially implement the iterator pattern (IEnumerable in C#) in the future.

interface IQuadList {
    add(quad: IQuad);
    count(): number;
    clear();
    getQuad(index: number): IQuad;
}

class QuadList implements IQuadList {
    private list: IQuad[];
    private size: number;

    constructor (startSize : number = 1) {
        if (startSize < 1)
            startSize = 1;

        this.size = 0;
        this.list = new Array(startSize);
    }

    add(quad: IQuad) {
        if (!this.isRoomInList()) {
            var newArray = new Array(this.list.length * 2);
            this.list = this.copyToArray(newArray);
        }

        this.list[this.size] = quad;
        this.size += 1;
    }

    clear() {
        for (var i = 0; i < this.list.length; i++) {
            this.list[i] = null;
        }

        this.size = 0;
    }

    copyToArray(destination : IQuad[]) {
        for (var i = 0; i < this.size; i++) {
            destination[i] = this.list[i];
        }

        return destination;
    }

    count(): number {
        return this.size;
    }

    getQuad(index: number): IQuad {
        return this.list[index];
    }

    isRoomInList() : bool {
        return this.size < this.list.length;
    }
}

Now I run tsc.exe over the TypeScipt and I get my JavaScript.

var QuadList = (function () {
    function QuadList(startSize) {
        if (typeof startSize === "undefined") { startSize = 1; }
        if(startSize < 1) {
            startSize = 1;
        }
        this.size = 0;
        this.list = new Array(startSize);
    }
    QuadList.prototype.add = function (quad) {
        if(!this.isRoomInList()) {
            var newArray = new Array(this.list.length * 2);
            this.list = this.copyToArray(newArray);
        }
        this.list[this.size] = quad;
        this.size += 1;
    };
    QuadList.prototype.clear = function () {
        for(var i = 0; i < this.list.length; i++) {
            this.list[i] = null;
        }
        this.size = 0;
    };
    QuadList.prototype.copyToArray = function (destination) {
        for(var i = 0; i < this.size; i++) {
            destination[i] = this.list[i];
        }
        return destination;
    };
    QuadList.prototype.count = function () {
        return this.size;
    };
    QuadList.prototype.getQuad = function (index) {
        return this.list[index];
    };
    QuadList.prototype.isRoomInList = function () {
        return this.size < this.list.length;
    };
    return QuadList;
})();

Now that we have got a basic list implemented my next post I will get started on the actual quad tree class. The TypeScript so far has enabled me to have type checking at compile time and the joy of not worrying about got-ya's in JavaScript.

TypeScript QuadTree part 1

With Microsoft's release of TypeScript I have decided to implement a QuadTree algorithm based off the pseudo code on wikipedia. This post will be the first in a series of perhaps 3 or 4 posts on my TypeScript QuadTree. This post will detail the creation of the point and quad classes which my QuadTree will be dependent on.

The first step that I took was the creation of the interfaces which TypeScript allows, as you will see these interfaces are very close to that in C#. I have declared a series of methods which must be implemented and the return types and parameters for the methods.

interface IPoint {
    getX(): number;
    getY(): number;
}

interface IQuad {
    getLeft(): number;
    getRight(): number;
    getTop(): number;
    getBottom(): number;
    getWidth(): number;
    getHalfWidth(): number;
    getHeight(): number;
    getHalfHeight(): number;
    getCenter(): IPoint;

    containsPoint(candidate: IPoint): bool;
    intersects(candidate: IQuad): bool;
}

After completing the interfaces it was time to get my hands dirty with the implementations of Point and Quad classes. There is no good reason for using a module to wrap the classes aside from the fact that I could do so.

module Shapes {
    export class Point implements IPoint {
        constructor (private x: number, private y: number) { }

        getX() { return this.x; }
        getY() { return this.y; }
    }

    export class Quad implements IQuad {
        constructor (private point: IPoint, private width: number, private height: number) { }

        getLeft() { return this.point.getX(); }
        getRight() { return this.point.getX() + this.width; }
        getTop() { return this.point.getY(); }
        getBottom() { return this.point.getY() + this.height; }
        getWidth() { return this.width; }
        getHalfWidth() { return this.width / 2; }
        getHeight() { return this.height; }
        getHalfHeight() { return this.height / 2; }
        getCenter() { return new Shapes.Point(this.point.getX() + (this.width / 2), this.point.getY() + (this.height / 2)); }

        containsPoint(candidate: IPoint) {
            var isWithinX = this.getLeft() < candidate.getX() && candidate.getX() < this.getRight();
            var isWithinY = this.getTop() < candidate.getY() && candidate.getY() < this.getBottom();

            return isWithinX && isWithinY;
        }

        intersects(candidate: IQuad) { 
            var isWithinX = this.getLeft() < candidate.getRight() && candidate.getLeft() < this.getRight();
            var isWithinY = this.getTop() < candidate.getBottom() && candidate.getTop() < this.getBottom();

            return isWithinX && isWithinY;
        }
    }
}

Once I had completed the point and quad classes, it was time to run the "compile" the TypeScript into JavaScript and that was easily done with the following command.

tsc quad.ts

The tsc "compiler" took the TypeScript that I had written and output the JavaScript to a file called quad.js. Here is the contents of my newly created quad.js.

var Shapes;
(function (Shapes) {
    var Point = (function () {
        function Point(x, y) {
            this.x = x;
            this.y = y;
        }
        Point.prototype.getX = function () {
            return this.x;
        };
        Point.prototype.getY = function () {
            return this.y;
        };
        return Point;
    })();
    Shapes.Point = Point;    
    var Quad = (function () {
        function Quad(point, width, height) {
            this.point = point;
            this.width = width;
            this.height = height;
        }
        Quad.prototype.getLeft = function () {
            return this.point.getX();
        };
        Quad.prototype.getRight = function () {
            return this.point.getX() + this.width;
        };
        Quad.prototype.getTop = function () {
            return this.point.getY();
        };
        Quad.prototype.getBottom = function () {
            return this.point.getY() + this.height;
        };
        Quad.prototype.getWidth = function () {
            return this.width;
        };
        Quad.prototype.getHalfWidth = function () {
            return this.width / 2;
        };
        Quad.prototype.getHeight = function () {
            return this.height;
        };
        Quad.prototype.getHalfHeight = function () {
            return this.height / 2;
        };
        Quad.prototype.getCenter = function () {
            return new Shapes.Point(this.point.getX() + (this.width / 2), this.point.getY() + (this.height / 2));
        };
        Quad.prototype.containsPoint = function (candidate) {
            var isWithinX = this.getLeft() < candidate.getX() && candidate.getX() < this.getRight();
            var isWithinY = this.getTop() < candidate.getY() && candidate.getY() < this.getBottom();
            return isWithinX && isWithinY;
        };
        Quad.prototype.intersects = function (candidate) {
            var isWithinX = this.getLeft() < candidate.getRight() && candidate.getLeft() < this.getRight();
            var isWithinY = this.getTop() < candidate.getBottom() && candidate.getTop() < this.getBottom();
            return isWithinX && isWithinY;
        };
        return Quad;
    })();
    Shapes.Quad = Quad;    
})(Shapes || (Shapes = {}));

I believe that the TypeScript has much greater readability than the JavaScript generated and like with CoffeeScript didn't have to worry about JavaScript traps and tricks. The JavaScript generated seems to be exactly what I was expecting, although jslint has several critiques of it. My next steps are to get the test harness online and finish the QuadTree implementation.

Lazy<T> .NET 3.5

On a large enterprise applicaiton I work on we are currently unable to upgrade from .NET3.5 to .NET4.0, although there is plenty of situations where we could use the .Lazy<T> class. So in order to get us through until we upgrade to .NET I have implemented a very basic .NET 3.5 version which can easily be replaced with the Microsoft version at a later date.

/// <summary>
/// A pre-.NET4 Lazy<T> implementation
/// </summary>
public class LazyLoader<T>
 where T : class
{
 private readonly object padlock;
 private readonly Func<T> function;

 private bool hasRun;
 private T instance;

 public LazyLoader(Func<T> function)
 {
  this.hasRun = false;
  this.padlock = new object();
  this.function = function;
 }

 public T Value()
 {
  lock (padlock)
  {
   if (!hasRun)
   {
    instance = function.Invoke();

    hasRun = true;
   }
  }

  return instance;
 }
}