Custom Beeswarm IV (handle unsorted data)

.block

license: mit

README.md

This block is a continuation of a previous one.

This sequel experiments a way to vizualise the distribution of things (whatever it is) in a horizontal way (ie. along the x-axis), where constraints/objectives are:

• to maintain the exact position of each datum (represented by a circle) along the x-axis
• to be able to hover each circle to show related datum (handle overlapping)

---

Compared to the previous block:

• this algorithm no longer requires the circles to draw to be x-based sorted. The main 'drawBeeswarm' function draws each circle one after each other, as they are listed in its input array.
• this algorithm is ~4 times slower because finding x-based possible colliders is more expensive (previously, gathering x-based possible colliders was easier because circles were arranged in a certain order)

Acknowledgments to:

• D3.js (v3.5.5)
• blockbuilder.org
• dat.gui

beeswarm.js

function Beeswarm () {		
	//-->for metrics purpose
  var totalPossibleColliders, maxPossibleColliders,
      totalTestedPlacements,
      visitedColliderCount, totalVisitedColliders, maxVisitedColliders;
  //<--for metrics purpose


  ////////////////////////
  // Custom Arrangement //
  ////////////////////////
	this._data = []; // original data to arrange
  this._radius = 4; // default radius
  this._x = // accessor to the x value
    function (datum) {
      return datum.x;
    };
  
  this.minDistanceBetweenCircles,
  this.minSquareDistanceBetweenCircles,
  this.xBasedDataManager, // for collision detection, x-based sorted direct-access doubly-linked list of data, used to find nearest already arranged data
  this.xBasedColliderManager, // for collision detection, x-based sorted direct-access doubly-linked list of already arranged data, limit collision detection to already arranged neighbours
	this.yBasedColliderManager, // for collision detection, y-based sorted direct-access doubly-linked list of already arranged data, limit collision detection to already arranged neighbours
  this.arrangement; // result, array of {datum: , x: , y: },
}

Beeswarm.prototype.data = function(_) {
  if (!arguments.length) return this._data;
  this._data = _;

  //for chaining purpose
  return this;
}

Beeswarm.prototype.radius = function (_) {
  if (!arguments.length) return this._radius;
  this._radius = _;

  //for chaining purpose
  return this;
}

Beeswarm.prototype.x = function (_) {
  if (!arguments.length) return this._x;
  this._x = _;

  //for chaining purpose
  return this;
}

Beeswarm.prototype.arrange = function() {
  initArrangement(this._data, this._radius);
  data.forEach(function (d) {
    var bestYPosition = -Infinity,
        relativeYPos,
        xBasedPossibleColliders = gatherXBasedPossibleColliders(d);
    if (xBasedPossibleColliders.length===0) {
      bestYPosition = 0;
    } else {
      yBasedColliderManager.clear();
      yBasedColliderManager.addMany(xBasedPossibleColliders);
      xBasedPossibleColliders.forEach(function(xbpc) {
        relativeYPos = yPosRelativeToXbpc(xbpc, d);
        placeBelow(d, xbpc, relativeYPos);
        if (isBetterPlacement(d, bestYPosition) &&
            !collidesWithOther(d, yBasedColliderManager.dln(xbpc), yBasedColliderManager)) {
          bestYPosition = d.y;
        }
        //-->for metrics purpose
        totalVisitedColliders += visitedColliderCount;
        if (visitedColliderCount > maxVisitedColliders) {
          maxVisitedColliders = visitedColliderCount;
        }
        visitedColliderCount = 0;
        //<--for metrics purpose
        placeAbove(d, xbpc, relativeYPos);
        if (isBetterPlacement(d, bestYPosition) &&
            !collidesWithOther(d, yBasedColliderManager.dln(xbpc), yBasedColliderManager)) {
          bestYPosition = d.y;
        }
        //-->for metrics purpose
        totalVisitedColliders += visitedColliderCount;
        if (visitedColliderCount > maxVisitedColliders) {
          maxVisitedColliders = visitedColliderCount;
        }
        visitedColliderCount = 0;
        //<--for metrics purpose
        totalTestedPlacements += 2; //for metrics purpose
      })
    };
    d.y = bestYPosition;
    xBasedColliderManager.add(d);
  });
  return arrangement;
};

