User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithm:linked-list [2013/05/02 19:58]
will [Options]
algorithm:linked-list [2015/02/02 08:28] (current)
Line 1: Line 1:
-[algorithm ​Linked-list]+======= λ Linked list ======
  
-====== Algorithm ======+<​nowiki>​ 
 +======= Algorithm ​=======
 <syntax js> <syntax js>
 function LinkedList() { function LinkedList() {
Line 18: Line 19:
         this.first = newFirst;         this.first = newFirst;
     },     },
-    // Removes the data from the list.+    // Removes the first instance of data from the list.
     remove: function(data) {     remove: function(data) {
         if (this.first && data === this.first.data) {         if (this.first && data === this.first.data) {
Line 25: Line 26:
         else {         else {
             var prev = this.first;             var prev = this.first;
-            while (prev !== null && ​prev.next ​&& ​prev.next.data ​!== data) {+            while (prev.next) { 
 +                if (prev.next.data ​=== data) { 
 +                    // Remove the next item by pointing to next+1 
 +                    prev.next = prev.next.next;​ 
 +                    break; 
 +                }
                 prev = prev.next;                 prev = prev.next;
-            } 
-            if (prev !== null && prev.next) { 
-                prev.next = prev.next.next;​ 
             }             }
         }         }
     }     }
-} +}</​syntax>​
-</​syntax>​+
  
-====== Support ======+======= Support ​=======
 <syntax js> <syntax js>
-// Run the algorithm source code quietly. 
-runSource();​ 
- 
 // Initial starting list. // Initial starting list.
-// Add hashes manually for now. 
 list = new LinkedList();​ list = new LinkedList();​
-list.add(8);​ list.first.hash = "A"; +list.add("8"); 
-list.add(21); list.first.hash = "B"; +list.add("21")
-list.add(3); list.first.hash "​C";​ +list.add("​3"​); 
-list.add(14); list.first.hash ​"​D"​;+list.add("14")
 + 
 +function preRun() { 
 +    if (!(list instanceof LinkedList)) { 
 +        // Copy the list from data - used for web-workers. 
 +        var mylist = new LinkedList(); 
 +        mylist.first = list.first; 
 +        // Replace the global 'list' with the converted one. 
 +        list mylist; 
 +    } 
 +}
 </​syntax>​ </​syntax>​
  
-====== Options ======+======= Tests ======= 
 +<syntax js> 
 +</​syntax>​ 
 + 
 +======= Options ​=======
 <syntax js> <syntax js>
 { {
-    "​height":​ "480px", +    ​"​title":​ "​Linked list",​ 
-    "preRunSouce": true,+    ​"​height":​ "430px", 
 +    "preRunSource": true, 
 +    "​persistentGlobals":​ ["​list"​]
 } }
 </​syntax>​ </​syntax>​
  
-====== Visualisation ======+======= Visualisation ​=======
 <syntax html> <syntax html>
 <​html>​ <​html>​
 <​head>​ <​head>​
