← Back to branch summary

~bcsaller/juju-gui/update-reductions

« back to all changes in this revision

Viewing changes to lib/d3/examples/sort/sort.js

  • Committer: kapil.foss at gmail
  • Date: 2012-07-13 18:45:59 UTC
  • Revision ID: kapil.foss@gmail.com-20120713184559-2xl7be17egsrz0c9
reshape

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/d3/examples/sort/sort.js
1
 
// Based on http://vis.stanford.edu/protovis/ex/sort.html
2
 
// Based on work by Robert Sedgewick
3
 
 
4
 
var width = 960,
5
 
    height = 50,
6
 
    n = 240;
7
 
 
8
 
var x = d3.scale.linear()
9
 
    .domain([0, n])
10
 
    .range([height, width - height]);
11
 
 
12
 
var a = d3.scale.linear()
13
 
    .domain([0, n - 1])
14
 
    .range([90 + 60, 270 - 60]);
15
 
 
16
 
var data = shuffle(d3.range(n)),
17
 
    duration = 250;
18
 
 
19
 
var vis = d3.select("#chart").append("svg")
20
 
    .attr("width", width)
21
 
    .attr("height", height);
22
 
 
23
 
var line = vis.selectAll("line")
24
 
    .data(data)
25
 
  .enter().append("line")
26
 
    .attr("x1", 0)
27
 
    .attr("y1", 0)
28
 
    .attr("x2", 0)
29
 
    .attr("y2", height)
30
 
    .attr("transform", transform);
31
 
 
32
 
start();
33
 
 
34
 
// Start the animation!
35
 
function start() {
36
 
  var passes = mergesort(data).reverse();
37
 
 
38
 
  update();
39
 
 
40
 
  function update() {
41
 
    var pass = passes.pop();
42
 
 
43
 
    line.data(pass, Number)
44
 
      .transition()
45
 
        .duration(duration)
46
 
        .attr("transform", transform);
47
 
 
48
 
    if (passes.length) {
49
 
      setTimeout(update, duration);
50
 
    } else {
51
 
      shuffle(data);
52
 
      setTimeout(start, duration + 4000);
53
 
    }
54
 
  }
55
 
}
56
 
 
57
 
function transform(d, i) {
58
 
  return "translate(" + x(i) + "," + height + ")rotate(" + a(d) + ")";
59
 
}
60
 
 
61
 
// Fisher-Yates shuffle
62
 
function shuffle(array) {
63
 
  var i = array.length, j, t;
64
 
  while (--i > 0) {
65
 
    j = ~~(Math.random() * (i + 1));
66
 
    t = array[j];
67
 
    array[j] = array[i];
68
 
    array[i] = t;
69
 
  }
70
 
  return array;
71
 
}
72
 
 
73
 
//
74
 
// Sorts the specified array using bottom-up mergesort, returning an array of
75
 
// arrays representing the state of the specified array after each insertion for
76
 
// each parallel pass. The first pass is performed at size = 2.
77
 
//
78
 
function mergesort(array) {
79
 
  var passes = [],
80
 
      i,
81
 
      j,
82
 
      n = array.length,
83
 
      m = 1;
84
 
 
85
 
  // double the size each pass
86
 
  while (m < array.length) {
87
 
    i = j = 0; while (i < array.length) j += merge(i, i += m, i += m);
88
 
    if (j) passes.push(array.slice());
89
 
    else m <<= 1;
90
 
  }
91
 
 
92
 
  // Merges two adjacent sorted arrays in-place.
93
 
  function merge(start, middle, end) {
94
 
    middle = Math.min(array.length, middle);
95
 
    end = Math.min(array.length, end);
96
 
    for (; start < middle; start++) {
97
 
      if (array[start] > array[middle]) {
98
 
        var v = array[start];
99
 
        array[start] = array[middle];
100
 
        insert(middle, end, v);
101
 
        return true;
102
 
      }
103
 
    }
104
 
    return false;
105
 
  }
106
 
 
107
 
  // Inserts the value v into the subarray specified by start and end.
108
 
  function insert(start, end, v) {
109
 
    while (start + 1 < end && array[start + 1] < v) {
110
 
      var tmp = array[start];
111
 
      array[start] = array[start + 1];
112
 
      array[start + 1] = tmp;
113
 
      start++;
114
 
    }
115
 
    array[start] = v;
116
 
  }
117
 
 
118
 
  return passes;
119
 
}