function initArrangement (originalData, radius) {
  minDistanceBetweenCircles = 2*radius;
  minSquareDistanceBetweenCircles = Math.pow(minDistanceBetweenCircles, 2);
  xBasedDataManager = new SortedDirectAccessDoublyLinkedList()
    .valueAccessor(function(d){return d.x;})
    .addMany(originalData);
  xBasedColliderManager = new SortedDirectAccessDoublyLinkedList()
    .valueAccessor(function(d){return d.x;});
  yBasedColliderManager = new SortedDirectAccessDoublyLinkedList()
    .valueAccessor(function(d){return d.y;});
  this.arrangement = this._data.map(function (d,i) {
    return {
      datum: d,
      id: i,
      x: this._x(d),
      y: -Infinity
    }; 
  },this);

  //-->for metrics purpose
  totalPossibleColliders = maxPossibleColliders = 0;
  totalTestedPlacements = 0;
  visitedColliderCount = totalVisitedColliders = maxVisitedColliders =0;
  //<--for metrics purpose
};

function findNearestBelowPossibleCollider(dln, visitedDln, xBasedDataManager) {
  if (visitedDln === null) { // special case: min reached
    return null;
  } else if ((dln.value - visitedDln.value) > minDistanceBetweenCircles) {
    // stop visit, remaining data are too far away
    return null;
  } else {// visitedDln is close enought
    if (isFinite(visitedDln.datum.y)) { // visitedDln is already arranged, and hence is the nearest possible x-based collider
      return(visitedDln.datum);
    }
    // continue finding
    return findNearestBelowPossibleCollider(dln, visitedDln.below, xBasedDataManager);
  }
};

function findNearestAbovePossibleCollider(dln, visitedDln, xBasedDataManager) {
  if (visitedDln === null) { // special case: max reached
    return null;
  } else if ((visitedDln.value - dln.value) > minDistanceBetweenCircles) {
    // stop visit, remaining data are too far away
    return null;
  } else {// visitedDln is close enought
    if (isFinite(visitedDln.datum.y)) { // visitedDln is already arranged, and hence is the nearest possible x-based collider
      return(visitedDln.datum);
    }
    // continue finding
    return findNearestAbovePossibleCollider(dln, visitedDln.above, xBasedDataManager);
  }
};

function gatherXBelowPossibleColliders(dln, visitedDln, xBasedColliderManager, xBasedPossibleColliders) {
  if (visitedDln === null) { // special case: min reached
    return;
  } else if ((dln.value - visitedDln.value) > minDistanceBetweenCircles) {
    // stop visit, remaining data are too far away
    return;
  } else {// visitedDln is close enought
    // visitedDln is already arranged, and hence is a possible x-based collider
    xBasedPossibleColliders.push(visitedDln.datum);
    // continue gathering
    gatherXBelowPossibleColliders(dln, visitedDln.below, xBasedColliderManager, xBasedPossibleColliders);
  }
};

function gatherXAbovePossibleColliders(dln, visitedDln, xBasedColliderManager, xBasedPossibleColliders) {
  if (visitedDln === null) { // special case: max reached
    return;
  } else if ((visitedDln.value - dln.value) > minDistanceBetweenCircles) {
    // stop visit, remaining data are too far away
    return;
  } else {// visitedDln is close enought
    // visitedDln is already arranged, and hence is a possible x-based collider
    xBasedPossibleColliders.push(visitedDln.datum);
    // continue gathering
    gatherXAbovePossibleColliders(dln, visitedDln.above, xBasedColliderManager, xBasedPossibleColliders);
  }
};

