ngraph.forcelayout2d.js 46 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652
  1. (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.ngraphCreate2dLayout = f()}})(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
  2. module.exports = createLayout;
  3. module.exports.simulator = require('./lib/createPhysicsSimulator');
  4. var eventify = require('ngraph.events');
  5. /**
  6. * Creates force based layout for a given graph.
  7. *
  8. * @param {ngraph.graph} graph which needs to be laid out
  9. * @param {object} physicsSettings if you need custom settings
  10. * for physics simulator you can pass your own settings here. If it's not passed
  11. * a default one will be created.
  12. */
  13. function createLayout(graph, physicsSettings) {
  14. if (!graph) {
  15. throw new Error('Graph structure cannot be undefined');
  16. }
  17. var createSimulator = (physicsSettings && physicsSettings.createSimulator) || require('./lib/createPhysicsSimulator');
  18. var physicsSimulator = createSimulator(physicsSettings);
  19. if (Array.isArray(physicsSettings)) throw new Error('Physics settings is expected to be an object');
  20. var nodeMass = defaultNodeMass;
  21. if (physicsSettings && typeof physicsSettings.nodeMass === 'function') {
  22. nodeMass = physicsSettings.nodeMass;
  23. }
  24. var nodeBodies = new Map();
  25. var springs = {};
  26. var bodiesCount = 0;
  27. var springTransform = physicsSimulator.settings.springTransform || noop;
  28. // Initialize physics with what we have in the graph:
  29. initPhysics();
  30. listenToEvents();
  31. var wasStable = false;
  32. var api = {
  33. /**
  34. * Performs one step of iterative layout algorithm
  35. *
  36. * @returns {boolean} true if the system should be considered stable; False otherwise.
  37. * The system is stable if no further call to `step()` can improve the layout.
  38. */
  39. step: function() {
  40. if (bodiesCount === 0) {
  41. updateStableStatus(true);
  42. return true;
  43. }
  44. var lastMove = physicsSimulator.step();
  45. // Save the movement in case if someone wants to query it in the step
  46. // callback.
  47. api.lastMove = lastMove;
  48. // Allow listeners to perform low-level actions after nodes are updated.
  49. api.fire('step');
  50. var ratio = lastMove/bodiesCount;
  51. var isStableNow = ratio <= 0.01; // TODO: The number is somewhat arbitrary...
  52. updateStableStatus(isStableNow);
  53. return isStableNow;
  54. },
  55. /**
  56. * For a given `nodeId` returns position
  57. */
  58. getNodePosition: function (nodeId) {
  59. return getInitializedBody(nodeId).pos;
  60. },
  61. /**
  62. * Sets position of a node to a given coordinates
  63. * @param {string} nodeId node identifier
  64. * @param {number} x position of a node
  65. * @param {number} y position of a node
  66. * @param {number=} z position of node (only if applicable to body)
  67. */
  68. setNodePosition: function (nodeId) {
  69. var body = getInitializedBody(nodeId);
  70. body.setPosition.apply(body, Array.prototype.slice.call(arguments, 1));
  71. },
  72. /**
  73. * @returns {Object} Link position by link id
  74. * @returns {Object.from} {x, y} coordinates of link start
  75. * @returns {Object.to} {x, y} coordinates of link end
  76. */
  77. getLinkPosition: function (linkId) {
  78. var spring = springs[linkId];
  79. if (spring) {
  80. return {
  81. from: spring.from.pos,
  82. to: spring.to.pos
  83. };
  84. }
  85. },
  86. /**
  87. * @returns {Object} area required to fit in the graph. Object contains
  88. * `x1`, `y1` - top left coordinates
  89. * `x2`, `y2` - bottom right coordinates
  90. */
  91. getGraphRect: function () {
  92. return physicsSimulator.getBBox();
  93. },
  94. /**
  95. * Iterates over each body in the layout simulator and performs a callback(body, nodeId)
  96. */
  97. forEachBody: forEachBody,
  98. /*
  99. * Requests layout algorithm to pin/unpin node to its current position
  100. * Pinned nodes should not be affected by layout algorithm and always
  101. * remain at their position
  102. */
  103. pinNode: function (node, isPinned) {
  104. var body = getInitializedBody(node.id);
  105. body.isPinned = !!isPinned;
  106. },
  107. /**
  108. * Checks whether given graph's node is currently pinned
  109. */
  110. isNodePinned: function (node) {
  111. return getInitializedBody(node.id).isPinned;
  112. },
  113. /**
  114. * Request to release all resources
  115. */
  116. dispose: function() {
  117. graph.off('changed', onGraphChanged);
  118. api.fire('disposed');
  119. },
  120. /**
  121. * Gets physical body for a given node id. If node is not found undefined
  122. * value is returned.
  123. */
  124. getBody: getBody,
  125. /**
  126. * Gets spring for a given edge.
  127. *
  128. * @param {string} linkId link identifer. If two arguments are passed then
  129. * this argument is treated as formNodeId
  130. * @param {string=} toId when defined this parameter denotes head of the link
  131. * and first argument is treated as tail of the link (fromId)
  132. */
  133. getSpring: getSpring,
  134. /**
  135. * Returns length of cumulative force vector. The closer this to zero - the more stable the system is
  136. */
  137. getForceVectorLength: getForceVectorLength,
  138. /**
  139. * [Read only] Gets current physics simulator
  140. */
  141. simulator: physicsSimulator,
  142. /**
  143. * Gets the graph that was used for layout
  144. */
  145. graph: graph,
  146. /**
  147. * Gets amount of movement performed during last step operation
  148. */
  149. lastMove: 0
  150. };
  151. eventify(api);
  152. return api;
  153. function updateStableStatus(isStableNow) {
  154. if (wasStable !== isStableNow) {
  155. wasStable = isStableNow;
  156. onStableChanged(isStableNow);
  157. }
  158. }
  159. function forEachBody(cb) {
  160. nodeBodies.forEach(cb);
  161. }
  162. function getForceVectorLength() {
  163. var fx = 0, fy = 0;
  164. forEachBody(function(body) {
  165. fx += Math.abs(body.force.x);
  166. fy += Math.abs(body.force.y);
  167. });
  168. return Math.sqrt(fx * fx + fy * fy);
  169. }
  170. function getSpring(fromId, toId) {
  171. var linkId;
  172. if (toId === undefined) {
  173. if (typeof fromId !== 'object') {
  174. // assume fromId as a linkId:
  175. linkId = fromId;
  176. } else {
  177. // assume fromId to be a link object:
  178. linkId = fromId.id;
  179. }
  180. } else {
  181. // toId is defined, should grab link:
  182. var link = graph.hasLink(fromId, toId);
  183. if (!link) return;
  184. linkId = link.id;
  185. }
  186. return springs[linkId];
  187. }
  188. function getBody(nodeId) {
  189. return nodeBodies.get(nodeId);
  190. }
  191. function listenToEvents() {
  192. graph.on('changed', onGraphChanged);
  193. }
  194. function onStableChanged(isStable) {
  195. api.fire('stable', isStable);
  196. }
  197. function onGraphChanged(changes) {
  198. for (var i = 0; i < changes.length; ++i) {
  199. var change = changes[i];
  200. if (change.changeType === 'add') {
  201. if (change.node) {
  202. initBody(change.node.id);
  203. }
  204. if (change.link) {
  205. initLink(change.link);
  206. }
  207. } else if (change.changeType === 'remove') {
  208. if (change.node) {
  209. releaseNode(change.node);
  210. }
  211. if (change.link) {
  212. releaseLink(change.link);
  213. }
  214. }
  215. }
  216. bodiesCount = graph.getNodesCount();
  217. }
  218. function initPhysics() {
  219. bodiesCount = 0;
  220. graph.forEachNode(function (node) {
  221. initBody(node.id);
  222. bodiesCount += 1;
  223. });
  224. graph.forEachLink(initLink);
  225. }
  226. function initBody(nodeId) {
  227. var body = nodeBodies.get(nodeId);
  228. if (!body) {
  229. var node = graph.getNode(nodeId);
  230. if (!node) {
  231. throw new Error('initBody() was called with unknown node id');
  232. }
  233. var pos = node.position;
  234. if (!pos) {
  235. var neighbors = getNeighborBodies(node);
  236. pos = physicsSimulator.getBestNewBodyPosition(neighbors);
  237. }
  238. body = physicsSimulator.addBodyAt(pos);
  239. body.id = nodeId;
  240. nodeBodies.set(nodeId, body);
  241. updateBodyMass(nodeId);
  242. if (isNodeOriginallyPinned(node)) {
  243. body.isPinned = true;
  244. }
  245. }
  246. }
  247. function releaseNode(node) {
  248. var nodeId = node.id;
  249. var body = nodeBodies.get(nodeId);
  250. if (body) {
  251. nodeBodies.delete(nodeId);
  252. physicsSimulator.removeBody(body);
  253. }
  254. }
  255. function initLink(link) {
  256. updateBodyMass(link.fromId);
  257. updateBodyMass(link.toId);
  258. var fromBody = nodeBodies.get(link.fromId),
  259. toBody = nodeBodies.get(link.toId),
  260. spring = physicsSimulator.addSpring(fromBody, toBody, link.length);
  261. springTransform(link, spring);
  262. springs[link.id] = spring;
  263. }
  264. function releaseLink(link) {
  265. var spring = springs[link.id];
  266. if (spring) {
  267. var from = graph.getNode(link.fromId),
  268. to = graph.getNode(link.toId);
  269. if (from) updateBodyMass(from.id);
  270. if (to) updateBodyMass(to.id);
  271. delete springs[link.id];
  272. physicsSimulator.removeSpring(spring);
  273. }
  274. }
  275. function getNeighborBodies(node) {
  276. // TODO: Could probably be done better on memory
  277. var neighbors = [];
  278. if (!node.links) {
  279. return neighbors;
  280. }
  281. var maxNeighbors = Math.min(node.links.length, 2);
  282. for (var i = 0; i < maxNeighbors; ++i) {
  283. var link = node.links[i];
  284. var otherBody = link.fromId !== node.id ? nodeBodies.get(link.fromId) : nodeBodies.get(link.toId);
  285. if (otherBody && otherBody.pos) {
  286. neighbors.push(otherBody);
  287. }
  288. }
  289. return neighbors;
  290. }
  291. function updateBodyMass(nodeId) {
  292. var body = nodeBodies.get(nodeId);
  293. body.mass = nodeMass(nodeId);
  294. if (Number.isNaN(body.mass)) {
  295. throw new Error('Node mass should be a number');
  296. }
  297. }
  298. /**
  299. * Checks whether graph node has in its settings pinned attribute,
  300. * which means layout algorithm cannot move it. Node can be marked
  301. * as pinned, if it has "isPinned" attribute, or when node.data has it.
  302. *
  303. * @param {Object} node a graph node to check
  304. * @return {Boolean} true if node should be treated as pinned; false otherwise.
  305. */
  306. function isNodeOriginallyPinned(node) {
  307. return (node && (node.isPinned || (node.data && node.data.isPinned)));
  308. }
  309. function getInitializedBody(nodeId) {
  310. var body = nodeBodies.get(nodeId);
  311. if (!body) {
  312. initBody(nodeId);
  313. body = nodeBodies.get(nodeId);
  314. }
  315. return body;
  316. }
  317. /**
  318. * Calculates mass of a body, which corresponds to node with given id.
  319. *
  320. * @param {String|Number} nodeId identifier of a node, for which body mass needs to be calculated
  321. * @returns {Number} recommended mass of the body;
  322. */
  323. function defaultNodeMass(nodeId) {
  324. var links = graph.getLinks(nodeId);
  325. if (!links) return 1;
  326. return 1 + links.length / 3.0;
  327. }
  328. }
  329. function noop() { }
  330. },{"./lib/createPhysicsSimulator":8,"ngraph.events":10}],2:[function(require,module,exports){
  331. module.exports = function() { return function anonymous(bodies,settings,random
  332. ) {
  333. var boundingBox = {
  334. min_x: 0, max_x: 0,
  335. min_y: 0, max_y: 0,
  336. };
  337. return {
  338. box: boundingBox,
  339. update: updateBoundingBox,
  340. reset: resetBoundingBox,
  341. getBestNewPosition: function (neighbors) {
  342. var base_x = 0, base_y = 0;
  343. if (neighbors.length) {
  344. for (var i = 0; i < neighbors.length; ++i) {
  345. let neighborPos = neighbors[i].pos;
  346. base_x += neighborPos.x;
  347. base_y += neighborPos.y;
  348. }
  349. base_x /= neighbors.length;
  350. base_y /= neighbors.length;
  351. } else {
  352. base_x = (boundingBox.min_x + boundingBox.max_x) / 2;
  353. base_y = (boundingBox.min_y + boundingBox.max_y) / 2;
  354. }
  355. var springLength = settings.springLength;
  356. return {
  357. x: base_x + (random.nextDouble() - 0.5) * springLength,
  358. y: base_y + (random.nextDouble() - 0.5) * springLength,
  359. };
  360. }
  361. };
  362. function updateBoundingBox() {
  363. var i = bodies.length;
  364. if (i === 0) return; // No bodies - no borders.
  365. var max_x = -Infinity;
  366. var max_y = -Infinity;
  367. var min_x = Infinity;
  368. var min_y = Infinity;
  369. while(i--) {
  370. // this is O(n), it could be done faster with quadtree, if we check the root node bounds
  371. var bodyPos = bodies[i].pos;
  372. if (bodyPos.x < min_x) min_x = bodyPos.x;
  373. if (bodyPos.y < min_y) min_y = bodyPos.y;
  374. if (bodyPos.x > max_x) max_x = bodyPos.x;
  375. if (bodyPos.y > max_y) max_y = bodyPos.y;
  376. }
  377. boundingBox.min_x = min_x;
  378. boundingBox.min_y = min_y;
  379. boundingBox.max_x = max_x;
  380. boundingBox.max_y = max_y;
  381. }
  382. function resetBoundingBox() {
  383. boundingBox.min_x = boundingBox.max_x = 0;
  384. boundingBox.min_y = boundingBox.max_y = 0;
  385. }
  386. } }
  387. },{}],3:[function(require,module,exports){
  388. function Vector(x, y) {
  389. if (typeof arguments[0] === 'object') {
  390. // could be another vector
  391. let v = arguments[0];
  392. if (!Number.isFinite(v.x)) throw new Error("Expected value is not a finite number at Vector constructor (x)");
  393. if (!Number.isFinite(v.y)) throw new Error("Expected value is not a finite number at Vector constructor (y)");
  394. this.x = v.x;
  395. this.y = v.y;
  396. } else {
  397. this.x = typeof x === "number" ? x : 0;
  398. this.y = typeof y === "number" ? y : 0;
  399. }
  400. }
  401. Vector.prototype.reset = function () {
  402. this.x = this.y = 0;
  403. };
  404. function Body(x, y) {
  405. this.isPinned = false;
  406. this.pos = new Vector(x, y);
  407. this.force = new Vector();
  408. this.velocity = new Vector();
  409. this.mass = 1;
  410. this.springCount = 0;
  411. this.springLength = 0;
  412. }
  413. Body.prototype.reset = function() {
  414. this.force.reset();
  415. this.springCount = 0;
  416. this.springLength = 0;
  417. }
  418. Body.prototype.setPosition = function (x, y) {
  419. this.pos.x = x || 0;
  420. this.pos.y = y || 0;
  421. };
  422. module.exports = function() { return Body; }
  423. },{}],4:[function(require,module,exports){
  424. module.exports = function() { return function anonymous(options
  425. ) {
  426. if (!Number.isFinite(options.dragCoefficient)) throw new Error('dragCoefficient is not a finite number');
  427. return {
  428. update: function(body) {
  429. body.force.x -= options.dragCoefficient * body.velocity.x;
  430. body.force.y -= options.dragCoefficient * body.velocity.y;
  431. }
  432. };
  433. } }
  434. },{}],5:[function(require,module,exports){
  435. module.exports = function() { return function anonymous(options,random
  436. ) {
  437. if (!Number.isFinite(options.springCoefficient)) throw new Error('Spring coefficient is not a number');
  438. if (!Number.isFinite(options.springLength)) throw new Error('Spring length is not a number');
  439. return {
  440. /**
  441. * Updates forces acting on a spring
  442. */
  443. update: function (spring) {
  444. var body1 = spring.from;
  445. var body2 = spring.to;
  446. var length = spring.length < 0 ? options.springLength : spring.length;
  447. var dx = body2.pos.x - body1.pos.x;
  448. var dy = body2.pos.y - body1.pos.y;
  449. var r = Math.sqrt(dx * dx + dy * dy);
  450. if (r === 0) {
  451. dx = (random.nextDouble() - 0.5) / 50;
  452. dy = (random.nextDouble() - 0.5) / 50;
  453. r = Math.sqrt(dx * dx + dy * dy);
  454. }
  455. var d = r - length;
  456. var coefficient = ((spring.coefficient > 0) ? spring.coefficient : options.springCoefficient) * d / r;
  457. body1.force.x += coefficient * dx
  458. body1.force.y += coefficient * dy;
  459. body1.springCount += 1;
  460. body1.springLength += r;
  461. body2.force.x -= coefficient * dx
  462. body2.force.y -= coefficient * dy;
  463. body2.springCount += 1;
  464. body2.springLength += r;
  465. }
  466. };
  467. } }
  468. },{}],6:[function(require,module,exports){
  469. module.exports = function() { return function anonymous(bodies,timeStep,adaptiveTimeStepWeight
  470. ) {
  471. var length = bodies.length;
  472. if (length === 0) return 0;
  473. var dx = 0, tx = 0;
  474. var dy = 0, ty = 0;
  475. for (var i = 0; i < length; ++i) {
  476. var body = bodies[i];
  477. if (body.isPinned) continue;
  478. if (adaptiveTimeStepWeight && body.springCount) {
  479. timeStep = (adaptiveTimeStepWeight * body.springLength/body.springCount);
  480. }
  481. var coeff = timeStep / body.mass;
  482. body.velocity.x += coeff * body.force.x;
  483. body.velocity.y += coeff * body.force.y;
  484. var vx = body.velocity.x;
  485. var vy = body.velocity.y;
  486. var v = Math.sqrt(vx * vx + vy * vy);
  487. if (v > 1) {
  488. // We normalize it so that we move within timeStep range.
  489. // for the case when v <= 1 - we let velocity to fade out.
  490. body.velocity.x = vx / v;
  491. body.velocity.y = vy / v;
  492. }
  493. dx = timeStep * body.velocity.x;
  494. dy = timeStep * body.velocity.y;
  495. body.pos.x += dx;
  496. body.pos.y += dy;
  497. tx += Math.abs(dx);
  498. ty += Math.abs(dy);
  499. }
  500. return (tx * tx + ty * ty)/length;
  501. } }
  502. },{}],7:[function(require,module,exports){
  503. /**
  504. * Our implementation of QuadTree is non-recursive to avoid GC hit
  505. * This data structure represent stack of elements
  506. * which we are trying to insert into quad tree.
  507. */
  508. function InsertStack () {
  509. this.stack = [];
  510. this.popIdx = 0;
  511. }
  512. InsertStack.prototype = {
  513. isEmpty: function() {
  514. return this.popIdx === 0;
  515. },
  516. push: function (node, body) {
  517. var item = this.stack[this.popIdx];
  518. if (!item) {
  519. // we are trying to avoid memory pressure: create new element
  520. // only when absolutely necessary
  521. this.stack[this.popIdx] = new InsertStackElement(node, body);
  522. } else {
  523. item.node = node;
  524. item.body = body;
  525. }
  526. ++this.popIdx;
  527. },
  528. pop: function () {
  529. if (this.popIdx > 0) {
  530. return this.stack[--this.popIdx];
  531. }
  532. },
  533. reset: function () {
  534. this.popIdx = 0;
  535. }
  536. };
  537. function InsertStackElement(node, body) {
  538. this.node = node; // QuadTree node
  539. this.body = body; // physical body which needs to be inserted to node
  540. }
  541. function QuadNode() {
  542. // body stored inside this node. In quad tree only leaf nodes (by construction)
  543. // contain bodies:
  544. this.body = null;
  545. // Child nodes are stored in quads. Each quad is presented by number:
  546. // 0 | 1
  547. // -----
  548. // 2 | 3
  549. this.quad0 = null;
  550. this.quad1 = null;
  551. this.quad2 = null;
  552. this.quad3 = null;
  553. // Total mass of current node
  554. this.mass = 0;
  555. // Center of mass coordinates
  556. this.mass_x = 0;
  557. this.mass_y = 0;
  558. // bounding box coordinates
  559. this.min_x = 0;
  560. this.min_y = 0;
  561. this.max_x = 0;
  562. this.max_y = 0;
  563. }
  564. function isSamePosition(point1, point2) {
  565. var dx = Math.abs(point1.x - point2.x);
  566. var dy = Math.abs(point1.y - point2.y);
  567. return dx < 1e-8 && dy < 1e-8;
  568. }
  569. function getChild(node, idx) {
  570. if (idx === 0) return node.quad0;
  571. if (idx === 1) return node.quad1;
  572. if (idx === 2) return node.quad2;
  573. if (idx === 3) return node.quad3;
  574. return null;
  575. }
  576. function setChild(node, idx, child) {
  577. if (idx === 0) node.quad0 = child;
  578. else if (idx === 1) node.quad1 = child;
  579. else if (idx === 2) node.quad2 = child;
  580. else if (idx === 3) node.quad3 = child;
  581. }
  582. module.exports = function() { return function createQuadTree(options, random) {
  583. options = options || {};
  584. options.gravity = typeof options.gravity === 'number' ? options.gravity : -1;
  585. options.theta = typeof options.theta === 'number' ? options.theta : 0.8;
  586. var gravity = options.gravity;
  587. var updateQueue = [];
  588. var insertStack = new InsertStack();
  589. var theta = options.theta;
  590. var nodesCache = [];
  591. var currentInCache = 0;
  592. var root = newNode();
  593. return {
  594. insertBodies: insertBodies,
  595. /**
  596. * Gets root node if it is present
  597. */
  598. getRoot: function() {
  599. return root;
  600. },
  601. updateBodyForce: update,
  602. options: function(newOptions) {
  603. if (newOptions) {
  604. if (typeof newOptions.gravity === 'number') {
  605. gravity = newOptions.gravity;
  606. }
  607. if (typeof newOptions.theta === 'number') {
  608. theta = newOptions.theta;
  609. }
  610. return this;
  611. }
  612. return {
  613. gravity: gravity,
  614. theta: theta
  615. };
  616. }
  617. };
  618. function newNode() {
  619. // To avoid pressure on GC we reuse nodes.
  620. var node = nodesCache[currentInCache];
  621. if (node) {
  622. node.quad0 = null;
  623. node.quad1 = null;
  624. node.quad2 = null;
  625. node.quad3 = null;
  626. node.body = null;
  627. node.mass = node.mass_x = node.mass_y = 0;
  628. node.min_x = node.max_x = node.min_y = node.max_y = 0;
  629. } else {
  630. node = new QuadNode();
  631. nodesCache[currentInCache] = node;
  632. }
  633. ++currentInCache;
  634. return node;
  635. }
  636. function update(sourceBody) {
  637. var queue = updateQueue;
  638. var v;
  639. var dx;
  640. var dy;
  641. var r;
  642. var fx = 0;
  643. var fy = 0;
  644. var queueLength = 1;
  645. var shiftIdx = 0;
  646. var pushIdx = 1;
  647. queue[0] = root;
  648. while (queueLength) {
  649. var node = queue[shiftIdx];
  650. var body = node.body;
  651. queueLength -= 1;
  652. shiftIdx += 1;
  653. var differentBody = (body !== sourceBody);
  654. if (body && differentBody) {
  655. // If the current node is a leaf node (and it is not source body),
  656. // calculate the force exerted by the current node on body, and add this
  657. // amount to body's net force.
  658. dx = body.pos.x - sourceBody.pos.x;
  659. dy = body.pos.y - sourceBody.pos.y;
  660. r = Math.sqrt(dx * dx + dy * dy);
  661. if (r === 0) {
  662. // Poor man's protection against zero distance.
  663. dx = (random.nextDouble() - 0.5) / 50;
  664. dy = (random.nextDouble() - 0.5) / 50;
  665. r = Math.sqrt(dx * dx + dy * dy);
  666. }
  667. // This is standard gravitation force calculation but we divide
  668. // by r^3 to save two operations when normalizing force vector.
  669. v = gravity * body.mass * sourceBody.mass / (r * r * r);
  670. fx += v * dx;
  671. fy += v * dy;
  672. } else if (differentBody) {
  673. // Otherwise, calculate the ratio s / r, where s is the width of the region
  674. // represented by the internal node, and r is the distance between the body
  675. // and the node's center-of-mass
  676. dx = node.mass_x / node.mass - sourceBody.pos.x;
  677. dy = node.mass_y / node.mass - sourceBody.pos.y;
  678. r = Math.sqrt(dx * dx + dy * dy);
  679. if (r === 0) {
  680. // Sorry about code duplication. I don't want to create many functions
  681. // right away. Just want to see performance first.
  682. dx = (random.nextDouble() - 0.5) / 50;
  683. dy = (random.nextDouble() - 0.5) / 50;
  684. r = Math.sqrt(dx * dx + dy * dy);
  685. }
  686. // If s / r < θ, treat this internal node as a single body, and calculate the
  687. // force it exerts on sourceBody, and add this amount to sourceBody's net force.
  688. if ((node.max_x - node.min_x) / r < theta) {
  689. // in the if statement above we consider node's width only
  690. // because the region was made into square during tree creation.
  691. // Thus there is no difference between using width or height.
  692. v = gravity * node.mass * sourceBody.mass / (r * r * r);
  693. fx += v * dx;
  694. fy += v * dy;
  695. } else {
  696. // Otherwise, run the procedure recursively on each of the current node's children.
  697. // I intentionally unfolded this loop, to save several CPU cycles.
  698. if (node.quad0) {
  699. queue[pushIdx] = node.quad0;
  700. queueLength += 1;
  701. pushIdx += 1;
  702. }
  703. if (node.quad1) {
  704. queue[pushIdx] = node.quad1;
  705. queueLength += 1;
  706. pushIdx += 1;
  707. }
  708. if (node.quad2) {
  709. queue[pushIdx] = node.quad2;
  710. queueLength += 1;
  711. pushIdx += 1;
  712. }
  713. if (node.quad3) {
  714. queue[pushIdx] = node.quad3;
  715. queueLength += 1;
  716. pushIdx += 1;
  717. }
  718. }
  719. }
  720. }
  721. sourceBody.force.x += fx;
  722. sourceBody.force.y += fy;
  723. }
  724. function insertBodies(bodies) {
  725. var xmin = Number.MAX_VALUE;
  726. var ymin = Number.MAX_VALUE;
  727. var xmax = Number.MIN_VALUE;
  728. var ymax = Number.MIN_VALUE;
  729. var i = bodies.length;
  730. // To reduce quad tree depth we are looking for exact bounding box of all particles.
  731. while (i--) {
  732. var pos = bodies[i].pos;
  733. if (pos.x < xmin) xmin = pos.x;
  734. if (pos.y < ymin) ymin = pos.y;
  735. if (pos.x > xmax) xmax = pos.x;
  736. if (pos.y > ymax) ymax = pos.y;
  737. }
  738. // Makes the bounds square.
  739. var maxSideLength = -Infinity;
  740. if (xmax - xmin > maxSideLength) maxSideLength = xmax - xmin ;
  741. if (ymax - ymin > maxSideLength) maxSideLength = ymax - ymin ;
  742. currentInCache = 0;
  743. root = newNode();
  744. root.min_x = xmin;
  745. root.min_y = ymin;
  746. root.max_x = xmin + maxSideLength;
  747. root.max_y = ymin + maxSideLength;
  748. i = bodies.length - 1;
  749. if (i >= 0) {
  750. root.body = bodies[i];
  751. }
  752. while (i--) {
  753. insert(bodies[i], root);
  754. }
  755. }
  756. function insert(newBody) {
  757. insertStack.reset();
  758. insertStack.push(root, newBody);
  759. while (!insertStack.isEmpty()) {
  760. var stackItem = insertStack.pop();
  761. var node = stackItem.node;
  762. var body = stackItem.body;
  763. if (!node.body) {
  764. // This is internal node. Update the total mass of the node and center-of-mass.
  765. var x = body.pos.x;
  766. var y = body.pos.y;
  767. node.mass += body.mass;
  768. node.mass_x += body.mass * x;
  769. node.mass_y += body.mass * y;
  770. // Recursively insert the body in the appropriate quadrant.
  771. // But first find the appropriate quadrant.
  772. var quadIdx = 0; // Assume we are in the 0's quad.
  773. var min_x = node.min_x;
  774. var min_y = node.min_y;
  775. var max_x = (min_x + node.max_x) / 2;
  776. var max_y = (min_y + node.max_y) / 2;
  777. if (x > max_x) {
  778. quadIdx = quadIdx + 1;
  779. min_x = max_x;
  780. max_x = node.max_x;
  781. }
  782. if (y > max_y) {
  783. quadIdx = quadIdx + 2;
  784. min_y = max_y;
  785. max_y = node.max_y;
  786. }
  787. var child = getChild(node, quadIdx);
  788. if (!child) {
  789. // The node is internal but this quadrant is not taken. Add
  790. // subnode to it.
  791. child = newNode();
  792. child.min_x = min_x;
  793. child.min_y = min_y;
  794. child.max_x = max_x;
  795. child.max_y = max_y;
  796. child.body = body;
  797. setChild(node, quadIdx, child);
  798. } else {
  799. // continue searching in this quadrant.
  800. insertStack.push(child, body);
  801. }
  802. } else {
  803. // We are trying to add to the leaf node.
  804. // We have to convert current leaf into internal node
  805. // and continue adding two nodes.
  806. var oldBody = node.body;
  807. node.body = null; // internal nodes do not cary bodies
  808. if (isSamePosition(oldBody.pos, body.pos)) {
  809. // Prevent infinite subdivision by bumping one node
  810. // anywhere in this quadrant
  811. var retriesCount = 3;
  812. do {
  813. var offset = random.nextDouble();
  814. var dx = (node.max_x - node.min_x) * offset;
  815. var dy = (node.max_y - node.min_y) * offset;
  816. oldBody.pos.x = node.min_x + dx;
  817. oldBody.pos.y = node.min_y + dy;
  818. retriesCount -= 1;
  819. // Make sure we don't bump it out of the box. If we do, next iteration should fix it
  820. } while (retriesCount > 0 && isSamePosition(oldBody.pos, body.pos));
  821. if (retriesCount === 0 && isSamePosition(oldBody.pos, body.pos)) {
  822. // This is very bad, we ran out of precision.
  823. // if we do not return from the method we'll get into
  824. // infinite loop here. So we sacrifice correctness of layout, and keep the app running
  825. // Next layout iteration should get larger bounding box in the first step and fix this
  826. return;
  827. }
  828. }
  829. // Next iteration should subdivide node further.
  830. insertStack.push(node, oldBody);
  831. insertStack.push(node, body);
  832. }
  833. }
  834. }
  835. } }
  836. },{}],8:[function(require,module,exports){
  837. /**
  838. * Manages a simulation of physical forces acting on bodies and springs.
  839. */
  840. module.exports = createPhysicsSimulator;
  841. var generateCreateBodyFunction = require('./codeGenerators/generateCreateBody');
  842. var generateQuadTreeFunction = require('./codeGenerators/generateQuadTree');
  843. var generateBoundsFunction = require('./codeGenerators/generateBounds');
  844. var generateCreateDragForceFunction = require('./codeGenerators/generateCreateDragForce');
  845. var generateCreateSpringForceFunction = require('./codeGenerators/generateCreateSpringForce');
  846. var generateIntegratorFunction = require('./codeGenerators/generateIntegrator');
  847. var dimensionalCache = {};
  848. function createPhysicsSimulator(settings) {
  849. var Spring = require('./spring');
  850. var merge = require('ngraph.merge');
  851. var eventify = require('ngraph.events');
  852. if (settings) {
  853. // Check for names from older versions of the layout
  854. if (settings.springCoeff !== undefined) throw new Error('springCoeff was renamed to springCoefficient');
  855. if (settings.dragCoeff !== undefined) throw new Error('dragCoeff was renamed to dragCoefficient');
  856. }
  857. settings = merge(settings, {
  858. /**
  859. * Ideal length for links (springs in physical model).
  860. */
  861. springLength: 10,
  862. /**
  863. * Hook's law coefficient. 1 - solid spring.
  864. */
  865. springCoefficient: 0.8,
  866. /**
  867. * Coulomb's law coefficient. It's used to repel nodes thus should be negative
  868. * if you make it positive nodes start attract each other :).
  869. */
  870. gravity: -12,
  871. /**
  872. * Theta coefficient from Barnes Hut simulation. Ranged between (0, 1).
  873. * The closer it's to 1 the more nodes algorithm will have to go through.
  874. * Setting it to one makes Barnes Hut simulation no different from
  875. * brute-force forces calculation (each node is considered).
  876. */
  877. theta: 0.8,
  878. /**
  879. * Drag force coefficient. Used to slow down system, thus should be less than 1.
  880. * The closer it is to 0 the less tight system will be.
  881. */
  882. dragCoefficient: 0.9, // TODO: Need to rename this to something better. E.g. `dragCoefficient`
  883. /**
  884. * Default time step (dt) for forces integration
  885. */
  886. timeStep : 0.5,
  887. /**
  888. * Adaptive time step uses average spring length to compute actual time step:
  889. * See: https://twitter.com/anvaka/status/1293067160755957760
  890. */
  891. adaptiveTimeStepWeight: 0,
  892. /**
  893. * This parameter defines number of dimensions of the space where simulation
  894. * is performed.
  895. */
  896. dimensions: 2,
  897. /**
  898. * In debug mode more checks are performed, this will help you catch errors
  899. * quickly, however for production build it is recommended to turn off this flag
  900. * to speed up computation.
  901. */
  902. debug: false
  903. });
  904. var factory = dimensionalCache[settings.dimensions];
  905. if (!factory) {
  906. var dimensions = settings.dimensions;
  907. factory = {
  908. Body: generateCreateBodyFunction(dimensions, settings.debug),
  909. createQuadTree: generateQuadTreeFunction(dimensions),
  910. createBounds: generateBoundsFunction(dimensions),
  911. createDragForce: generateCreateDragForceFunction(dimensions),
  912. createSpringForce: generateCreateSpringForceFunction(dimensions),
  913. integrate: generateIntegratorFunction(dimensions),
  914. };
  915. dimensionalCache[dimensions] = factory;
  916. }
  917. var Body = factory.Body;
  918. var createQuadTree = factory.createQuadTree;
  919. var createBounds = factory.createBounds;
  920. var createDragForce = factory.createDragForce;
  921. var createSpringForce = factory.createSpringForce;
  922. var integrate = factory.integrate;
  923. var createBody = pos => new Body(pos);
  924. var random = require('ngraph.random').random(42);
  925. var bodies = []; // Bodies in this simulation.
  926. var springs = []; // Springs in this simulation.
  927. var quadTree = createQuadTree(settings, random);
  928. var bounds = createBounds(bodies, settings, random);
  929. var springForce = createSpringForce(settings, random);
  930. var dragForce = createDragForce(settings);
  931. var totalMovement = 0; // how much movement we made on last step
  932. var forces = [];
  933. var forceMap = new Map();
  934. var iterationNumber = 0;
  935. addForce('nbody', nbodyForce);
  936. addForce('spring', updateSpringForce);
  937. var publicApi = {
  938. /**
  939. * Array of bodies, registered with current simulator
  940. *
  941. * Note: To add new body, use addBody() method. This property is only
  942. * exposed for testing/performance purposes.
  943. */
  944. bodies: bodies,
  945. quadTree: quadTree,
  946. /**
  947. * Array of springs, registered with current simulator
  948. *
  949. * Note: To add new spring, use addSpring() method. This property is only
  950. * exposed for testing/performance purposes.
  951. */
  952. springs: springs,
  953. /**
  954. * Returns settings with which current simulator was initialized
  955. */
  956. settings: settings,
  957. /**
  958. * Adds a new force to simulation
  959. */
  960. addForce: addForce,
  961. /**
  962. * Removes a force from the simulation.
  963. */
  964. removeForce: removeForce,
  965. /**
  966. * Returns a map of all registered forces.
  967. */
  968. getForces: getForces,
  969. /**
  970. * Performs one step of force simulation.
  971. *
  972. * @returns {boolean} true if system is considered stable; False otherwise.
  973. */
  974. step: function () {
  975. for (var i = 0; i < forces.length; ++i) {
  976. forces[i](iterationNumber);
  977. }
  978. var movement = integrate(bodies, settings.timeStep, settings.adaptiveTimeStepWeight);
  979. iterationNumber += 1;
  980. return movement;
  981. },
  982. /**
  983. * Adds body to the system
  984. *
  985. * @param {ngraph.physics.primitives.Body} body physical body
  986. *
  987. * @returns {ngraph.physics.primitives.Body} added body
  988. */
  989. addBody: function (body) {
  990. if (!body) {
  991. throw new Error('Body is required');
  992. }
  993. bodies.push(body);
  994. return body;
  995. },
  996. /**
  997. * Adds body to the system at given position
  998. *
  999. * @param {Object} pos position of a body
  1000. *
  1001. * @returns {ngraph.physics.primitives.Body} added body
  1002. */
  1003. addBodyAt: function (pos) {
  1004. if (!pos) {
  1005. throw new Error('Body position is required');
  1006. }
  1007. var body = createBody(pos);
  1008. bodies.push(body);
  1009. return body;
  1010. },
  1011. /**
  1012. * Removes body from the system
  1013. *
  1014. * @param {ngraph.physics.primitives.Body} body to remove
  1015. *
  1016. * @returns {Boolean} true if body found and removed. falsy otherwise;
  1017. */
  1018. removeBody: function (body) {
  1019. if (!body) { return; }
  1020. var idx = bodies.indexOf(body);
  1021. if (idx < 0) { return; }
  1022. bodies.splice(idx, 1);
  1023. if (bodies.length === 0) {
  1024. bounds.reset();
  1025. }
  1026. return true;
  1027. },
  1028. /**
  1029. * Adds a spring to this simulation.
  1030. *
  1031. * @returns {Object} - a handle for a spring. If you want to later remove
  1032. * spring pass it to removeSpring() method.
  1033. */
  1034. addSpring: function (body1, body2, springLength, springCoefficient) {
  1035. if (!body1 || !body2) {
  1036. throw new Error('Cannot add null spring to force simulator');
  1037. }
  1038. if (typeof springLength !== 'number') {
  1039. springLength = -1; // assume global configuration
  1040. }
  1041. var spring = new Spring(body1, body2, springLength, springCoefficient >= 0 ? springCoefficient : -1);
  1042. springs.push(spring);
  1043. // TODO: could mark simulator as dirty.
  1044. return spring;
  1045. },
  1046. /**
  1047. * Returns amount of movement performed on last step() call
  1048. */
  1049. getTotalMovement: function () {
  1050. return totalMovement;
  1051. },
  1052. /**
  1053. * Removes spring from the system
  1054. *
  1055. * @param {Object} spring to remove. Spring is an object returned by addSpring
  1056. *
  1057. * @returns {Boolean} true if spring found and removed. falsy otherwise;
  1058. */
  1059. removeSpring: function (spring) {
  1060. if (!spring) { return; }
  1061. var idx = springs.indexOf(spring);
  1062. if (idx > -1) {
  1063. springs.splice(idx, 1);
  1064. return true;
  1065. }
  1066. },
  1067. getBestNewBodyPosition: function (neighbors) {
  1068. return bounds.getBestNewPosition(neighbors);
  1069. },
  1070. /**
  1071. * Returns bounding box which covers all bodies
  1072. */
  1073. getBBox: getBoundingBox,
  1074. getBoundingBox: getBoundingBox,
  1075. invalidateBBox: function () {
  1076. console.warn('invalidateBBox() is deprecated, bounds always recomputed on `getBBox()` call');
  1077. },
  1078. // TODO: Move the force specific stuff to force
  1079. gravity: function (value) {
  1080. if (value !== undefined) {
  1081. settings.gravity = value;
  1082. quadTree.options({gravity: value});
  1083. return this;
  1084. } else {
  1085. return settings.gravity;
  1086. }
  1087. },
  1088. theta: function (value) {
  1089. if (value !== undefined) {
  1090. settings.theta = value;
  1091. quadTree.options({theta: value});
  1092. return this;
  1093. } else {
  1094. return settings.theta;
  1095. }
  1096. },
  1097. /**
  1098. * Returns pseudo-random number generator instance.
  1099. */
  1100. random: random
  1101. };
  1102. // allow settings modification via public API:
  1103. expose(settings, publicApi);
  1104. eventify(publicApi);
  1105. return publicApi;
  1106. function getBoundingBox() {
  1107. bounds.update();
  1108. return bounds.box;
  1109. }
  1110. function addForce(forceName, forceFunction) {
  1111. if (forceMap.has(forceName)) throw new Error('Force ' + forceName + ' is already added');
  1112. forceMap.set(forceName, forceFunction);
  1113. forces.push(forceFunction);
  1114. }
  1115. function removeForce(forceName) {
  1116. var forceIndex = forces.indexOf(forceMap.get(forceName));
  1117. if (forceIndex < 0) return;
  1118. forces.splice(forceIndex, 1);
  1119. forceMap.delete(forceName);
  1120. }
  1121. function getForces() {
  1122. // TODO: Should I trust them or clone the forces?
  1123. return forceMap;
  1124. }
  1125. function nbodyForce(/* iterationUmber */) {
  1126. if (bodies.length === 0) return;
  1127. quadTree.insertBodies(bodies);
  1128. var i = bodies.length;
  1129. while (i--) {
  1130. var body = bodies[i];
  1131. if (!body.isPinned) {
  1132. body.reset();
  1133. quadTree.updateBodyForce(body);
  1134. dragForce.update(body);
  1135. }
  1136. }
  1137. }
  1138. function updateSpringForce() {
  1139. var i = springs.length;
  1140. while (i--) {
  1141. springForce.update(springs[i]);
  1142. }
  1143. }
  1144. }
  1145. function expose(settings, target) {
  1146. for (var key in settings) {
  1147. augment(settings, target, key);
  1148. }
  1149. }
  1150. function augment(source, target, key) {
  1151. if (!source.hasOwnProperty(key)) return;
  1152. if (typeof target[key] === 'function') {
  1153. // this accessor is already defined. Ignore it
  1154. return;
  1155. }
  1156. var sourceIsNumber = Number.isFinite(source[key]);
  1157. if (sourceIsNumber) {
  1158. target[key] = function (value) {
  1159. if (value !== undefined) {
  1160. if (!Number.isFinite(value)) throw new Error('Value of ' + key + ' should be a valid number.');
  1161. source[key] = value;
  1162. return target;
  1163. }
  1164. return source[key];
  1165. };
  1166. } else {
  1167. target[key] = function (value) {
  1168. if (value !== undefined) {
  1169. source[key] = value;
  1170. return target;
  1171. }
  1172. return source[key];
  1173. };
  1174. }
  1175. }
  1176. },{"./codeGenerators/generateBounds":2,"./codeGenerators/generateCreateBody":3,"./codeGenerators/generateCreateDragForce":4,"./codeGenerators/generateCreateSpringForce":5,"./codeGenerators/generateIntegrator":6,"./codeGenerators/generateQuadTree":7,"./spring":9,"ngraph.events":10,"ngraph.merge":11,"ngraph.random":12}],9:[function(require,module,exports){
  1177. module.exports = Spring;
  1178. /**
  1179. * Represents a physical spring. Spring connects two bodies, has rest length
  1180. * stiffness coefficient and optional weight
  1181. */
  1182. function Spring(fromBody, toBody, length, springCoefficient) {
  1183. this.from = fromBody;
  1184. this.to = toBody;
  1185. this.length = length;
  1186. this.coefficient = springCoefficient;
  1187. }
  1188. },{}],10:[function(require,module,exports){
  1189. module.exports = function eventify(subject) {
  1190. validateSubject(subject);
  1191. var eventsStorage = createEventsStorage(subject);
  1192. subject.on = eventsStorage.on;
  1193. subject.off = eventsStorage.off;
  1194. subject.fire = eventsStorage.fire;
  1195. return subject;
  1196. };
  1197. function createEventsStorage(subject) {
  1198. // Store all event listeners to this hash. Key is event name, value is array
  1199. // of callback records.
  1200. //
  1201. // A callback record consists of callback function and its optional context:
  1202. // { 'eventName' => [{callback: function, ctx: object}] }
  1203. var registeredEvents = Object.create(null);
  1204. return {
  1205. on: function (eventName, callback, ctx) {
  1206. if (typeof callback !== 'function') {
  1207. throw new Error('callback is expected to be a function');
  1208. }
  1209. var handlers = registeredEvents[eventName];
  1210. if (!handlers) {
  1211. handlers = registeredEvents[eventName] = [];
  1212. }
  1213. handlers.push({callback: callback, ctx: ctx});
  1214. return subject;
  1215. },
  1216. off: function (eventName, callback) {
  1217. var wantToRemoveAll = (typeof eventName === 'undefined');
  1218. if (wantToRemoveAll) {
  1219. // Killing old events storage should be enough in this case:
  1220. registeredEvents = Object.create(null);
  1221. return subject;
  1222. }
  1223. if (registeredEvents[eventName]) {
  1224. var deleteAllCallbacksForEvent = (typeof callback !== 'function');
  1225. if (deleteAllCallbacksForEvent) {
  1226. delete registeredEvents[eventName];
  1227. } else {
  1228. var callbacks = registeredEvents[eventName];
  1229. for (var i = 0; i < callbacks.length; ++i) {
  1230. if (callbacks[i].callback === callback) {
  1231. callbacks.splice(i, 1);
  1232. }
  1233. }
  1234. }
  1235. }
  1236. return subject;
  1237. },
  1238. fire: function (eventName) {
  1239. var callbacks = registeredEvents[eventName];
  1240. if (!callbacks) {
  1241. return subject;
  1242. }
  1243. var fireArguments;
  1244. if (arguments.length > 1) {
  1245. fireArguments = Array.prototype.splice.call(arguments, 1);
  1246. }
  1247. for(var i = 0; i < callbacks.length; ++i) {
  1248. var callbackInfo = callbacks[i];
  1249. callbackInfo.callback.apply(callbackInfo.ctx, fireArguments);
  1250. }
  1251. return subject;
  1252. }
  1253. };
  1254. }
  1255. function validateSubject(subject) {
  1256. if (!subject) {
  1257. throw new Error('Eventify cannot use falsy object as events subject');
  1258. }
  1259. var reservedWords = ['on', 'fire', 'off'];
  1260. for (var i = 0; i < reservedWords.length; ++i) {
  1261. if (subject.hasOwnProperty(reservedWords[i])) {
  1262. throw new Error("Subject cannot be eventified, since it already has property '" + reservedWords[i] + "'");
  1263. }
  1264. }
  1265. }
  1266. },{}],11:[function(require,module,exports){
  1267. module.exports = merge;
  1268. /**
  1269. * Augments `target` with properties in `options`. Does not override
  1270. * target's properties if they are defined and matches expected type in
  1271. * options
  1272. *
  1273. * @returns {Object} merged object
  1274. */
  1275. function merge(target, options) {
  1276. var key;
  1277. if (!target) { target = {}; }
  1278. if (options) {
  1279. for (key in options) {
  1280. if (options.hasOwnProperty(key)) {
  1281. var targetHasIt = target.hasOwnProperty(key),
  1282. optionsValueType = typeof options[key],
  1283. shouldReplace = !targetHasIt || (typeof target[key] !== optionsValueType);
  1284. if (shouldReplace) {
  1285. target[key] = options[key];
  1286. } else if (optionsValueType === 'object') {
  1287. // go deep, don't care about loops here, we are simple API!:
  1288. target[key] = merge(target[key], options[key]);
  1289. }
  1290. }
  1291. }
  1292. }
  1293. return target;
  1294. }
  1295. },{}],12:[function(require,module,exports){
  1296. module.exports = random;
  1297. // TODO: Deprecate?
  1298. module.exports.random = random,
  1299. module.exports.randomIterator = randomIterator
  1300. /**
  1301. * Creates seeded PRNG with two methods:
  1302. * next() and nextDouble()
  1303. */
  1304. function random(inputSeed) {
  1305. var seed = typeof inputSeed === 'number' ? inputSeed : (+new Date());
  1306. return new Generator(seed)
  1307. }
  1308. function Generator(seed) {
  1309. this.seed = seed;
  1310. }
  1311. /**
  1312. * Generates random integer number in the range from 0 (inclusive) to maxValue (exclusive)
  1313. *
  1314. * @param maxValue Number REQUIRED. Omitting this number will result in NaN values from PRNG.
  1315. */
  1316. Generator.prototype.next = next;
  1317. /**
  1318. * Generates random double number in the range from 0 (inclusive) to 1 (exclusive)
  1319. * This function is the same as Math.random() (except that it could be seeded)
  1320. */
  1321. Generator.prototype.nextDouble = nextDouble;
  1322. /**
  1323. * Returns a random real number uniformly in [0, 1)
  1324. */
  1325. Generator.prototype.uniform = nextDouble;
  1326. Generator.prototype.gaussian = gaussian;
  1327. function gaussian() {
  1328. // use the polar form of the Box-Muller transform
  1329. // based on https://introcs.cs.princeton.edu/java/23recursion/StdRandom.java
  1330. var r, x, y;
  1331. do {
  1332. x = this.nextDouble() * 2 - 1;
  1333. y = this.nextDouble() * 2 - 1;
  1334. r = x * x + y * y;
  1335. } while (r >= 1 || r === 0);
  1336. return x * Math.sqrt(-2 * Math.log(r)/r);
  1337. }
  1338. function nextDouble() {
  1339. var seed = this.seed;
  1340. // Robert Jenkins' 32 bit integer hash function.
  1341. seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff;
  1342. seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
  1343. seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff;
  1344. seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff;
  1345. seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff;
  1346. seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
  1347. this.seed = seed;
  1348. return (seed & 0xfffffff) / 0x10000000;
  1349. }
  1350. function next(maxValue) {
  1351. return Math.floor(this.nextDouble() * maxValue);
  1352. }
  1353. /*
  1354. * Creates iterator over array, which returns items of array in random order
  1355. * Time complexity is guaranteed to be O(n);
  1356. */
  1357. function randomIterator(array, customRandom) {
  1358. var localRandom = customRandom || random();
  1359. if (typeof localRandom.next !== 'function') {
  1360. throw new Error('customRandom does not match expected API: next() function is missing');
  1361. }
  1362. return {
  1363. forEach: forEach,
  1364. /**
  1365. * Shuffles array randomly, in place.
  1366. */
  1367. shuffle: shuffle
  1368. };
  1369. function shuffle() {
  1370. var i, j, t;
  1371. for (i = array.length - 1; i > 0; --i) {
  1372. j = localRandom.next(i + 1); // i inclusive
  1373. t = array[j];
  1374. array[j] = array[i];
  1375. array[i] = t;
  1376. }
  1377. return array;
  1378. }
  1379. function forEach(callback) {
  1380. var i, j, t;
  1381. for (i = array.length - 1; i > 0; --i) {
  1382. j = localRandom.next(i + 1); // i inclusive
  1383. t = array[j];
  1384. array[j] = array[i];
  1385. array[i] = t;
  1386. callback(t);
  1387. }
  1388. if (array.length) {
  1389. callback(array[0]);
  1390. }
  1391. }
  1392. }
  1393. },{}]},{},[1])(1)
  1394. });