stengerh/shuffler.html

## shuffler.html
<!DOCTYPE html>
<html>
<head>
    <title>Shuffler Test</title>
    <script type="text/javascript" src="shuffler.js"></script>
</head>
<body>
    <h1>Shuffler</h1>
    <p>See <a href="http://www.tedunangst.com/flak/post/efficient-uniform-shuffling">Efficient Uniform Shuffling</a>.

    <h2>Test Code</h2>
    <pre id="test-code"></pre>

    <h2>Output</h2>
    <pre id="test-output"></pre>
    <p>Time taken: <span id="test-time"></span> seconds</p>
    <script type="text/javascript" src="shufflertest.js"></script>

    <h2>Source Code</h2>
    <ul>
        <li>shuffler.html (this file)</li>
        <li><a href="shuffler.js">shuffler.js</a></li>
        <li><a href="shufflertest.js">shufflertest.js</a></li>
    </ul>
</body>
</html>

## shuffler.js
(function () {
    "use strict";

    function fyshuffle (items) {
        for (var i = items.length - 1; i >= 1; --i) {
            var j = Math.floor(Math.random() * (i + 1));
            var temp = items[j];
            items[j] = items[i];
            items[i] = temp;
        }
    }

    function insert(spl, item, pos) {
        while (true) {
            while (pos >= spl.size) {
                pos = pos - spl.size;
            }
            if (spl.items[pos] === undefined) {
                spl.items[pos] = item;
                break;
            }
            pos = pos + 1;
        }
    }

    var Shuffler = function (size, spacing) {
        if (spacing === undefined) {
            spacing = 8;
        }

        this.size = size * spacing;
        this.items = new Array();
    };

    Shuffler.prototype.add = function (items) {
        var gap = this.size / items.length;
        var start = Math.floor(Math.random() * this.size);
        fyshuffle(items);
        for (var i = 0; i < items.length; ++i) {
            var pos = Math.floor(start + (i * gap) + Math.random() * Math.floor(gap * 2 / 3));
            insert(this, items[i], pos);
        }
    }

    Shuffler.prototype.finish = function () {
        var pl = new Array();
        for (var i = 0; i < this.size; ++i) {
            if (this.items[i] !== undefined) {
                pl.push(this.items[i]);
            }
        }
        this.items = new Array();
        return pl;
    }

    window.Shuffler = Shuffler;
})();

## shufflertest.js
(function () {
    "use strict";

    function testgenres() {
        var spl = new Shuffler(31);
        spl.add("A A A A A A A A A A".split(" "));
        spl.add("B B B B B B B B B B B".split(" "));
        spl.add("C C C C C C C C C C C".split(" "));
        return spl.finish().join("");
    }

    function testalbums() {
        var spl = new Shuffler(11);
        spl.add("W W W W".split(" "));
        spl.add("X X".split(" "));
        spl.add("B B B".split(" "));
        spl.add("T".split(" "));
        spl.add("J".split(" "));
        return spl.finish().join("");
    }

    function testrandom() {
        var spl = new Shuffler(200000);
        for (var i = 1; i <= 20000; ++i) {
            spl.add(["s" + i]);
        }
        for (var i = 1; i <= 8000; ++i) {
            var size = 8 + Math.floor(Math.random() * 7);
            var a = new Array(size);
            for (var j = 1; j <= size; ++j) {
                a[j - 1] = "a" + i + "t" + j;
            }
            spl.add(a);
        }
        return spl.finish().length;
    }

    function runtests () {
        var result = "";
        for (var i = 0; i < 4; ++i) {
            result += testgenres() + "\n";
        }
        for (var i = 0; i < 4; ++i) {
            result += testalbums() + "\n";
        }
        result += testrandom() + "\n";
        return result;
    }

    var codeElement = document.getElementById("test-code");
    var indent = "    ";
    var codeStr = indent + testgenres + "\n\n"
            + indent + testalbums + "\n\n"
            + indent + testrandom + "\n\n"
            + indent + runtests;
    codeElement.textContent = codeStr;

    var outputElement = document.getElementById("test-output");
    var start = window.performance.now();
    var outputStr = runtests();
    var end = window.performance.now();
    outputElement.textContent = outputStr;

    var timeElement = document.getElementById("test-time");
    timeElement.textContent = ((end - start) / 1000).toFixed(3);
})();
	<!DOCTYPE html>
	<html>
	<head>
	<title>Shuffler Test</title>
	<script type="text/javascript" src="shuffler.js"></script>
	</head>
	<body>
	<h1>Shuffler</h1>
	<p>See <a href="http://www.tedunangst.com/flak/post/efficient-uniform-shuffling">Efficient Uniform Shuffling</a>.

	<h2>Test Code</h2>
	<pre id="test-code"></pre>

	<h2>Output</h2>
	<pre id="test-output"></pre>
	<p>Time taken: <span id="test-time"></span> seconds</p>
	<script type="text/javascript" src="shufflertest.js"></script>

	<h2>Source Code</h2>
	<ul>
	<li>shuffler.html (this file)</li>
	<li><a href="shuffler.js">shuffler.js</a></li>
	<li><a href="shufflertest.js">shufflertest.js</a></li>
	</ul>
	</body>
	</html>
	(function () {
	"use strict";

	function fyshuffle (items) {
	for (var i = items.length - 1; i >= 1; --i) {
	var j = Math.floor(Math.random() * (i + 1));
	var temp = items[j];
	items[j] = items[i];
	items[i] = temp;
	}
	}

	function insert(spl, item, pos) {
	while (true) {
	while (pos >= spl.size) {
	pos = pos - spl.size;
	}
	if (spl.items[pos] === undefined) {
	spl.items[pos] = item;
	break;
	}
	pos = pos + 1;
	}
	}

	var Shuffler = function (size, spacing) {
	if (spacing === undefined) {
	spacing = 8;
	}

	this.size = size * spacing;
	this.items = new Array();
	};

	Shuffler.prototype.add = function (items) {
	var gap = this.size / items.length;
	var start = Math.floor(Math.random() * this.size);
	fyshuffle(items);
	for (var i = 0; i < items.length; ++i) {
	var pos = Math.floor(start + (i * gap) + Math.random() * Math.floor(gap * 2 / 3));
	insert(this, items[i], pos);
	}
	}

	Shuffler.prototype.finish = function () {
	var pl = new Array();
	for (var i = 0; i < this.size; ++i) {
	if (this.items[i] !== undefined) {
	pl.push(this.items[i]);
	}
	}
	this.items = new Array();
	return pl;
	}

	window.Shuffler = Shuffler;
	})();
	(function () {
	"use strict";

	function testgenres() {
	var spl = new Shuffler(31);
	spl.add("A A A A A A A A A A".split(" "));
	spl.add("B B B B B B B B B B B".split(" "));
	spl.add("C C C C C C C C C C C".split(" "));
	return spl.finish().join("");
	}

	function testalbums() {
	var spl = new Shuffler(11);
	spl.add("W W W W".split(" "));
	spl.add("X X".split(" "));
	spl.add("B B B".split(" "));
	spl.add("T".split(" "));
	spl.add("J".split(" "));
	return spl.finish().join("");
	}

	function testrandom() {
	var spl = new Shuffler(200000);
	for (var i = 1; i <= 20000; ++i) {
	spl.add(["s" + i]);
	}
	for (var i = 1; i <= 8000; ++i) {
	var size = 8 + Math.floor(Math.random() * 7);
	var a = new Array(size);
	for (var j = 1; j <= size; ++j) {
	a[j - 1] = "a" + i + "t" + j;
	}
	spl.add(a);
	}
	return spl.finish().length;
	}

	function runtests () {
	var result = "";
	for (var i = 0; i < 4; ++i) {
	result += testgenres() + "\n";
	}
	for (var i = 0; i < 4; ++i) {
	result += testalbums() + "\n";
	}
	result += testrandom() + "\n";
	return result;
	}

	var codeElement = document.getElementById("test-code");
	var indent = " ";
	var codeStr = indent + testgenres + "\n\n"
	+ indent + testalbums + "\n\n"
	+ indent + testrandom + "\n\n"
	+ indent + runtests;
	codeElement.textContent = codeStr;

	var outputElement = document.getElementById("test-output");
	var start = window.performance.now();
	var outputStr = runtests();
	var end = window.performance.now();
	outputElement.textContent = outputStr;

	var timeElement = document.getElementById("test-time");
	timeElement.textContent = ((end - start) / 1000).toFixed(3);
	})();