Highway Sort — Algorithm on the Road

The trip back home to Boone from Wilmington is a long ride, about 5 hours. It’s so easy to zone out and just drive but there’s so much to see while driving.The other day on the way back from Wilmington, I was cruising along with a large pack of cars. Some people like to drive faster than others, some slower. I pulled into a left lane, joining a pack of faster cars to pass a couple slower cars. After passing the slower cars, I found a car moving at a similar pace as mine and merged behind it. Then, the other cars that I was sharing the left lane with did the same. I saw the fastest car from the left lane group move in front of the pack in the right lane.

That left lane group I was in for a short moment managed to sort itself back into the right lane, each car finding a new position based on their speed preference.

I started noticing this sorting behavior every time I ran into traffic. Of course, if there was more than 2 lanes going the same direction, the sorting got a little wonky because the fast drivers would just continue on in the left lane until I couldn’t see them anymore.

This “highway sorting” is a real life example of Insertion Sort. The fast cars are moving up the queue of cars and finding their new position in the line of cars based on their preferred speed.

What happens when you add more lanes for the fast cars to move into?

Extending Squel.js

I have started using Squel.js for an application that I am developing. The application uses an already existing and rather old SQL Anywhere database, which Squel.js does not support out-of-box. However, the queries in my application are simple enough that Squel.js is working just fine, except for one problem…The version of SQL Anywhere I am using does not support the LIMIT and OFFSET keywords (e.g. SELECT * FROM Items LIMIT 10 OFFSET 20). There are two similar keywords I can use called TOP and START AT (e.g. SELECT TOP 10 START AT 20 * FROM Items). The problem is that Squel.js supports LIMIT OFFSET and not TOP START AT. This is not exactly a “lack of support”, it’s just that MySQL and PostgreSQL does not use the TOP START AT keywords. (Squel.js aims to mostly support MySQL and PostgreSQL)

TL;DR → I’ve created a plugin that adds support for TOP X, FIRST, and START AT Y. Install plugin or contribute.

Creating a plugin

NOTE: If you are adding support for a keyword or query that is part of MySQL or PostgreSQL, please consider submitting a patch/pull request directly to Squel.js instead of creating a plugin. This article is still relevant to those not creating a plugin.

Squel.js has some documentation on how to extend the query builder. I combined the two examples provided to create a plugin that adds TOP and START AT support. From now on in this article I’ll be using the squel-top-start-at plugin as an example.

What’s your syntax

First things first, what is the syntax of the keyword or query you are creating a plugin for? In my case, the syntax looks something like:

SELECT [ TOP { ALL | expression } [ START AT expression ] ]...  

Start new class

Go ahead and define your new keyword class and have it inherit from squel.cls.Block:

var squel = require('squel');

// inheritsFrom is from Squel.js documentation...
// OOP Inheritance mechanism (substitute your own favourite library for this!)
Function.prototype.inheritsFrom = function( parentClassOrObject ) {  
  this.prototype = new parentClassOrObject;
  this.prototype.constructor = this;
  this.prototype.parent = parentClassOrObject.prototype;
};

var TopStartAtBlock = function() {};  
TopStartAtBlock.inheritsFrom(squel.cls.Block);  

Add query building methods

Start adding methods to your new class. The methods you add will be exposed to the query builder except for any “private” methods that begin with an underscore _.

I’ll go ahead and define the top, startAt, and two sanitation methods…

TopStartAtBlock.prototype._sanitizeTop = function(top) {  
    var parsed = parseInt(top);
    if (isNaN(parsed)) {
        if (top && typeof top === 'string' && top.toLowerCase() == 'all') {
            return 'ALL';
        } else {
            throw new Error('Invalid argument for top()');
        }
    }

    if (parsed > 0) {
        return top;
    } else {
        throw new Error('Invalid argument for top()');
    }
};

TopStartAtBlock.prototype._sanitizeStartAt = function(start) {  
    var parsed = parseInt(start);
    if (isNaN(parsed)) {
        throw new Error('Invalid argument for startAt()');
    }

    if (parsed > 0) {
        return start;
    } else {
        throw new Error('Invalid argument for startAt()');
    }
};

TopStartAtBlock.prototype.top = function(top) {  
    this._top = this._sanitizeTop(top);
};

TopStartAtBlock.prototype.startAt = function(start) {  
    this._start = this._sanitizeStartAt(start);
};

The top and startAt methods are simply setters. The sanitation methods are checking for non-numeric values that are less than one (with an exception for “ALL” as a TOP argument). If the input value fails sanitation, an error should be thrown.

Build the clause

Next, we will implement the buildStr method which will build and return the query clause.

TopStartAtBlock.prototype.buildStr = function() {  
    // Error check. Cannot have START AT without a TOP.
    if (this._start && !this._top) {
        throw new Error('Must call top() along with startAt()');
    }

    var clause = '';

    if (this._top) {
        clause = 'TOP ' + this._top;
    }

    if (this._start) {
        clause += ' START AT ' + this._start;
    }

    return clause;
}

buildStr is a pretty straightforward method. First, you’ll see error checking. Do not someone to build a query like SELECT START AT 1 * FROM Items; that is improper syntax.

The next thing to point out is that clause is initialized as an empty string. An empty string should be returned from your the buildStr method if none of your new query building methods are called. If you return null or undefined from buildStr then a TypeError will be thrown with a stack trace along the lines of:

TypeError: Cannot read property 'length' of undefined  
    at /home/bostrt/node_modules/squel/squel.js:1263:21
    at Array.filter (native)
    at Select.cls.QueryBuilder.QueryBuilder.toString (/home/bostrt/node_modules/squel/squel.js:1262:22)
    at repl:1:35
    at REPLServer.self.eval (repl.js:110:21)
    ...

Connect to Squel.js

Now lets connect the plugin to Squel.js.

I’m going to define an alternative SELECT query builder called selectTop for the squel-top-start-at plugin.

exports.selectTop = squel.selectTop = function(options) {  
    var allowNestedOptions = options || {};
    allowNestedOptions['allowNested'] = true;

    return squel.select(options, [
        new squel.cls.StringBlock(options, 'SELECT'),
        new TopStartAtBlock(options),
        new squel.cls.DistinctBlock(options),
        new squel.cls.GetFieldBlock(options),
        new squel.cls.FromTableBlock(allowNestedOptions),
        new squel.cls.JoinBlock(allowNestedOptions),
        new squel.cls.WhereBlock(options),
        new squel.cls.GroupByBlock(options),
        new squel.cls.OrderByBlock(options),
        new squel.cls.LimitBlock(options),
        new squel.cls.OffsetBlock(options)
        ]);
};

The function above has all of the same building blocks as the standard SELECT query builder in Squel.js except for the addition of the new TopStartAtBlock. Also, notice that exports.selectTop and squel.selectTop are both assigned to the new/alternative SELECT query builder.

All done

That’s it. Squel.js makes it very easy to extend its query building mechanism. Check out the complete source code for the squel-top-stat-at plugin by going to: https://github.com/bostrt/squel-top-start-at

If you have any questions about building a Squel.js plugin or about the squel-top-start-at plugin contact me @robertbost or comment below. Thanks for reading.

Example Usage
// Require squel before requring squel-top-start-at plugin.
var squel = require('squel');  
var selectTop = require('squel-top-start-at').selectTop;

var query = selectTop.top(10).startAt(1).from('Item').toString;  
// query => SELECT TOP 10 START AT 1 FROM Item
I have started using Squel.js for an application that I am developing. The application uses an already existing and rather old SQL Anywhere database, which Squel.js does not support out-of-box. However, the queries in my application are simple enough that Squel.js is working just fine, except for one problem…The version of SQL Anywhere I am using does not support the LIMIT and OFFSET keywords (e.g. SELECT * FROM Items LIMIT 10 OFFSET 20). There are two similar keywords I can use called TOP and START AT (e.g. SELECT TOP 10 START AT 20 * FROM Items). The problem is that Squel.js supports LIMIT OFFSET and not TOP START AT. This is not exactly a “lack of support”, it’s just that MySQL and PostgreSQL does not use the TOP START AT keywords. (Squel.js aims to mostly support MySQL and PostgreSQL)

TL;DR → I’ve created a plugin that adds support for TOP X, FIRST, and START AT Y. Install plugin or contribute.

Creating a plugin

NOTE: If you are adding support for a keyword or query that is part of MySQL or PostgreSQL, please consider submitting a patch/pull request directly to Squel.js instead of creating a plugin. This article is still relevant to those not creating a plugin.

Squel.js has some documentation on how to extend the query builder. I combined the two examples provided to create a plugin that adds TOP and START AT support. From now on in this article I’ll be using the squel-top-start-at plugin as an example.

What’s your syntax

First things first, what is the syntax of the keyword or query you are creating a plugin for? In my case, the syntax looks something like:

SELECT [ TOP { ALL | expression } [ START AT expression ] ]...  

Start new class

Go ahead and define your new keyword class and have it inherit from squel.cls.Block:

var squel = require('squel');

// inheritsFrom is from Squel.js documentation...
// OOP Inheritance mechanism (substitute your own favourite library for this!)
Function.prototype.inheritsFrom = function( parentClassOrObject ) {  
  this.prototype = new parentClassOrObject;
  this.prototype.constructor = this;
  this.prototype.parent = parentClassOrObject.prototype;
};

var TopStartAtBlock = function() {};  
TopStartAtBlock.inheritsFrom(squel.cls.Block);  

Add query building methods

Start adding methods to your new class. The methods you add will be exposed to the query builder except for any “private” methods that begin with an underscore _.

I’ll go ahead and define the top, startAt, and two sanitation methods…

TopStartAtBlock.prototype._sanitizeTop = function(top) {  
    var parsed = parseInt(top);
    if (isNaN(parsed)) {
        if (top && typeof top === 'string' && top.toLowerCase() == 'all') {
            return 'ALL';
        } else {
            throw new Error('Invalid argument for top()');
        }
    }

    if (parsed > 0) {
        return top;
    } else {
        throw new Error('Invalid argument for top()');
    }
};

TopStartAtBlock.prototype._sanitizeStartAt = function(start) {  
    var parsed = parseInt(start);
    if (isNaN(parsed)) {
        throw new Error('Invalid argument for startAt()');
    }

    if (parsed > 0) {
        return start;
    } else {
        throw new Error('Invalid argument for startAt()');
    }
};

TopStartAtBlock.prototype.top = function(top) {  
    this._top = this._sanitizeTop(top);
};

TopStartAtBlock.prototype.startAt = function(start) {  
    this._start = this._sanitizeStartAt(start);
};

The top and startAt methods are simply setters. The sanitation methods are checking for non-numeric values that are less than one (with an exception for “ALL” as a TOP argument). If the input value fails sanitation, an error should be thrown.

Build the clause

Next, we will implement the buildStr method which will build and return the query clause.

TopStartAtBlock.prototype.buildStr = function() {  
    // Error check. Cannot have START AT without a TOP.
    if (this._start && !this._top) {
        throw new Error('Must call top() along with startAt()');
    }

    var clause = '';

    if (this._top) {
        clause = 'TOP ' + this._top;
    }

    if (this._start) {
        clause += ' START AT ' + this._start;
    }

    return clause;
}

buildStr is a pretty straightforward method. First, you’ll see error checking. Do not someone to build a query like SELECT START AT 1 * FROM Items; that is improper syntax.

The next thing to point out is that clause is initialized as an empty string. An empty string should be returned from your the buildStr method if none of your new query building methods are called. If you return null or undefined from buildStr then a TypeError will be thrown with a stack trace along the lines of:

TypeError: Cannot read property 'length' of undefined  
    at /home/bostrt/node_modules/squel/squel.js:1263:21
    at Array.filter (native)
    at Select.cls.QueryBuilder.QueryBuilder.toString (/home/bostrt/node_modules/squel/squel.js:1262:22)
    at repl:1:35
    at REPLServer.self.eval (repl.js:110:21)
    ...

Connect to Squel.js

Now lets connect the plugin to Squel.js.

I’m going to define an alternative SELECT query builder called selectTop for the squel-top-start-at plugin.

exports.selectTop = squel.selectTop = function(options) {  
    var allowNestedOptions = options || {};
    allowNestedOptions['allowNested'] = true;

    return squel.select(options, [
        new squel.cls.StringBlock(options, 'SELECT'),
        new TopStartAtBlock(options),
        new squel.cls.DistinctBlock(options),
        new squel.cls.GetFieldBlock(options),
        new squel.cls.FromTableBlock(allowNestedOptions),
        new squel.cls.JoinBlock(allowNestedOptions),
        new squel.cls.WhereBlock(options),
        new squel.cls.GroupByBlock(options),
        new squel.cls.OrderByBlock(options),
        new squel.cls.LimitBlock(options),
        new squel.cls.OffsetBlock(options)
        ]);
};

The function above has all of the same building blocks as the standard SELECT query builder in Squel.js except for the addition of the new TopStartAtBlock. Also, notice that exports.selectTop and squel.selectTop are both assigned to the new/alternative SELECT query builder.

All done

That’s it. Squel.js makes it very easy to extend its query building mechanism. Check out the complete source code for the squel-top-stat-at plugin by going to: https://github.com/bostrt/squel-top-start-at

If you have any questions about building a Squel.js plugin or about the squel-top-start-at plugin contact me @robertbost or comment below. Thanks for reading.

Example Usage
// Require squel before requring squel-top-start-at plugin.
var squel = require('squel');  
var selectTop = require('squel-top-start-at').selectTop;

var query = selectTop.top(10).startAt(1).from('Item').toString;  
// query => SELECT TOP 10 START AT 1 FROM Item

query = selectTop.top(25).from('Customer').toString();  
// query => SELECT TOP 25 * FROM Customer

query = selectTop.first().from('Item').toString();  
// query => SELECT FIRST * FROM Item
The plugin is also connected directly to Squel.js
// selectTop is also directly connected to squel
var squel = require('squel');  
require('squel-top-start-at');

var query = squel.selectTop().top(10).startAt(100).from('PhoneNumber').toString();  
// query => SELECT TOP 10 START AT 100 * FROM PhoneNumber
query = selectTop.top(25).from('Customer').toString(); // query => SELECT TOP 25 * FROM Customer query = selectTop.first().from('Item').toString(); // query => SELECT FIRST * FROM Item 
The plugin is also connected directly to Squel.js
// selectTop is also directly connected to squel
var squel = require('squel');  
require('squel-top-start-at');

var query = squel.selectTop().top(10).startAt(100).from('PhoneNumber').toString();  
// query => SELECT TOP 10 START AT 100 * FROM PhoneNumber