Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active December 3, 2018 08:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kcnarf/f76794f5590563a2a4347a324ac7c099 to your computer and use it in GitHub Desktop.
Save Kcnarf/f76794f5590563a2a4347a324ac7c099 to your computer and use it in GitHub Desktop.
Download ZIP
Custom Beeswarm IV (handle unsorted data)
Raw
.block
license: mit
Raw
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:

Raw
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++);
}
};
Raw
data.csv
stem rank trend
jean 1 0.0221834557
excelent 2 0.0172573247
bon 3 0.0152706367
conseil 4 0.0142771343
part 5 0.0139849763
ecout 6 0.0125657668
promotion 7 0.0116647465
disponibilit 8 0.0107923086
serviabl 9 0.0099251458
acesoir 10 0.0098934332
haut 11 0.009431776
pantalon 12 0.0093578819
bele 13 0.0092871115
aceuil 14 0.0092121588
nouveaut 15 0.0090155204
achat 16 0.008722844
promo 17 0.0086278463
tendanc 18 0.0085356217
manqu 19 0.0084932708
parfait 20 0.0083623534
done 21 0.008355304
feme 22 0.0083248405
vent 23 0.0083132016
avoi 24 0.0080424169
chaleureu 25 0.0078822066
comand 26 0.0075604839
quelqu 27 0.0074075752
tenu 28 0.0072492987
chausur 29 0.00711808
disponibl 30 0.0068948326
person 31 0.0068073546
originalit 32 0.0067217905
vendeu 33 0.0067063822
rien 34 0.0067047717
esay 35 0.0067006641
satisfait 36 0.006684763
cher 37 0.0066836778
acueil 38 0.0066314869
colection 39 0.0064813458
metr 40 0.0064580388
tre 41 0.0064376867
servic 42 0.0063193197
sympath 43 0.0061779954
être 44 0.0061047823
sup 45 0.0060575513
dispos 46 0.0060483871
goût 47 0.0059637097
ador 48 0.0059467335
boutiqu 49 0.0059089954
beau 50 0.0058717403
regulier 51 0.0057329804
certain 52 0.005686449
ofre 53 0.005585669
gentil 54 0.0055481446
styl 55 0.005431152
fidelit 56 0.005398658
foi 57 0.0053355415
propos 58 0.00518158
profesion 59 0.0051523297
game 60 0.0051314774
cart 61 0.0050913638
chos 62 0.0050861437
coup 63 0.0050283014
souriant 64 0.0049009439
tail 65 0.004843215
raport 66 0.0048075105
autr 67 0.0046451013
general 68 0.0046430266
reduction 69 0.0046182266
mode 70 0.004570462
achet 71 0.0045116366
amelior 72 0.0045047883
present 73 0.004487011
elev 74 0.0044661415
rest 75 0.0044256491
jol 76 0.0043042359
acueilant 77 0.0041950808
marqu 78 0.0040932108
produit 79 0.0039764739
diferent 80 0.0039120302
modern 81 0.0038882488
enseign 82 0.0038190136
agreabl 83 0.0037894
trouv 84 0.0037702036
parfoi 85 0.0036276761
port 86 0.0035256142
magasin 87 0.0034050179
chang 88 0.0031922043
agenc 89 0.003190358
clai 90 0.0031812945
ainsi 91 0.0031549695
choi 92 0.0030694137
rayon 93 0.0030580465
client 94 0.0029360714
vête 95 0.0028722762
dire 96 0.0027721774
qualit 97 0.0027403058
var 98 0.0026126169
personel 99 0.0025779703
aimabl 100 0.0025749765
internet 101 0.0025134409
pri 102 0.00238414
sai 103 0.0023536115
abordabl 104 0.0022652921
bone 105 0.0022487593
matier 106 0.0021982583
promod 107 0.0020265214
larg 108 0.0018647201
stock 109 0.0018290033
sympa 110 0.0018003201
corect 111 0.0017615927
vraiment 112 0.0016633065
petit 113 0.0016439206
aime 114 0.0015219369
model 115 0.0014867544
equip 116 0.0011670831
couleu 117 0.0011177858
seul 118 0.0010356827
bais 119 0.0010036041
renouvel 120 0.0009602366
nouvel 121 0.0009557945
niveau 122 0.0004725302
articl 123 0.0003851409
vete 124 0.000353736
domag 125 0.0002193117
raisonabl 126 -0.0001944124
esayag 127 -0.00025102
valeu 128 -0.0002974617
site 129 -0.00040451
amabilit 130 -0.0005457864
grand 131 -0.0008885675
original 132 -0.0009822167
acesibl 133 -0.0010942806
sourir 134 -0.0011092602
diversit 135 -0.001424439
tisu 136 -0.0016639137
cabin 137 -0.0025446106
ane 138 -0.0032602282
propr 139 -0.0039869126
joli 140 -0.0051917043
clas 141 -0.0052463184
variet 142 -0.007044379
atractif 143 -0.0072967461
cais 144 -0.0080716152
rang 145 -0.0081059257
robe 146 -0.0084245392
espac 147 -0.0087132705
atent 148 -0.0109695748
interesant 149 -0.0113475782
sold 150 -0.0611010533
Raw
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>
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment