Tuesday, May 06, 2008

Reluctant Sorting Algorithms Demonstration (Java Applets)

This is a follow-up of another recent article, Reluctant Sorting Algorithms. Hereby I present visualization of neglection and desertion sorting algorithms, written as Java applets. Unfortunately the demonstration doesn't look as nice as Erlang source code. I'd even say, the demonstration shows that these algorithms suck! So better admire the beauty of their source code in Erlang.

Demo

Click on an applet to start (you may need to click twice in IE).


Neglection sort


Desertion sort

Source code

This program is free software; you can redistribute it and/or modify it under the MIT/X11 License.

If you're going to make these applets run in the local environment, you'll also need SortAlgorithm and SortItem classes, both grabbed from Sorting Algorithms Demo by James Gosling, Jason Harrison, Jim Boritz et al.

Sunday, May 04, 2008

Erlang Template Engine (Prototype)

Some may argue, that it is pointless to write one's own template engine. But what if there's no suitable one? Common template engines are too heavy, provide enormous functionality, most of which is unnecessary rubbish, if you use templates right. What do I mean by right use of templates? To answer this question, I would like you to answer another one: what templates are intended for? Templates are intended for representation, hence must not include any logic. Logic is for developers, templates are for designers. Only template engines following this concept but still fully-functional I'm aware of are PHPLib's Template and Google CTemplate. Update: Plus Template::Simple for Perl.

Several years ago I wrote a template engine in Perl, which used PHPLib syntax, but had object-oriented approach for templates, so that every template or block inside a template was an object. If I get round to that, I'll clean up the code and post it in this blog later, and perhaps switch to Google CTemplate syntax, which I discovered recently.

If we deal with an object-oriented language, the natural way of representing a template is wrapping it into an object, using object's properties for template's variables and regarding nested templates as nested objects.

Erlang is a functional programming language. What is the natural way to express anything in a functional programming language? Right, wrap it into a function! In this article I present my experiment of creating a template engine using functional paradigm.

My Erlang template engine uses Google CTemplate syntax. Template variables are expressed through function arguments, and nested templates are expressed through descent calls to other functions.

% et - Erlang template engine
% Copyright (c) 2008 Ivan Fomichev
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, including without limitation the rights
% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
% copies of the Software, and to permit persons to whom the Software is
% furnished to do so, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included in
% all copies or substantial portions of the Software.
%
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
% THE SOFTWARE.

-module(et).
-export([from_file/3, do/4, arg/2, set_arg/3, none/2, dict/2, switch/5, foreach/4]).

from_file(Logic, Filename, Args) ->
    case file:read_file(Filename) of
        {ok, Binary} -> Logic(binary_to_list(Binary), Args);
        Error -> throw(Error)
    end.

do(Logic, Template, Section, Args) ->
    validate_name(Section),
    
    StartRx = "{{#" ++ Section ++ "}}[ \t]*(\r?\n|\n)?",
    EndRx   = "{{/" ++ Section ++ "}}[ \t]*(\r?\n|\n)?",
    
    case regexp:match(Template, StartRx) of
        {match, StartPos, StartLength} ->
            Rest = string:substr(Template, StartPos + StartLength),
            case regexp:match(Rest, EndRx) of
                {match, EndPos, EndLength} ->
                    Template2 = lists:sublist(Rest, EndPos - 1),
                    Template3 = lists:sublist(Template, StartPos - 1) ++
                        Logic(Template2, Args) ++
                        string:substr(Rest, EndPos + EndLength),
                    dict(Template3, Args);
                        
                nomatch -> throw({template, "No such section " ++ Section})
            end;
        nomatch -> throw({template, "No such section " ++ Section})
    end.

validate_name(Name) ->
    Allowed = lists:seq($0, $9) ++ lists:seq($A, $Z) ++ "_" ++ lists:seq($a, $z),
    AllowedLen = string:span(Name, Allowed),
    if
        AllowedLen == length(Name) -> ok;
        true -> throw({template, "Invalid identifier " ++ Name})
    end.

