λ Queue list-based

======= Algorithm ======= <syntax js> function Queue() { this.first = null; this.last = null; } Queue.Node = function(data, next) { this.data = data; this.next = next; } Queue.prototype = { // Adds new data to the list at the end of the list. enqueue: function(data) { var newLast = new Queue.Node(data, null); if (this.last) { this.last.next = newLast; this.last = newLast; } else { this.first = this.last = newLast; } }, // Removes the first element from the list. dequeue: function(data) { var popped = this.first; if (popped) { this.first = this.first.next; if (!this.first) { this.last = null; } } return popped? popped.data : null; } }</syntax> ======= Support ======= <syntax js> // Initial starting queue. queue = new Queue(); queue.enqueue("A"); queue.enqueue("B"); queue.enqueue("C"); function preRun() { if (!(queue instanceof Queue)) { // Copy the queue from data - used for web-workers. var myqueue = new Queue(); myqueue.first = queue.first; myqueue.last = queue.last; // Replace the global 'queue' with the converted one. queue = myqueue; } } </syntax> ======= Tests ======= <syntax js> function testA() { var q = new Queue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); assert(q.dequeue() === 1); assert(q.dequeue() === 2); assert(q.dequeue() === 3); assert(q.dequeue() === null, "End of queue."); } function testB() { var q = new Queue(); q.enqueue(1); q.enqueue(2); assert(q.dequeue() === 1); q.enqueue(3); q.enqueue(4); assert(q.dequeue() === 2); q.enqueue(5); assert(q.dequeue() === 3); assert(q.dequeue() === 4); assert(q.dequeue() === 5); assert(q.dequeue() === null, "End of queue."); }</syntax> ======= Options ======= <syntax js> { "title": "Queue list-based", "height": "450px", "preRunSource": true, "persistentGlobals": ["queue"] } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script src="http://d3js.org/d3.v3.js"></script> <link rel="stylesheet" type="text/css" href="algorithms-lib/list.css"/> <script src="algorithms-lib/list.js"></script> <script> function setup() { svg = d3.select("#result") .append("svg") .attr("width", 348) .attr("height", 400) .append("g").attr("transform", "translate(10.5, 20.5)"); listVis = new ListVisualisation(svg); returnText = svg.append("text") .attr("dx", "0") .attr("dy", "40"); } var listNodesToDisplay = []; var newNodesToDisplay = []; var nodeIndex = 1; var nodeConstructor; function idNode(node) { if (node.constructor === nodeConstructor && !node.hasOwnProperty("id")) { node.id = nodeIndex++; return true; } return false; } function updateList(x, clean, duration) { var list = x.lookupInScope("queue"); var listNodes = []; var node = list.first; while (node) { listNodes.push(node); if (newNodesToDisplay.indexOf(node)!==-1) { newNodesToDisplay.splice(newNodesToDisplay.indexOf(node),1); delete node.isnew; } node = node.next; } if (clean) { listNodesToDisplay = listNodes; newNodesToDisplay = []; } else { // merge listNodes with listNodesToDisplay var displayI = 0; for (var i=0; i<listNodes.length; i++) { var newDisplayI = listNodesToDisplay.indexOf(listNodes[i]) if (newDisplayI === -1) { listNodesToDisplay.splice(displayI, 0, listNodes[i]); displayI++; } else { displayI = newDisplayI+1; } } } var nodes = newNodesToDisplay.concat(listNodesToDisplay); // Position and ensure every node has an id. var nX = 30; var nNewX = 130; 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; } } } listVis.nodesToDisplay = nodes; listVis.pointersToDisplay = [{value:list.first, name:"first", x:15, y:20, id:-1}, {value:list.last, name:"last", x:60, y:20, id:-2}]; if (clean) { listVis.clear(duration); timeout = setTimeout(function() { updateList(x, false, 1000); }, 1000); } else { listVis.update(duration); } } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } var hasRun = false; var timeout; function update(n, x, isRunning, duration) { // Capture new nodes created. nodeConstructor = x.lookupInScope("Queue").Node; if (idNode(x.thisObject)) { if (newNodesToDisplay.indexOf(x.thisObject) === -1 && listNodesToDisplay.indexOf(x.thisObject) === -1) { newNodesToDisplay.push(x.thisObject); x.thisObject.isnew = true; } } updateList(x, false, duration); if (!isRunning && hasRun && !timeout) { timeout = setTimeout(function() { updateList(x, true, 1000); }, 2000); } else if (timeout) { window.clearTimeout(timeout); timeout = undefined; } hasRun = true; document.getElementById("addButton").disabled = isRunning; document.getElementById("removeButton").disabled = isRunning; var poppedValue = x.lookupInScope("popped"); svg.selectAll(".data").classed("selected", function(d) {return d===poppedValue;}); returnText.text(function() {console.log(poppedValue); return poppedValue !== poppedMarker? "Dequeued: "+ (typeof poppedValue === "object"? poppedValue.data : poppedValue) : ""; }); returnText.attr("transform", function() { var lastNode = listNodesToDisplay[listNodesToDisplay.length-1]; return lastNode? "translate(0," + (lastNode.y) +")" : "translate(0,60)"; }); } function pushNode() { var data = document.getElementById('input').value; data = data.replace(/"/g, '\\\"'); runScript("queue.enqueue(\""+ data +"\")"); } function popNode() { runScript("popped = queue.dequeue()"); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <button id="addButton" onclick="pushNode()">Enqueue</button><button id="removeButton" onclick="popNode()">Dequeue</button> <input id="input" value="7"><br><br> <div id=result> </div> </body> </html></syntax>