function gatherXBasedPossibleColliders (datum) {
  var xBasedPossibleColliders = [];
  var dln = xBasedDataManager.dln(datum);
  //use xBasedDataManager to retrieve nearest already arranged data
  var nearestXBelowAlreadyArrangedData = findNearestBelowPossibleCollider(dln, dln.below, xBasedDataManager);
  var nearestXAboveAlreadyArrangedData = findNearestAbovePossibleCollider(dln, dln.above, xBasedDataManager);

  //use xBasedColliderManager to retrieve already arranged data that may collide with datum (ie, close enought to datum considering x position)
  if (nearestXBelowAlreadyArrangedData != null) {
    //visit x-below already arranged nodes
    dln = xBasedColliderManager.dln(nearestXBelowAlreadyArrangedData);
    gatherXBelowPossibleColliders(dln, dln, xBasedColliderManager, xBasedPossibleColliders);
  }

  if (nearestXAboveAlreadyArrangedData != null) {
    //visit x-above already arranged nodes
    dln = xBasedColliderManager.dln(nearestXAboveAlreadyArrangedData);
    gatherXAbovePossibleColliders(dln, dln, xBasedColliderManager, xBasedPossibleColliders);
  }

  //-->for metrics purpose
  totalPossibleColliders += xBasedPossibleColliders.length;
  if (xBasedPossibleColliders.length > maxPossibleColliders) {
    maxPossibleColliders = xBasedPossibleColliders.length;
  }
  //<--for metrics purpose
  return xBasedPossibleColliders;
};

function isBetterPlacement(datum, bestYPosition) {
  return Math.abs(datum.y) < Math.abs(bestYPosition);
};

function yPosRelativeToXbpc(xbpc, d) {
  // handle Float approximation with +1E-6
  return Math.sqrt(minSquareDistanceBetweenCircles-Math.pow(d.x-xbpc.x,2))+1E-6;
};

function placeBelow(d, aad, relativeYPos) {
  d.y = aad.y - relativeYPos;

  //showOnTheFlyCircleArrangement(d, "test");
};

function placeAbove(d, aad, relativeYPos) {
  d.y = aad.y + relativeYPos;

  //showOnTheFlyCircleArrangement(d, "test");
};

function areCirclesColliding(d0, d1) {
  visitedColliderCount++; //for metrics prupose

  return (Math.pow(d1.y-d0.y, 2) + Math.pow(d1.x-d0.x, 2)) < minSquareDistanceBetweenCircles;
};

function collidesWithBelow(datum, visitedDln, yBasedColliderManager, visitCount) {
  if (visitedDln === null) { // special case: y_min reached, no collision detected
    return false;
  } else if ((datum.y - visitedDln.datum.y) > minDistanceBetweenCircles) {
    // stop visit, no collision detected, remaining data are too far away
    return false;
  } else if (areCirclesColliding(datum, visitedDln.datum)) {
    return true;
  } else {
    // continue visit
    return collidesWithBelow(datum, visitedDln.below, yBasedColliderManager, visitCount++)
  }
};

function collidesWithAbove(datum, visitedDln, yBasedColliderManager, visitCount) {
  if (visitedDln === null) { // special case: y_max reached, no collision detected
    return false;
  } else if ((visitedDln.datum.y - datum.y) > minDistanceBetweenCircles) {
    // stop visit, no collision detected, remaining data are too far away
    return false;
  } else if (areCirclesColliding(datum, visitedDln.datum)) {
    return true;
  } else {
    // continue visit
    return collidesWithAbove(datum, visitedDln.above, yBasedColliderManager, visitCount++)
  }
};

function collidesWithOther (datum, visitedDln, yBasedColliderManager) {
  var visitCount = 0;
  //visit below dlns for collision check
  if (collidesWithBelow(datum, visitedDln.below, yBasedColliderManager, visitCount++)) {
    return true;
  } else {
    //visit above dlns for collision check
    return collidesWithAbove(datum, visitedDln.above, yBasedColliderManager, visitCount++);
  }
};

data.csv

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }

  circle {
    stroke-width: 1.5px;
  }

  line {
    stroke: #999;
  }

</style>
<body>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
	<script src="https://d3js.org/d3.v3.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5.1/dat.gui.min.js">
  </script>
  <script src="sorted_direct_access_doubly_linked_list.js"></script>
  <script src="beeswarm.js"></script>
  <script>
    var width = 960,
        height = 500;
    var csvData = []; // data retrieve from CSV
    var memorizedSortedData = [] // allow to maintain sort when changing radius
    var availableSortings = ['min -> max', 'max -> min', 'shuffled'];
		var config = {
      radius: 4,
      manyPoints: false,
      sorting: "shuffled",
      sortOptions: {
        shuffled: function() {
          config.sorting = "shuffled";
          renewData();
          drawBeeswarm();
        },
        minToMax: function() {
          config.sorting = "minToMax";
          renewData();
          drawBeeswarm();
        },
        maxToMin: function() {
          config.sorting = "maxToMin";
          renewData();
          drawBeeswarm();
        }
      }
    };

    insertControls();
    
    var fill = d3.scale.linear().domain([1,150]).range(['lightgreen', 'pink']);

    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height);

    svg.append("line")
    	.attr("id", "x-axis")
      .attr("x1", 0)
      .attr("y1", height/2)
      .attr("x2", width)
      .attr("y2", height/2)
      .style("stroke", "lightgrey");
    
    var nodeContainer = svg.append("g").attr("id", "node-container");
		
    var tooltip, stem, rank, value;
    prepareTooltip();
    
    //-->for metrics purpose
    var informationPanel, computationTimeInfo, dataLengthInfo, posibleCollidersInfo, placementInfo, visitedCollidersInfo;
    prepareInformationPanel();
    
    
    var totalPossibleColliders, maxPossibleColliders,
        totalTestedPlacements,
      	visitedColliderCount, totalVisitedColliders, maxVisitedColliders;
    //<--for metrics purpose
    
    
    ////////////////////////
    // Custom Arrangement //
    ////////////////////////
    
    var minDistanceBetweenCircles,
        minSquareDistanceBetweenCircles,
      	xBasedDataManager, // for collision detection, x-based sorted direct-access doubly-linked list of data, used to find nearest already arranged data
        xBasedColliderManager, // for collision detection, x-based sorted direct-access doubly-linked list of already arranged data, limit collision detection to already arranged neighbours
     		yBasedColliderManager; // for collision detection, y-based sorted direct-access doubly-linked list of already arranged data, limit collision detection to already arranged neighbours
    
		function initArrangement(originalData, radius) {
      minDistanceBetweenCircles = 2*radius;
      minSquareDistanceBetweenCircles = Math.pow(minDistanceBetweenCircles, 2);
      xBasedDataManager = new SortedDirectAccessDoublyLinkedList()
        .valueAccessor(function(d){return d.x;})
      	.addMany(originalData);
      xBasedColliderManager = new SortedDirectAccessDoublyLinkedList()
        .valueAccessor(function(d){return d.x;});
      yBasedColliderManager = new SortedDirectAccessDoublyLinkedList()
        .valueAccessor(function(d){return d.y;});
      //-->for metrics purpose
      totalPossibleColliders = maxPossibleColliders = 0;
      totalTestedPlacements = 0;
      visitedColliderCount = totalVisitedColliders = maxVisitedColliders =0;
      //<--for metrics purpose
    };
    
    function findNearestBelowPossibleCollider(dln, visitedDln, xBasedDataManager) {
      if (visitedDln === null) { // special case: min reached
        return null;
      } else if ((dln.value - visitedDln.value) > minDistanceBetweenCircles) {
        // stop visit, remaining data are too far away
        return null;
      } else {// visitedDln is close enought
        if (isFinite(visitedDln.datum.y)) { // visitedDln is already arranged, and hence is the nearest possible x-based collider
          return(visitedDln.datum);
        }
        // continue finding
        return findNearestBelowPossibleCollider(dln, visitedDln.below, xBasedDataManager);
      }
    };
    
    function findNearestAbovePossibleCollider(dln, visitedDln, xBasedDataManager) {
      if (visitedDln === null) { // special case: max reached
        return null;
      } else if ((visitedDln.value - dln.value) > minDistanceBetweenCircles) {
        // stop visit, remaining data are too far away
        return null;
      } else {// visitedDln is close enought
        if (isFinite(visitedDln.datum.y)) { // visitedDln is already arranged, and hence is the nearest possible x-based collider
          return(visitedDln.datum);
        }
        // continue finding
        return findNearestAbovePossibleCollider(dln, visitedDln.above, xBasedDataManager);
      }
    };
    
    function gatherXBelowPossibleColliders(dln, visitedDln, xBasedColliderManager, xBasedPossibleColliders) {
      if (visitedDln === null) { // special case: min reached
        return;
      } else if ((dln.value - visitedDln.value) > minDistanceBetweenCircles) {
        // stop visit, remaining data are too far away
        return;
      } else {// visitedDln is close enought
        // visitedDln is already arranged, and hence is a possible x-based collider
        xBasedPossibleColliders.push(visitedDln.datum);
        // continue gathering
        gatherXBelowPossibleColliders(dln, visitedDln.below, xBasedColliderManager, xBasedPossibleColliders);
      }
    };
    
    function gatherXAbovePossibleColliders(dln, visitedDln, xBasedColliderManager, xBasedPossibleColliders) {
      if (visitedDln === null) { // special case: max reached
        return;
      } else if ((visitedDln.value - dln.value) > minDistanceBetweenCircles) {
        // stop visit, remaining data are too far away
        return;
      } else {// visitedDln is close enought
        // visitedDln is already arranged, and hence is a possible x-based collider
        xBasedPossibleColliders.push(visitedDln.datum);
        // continue gathering
        gatherXAbovePossibleColliders(dln, visitedDln.above, xBasedColliderManager, xBasedPossibleColliders);
      }
    };
    
    function gatherXBasedPossibleColliders (datum) {
      var xBasedPossibleColliders = [];
      var dln = xBasedDataManager.dln(datum);
      //use xBasedDataManager to retrieve nearest already arranged data
      var nearestXBelowAlreadyArrangedData = findNearestBelowPossibleCollider(dln, dln.below, xBasedDataManager);
      var nearestXAboveAlreadyArrangedData = findNearestAbovePossibleCollider(dln, dln.above, xBasedDataManager);
      
      //use xBasedColliderManager to retrieve already arranged data that may collide with datum (ie, close enought to datum considering x position)
      if (nearestXBelowAlreadyArrangedData != null) {
        	//visit x-below already arranged nodes
        dln = xBasedColliderManager.dln(nearestXBelowAlreadyArrangedData);
      	gatherXBelowPossibleColliders(dln, dln, xBasedColliderManager, xBasedPossibleColliders);
      }
			
      if (nearestXAboveAlreadyArrangedData != null) {
        //visit x-above already arranged nodes
        dln = xBasedColliderManager.dln(nearestXAboveAlreadyArrangedData);
        gatherXAbovePossibleColliders(dln, dln, xBasedColliderManager, xBasedPossibleColliders);
      }
      
      //-->for metrics purpose
      totalPossibleColliders += xBasedPossibleColliders.length;
      if (xBasedPossibleColliders.length > maxPossibleColliders) {
        maxPossibleColliders = xBasedPossibleColliders.length;
      }
      //<--for metrics purpose
      return xBasedPossibleColliders;
    };

    function isBetterPlacement(datum, bestYPosition) {
      return Math.abs(datum.y) < Math.abs(bestYPosition);
    };

    function yPosRelativeToXbpc(xbpc, d) {
      // handle Float approximation with +1E-6
      return Math.sqrt(minSquareDistanceBetweenCircles-Math.pow(d.x-xbpc.x,2))+1E-6;
    };
    
    function placeBelow(d, aad, relativeYPos) {
      d.y = aad.y - relativeYPos;
      
      //showOnTheFlyCircleArrangement(d, "test");
    };

    function placeAbove(d, aad, relativeYPos) {
      d.y = aad.y + relativeYPos;
      
      //showOnTheFlyCircleArrangement(d, "test");
    };

    function areCirclesColliding(d0, d1) {
      visitedColliderCount++; //for metrics prupose
      
      return (Math.pow(d1.y-d0.y, 2) + Math.pow(d1.x-d0.x, 2)) < minSquareDistanceBetweenCircles;
    };
    
    function collidesWithBelow(datum, visitedDln, yBasedColliderManager, visitCount) {
      if (visitedDln === null) { // special case: y_min reached, no collision detected
        return false;
      } else if ((datum.y - visitedDln.datum.y) > minDistanceBetweenCircles) {
        // stop visit, no collision detected, remaining data are too far away
        return false;
      } else if (areCirclesColliding(datum, visitedDln.datum)) {
        return true;
      } else {
        // continue visit
        return collidesWithBelow(datum, visitedDln.below, yBasedColliderManager, visitCount++)
      }
    };
    
    function collidesWithAbove(datum, visitedDln, yBasedColliderManager, visitCount) {
      if (visitedDln === null) { // special case: y_max reached, no collision detected
        return false;
      } else if ((visitedDln.datum.y - datum.y) > minDistanceBetweenCircles) {
        // stop visit, no collision detected, remaining data are too far away
        return false;
      } else if (areCirclesColliding(datum, visitedDln.datum)) {
        return true;
      } else {
        // continue visit
        return collidesWithAbove(datum, visitedDln.above, yBasedColliderManager, visitCount++)
      }
    };

    function collidesWithOther (datum, visitedDln, yBasedColliderManager) {
      var visitCount = 0;
      //visit below dlns for collision check
      if (collidesWithBelow(datum, visitedDln.below, yBasedColliderManager, visitCount++)) {
        return true;
      } else {
        //visit above dlns for collision check
        return collidesWithAbove(datum, visitedDln.above, yBasedColliderManager, visitCount++);
      }
    };

    function arrangeCircles (data) {
      initArrangement(data, config.radius);
      data.forEach(function (d) {
        var bestYPosition = -Infinity,
            relativeYPos,
        		xBasedPossibleColliders = gatherXBasedPossibleColliders(d);
        if (xBasedPossibleColliders.length===0) {
          bestYPosition = 0;
        } else {
          yBasedColliderManager.clear();
          yBasedColliderManager.addMany(xBasedPossibleColliders);
          xBasedPossibleColliders.forEach(function(xbpc) {
            relativeYPos = yPosRelativeToXbpc(xbpc, d);
            placeBelow(d, xbpc, relativeYPos);
            if (isBetterPlacement(d, bestYPosition) &&
                !collidesWithOther(d, yBasedColliderManager.dln(xbpc), yBasedColliderManager)) {
              bestYPosition = d.y;
            }
            //-->for metrics purpose
              totalVisitedColliders += visitedColliderCount;
              if (visitedColliderCount > maxVisitedColliders) {
                maxVisitedColliders = visitedColliderCount;
              }
              visitedColliderCount = 0;
            //<--for metrics purpose
            placeAbove(d, xbpc, relativeYPos);
            if (isBetterPlacement(d, bestYPosition) &&
                !collidesWithOther(d, yBasedColliderManager.dln(xbpc), yBasedColliderManager)) {
              bestYPosition = d.y;
            }
            //-->for metrics purpose
              totalVisitedColliders += visitedColliderCount;
              if (visitedColliderCount > maxVisitedColliders) {
                maxVisitedColliders = visitedColliderCount;
              }
              visitedColliderCount = 0;
            //<--for metrics purpose
      			totalTestedPlacements += 2; //for metrics purpose
          })
        };
        d.y = bestYPosition;
        xBasedColliderManager.add(d);
      });
    };

    function showCircles (data) {
      nodeContainer.selectAll("circle").remove();
      var node = nodeContainer.selectAll("circle")
          .data(data)
        .enter().append("circle")
          .attr("r", config.radius-0.75)
          .attr("cx", function(d) { return d.x; })
          .attr("cy", function(d) { return height/2 + d.y; })
          .style("fill", function(d) { return fill(d.rank); })
          .style("stroke", function(d) { return d3.rgb(fill(d.rank)).darker(); })
          .on("mouseenter", function(d) {
            stem.text(d.stem);
            rank.text(d.rank);
            value.text(d.trend);
            tooltip.transition().duration(0).style("opacity", 1); // remove fade out transition on mouseleave
          })
          .on("mouseleave", function(d) {
            tooltip.transition().duration(1000).style("opacity", 0);
          });
    };
    
    function drawBeeswarm() {
      var data = copyData(memorizedSortedData);
      
      var startTime = Date.now();
      /* target Beeswarm API
      var beeswarm = new Beeswarm()
      	.data(data)
      	.x(function(d) { return d.x; })
      	.arrange();
      */arrangeCircles(data);
      showMetrics(data, (Date.now()-startTime));
      
      showCircles(data);
    };
		
    d3.csv("data.csv", dottype, function(error, data) {
      if (error) throw error;
      renewData();
      drawBeeswarm();
    });
    
    ////////////////////////
    // bl.ocks' utilities //
    ////////////////////////
    
    function dottype(d) {
      d.id = d.stem;
      d.stem = d.stem;
      d.rank = +d.rank;
      d.trend = +d.trend;
      d.originalX = width/2+d.trend*6000;
      d.x = d.originalX;
      d.y = -Infinity;
      csvData.push(d);
      return d;
    };
    
    function copyData(data) {
      return data.map(function(d) {
          return {
            id: d.id,
            stem: d.stem,
            rank: d.rank,
            trend: d.trend,
            originalX: d.originalX,
            x: d.originalX,
            y: d.y
          }
         });
    };

    function quadruple(data) {
      // Quadruples data while maintaining order and uniq id
      var quadrupledData = [],
          i;
      data.forEach(function(d) {
        for (i=1; i<4; i++) {
          quadrupledData.push({
            id: d.id+"_"+i,
            stem: d.stem,
            rank: d.rank,
            trend: d.trend,
            originalX: d.originalX+i*1E-3,
            x: d.x+i*1E-3,
            y: d.y
          })
        }
        quadrupledData.push(d);
      })
      return quadrupledData;
    };
    
    function renewData () {
      var newData = copyData(csvData);
      
      if (config.manyPoints) {
        newData = quadruple(newData);
      }
          
      if (config.sorting === "maxToMin" ) {
        memorizedSortedData = newData;
      } else if (config.sorting === "minToMax" ) {
        memorizedSortedData = newData.reverse();
      } else {
      	memorizedSortedData = d3.shuffle(newData);
      }
    };
	
    function insertControls () {
      var ctrls = new dat.GUI({width: 200});
      radiusCtrl = ctrls.add(config, "radius", 1, 20);
      radiusCtrl.onChange(function(value) {
        drawBeeswarm();
      });
      manyPointsCtrl = ctrls.add(config, "manyPoints");
      manyPointsCtrl.onChange(function(value) {
        renewData();
        drawBeeswarm();
      });
      sortingFolder = ctrls.addFolder("Sorting");
      sortingFolder.open();
      sortingCtrl = sortingFolder.add(config.sortOptions, "shuffled");
      sortingCtrl = sortingFolder.add(config.sortOptions, "minToMax");
      sortingCtrl = sortingFolder.add(config.sortOptions, "maxToMin");
    };
    
    function prepareTooltip() {
      tooltip = svg.append("g")
      	.attr("id", "tooltip")
        .attr("transform", "translate("+[width/2, 50]+")")
        .style("opacity", 0);
      var titles = tooltip.append("g").attr("transform", "translate("+[-5,0]+")")
      titles.append("text").attr("text-anchor", "end").text("stem(fr):");
      titles.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,15]+")")
        .text("rank:");
      titles.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,30]+")")
        .text("x-value:");
      var values = tooltip.append("g").attr("transform", "translate("+[5,0]+")")
      stem = values.append("text")
      	.attr("text-anchor", "start");
      rank = values.append("text")
      	.attr("text-anchor", "start")
        .attr("transform", "translate("+[0,15]+")");
      value = values.append("text")
      	.attr("text-anchor", "start")
        .attr("transform", "translate("+[0,30]+")");
    };
    
    function prepareInformationPanel() {
      var i=4;
      informationPanel = svg.append("g")
      	.attr("id", "infomation-panel")
        .attr("transform", "translate("+[width-20, height-20]+")");
      computationTimeInfo = informationPanel.append("text")
      	.attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      dataLengthInfo = informationPanel.append("text")
      	.attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      possibleCollidersInfo = informationPanel.append("text")
      	.attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      placementInfo = informationPanel.append("text")
      	.attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      visitedCollidersInfo = informationPanel.append("text")
      	.attr("text-anchor", "end");
    };
    
    function showMetrics(data, elapsed) {
      computationTimeInfo.text("Arrangement took: "+elapsed+" ms");
      dataLengthInfo.text("# data: "+data.length);
      possibleCollidersInfo.text("# possible colliders: ~"+Math.round(totalPossibleColliders/data.length)+" per data ("+maxPossibleColliders+" max, "+totalPossibleColliders+" total)");
      placementInfo.text("# tested placements: ~"+Math.round(totalTestedPlacements/data.length)+" per data ("+(maxPossibleColliders*2)+" max, "+totalTestedPlacements+" total)");
      visitedCollidersInfo.text("# collision checks: ~"+Math.round(totalVisitedColliders/totalTestedPlacements)+" per placement ("+maxVisitedColliders+" max, "+totalVisitedColliders+" total)")
    };

    function showOnTheFlyCircleArrangement(d, type) {
      nodeContainer.selectAll("circle.test").remove();
      nodeContainer.append("circle")
      	.datum(d)
      	.classed(type, true)
      	.attr("r", config.radius)
        .attr("cx", function(d) { return d.x; })
        .attr("cy", function(d) { return height/2 + d.y; })
        .style("fill", function(d) { return fill(d.rank); })
        .style("stroke", function(d) { return d3.rgb(fill(d.rank)).darker(); })
    };
  </script>
</body>

sorted_direct_access_doubly_linked_list.js

// each data MUST have a 'value' property (for sorting)
// each data MUST have a 'id' property (for direct-access)

// data in SortedDirectAccessDoublyLinkedList are sorted by 'value', from min to max, in a doubly-linked list
// each node in the doubly-linked list is of the form {datum: , value: , prev: , next: }
// 'datum' refers to the original datum; 'value' is retrieved from data, below'/'above' refer to previous/next value-based nodes

function SortedDirectAccessDoublyLinkedList () {
  this._valueAccessor = // accessor to the value to sort on
    function (datum) {
    return datum.value;
  }
  this._min = null; // reference to the doubly-linked node with the min value
  this._max = null; // reference to the doubly-linked node with the max value
  this.size = 0 // number of data in the doubly-linked list
  this._idToNode = {}; // direct access to a node of the doubly-linked list
}

SortedDirectAccessDoublyLinkedList.prototype.valueAccessor = function (_) {
  if (!arguments.length) return this._valueAccessor;
  this._valueAccessor = _;

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.clear = function () {
  this._min = null;
  this._max = null;
  this.size = 0;
  this._idToNode = {};

  //for chaining purpose
  return this
};

SortedDirectAccessDoublyLinkedList.prototype.dln = function (datum){
  // dln = doubly-linked node
  return this._idToNode[datum.id];
};

SortedDirectAccessDoublyLinkedList.prototype.addMany = function (data) {

  data.forEach( function (datum, item) {
    this.add(datum);
  }, this)

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.add = function (datum){
  //create a new doubly-linked node
  var dln = {
    datum: datum, // original datum
    value: this._valueAccessor(datum),
    below: null,	// previous value-based node
    above: null		// next value-based node
  };

  //insert node in the adequate position in the doubly-linked list
  if (this.size === 0) { //special case: no node in the list yet
    this._min = this._max = dln;
  } else if (dln.value <= this._min.value) {//special case: new datum is the min
    dln.above = this._min;
    dln.above.below = dln;
    this._min = dln;
  } else if (dln.value >= this._max.value) { //special case: new datum is the max
    dln.below = this._max;
    dln.below.above = dln;
    this._max = dln;
  } else {
    //insert the node at the adequate position
    var current = this._max;
    //loop to find immediate below
    while (current.value > dln.value) {
      current = current.below;
    }
    dln.below = current;
    dln.above = current.above;
    dln.above.below = dln;
    dln.below.above = dln;
  }

  //direct access to the node
  this._idToNode[dln.datum.id] = dln;

  //update size
  this.size++;

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.remove = function (datum) {
  var dln = this.dln(datum);

  //remove node from the doubly-linked list
  if (this.size === 1) { //special case: last item to remove
    this._min = this._max = null;
  } else if (dln === this._min) { //special case: datum is the min
    this._min = this._min.above;
    this._min.below = null;
  } else if (dln === this._max) { //special case: datum is the max
    this._max = this._max.below;
    this._max.above = null;
  } else {
    //remove pointers to the node
    dln.above.below = dln.below;
    dln.below.above = dln.above;
  }

  dln = null // carbage collector
  delete this._idToNode[datum.id]; //remove direct access to the node

  //update size
  this.size--;

  //for chaining purpose
  return this;
}

thumbnail.png