arg(Key, Args) ->
    case lists:keysearch(Key, 1, Args) of
        {value, {_, Value}} -> Value;
        _ -> undefined
    end.

set_arg(Key, Value, Args) ->
    lists:keystore(Key, 1, Args, {Key, Value}).
    
arg_sort(A, B) ->
    KeyA = element(1, A),
    KeyB = element(1, B),
    KeyA =< KeyB.

none(_, _) -> "".

dict("", _) -> "";

dict(Template, []) -> Template;

dict(Template, [{Name, Value} | T]) ->
    validate_name(Name),
    Rx = "{{" ++ Name ++ "}}",
    Replacement = if
        is_list(Value) -> Value;
        is_float(Value) -> hd(io_lib:format("~g", [Value])); % TODO: choose precision
        is_integer(Value) -> integer_to_list(Value);
        true -> ""
    end,
    case regexp:gsub(Template, Rx, Replacement) of
        {ok, Result, _} -> dict(Result, T)
    end.

switch(_, Template, Section, Args, false) -> do(fun none/2, Template, Section, Args);

switch(Logic, Template, Section, Args, true) -> do(Logic, Template, Section, Args).

foreach_fun(_, "", _, _, _) -> "";

foreach_fun(_, _, [], _, Acc) -> lists:flatten(lists:reverse(Acc));

foreach_fun(Logic, Template, [Args | T], I, Acc) ->
    Args2 = lists:umerge(fun arg_sort/2,
        lists:usort(fun arg_sort/2, [
                {"__i", I},
                {"__first", I =:= 1},
                {"__last", T =:= []},
                {"__odd", I rem 2 =:= 1},
                {"__even", I rem 2 =:= 0}
            ]),
        lists:usort(fun arg_sort/2, Args)),
    Result = Logic(Template, Args2),
    foreach_fun(Logic, Template, T, I + 1, [Result | Acc]).
    
foreach(Logic, Template, Section, Args) ->
    do(fun(Template2, Args2) ->
            Data = arg(Section, Args2),
            foreach_fun(Logic, Template2, Data, 1, [])
        end,
        Template, Section, Args).

Simple example

Let's use Google CTemplate's example for demonstration:

Hello {{name}}
You have just won ${{value}}!
{{#in_ca}}
Well, ${{taxed_value}}, after taxes.
{{/in_ca}}

To animate this template, we write a view module:

-module(example).
-export([view/1]).

view(Args) ->
    et:from_file(fun example/2, "example.tpl", Args).

example(Template, Args) ->
    Bool = et:arg("in_ca", Args),
    et:switch(fun in_ca/2, Template, "in_ca", Args, Bool).

in_ca(Template, Args) ->
    TaxedValue = et:arg("value", Args) * 0.83,
    Args2 = et:set_arg("taxed_value", TaxedValue, Args),
    et:dict(Template, Args2).

Invoked with arguments, links:view returns rendered template:

1> c(et).
{ok,et}
2> c(example).
{ok,example}
3> io:format(example:view([{"name", "John Smith"}, {"value", 25.60}, {"in_ca", true}]), []).
Hello John Smith
You have just won $25.6000!
Well, $21.2480, after taxes.
ok

Complex example

Here's something more complex:

<h1>{{header}}</h1>
{{#list}}
<ul>
{{#item}}
{{#current}}
    <li><strong>{{name}}</strong></li>
{{/current}}
{{#link}}
    <li><a href="{{url}}">{{name}}</a></li>
{{/link}}
{{/item}}
</ul>
{{/list}}
{{#empty}}
<p>The list is empty.</p>
{{/empty}}

And the corresponding code:

-module(links).
-export([view/1]).

view(Args) ->
    et:from_file(fun links/2, "links.tpl", Args).

links(Template, Args) ->
    Empty = et:arg("item", Args) =:= [],
    Result = et:switch(fun list/2, Template, "list", Args, not Empty),
    et:switch(fun et:dict/2, Result, "empty", Args, Empty).

list(Template, Args) ->
    et:foreach(fun item/2, Template, "item", Args).

item(Template, Args) ->
    Current = et:arg("current", Args),
    Result = et:switch(fun et:dict/2, Template, "current", Args, Current),
    et:switch(fun et:dict/2, Result, "link", Args, not Current).

This is how it works:

4> c(links).
{ok,links}
5> io:format(links:view([
5>     {"header", "Colors"},
5>     {"item", [
5>         [
5>             {"name", "red"},
5>             {"current", true},
5>             {"url", "#Red"}
5>         ],
5>         [
5>             {"name", "green"},
5>             {"current", false},
5>             {"url", "#Green"}
5>         ]
5>     ]}
5> ]), []).
<h1>Colors</h1>
<ul>
    <li><strong>red</strong></li>
    <li><a href="#Green">green</a></li>
</ul>
ok
6> io:format(links:view([{"header", "Colors"}, {"item", []}]), []).
<h1>Colors</h1>
<p>The list is empty.</p>
ok

Ideas

  • Better diagnostics
  • Filters (HTML, URL, JavaScript etc.) and formats (date, float, etc.)
  • Performance?

If you've found this module useful, please let me know. It will encourage me to develop this into more than a prototype :-)

Copyright

All source code in this article is free software; you can redistribute it and/or modify it under the MIT/X11 License:

Copyright (c) 2008 Ivan Fomichev

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

Friday, April 25, 2008

JavaScript Creole 1.0 Wiki Markup Parser

Update. If you look for a server-side lightweight wiki engine solution, you may be interested in my PHP port of this wiki parser.

Source code

This program is free software; you can redistribute it and/or modify it under the MIT/X11 License.

/*
 * JavaScript Creole 1.0 Wiki Markup Parser
 * $Id: creole.js 14 2009-03-21 16:15:08Z ifomichev $
 *
 * Copyright (c) 2009 Ivan Fomichev
 *
 * Portions Copyright (c) 2007 Chris Purcell
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

if (!Parse) { var Parse = {}; }
if (!Parse.Simple) { Parse.Simple = {}; }

Parse.Simple.Base = function(grammar, options) {
    if (!arguments.length) { return; }

    this.grammar = grammar;
    this.grammar.root = new this.ruleConstructor(this.grammar.root);
    this.options = options;
};

Parse.Simple.Base.prototype = {
    ruleConstructor: null,
    grammar: null,
    options: null,

    parse: function(node, data, options) {
        if (options) {
            for (i in this.options) {
                if (typeof options[i] == 'undefined') { options[i] = this.options[i]; }
            }
        }
        else {
            options = this.options;
        }
        data = data.replace(/\r\n?/g, '\n');
        this.grammar.root.apply(node, data, options);
        if (options && options.forIE) { node.innerHTML = node.innerHTML.replace(/\r?\n/g, '\r\n'); }
    }
};

Parse.Simple.Base.prototype.constructor = Parse.Simple.Base;

Parse.Simple.Base.Rule = function(params) {
    if (!arguments.length) { return; }

    for (var p in params) { this[p] = params[p]; }
    if (!this.children) { this.children = []; }
};

Parse.Simple.Base.prototype.ruleConstructor = Parse.Simple.Base.Rule;

Parse.Simple.Base.Rule.prototype = {
    regex: null,
    capture: null,
    replaceRegex: null,
    replaceString: null,
    tag: null,
    attrs: null,
    children: null,

    match: function(data, options) {
        return data.match(this.regex);
    },

    build: function(node, r, options) {
        var data;
        if (this.capture !== null) {
            data = r[this.capture];
        }

        var target;
        if (this.tag) {
            target = document.createElement(this.tag);
            node.appendChild(target);
        }
        else { target = node; }

        if (data) {
            if (this.replaceRegex) {
                data = data.replace(this.replaceRegex, this.replaceString);
            }
            this.apply(target, data, options);
        }

        if (this.attrs) {
            for (var i in this.attrs) {
                target.setAttribute(i, this.attrs[i]);
                if (options && options.forIE && i == 'class') { target.className = this.attrs[i]; }
            }
        }
        return this;
    },

    apply: function(node, data, options) {
        var tail = '' + data;
        var matches = [];

        if (!this.fallback.apply) {
            this.fallback = new this.constructor(this.fallback);
        }

        while (true) {
            var best = false;
            var rule  = false;
            for (var i = 0; i < this.children.length; i++) {
                if (typeof matches[i] == 'undefined') {
                    if (!this.children[i].match) {
                        this.children[i] = new this.constructor(this.children[i]);
                    }
                    matches[i] = this.children[i].match(tail, options);
                }
                if (matches[i] && (!best || best.index > matches[i].index)) {
                    best = matches[i];
                    rule = this.children[i];
                    if (best.index == 0) { break; }
                }
            }
                
            var pos = best ? best.index : tail.length;
            if (pos > 0) {
                this.fallback.apply(node, tail.substring(0, pos), options);
            }
            
            if (!best) { break; }

            if (!rule.build) { rule = new this.constructor(rule); }
            rule.build(node, best, options);

            var chopped = best.index + best[0].length;
            tail = tail.substring(chopped);
            for (var i = 0; i < this.children.length; i++) {
                if (matches[i]) {
                    if (matches[i].index >= chopped) {
                        matches[i].index -= chopped;
                    }
                    else {
                        matches[i] = void 0;
                    }
                }
            }
        }

        return this;
    },

    fallback: {
        apply: function(node, data, options) {
            if (options && options.forIE) {
                // workaround for bad IE
                data = data.replace(/\n/g, ' \r');
            }
            node.appendChild(document.createTextNode(data));
        }
    }    
};

Parse.Simple.Base.Rule.prototype.constructor = Parse.Simple.Base.Rule;

Parse.Simple.Creole = function(options) {
    var rx = {};
    rx.link = '[^\\]|~\\n]*(?:(?:\\](?!\\])|~.)[^\\]|~\\n]*)*';
    rx.linkText = '[^\\]~\\n]*(?:(?:\\](?!\\])|~.)[^\\]~\\n]*)*';
    rx.uriPrefix = '\\b(?:(?:https?|ftp)://|mailto:)';
    rx.uri = rx.uriPrefix + rx.link;
    rx.rawUri = rx.uriPrefix + '\\S*[^\\s!"\',.:;?]';
    rx.interwikiPrefix = '[\\w.]+:';
    rx.interwikiLink = rx.interwikiPrefix + rx.link;
    rx.img = '\\{\\{((?!\\{)[^|}\\n]*(?:}(?!})[^|}\\n]*)*)' +
             (options && options.strict ? '' : '(?:') + 
             '\\|([^}~\\n]*((}(?!})|~.)[^}~\\n]*)*)' +
             (options && options.strict ? '' : ')?') +
             '}}';

    var formatLink = function(link, format) {
        if (format instanceof Function) {
            return format(link);
        }

        format = format instanceof Array ? format : [ format ];
        if (typeof format[1] == 'undefined') { format[1] = ''; }
        return format[0] + link + format[1];
    };

    var g = {
        hr: { tag: 'hr', regex: /(^|\n)\s*----\s*(\n|$)/ },

        br: { tag: 'br', regex: /\\\\/ },
        
        preBlock: { tag: 'pre', capture: 2,
            regex: /(^|\n)\{\{\{\n((.*\n)*?)\}\}\}(\n|$)/,
            replaceRegex: /^ ([ \t]*\}\}\})/gm,
            replaceString: '$1' },
        tt: { tag: 'tt',
            regex: /\{\{\{(.*?\}\}\}+)/, capture: 1,
            replaceRegex: /\}\}\}$/, replaceString: '' },

        ulist: { tag: 'ul', capture: 0,
            regex: /(^|\n)([ \t]*\*[^*#].*(\n|$)([ \t]*[^\s*#].*(\n|$))*([ \t]*[*#]{2}.*(\n|$))*)+/ },
        olist: { tag: 'ol', capture: 0,
            regex: /(^|\n)([ \t]*#[^*#].*(\n|$)([ \t]*[^\s*#].*(\n|$))*([ \t]*[*#]{2}.*(\n|$))*)+/ },
        li: { tag: 'li', capture: 0,
            regex: /[ \t]*([*#]).+(\n[ \t]*[^*#\s].*)*(\n[ \t]*\1[*#].+)*/,
            replaceRegex: /(^|\n)[ \t]*[*#]/g, replaceString: '$1' },

        table: { tag: 'table', capture: 0,
            regex: /(^|\n)(\|.*?[ \t]*(\n|$))+/ },
        tr: { tag: 'tr', capture: 2, regex: /(^|\n)(\|.*?)\|?[ \t]*(\n|$)/ },
        th: { tag: 'th', regex: /\|+=([^|]*)/, capture: 1 },
        td: { tag: 'td', capture: 1,
            regex: '\\|+([^|~\\[{]*((~(.|(?=\\n)|$)|' +
                   '\\[\\[' + rx.link + '(\\|' + rx.linkText + ')?\\]\\]' +
                   (options && options.strict ? '' : '|' + rx.img) +
                   '|[\\[{])[^|~]*)*)' },

        singleLine: { regex: /.+/, capture: 0 },
        paragraph: { tag: 'p', capture: 0,
            regex: /(^|\n)([ \t]*\S.*(\n|$))+/ },
        text: { capture: 0, regex: /(^|\n)([ \t]*[^\s].*(\n|$))+/ },

        strong: { tag: 'strong', capture: 1,
            regex: /\*\*([^*~]*((\*(?!\*)|~(.|(?=\n)|$))[^*~]*)*)(\*\*|\n|$)/ },
        em: { tag: 'em', capture: 1,
            regex: '\\/\\/(((?!' + rx.uriPrefix + ')[^\\/~])*' +
                   '((' + rx.rawUri + '|\\/(?!\\/)|~(.|(?=\\n)|$))' +
                   '((?!' + rx.uriPrefix + ')[^\\/~])*)*)(\\/\\/|\\n|$)' },

        img: { regex: rx.img,
            build: function(node, r, options) {
                var img = document.createElement('img');
                img.src = r[1];
                img.alt = r[2] === undefined
                    ? (options && options.defaultImageText ? options.defaultImageText : '')
                    : r[2].replace(/~(.)/g, '$1');
                node.appendChild(img);
            } },

        namedUri: { regex: '\\[\\[(' + rx.uri + ')\\|(' + rx.linkText + ')\\]\\]',
            build: function(node, r, options) {
                var link = document.createElement('a');
                link.href = r[1];
                if (options && options.isPlainUri) {
                    link.appendChild(document.createTextNode(r[2]));
                }
                else {
                    this.apply(link, r[2], options);
                }
                node.appendChild(link);
            } },

        namedLink: { regex: '\\[\\[(' + rx.link + ')\\|(' + rx.linkText + ')\\]\\]',
            build: function(node, r, options) {
                var link = document.createElement('a');
                
                link.href = options && options.linkFormat
                    ? formatLink(r[1].replace(/~(.)/g, '$1'), options.linkFormat)
                    : r[1].replace(/~(.)/g, '$1');
                this.apply(link, r[2], options);
                
                node.appendChild(link);
            } },

        unnamedUri: { regex: '\\[\\[(' + rx.uri + ')\\]\\]',
            build: 'dummy' },
        unnamedLink: { regex: '\\[\\[(' + rx.link + ')\\]\\]',
            build: 'dummy' },
        unnamedInterwikiLink: { regex: '\\[\\[(' + rx.interwikiLink + ')\\]\\]',
            build: 'dummy' },

        rawUri: { regex: '(' + rx.rawUri + ')',
            build: 'dummy' },

        escapedSequence: { regex: '~(' + rx.rawUri + '|.)', capture: 1,
            tag: 'span', attrs: { 'class': 'escaped' } },
        escapedSymbol: { regex: /~(.)/, capture: 1,
            tag: 'span', attrs: { 'class': 'escaped' } }
    };
    g.unnamedUri.build = g.rawUri.build = function(node, r, options) {
        if (!options) { options = {}; }
        options.isPlainUri = true;
        g.namedUri.build.call(this, node, Array(r[0], r[1], r[1]), options);
    };
    g.unnamedLink.build = function(node, r, options) {
        g.namedLink.build.call(this, node, Array(r[0], r[1], r[1]), options);
    };
    g.namedInterwikiLink = { regex: '\\[\\[(' + rx.interwikiLink + ')\\|(' + rx.linkText + ')\\]\\]',
        build: function(node, r, options) {
                var link = document.createElement('a');
                
                var m, f;
                if (options && options.interwiki) {
                m = r[1].match(/(.*?):(.*)/);
                f = options.interwiki[m[1]];
            }
            
            if (typeof f == 'undefined') {
                if (!g.namedLink.apply) {
                    g.namedLink = new this.constructor(g.namedLink);
                }
                return g.namedLink.build.call(g.namedLink, node, r, options);
            }

            link.href = formatLink(m[2].replace(/~(.)/g, '$1'), f);
            
            this.apply(link, r[2], options);
            
            node.appendChild(link);
        }
    };
    g.unnamedInterwikiLink.build = function(node, r, options) {
        g.namedInterwikiLink.build.call(this, node, Array(r[0], r[1], r[1]), options);
    };
    g.namedUri.children = g.unnamedUri.children = g.rawUri.children =
            g.namedLink.children = g.unnamedLink.children =
            g.namedInterwikiLink.children = g.unnamedInterwikiLink.children =
        [ g.escapedSymbol, g.img ];

    for (var i = 1; i <= 6; i++) {
        g['h' + i] = { tag: 'h' + i, capture: 2,
            regex: '(^|\\n)[ \\t]*={' + i + '}[ \\t]' +
                   '([^~]*?(~(.|(?=\\n)|$))*)[ \\t]*=*\\s*(\\n|$)'
        };
    }

    g.ulist.children = g.olist.children = [ g.li ];
    g.li.children = [ g.ulist, g.olist ];
    g.li.fallback = g.text;

    g.table.children = [ g.tr ];
    g.tr.children = [ g.th, g.td ];
    g.td.children = [ g.singleLine ];
    g.th.children = [ g.singleLine ];

    g.h1.children = g.h2.children = g.h3.children =
            g.h4.children = g.h5.children = g.h6.children =
            g.singleLine.children = g.paragraph.children =
            g.text.children = g.strong.children = g.em.children =
        [ g.escapedSequence, g.strong, g.em, g.br, g.rawUri,
            g.namedUri, g.namedInterwikiLink, g.namedLink,
            g.unnamedUri, g.unnamedInterwikiLink, g.unnamedLink,
            g.tt, g.img ];

    g.root = {
        children: [ g.h1, g.h2, g.h3, g.h4, g.h5, g.h6,
            g.hr, g.ulist, g.olist, g.preBlock, g.table ],
        fallback: { children: [ g.paragraph ] }
    };

    Parse.Simple.Base.call(this, g, options);
};

Parse.Simple.Creole.prototype = new Parse.Simple.Base();

Parse.Simple.Creole.prototype.constructor = Parse.Simple.Creole;

Wednesday, April 23, 2008

Reluctant Sorting Algorithms

I would like to present you two new sorting algorithms. They wholly follow spirit of multiply and surrender paradigm and still are damn beautiful. Unlike such infamous algorithms as bogosort or bozo sort, these algorithms are truly eager to achieve the result, even though not the speediest way.

Neglection sort

The first one is neglection sort. As follows from its name, it is a representative of the selection sort family with a strong reluctant flavor. A general selection sorting algorithm consists of the following steps:

  1. Find the minimum element in the list
  2. Put the element in the beginning of the list
  3. Repeat from the step 1 for the rest of the list until it's empty

This is expressed in Erlang just straightly:

sort(List) -> sort(List, []).

sort([], Acc) -> lists:reverse(Acc);

sort(List, Acc) ->
  {Min, Rest} = select(List),
  sort(Rest, [Min | Acc]).

Variations of the selection sort (such as heapsort) differ from each other in definition of the select function. For neglection sort, we define it multiply-and-surrender way:

  1. Remove the first element from the list and sort the list using neglection sort
  2. If the list is not empty and the first element of the sorted list is less than the removed element, return the first element, otherwise return the removed element

Let's implement it in Erlang. We name the function neglect, as it is the very heart of the algorithm, then the whole algorithm reads as follows:

-module(neglection_sort).
-export([sort/1]).

sort(List) -> sort(List, []).

sort([], Acc) -> lists:reverse(Acc);

sort(List, Acc) ->
  {Min, Rest} = neglect(List),
  sort(Rest, [Min | Acc]).

neglect([H | T]) -> neglect(H, sort(T)).

neglect(H, [Min | Rest]) when Min < H -> {Min, [H | Rest]};

neglect(H, Acc) -> {H, Acc}.

The complexity of the neglection sort is perfectly exponential, Ο(cn).

Desertion sort

As it is clear from the name, desertion sort is an essentially reluctant algorithm, designed after the insertion sort. It is well known, that a general insertion sorting algorithm can be expressed the following way:

  1. Remove the first element from the list and insert it into the right place
  2. Repeat the algorithm for the rest of the list

It is being implemented in Erlang as natural as in speech:

sort(List) -> sort(List, []).

sort([], Acc) -> Acc;

sort([H | T], Acc) -> sort(T, insert(H, Acc)).

The only thing having been left is to define the insert function. Let's do it the reluctant way, backward recursion is always good at it:

  1. Unless the element to insert is less than the first element of the list, then replace the first element of the list with the element to insert, sort the list with desertion sort, and return the former first element of the list and the sorted list as a whole list
  2. Otherwise return the element and the list as a whole list

Though it is not very clear in English language, the glorious Erlang puts everything on its place (and, of course, we name the engine function desert):

-module(desertion_sort).
-export([sort/1]).

sort(List) -> sort(List, []).

sort([], Acc) -> Acc;

sort([H | T], Acc) -> sort(T, desert(H, Acc)).

desert(Elem, [H | T]) when Elem >= H -> [H | sort([Elem | T])];

desert(Elem, Acc) -> [Elem | Acc].

Magnificent! Desertion sort has complexity of Ο(cn) as well!

To be continued…

See also

There is a list of related algorithms, besides above mentioned bogosort and bozo-sort.

  • Bogobogosort by David Morgan-Mar
  • Hanoi sort by David Morgan-Mar
  • Slowsort by Andrei Broder and Jorge Stolfi, in “Pessimal Algorithms and Simplexity Analysis”

Notes

  • If you are aware of a prior work that describes either algorithm, please make comment on this post
  • All source code in this article is free software; you can redistribute it and/or modify it under the MIT/X11 License:
    Copyright (c) 2008 Ivan Fomichev
    
    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:
    
    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.

Saturday, March 29, 2008

xorg.conf Cyrillic Keyboard Configuration

        Option          "XkbLayout"     "us,ru(winkeys)"
        Option          "XkbVariant"    "base"
        Option          "XkbOptions"    "grp:alt_shift_toggle"

The first line adopts Windows keyboard cyrillic layout for Russian, the second line allows using hotkeys like <Ctrl>+C while being in Russian layout, the third line adopts Windows' <Alt>+<Shift> key for switching between keyboard layouts.