-<script src="​http://​d3js.org/​d3.v2.js"></​script>​ +<script src="​http://​d3js.org/​d3.v3.js"></​script>​ 
-<style type='text/css'>​ +<link rel="​stylesheet" ​type="text/css" href="​algorithms-lib/list.css"/>​ 
-.data rect { +<script src="​algorithms-lib/list.js">​</script>
-  fill: #eee; +
-  stroke: #ccc; +
-+
-.ptr rect { +
-  fill: #eef; +
-  stroke: #ccf; +
-+
-.selected rect { +
-  fill: #fee; +
-  stroke: #f00; +
-+
-.arrow { +
-  stroke-width: 1; +
-  stroke: #000; +
-  fill: none; +
-  marker-end: url(#​arrow);​ +
-+
-.hidden { +
-  ​stroke:​ none; +
-  marker-end: none; +
-+
-.null { +
-  stroke-width:​ 1; +
-  stroke: #000; +
-  fill: none; +
-+
-.ptr text { +
-  font-size:​10pt;​ +
-+
-</style>+
 <​script>​ <​script>​
 function setup() { function setup() {
Line 101: Line 85:
         .attr("​width",​ 348)         .attr("​width",​ 348)
         .attr("​height",​ 400)         .attr("​height",​ 400)
-        .append("​g"​).attr("​transform",​ "​translate(0.5,0.5)");+        .append("​g"​).attr("​transform",​ "​translate(10.5, 20.5)");
     ​     ​
-    ​svg.append("svg:defs").append("​svg:marker") +    ​listVis = new ListVisualisation(svg)
-        .attr("​id", "arrow"​) +     
-        .attr("​viewBox",​ "​0 ​10 10") +    returnText = svg.append("​text") 
-        .attr("​refX", ​0) +        .attr("​dx", "​0"​) 
-        .attr("refY", 5) +        .attr("​dy", "40");
-        .attr("​markerWidth",​ 6) +
-        .attr("​markerHeight",​ 6) +
-        .attr("​orient",​ "​auto"​) +
-        .append("​svg:​path"​) +
-        .attr("​d",​ "M0,0 L10,5 L0,10 z");+
 } }
  
-var linesAtY ​{};+var listNodesToDisplay ​[]; 
 +var newNodesToDisplay = [];
  
-function orthoLineTo(node,​ node2) { +var nodeIndex ​1
-    // Returns a path as SVG string connecting node to node2. +var nodeConstructor
-    // Always returns a 4 segment path with the segments spaced out to enable better interpolation. +function idNode(node) { 
-    ​var path "M 15 0 "+    if (node.constructor ​=== nodeConstructor ​&& ​!node.hasOwnProperty("​id"​)) { 
-    var dx = node2.x - node.x+        ​node.id ​nodeIndex++
-    var dy = node2.y - node.y; +        ​return true;
-    ​ +
-    if (dy === && ​dx > 0 && dx < 160) { +
-        ​dx dx - 30-15/2+
-        ​path += "​L"​+ Math.floor(dx*0.33) + " 0 L "​+Math.floor(dx*0.66) +" 0" + "L "+dx +" 0";+
     }     }
-    ​else if (dy === 0) { +    return ​false;
-        dx = dx-15; +
-        var midy = -30; +
-        var endy = -15-5; +
-        var midyRoot = node.y+midy;​ +
- +
-        var numLines = linesAtY[midyRoot]?​ linesAtY[midyRoot] : 0; +
-        linesAtY[midyRoot] = numLines+1;​ +
-        midy += Math.ceil(numLines/​2)*3*(numLines%2?​-1:​1);​ +
- +
-        path += "L 15 "​+midy+"​ L "​+dx+"​ "​+midy+"​ L "​+dx+"​ "​+endy;​ +
-    } +
-    else if (dy !== 0) { +
-        dx = dx-15; +
-        var midy = (dy<​0?​-1:​1) * 30; +
-        var endy = (dy<​0?​1:​-1) * 20 + dy; +
-        var midyRoot = node.y+midy;​ +
- +
-        var numLines = linesAtY[midyRoot]?​ linesAtY[midyRoot] : 0; +
-        linesAtY[midyRoot] = numLines+1;​ +
-        midy += Math.ceil(numLines/​2)*3*(numLines%2?​-1:​1);​ +
- +
-        path += "L 15 "​+midy+"​ L "​+dx+"​ "​+midy+"​ L "​+dx+"​ "​+endy;​ +
-    } +
- +
-    ​return ​path;+
 } }
  
-var allNodes = []; +function ​updateList(x, clean, duration) {
-var listNodesToDisplay = []; +
-var newNodesToDisplay = []; +
- +
-function ​updateD3(x, clean, duration) {+
     var list = x.lookupInScope("​list"​);​     var list = x.lookupInScope("​list"​);​
     var listNodes = [];     var listNodes = [];
Line 166: Line 113:
     while (node) {     while (node) {
         listNodes.push(node);​         listNodes.push(node);​
-        if (newNodesToDisplay.indexOf(node)!==-1) newNodesToDisplay.splice(newNodesToDisplay.indexOf(node),​1);​+        if (newNodesToDisplay.indexOf(node)!==-1) ​
 +            ​newNodesToDisplay.splice(newNodesToDisplay.indexOf(node),​1);​ 
 +            delete node.isnew;​ 
 +        }
         node = node.next;         node = node.next;
     }     }
Line 172: Line 122:
     if (clean) {     if (clean) {
         listNodesToDisplay = listNodes;         listNodesToDisplay = listNodes;
 +        newNodesToDisplay = [];
     }     }
     else {     else {
Line 190: Line 141:
     var nodes = newNodesToDisplay.concat(listNodesToDisplay);​     var nodes = newNodesToDisplay.concat(listNodesToDisplay);​
     ​     ​
-    ​var spacing ​80+ // Position and ensure every node has an id. 
-    var d3nodes ​svg.selectAll(".data"+    ​var nX 30
-          .data(nodes, function(d) {return ""​+d.hash;});+    var nNewX 90; 
 +    var nY = 100; 
 +    for (var i=0; i<nodes.length; i++{ 
 +        ​idNode(nodes[i]); 
 +        if (nodes[i].isnew) { 
 +            nodes[i].x = nNewX; 
 +            nodes[i].y = 20; 
 +            nNewX += 60; 
 +        ​} 
 +        else { 
 +            nodes[i].x = nX; 
 +            nodes[i].y = nY; 
 +            nX += 60; 
 +            if (nX > 300
 +                nX = 30; 
 +                nY += 60; 
 +            } 
 +        } 
 +    }
     ​     ​
-    ​// Position the nodes+    ​listVis.nodesToDisplay = nodes; 
-    ​for (var i=0; i<​listNodesToDisplay.lengthi++) { +    ​listVis.pointersToDisplay ​[{value:​list.first, name:"​first",​ x:15, y:20, id:-1}]; 
-        ​var nx = i%4+    if (clean) { 
-        ​var ny Math.floor(i/4); +        ​listVis.clear(duration)
-        ​listNodesToDisplay[i].= 30 + spacing * nx+        ​timeout ​setTimeout(function() { 
-        ​listNodesToDisplay[i].y = 80 + 60 * ny;+            ​updateList(x, false, 1000)
 +        ​}, 1000);
     }     }
-    ​for (var i=0; i<​newNodesToDisplay.length;​ i++) +    ​else 
-        var nx = (i+1)%4; +    ​ listVis.update(duration); 
-        var ny = Math.floor((i+1)/4); +
-        newNodesToDisplay[i].x = 30 + spacing * nx; +
-        newNodesToDisplay[i].y = 20 + 60 * ny;+
     }     }
-     +
-    // Create any new nodes + 
-    var g = d3nodes.enter().append("​g"​) +var poppedMarker ​= {}; 
-          .attr("​class",​ "​data"​);​ +function ​globals() { 
-     +    // Return a unique marker that enables to identify when popped has not been set
-    g.append("​rect"​) +    ​return ​{"popped": ​poppedMarker};
-          .attr("​x",​ -30) +
-          .attr("​y",​ -15) +
-          .attr("​width",​ 30) +
-          .attr("​height",​ 30); +
-    g.append("​rect"​) +
-          .attr("​x",​ 0) +
-          .attr("​y",​ -15) +
-          .attr("​width",​ 30) +
-          .attr("​height",​ 30); +
-    g.append("​text"​) +
-          .attr("​class",​ "​text"​) +
-          .attr("​dx",​ "​-15"​) +
-          .attr("​dy",​ "​.35em"​) +
-          .attr("​text-anchor",​ "​middle"​);​ +
-    g.append("​svg:​path"​) +
-          .attr("​class",​ "​arrow"​) +
-          .attr("​marker-end",​ "​url(#​arrow)"​);​ +
-    g.append("​svg:​path"​) +
-          .attr("​class",​ "​null"​);​ +
-     +
-     +
-    g.attr("​transform",​ function(d, i) { +
-        return "​translate("​ + d.x + ","​ + d.y +"​)";​ +
-    ​}); +
-           +
-    // Create the pointer +
-    ​var d3ptrs ​svg.selectAll("​.ptr"​) +
-          .data([{next:​list.first,​ hash:"​first",​ x:0, y:20}], function(d) {return ""​+d.hash;​})+
-    var p = d3ptrs.enter().append("​g"​) +
-          .attr("​class",​ "​ptr"​) +
-          .attr("​transform",​ "​translate(15,​20)"​);​ +
-    p.append("​rect"​) +
-          .attr("​x",​ -15) +
-          .attr("​y",​ -15) +
-          .attr("​width",​ 30) +
-          .attr("​height",​ 30); +
-    p.append("​svg:​path"​) +
-          .attr("​class",​ "​arrow"​) +
-          .attr("​marker-end",​ "​url(#​arrow)"​) +
-          .attr("​transform",​ "​translate(-15,​0)"​);​ +
-    p.append("​svg:​path"​) +
-          .attr("​class",​ "​null"​) +
-          .attr("​transform",​ "​translate(-15,​0)"​);​ +
-    p.append("​text"​) +
-          .attr("​class",​ "​text"​) +
-          .attr("​dy",​ "​-.35em"​) +
-          .attr("​text-anchor",​ "​middle"​) +
-          .text("​first"​);​ +
-     +
-    d3nodes.transition().duration(duration).attr("​transform", ​function(d, i) { +
-        return "​translate("​ + d.x + ","​ + d.y +"​)";​ +
-    }); +
-    ​ +
-    // Update the text+
-    ​d3nodes.select("​text"​).text(function(d) ​{return d.data? ​""​+d.data ​"?"​}); +
-     +
-    // Animate arrows +
-    linesAtY = {}; +
-     +
-    function animateArrows(nodes) { +
-        nodes.filter(function(d,​ i) {return d.next}).select("​.arrow"​) +
-           ​.classed("​hidden",​ false) +
-           ​.transition().duration(duration) +
-           ​.attr("​d",​ function(d) {return orthoLineTo(d,​ d.next);​});​ +
-     +
-        nodes.filter(function(d) {return !d.next}).select("​.arrow"​) +
-              .classed("​hidden",​ true) +
-              .transition().duration(duration) +
-              .attr("​d",​ "M 15 0 L 15 0 L 15 0 L 15 0"); +
-     +
-        // Animate nulls +
-        nodes.select("​.null"​) +
-              .attr("​d",​ function(d) { +
-                  if (d.next) return "M 15 0"; +
-                  else return "M 1 -15 L 30 15 M 0 15 L 30 -15";​ +
-              }); +
-    } +
-     +
-    animateArrows(d3nodes);​ +
-    animateArrows(d3ptrs);​ +
-     +
-    // update & delete +
-    d3nodes.exit().transition().attr("​opacity",​ 0).remove();​ +
-     +
-    // highlight the prev node +
-    var prev = x.lookupInScope("​prev"​);​ +
-    d3nodes.classed("​selected",​ function(d) {return d===prev;});+
 } }
  
 var hasRun = false; var hasRun = false;
-var nodeIndex = 0;+var timeout;
 function update(n, x, isRunning, duration) { function update(n, x, isRunning, duration) {
-    // Add a unique hash to all nodes created. +    // Capture new nodes created. 
-    ​var nodeC = x.lookupInScope("​LinkedList"​).Node;​ +    ​nodeConstructor ​= x.lookupInScope("​LinkedList"​).Node;​ 
-    if (x.thisObject.constructor === nodeC && !x.thisObject.hash) { +    if (idNode(x.thisObject)) {
-        x.thisObject.hash = ""​+nodeIndex;​ +
-        nodeIndex++;​+
         if (newNodesToDisplay.indexOf(x.thisObject) === -1 && listNodesToDisplay.indexOf(x.thisObject) === -1) {         if (newNodesToDisplay.indexOf(x.thisObject) === -1 && listNodesToDisplay.indexOf(x.thisObject) === -1) {
             newNodesToDisplay.push(x.thisObject);​             newNodesToDisplay.push(x.thisObject);​
 +            x.thisObject.isnew = true;
         }         }
     }     }
     ​     ​
-    ​// Update the d3 visualisation. +    ​updateList(x, false, duration);
-    updateD3(x, false, duration);+
     ​     ​
-    ​var clean = !n; // clean out old nodes when no ast-node (ie. end of running) +    if (!isRunning ​&& hasRun ​&& !timeout) { 
-    ​if (clean && hasRun) { +        ​timeout = setTimeout(function() { 
-        setTimeout(function() {updateD3(x, true, 1000)}, ​3000);+            updateList(x, true, 1000)
 +        ​}, 2000)
 +    } 
 +    else if (timeout) { 
 +        window.clearTimeout(timeout);​ 
 +        timeout = undefined;
     }     }
     hasRun = true;     hasRun = true;
Line 326: Line 209:
     document.getElementById("​addButton"​).disabled = isRunning;     document.getElementById("​addButton"​).disabled = isRunning;
     document.getElementById("​removeButton"​).disabled = isRunning;     document.getElementById("​removeButton"​).disabled = isRunning;
 +    ​
 +    ​
 +    var prevNode = x.lookupInScope("​prev"​);​
 +    ​
 +    svg.selectAll("​.data"​).classed("​selected",​ function(d) {return d===prevNode;​});​
 } }
-function ​addNode() { + 
-    ​runScript("​list.add("​+ ​document.getElementById('​input'​).value +"​)"​);​+function ​pushNode() { 
 +    ​var data = document.getElementById('​input'​).value
 +    data = data.replace(/"/​g,​ '​\\\"'​);​ 
 +    runScript("​list.add(\""​data +"\"​)"​);​
 } }
-function ​removeNode() { +function ​popNode() { 
-    ​runScript("​list.remove("​+ ​document.getElementById('​input'​).value +"​)"​);​+    ​var data = document.getElementById('​input'​).value
 +    data = data.replace(/"/​g,​ '​\\\"'​);​ 
 +    runScript("​list.remove(\""​data +"\"​)"​);​
 } }
  
Line 340: Line 233:
 </​head>​ </​head>​
 <body style="​height:​480px">​ <body style="​height:​480px">​
-<button id="​addButton"​ onclick="​addNode()">​Add</​button><​button id="​removeButton"​ onclick="​removeNode()">​Remove</​button>​ <input id="​input"​ value="​7"><​br><​br>​+<button id="​addButton"​ onclick="​pushNode()">​Add</​button><​button id="​removeButton"​ onclick="​popNode()">​Remove</​button>​ <input id="​input"​ value="​7"><​br><​br>​
 <div id=result>​ <div id=result>​
 </​div>​ </​div>​
Line 346: Line 239:
 </​html>​ </​html>​
 </​syntax>​ </​syntax>​
 +</​nowiki>​
algorithm/linked-list.1367549883.txt.gz · Last modified: 2015/02/02 08:23 (external edit)