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++);
  }
};