Custom Beeswarm IV (handle unsorted data)

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:

<!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");
    };

https://d3js.org/d3.v3.min.js

https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5.1/dat.gui.min.js