<commit_before>/* algorithms.js v0.8.0 | (c) 2014 <NAME> | https://github.com/felipernb/algorithms.js/blob/master/LICENSE */
!function(t,r){r.true=t,!function(e){if("object"==typeof t&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var n;"undefined"!=typeof window?n=window:"undefined"!=typeof r?n=r:"undefined"!=typeof self&&(n=self),n.algorithms=e()}}(function(){return function t(r,e,n){function i(s,a){if(!e[s]){if(!r[s]){var u="function"==typeof require&&require;if(!a&&u)return u(s,!0);if(o)return o(s,!0);var h=new Error("Cannot find module '"+s+"'");throw h.code="MODULE_NOT_FOUND",h}var c=e[s]={exports:{}};r[s][0].call(c.exports,function(t){var e=r[s][1][t];return i(e?e:t)},c,c.exports,t,r,e,n)}return e[s].exports}for(var o="function"==typeof require&&require,s=0;s<n.length;s++)i(n[s]);return i}({1:[function(t,r){"use strict";function e(t,r){var e={},n={},i={},o={},s={},a=0,u=1;e[r]=0,i[0]=r,o[r]=!0,s[r]=1,t.vertices.forEach(function(t){t!==r&&(e[t]=1/0,o[t]=!1,s[t]=0)});for(var h;a!=u;){h=i[a++],o[h]=!1;for(var c=t.neighbors(h),f=0;f<c.length;f++){var l=c[f],p=e[h]+t.edge(h,l);if(p<e[l]&&(e[l]=p,n[l]=h,!o[l]&&(i[u++]=l,o[l]=!0,s[l]++,s[l]>t.vertices.size)))return{distance:{}}}}return{distance:e,previous:n}}r.exports=e},{}],2:[function(t,r){"use strict";var e=function(t,r){var e={},n={},i=[],o=0;t.vertices.forEach(function(r){t.neighbors(r).forEach(function(e){i.push({source:r,target:e,weight:t.edge(r,e)})}),e[r]=1/0,++o}),e[r]=0;var s,a,u,h=i.length;for(u=0;o>u;++u){for(var c=!1,f=0;h>f;f++)s=e[i[f].source]+i[f].weight,a=e[i[f].target],a>s&&(c=!0,e[i[f].target]=s,n[i[f].target]=i[f].source);if(!c)break}return u==o?{distance:{}}:{distance:e,previous:n}};r.exports=e},{}],3:[function(t,r){"use strict";var e=t("./breadth_first_search"),n=function(t,r){var n={},i={};return n[r]=0,e(t,r,{onTraversal:function(t,r){n[r]=n[t]+1,i[r]=t}}),{distance:n,previous:i}};r.exports=n},{"./breadth_first_search":4}],4:[function(t,r){"use strict";var e=t("../../data_structures/queue"),n=function(t,r){t=t||{},t.allowTraversal=t.allowTraversal||function(){var t=r.reduce(function(t,r){return t[r]=!0,t},{});return function(r,e){return t[e]?!1:(t[e]=!0,!0)}}();var e=function(){};return t.onTraversal=t.onTraversal||e,t.enterVertex=t.enterVertex||e,t.leaveVertex=t.leaveVertex||e,t},i=function(t,r,i){var o=new e;o.push(r),i=n(i,[r]);for(var s,a=function(t){i.allowTraversal(s,t)&&(i.onTraversal(s,t),o.push(t))};!o.isEmpty();)s=o.pop(),i.enterVertex(s),t.neighbors(s).forEach(a),i.leaveVertex(s)};r.exports=i},{"../../data_structures/queue":48}],5:[function(t,r){"use strict";var e=function(t,r){t=t||{},t.allowTraversal=t.allowTraversal||function(){var t={};return r.forEach(function(r){t[r]=!0}),function(r,e){return t[e]?!1:(t[e]=!0,!0)}}();var e=function(){};return t.beforeTraversal=t.beforeTraversal||e,t.afterTraversal=t.afterTraversal||e,t.enterVertex=t.enterVertex||e,t.leaveVertex=t.leaveVertex||e,t},n=function(t,r,n){i(t,r,e(n,[r]))},i=function t(r,e,n){n.enterVertex(e),r.neighbors(e).forEach(function(i){n.allowTraversal(e,i)&&(n.beforeTraversal(e,i),t(r,i,n),n.afterTraversal(e,i))}),n.leaveVertex(e)};r.exports=n},{}],6:[function(t,r){"use strict";function e(t,r){var e={},i={},o=new n;e[r]=0,t.vertices.forEach(function(t){t!==r&&(e[t]=1/0),o.insert(t,e[t])});for(var s,a=function(r){var n=e[s]+t.edge(s,r);n<e[r]&&(e[r]=n,i[r]=s,o.changePriority(r,e[r]))};!o.isEmpty();)s=o.extract(),t.neighbors(s).forEach(a);return{distance:e,previous:i}}var n=t("../../data_structures/priority_queue");r.exports=e},{"../../data_structures/priority_queue":47}],7:[function(t,r){"use strict";var e=t("../../data_structures/graph"),n=t("../../algorithms/graph/depth_first_search"),i=function(t){var r={};if(t.vertices.forEach(function(e){r[e]=t.neighbors(e).length}),t.directed)t.vertices.forEach(function(e){t.neighbors(e).forEach(function(t){r[t]-=1})});else{var e=!1;t.vertices.forEach(function(t){r[t]%=2,r[t]&&(e&&(r[t]=-1),e=!0)})}var n,i,o;return t.vertices.forEach(function(t){if(1==r[t]){if(n)throw new Error("Duplicate start vertex.");n=t}else if(-1==r[t]){if(i)throw new Error("Duplicate finish vertex.");i=t}else{if(r[t])throw new Error("Unexpected vertex degree for "+t);o||(o=t)}}),n||i||(n=i=o),{start:n,finish:i}},o=function(t){if(!t.vertices.size)return[];var r=i(t),o=[r.finish],s=new e(t.directed);return t.vertices.forEach(s.addVertex.bind(s)),n(t,r.start,{allowTraversal:function(t,r){return!s.edge(t,r)},beforeTraversal:function(t,r){s.addEdge(t,r)},afterTraversal:function(t){o.push(t)}}),t.vertices.forEach(function(r){if(s.neighbors(r).length<t.neighbors(r).length)throw new Error("There is no euler path for a disconnected graph.")}),o.reverse()};r.exports=o},{"../../algorithms/graph/depth_first_search":5,"../../data_structures/graph":43}],8:[function(t,r){"use strict";var e=function(t){var r=Object.create(null);t.vertices.forEach(function(e){r[e]=Object.create(null),t.vertices.forEach(function(n){r[e][n]=e===n?0:void 0!==t.edge(e,n)?t.edge(e,n):1/0})});var e=Object.create(null);t.vertices.forEach(function(t){e[t]=Object.create(null)}),t.vertices.forEach(function(n){t.vertices.forEach(function(i){t.vertices.forEach(function(t){var o=r[i][n]+r[n][t];o<r[i][t]&&(r[i][t]=o,e[i][t]=n)})})}),t.vertices.forEach(function(t){if(r[t][t]<0)throw new Error("The graph contains a negative-weighted cycle!")});var n=function(t,n){if(!Number.isFinite(r[t][n]))return null;var i=[t];return t!=n&&!function t(r,n){if(void 0===e[r][n])i.push(n);else{var o=e[r][n];t(r,o),t(o,n)}}(t,n),i};return{distance:r,path:n}};r.exports=e},{}],9:[function(t,r){"use strict";var e=t("../../data_structures/disjoint_set_forest"),n=t("../../data_structures/graph"),i=function(t){if(t.directed)throw new Error("Can't build MST of a directed graph.");var r=new e,i=new n(!1);t.vertices.forEach(i.addVertex.bind(i));var o=[];return t.vertices.forEach(function(r){t.neighbors(r).forEach(function(e){e>r&&o.push({ends:[r,e],weight:t.edge(r,e)})})}),o.sort(function(t,r){return t.weight-r.weight}).forEach(function(t){r.sameSubset(t.ends[0],t.ends[1])||(i.addEdge(t.ends[0],t.ends[1],t.weight),r.merge(t.ends[0],t.ends[1]))}),i};r.exports=i},{"../../data_structures/disjoint_set_forest":42,"../../data_structures/graph":43}],10:[function(t,r){"use strict";var e=t("../../data_structures/priority_queue"),n=t("../../data_structures/graph"),i=function(t){if(t.directed)throw new Error("Can't build MST of a directed graph.");var r=new n(!1),i=Object.create(null),o=new e;t.vertices.forEach(function(t){o.insert(t,1/0)});for(var s=function(r){var e=t.edge(u,r);e<o.priority(r)&&(o.changePriority(r,e),i[r]=u)};!o.isEmpty();){var a=o.extract(!0),u=a.item,h=a.priority;i[u]?r.addEdge(i[u],u,h):r.addVertex(u),t.neighbors(u).forEach(s)}return r};r.exports=i},{"../../data_structures/graph":43,"../../data_structures/priority_queue":47}],11:[function(t,r){"use strict";var e=t("../../data_structures/stack"),n=t("../../algorithms/graph/depth_first_search"),i=function(t){var r=new e,i={},o=0;return t.vertices.forEach(function(e){i[e]||n(t,e,{allowTraversal:function(t,r){return!i[r]},enterVertex:function(t){i[t]=++o},leaveVertex:function(t){r.push(t)}})}),r};r.exports=i},{"../../algorithms/graph/depth_first_search":5,"../../data_structures/stack":50}],12:[function(t,r){"use strict";var e=function(t,r){for(var e,n,i=0,o=1,s=1,a=0,u=r,h=t;0!==u;)e=Math.floor(h/u),n=u,u=h-e*u,h=n,n=i,i=o-e*i,o=n,n=s,s=a-e*s,a=n;return{x:o,y:a}};r.exports=e},{}],13:[function(t,r){"use strict";var e=function(t,r){return t*r},n=function(t,r,n,i){if(void 0===n&&(n=e,i=1),0>r||Math.floor(r)!=r)throw new Error("Power must be a positive integer or zero.");if(!r){if(void 0===i)throw new Error("The power is zero, but identity value not set.");return i}for(var o,s=function(t){o=void 0===o?t:n(o,t)},a=t;r;r>>>=1,a=n(a,a))1&r&&s(a);return o};r.exports=n},{}],14:[function(t,r){"use strict";var e=t("./fast_power"),n=function(t){return 2>t?t:n(t-1)+n(t-2)},i=function(t){for(var r=0,e=1,n=t,i=1;t>i;i++)n=e+r,r=e,e=n;return n},o=function(){var t=[0,1],r=function(e){return void 0===t[e]&&(t[e]=r(e-1)+r(e-2)),t[e]};return r}(),s=function(t){var r=(1+Math.sqrt(5))/2;return Math.floor(Math.pow(r,t)/Math.sqrt(5)+.5)},a=function(t){var r=[[1,1],[1,0]],n=function(t,r){return[[t[0][0]*r[0][0]+t[0][1]*r[1][0],t[0][0]*r[0][1]+t[0][1]*r[1][1]],[t[1][0]*r[0][0]+t[1][1]*r[1][0],t[1][0]*r[0][1]+t[1][1]*r[1][1]]]},i=e(r,t,n,[[1,0],[0,1]]);return i[0][1]};i.exponential=n,i.withMemoization=o,i.direct=s,i.logarithmic=a,r.exports=i},{"./fast_power":13}],15:[function(t,r){"use strict";var e=function(t){for(var r=t.length-1;r>0;r--){var e=Math.floor(Math.random()*(r+1)),n=t[r];t[r]=t[e],t[e]=n}};r.exports=e},{}],16:[function(t,r){"use strict";var e=function(t,r){var e=t;for(t=Math.max(t,r),r=Math.min(e,r);0!==r;)e=r,r=t%r,t=e;return t},n=function(t,r){if(0===t)return r;if(0===r)return t;for(var e=0;0===(1&(t|r));++e)t>>=1,r>>=1;for(;0===(1&t);)t>>=1;var n;do{for(;0===(1&r);)r>>=1;t>r&&(n=r,r=t,t=n),r-=t}while(0!==r);return t<<e};e.binary=n,r.exports=e},{}],17:[function(t,r){"use strict";var e=function(t,r,e){r=r||1e-7,e=e||1e7;var n,i,o=t,s=0,a=0;do a++,i=(o-s)/2+s,n=i*i,t>n?s=i:o=i;while(Math.abs(n-t)>r&&e>a);var u=Math.round(i);return u*u===t&&(i=u),i};r.exports=e},{}],18:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){if(!t.length)return!1;for(var n=new e(r),i=t.length-1;i&&n.greaterThanOrEqual(t[i-1],t[i]);)i-=1;if(!i)return!1;for(var o=t[--i],s=t.length-1;n.lessThanOrEqual(t[s],o);)s-=1;t[i]=t[s],t[s]=o;for(var a=i,u=t.length;++a<--u;){var h=t[a];t[a]=t[u],t[u]=h}return!0};r.exports=n},{"../../util/comparator":57}],19:[function(t,r){"use strict";var e=function(t){if(0===t.length)return[];for(var r=[],e=[],n=0;n<t.length;n++)e[n]=!0;for(n=0;n<Math.pow(2,t.length);n++){r.push([]);for(var i=0;i<t.length;i++)n%Math.pow(2,i)===0&&(e[i]=!e[i]),e[i]&&r[n].push(t[i])}return r},n=function(t){if(0===t.length)return[];if(1==t.length)return[[],[t[0]]];var r=[],e=t[0];return t.splice(0,1),n(t).forEach(function(t){r.push(t);var n=[e];n.push.apply(n,t),r.push(n)}),r},i=e;i.recursive=n,r.exports=i},{}],20:[function(t,r){"use strict";var e=function(t,r){if(r>t.length)throw new Error("Sample size exceeds the total number of elements.");for(var e=t.slice(0,r),n=r;n<t.length;++n){var i=Math.floor(Math.random()*(n+1));r>i&&(e[i]=t[n])}return e};r.exports=e},{}],21:[function(t,r){"use strict";var e=function(t){var r=t.reduce(function(t,r){return t[r]=t[r]+1||1,t},{}),e=Object.keys(r).map(function(e){return r[e]/t.length});return e.reduce(function(t,r){return t-r*Math.log(r)},0)*Math.LOG2E};r.exports=e},{}],22:[function(t,r){"use strict";var e=t("../../data_structures/queue.js"),n=function(t,r){var n=new e;n.push(t);for(var i;!n.isEmpty();)i=n.pop(),r(i.value),i.left&&n.push(i.left),i.right&&n.push(i.right)};r.exports=n},{"../../data_structures/queue.js":48}],23:[function(t,r){"use strict";var e=function(t,r){for(var e=0,n=t.length-1;n>=e;){var i=(n-e>>1)+e;if(t[i]===r)return i;t[i]<r?e=i+1:n=i-1}return-1};r.exports=e},{}],24:[function(t,r){"use strict";var e=function(t,r){t&&(e(t.left,r),r(t.value),e(t.right,r))},n=function(t,r){t&&(r(t.value),n(t.left,r),n(t.right,r))},i=function(t,r){t&&(i(t.left,r),i(t.right,r),r(t.value))};e.preOrder=n,e.postOrder=i,r.exports=e},{}],25:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=t.length,o=i-1,s=!1,a=0;i-1>a;a++){for(var u=0,h=0;o>h;h++)if(n.greaterThan(t[h],t[h+1])){var c=t[h];t[h]=t[h+1],t[h+1]=c,u=h,s=!0}if(!s)return t;o=u}return t};r.exports=n},{"../../util/comparator":57}],26:[function(t,r){"use strict";var e=function(t){for(var r=n(t),e=[],i=t.length,o=0;i>o;o++){var s=t[o].key;void 0===e[s]&&(e[s]=[]),e[s].push(t[o])}t=[];var a=0;for(o=0;r>=o;o++)if(void 0!==e[o])for(var u=e[o].length,h=0;u>h;h++)t[a++]=e[o][h];return t},n=function(t){for(var r=t[0].key,e=t.length,n=1;e>n;n++)t[n].key>r&&(r=t[n].key);return r};r.exports=e},{}],27:[function(t,r){"use strict";var e=t("../../data_structures/heap").MinHeap,n=function(t,r){var n=new e(r);n.heapify(t);for(var i=[];!n.isEmpty();)i.push(n.extract());return i};r.exports=n},{"../../data_structures/heap":45}],28:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=1,o=t.length;o>i;i++){for(var s=t[i],a=i;a>0&&n.lessThan(s,t[a-1]);)t[a]=t[a-1],a--;t[a]=s}return t};r.exports=n},{"../../util/comparator":57}],29:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){var n=new e(r);return function t(r){if(r.length>1){var e=r.length>>1,o=t(r.slice(0,e)),s=t(r.slice(e));r=i(o,s,n)}return r}(t)},i=function(t,r,e){for(var n=0,i=0,o=[];n<t.length&&i<r.length;)o.push(e.lessThan(t[n],r[i])?t[n++]:r[i++]);return o.concat(n<t.length?t.slice(n):r.slice(i))};r.exports=n},{"../../util/comparator":57}],30:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){var n=new e(r);return function t(r,e,o){if(o>e){var s=i(r,n,e,o);t(r,e,s-1),t(r,s+1,o)}return r}(t,0,t.length-1)},i=function(t,r,e,n){o(t,Math.floor(Math.random()*(n-e))+e,n);for(var i=n,s=e,a=e;n>a;a++)r.lessThan(t[a],t[i])&&(o(t,a,s),s++);return o(t,s,i),s},o=function(t,r,e){var n=t[e];t[e]=t[r],t[r]=n};r.exports=n},{"../../util/comparator":57}],31:[function(t,r){"use strict";var e=function(t){for(var r=i(t),e=0===r?1:1+Math.floor(Math.log(r)/Math.log(10)),o=0;e>o;o++)t=n(t,o);return t},n=function(t,r){for(var e=t.length,n=[],i=0;10>i;i++)n[i]=[];for(i=0;e>i;i++){var o=parseInt((t[i].key/Math.pow(10,r)).toFixed(r))%10;n[o].push(t[i])}var s=0;for(i=0;10>i;i++)for(var a=n[i].length,u=0;a>u;u++)t[s++]=n[i][u];return t},i=function(t){for(var r,e=1;e<t.length;e++)(void 0===r||t[e].key>r)&&(r=t[e].key);return r};r.exports=e},{}],32:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=t.length,o=0;i-1>o;o++){for(var s=o,a=o+1;i>a;a++)n.greaterThan(t[s],t[a])&&(s=a);if(s!=o){var u=t[o];t[o]=t[s],t[s]=u}}return t};r.exports=n},{"../../util/comparator":57}],33:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=0,o=t.length-1,s=parseInt((o-i+1)/2),a=0,u=0,h=0;s>=1;){for(a=i+s;o>=a;a+=1){for(h=t[a],u=a-s;u>=i&&n.greaterThan(t[u],h);)t[u+s]=t[u],u-=s;t[u+s]=h}s=parseInt(s/2)}return t};r.exports=n},{"../../util/comparator":57}],34:[function(t,r){"use strict";var e=function(t,r){if(t.length!=r.length)throw new Error("Strings must be equal in length");for(var e=0,n=0;n<t.length;n++)t[n]!=r[n]&&e++;return e};r.exports=e},{}],35:[function(t,r){"use strict";var e={},n=(-1>>>0).toString(2).length,i=function(t){var r=[],e=0,i=0;return t.split("").forEach(function(t){e=e<<1|t,i+=1,i==n&&(r.push(e),e=i=0)}),i?r.push(e,i):r.push(n),r},o=function(t){if(!t.length)return"";if(1==t.length)throw new Error("Compressed array must be either empty or at least 2 blocks big.");var r=new Array(n+1).join(0),e=t.slice(0,-2).map(function(t){return(r+(t>>>0).toString(2)).slice(-r.length)}).join(""),i=t.slice(-1)[0],o=t.slice(-2)[0];return e+=(r+(o>>>0).toString(2)).slice(-i)};e.encode=function(t,r){if(!t.length)return{encoding:{},value:r?[]:""};var e={};t.split("").forEach(function(t){e[t]=(e[t]||0)+1});var n=Object.keys(e).map(function(t){return{char:t,count:e[t]}}),o=function(t,r){return t.count-r.count},s=function(t,r){return t&&(r&&t.count<r.count||!r)};n.sort(o);for(var a=[],u=0,h=0,c=function(){return s(n[u],a[h])?n[u++]:a[h++]},f=n.length;f>1;--f){var l=c(),p=c();l.code="0",p.code="1";var g={count:l.count+p.count,parts:[l,p]};a.push(g)}var d=c();d.code=n.length>1?"":"0",function t(r){if(r.parts){var e=r.parts[0],n=r.parts[1];e.code+=r.code,n.code+=r.code,t(e),t(n)}}(d);var v=n.reduce(function(t,r){return t[r.char]=r.code.split("").reverse().join(""),t},{}),_=t.split("").map(function(t){return v[t]}).join("");return{encoding:v,value:r?i(_):_}},e.decode=function(t,r){Array.isArray(r)&&(r=o(r));var e=Object.keys(t).reduce(function(r,e){return r[t[e]]=e,r},{}),n=[],i=r.split("").reduce(function(t,r){t+=r;var i=e[t];return i&&(n.push(i),t=""),t},"");if(i)throw new Error("Invalid string to decode.");return n.join("")},r.exports=e},{}],36:[function(t,r){"use strict";var e=function(t,r){for(var e=t.length,i=r.length,o=0,s=0,a=n(r);e>o+s;)if(r[s]===t[o+s]){if(s===i-1)return o;++s}else a[s]>=0?(s=a[s],o=o+s-a[s]):(s=0,++o);return e},n=function(t){var r=t.length,e=[],n=2,i=0;for(e[0]=-1,e[1]=0;r>n;)t[n-1]===t[i]?(++i,e[n]=i,++n):i>0?i=e[i]:(e[n]=0,++n);return e};r.exports=e},{}],37:[function(t,r){"use strict";var e=function(t,r){var e,n,i=[];for(e=0;e<=t.length;e++)i[e]=[],i[e][0]=e;for(n=0;n<=r.length;n++)i[0][n]=n;for(e=1;e<=t.length;e++)for(n=1;n<=r.length;n++)i[e][n]=Math.min(i[e-1][n-1],i[e-1][n],i[e][n-1])+(t[e-1]!=r[n-1]?1:0);return i[t.length][r.length]};r.exports=e},{}],38:[function(t,r){"use strict";var e=function(t,r){var e,n,i=[];for(e=0;e<t.length+1;e++)i[e]=[],i[e][0]=0;for(e=0;e<r.length+1;e++)i[0][e]=0;for(e=1;e<t.length+1;e++)for(n=1;n<r.length+1;n++)if(t[e-1]==r[n-1]){var o=i[e-1][n-1]+1;i[e][n]=o}else i[e][n]=Math.max(i[e][n-1],i[e-1][n]);e=t.length,n=r.length;for(var s="";0!==i[e][n];)t[e-1]===r[n-1]?(s+=t[e-1],e--,n--):i[e-1][n]>i[e][n-1]?e--:n--;return s.split("").reverse().join("")};r.exports=e},{}],39:[function(t,r){"use strict";var e=997,n=function(t,r){if(0===r.length)return 0;for(var n,o=i(r),s=t.substring(0,r.length),a=r.length;a<=t.length;a++)if(void 0===n?n=i(s):(n-=s.charCodeAt(0)*Math.pow(e,r.length-1),n*=e,n+=t.charCodeAt(a),s=s.substring(1)+t[a]),o===n&&r===s)return a===r.length?0:a-r.length+1;return-1},i=function(t){for(var r=0,n=0;n<t.length;n++)r+=t.charCodeAt(n)*Math.pow(e,t.length-n-1);return r};r.exports=n},{}],40:[function(t,r){"use strict";r.exports={BST:t("./data_structures/bst"),Graph:t("./data_structures/graph"),HashTable:t("./data_structures/hash_table"),Heap:t("./data_structures/heap"),LinkedList:t("./data_structures/linked_list"),PriorityQueue:t("./data_structures/priority_queue"),Queue:t("./data_structures/queue"),Stack:t("./data_structures/stack"),Set:t("./data_structures/set"),DisjointSetForest:t("./data_structures/disjoint_set_forest")}},{"./data_structures/bst":41,"./data_structures/disjoint_set_forest":42,"./data_structures/graph":43,"./data_structures/hash_table":44,"./data_structures/heap":45,"./data_structures/linked_list":46,"./data_structures/priority_queue":47,"./data_structures/queue":48,"./data_structures/set":49,"./data_structures/stack":50}],41:[function(t,r){"use strict";function e(t){this.root=null,this._size=0,this._comparator=new i(t),Object.defineProperty(this,"size",{get:function(){return this._size}.bind(this)})}function n(t,r){this.value=t,this.parent=r,this.left=null,this.right=null}var i=t("../util/comparator");e.prototype.insert=function(t,r){if(!r){if(!this.root)return this.root=new n(t),void this._size++;r=this.root}var e=this._comparator.lessThan(t,r.value)?"left":"right";r[e]?this.insert(t,r[e]):(r[e]=new n(t,r),this._size++)},e.prototype.contains=function(t){return!!this._find(t)},e.prototype._find=function(t,r){if(!r){if(!this.root)return!1;r=this.root}return r.value===t?r:this._comparator.lessThan(t,r.value)?r.left&&this._find(t,r.left):this._comparator.greaterThan(t,r.value)?r.right&&this._find(t,r.right):void 0},e.prototype._replaceNodeInParent=function(t,r){var e=t.parent;e?(e[t===e.left?"left":"right"]=r,r&&(r.parent=e)):this.root=r},e.prototype._findMin=function(t){for(var r=t;r.left;)r=r.left;return r},e.prototype.remove=function(t){var r=this._find(t);if(!r)throw new Error("Item not found in the tree");if(r.left&&r.right){var e=this._findMin(r.right);this.remove(e.value),r.value=e.value}else this._replaceNodeInParent(r,r.left||r.right),this._size--},r.exports=e},{"../util/comparator":57}],42:[function(t,r){"use strict";function e(){this._parents={},this._ranks={},this._sizes={}}e.prototype._introduce=function(t){t in this._parents||(this._parents[t]=t,this._ranks[t]=0,this._sizes[t]=1)},e.prototype.sameSubset=function(t){this._introduce(t);var r=this.root(t);return[].slice.call(arguments,1).every(function(t){return this._introduce(t),this.root(t)==r}.bind(this))},e.prototype.root=function(t){return this._introduce(t),this._parents[t]!=t&&(this._parents[t]=this.root(this._parents[t])),this._parents[t]},e.prototype.size=function(t){return this._introduce(t),this._sizes[this.root(t)]},e.prototype.merge=function t(r,e){arguments.length>2&&t.apply(this,[].slice.call(arguments,1)),this._introduce(r),this._introduce(e);var n=this.root(r),i=this.root(e);return this._ranks[n]<this._ranks[i]?(this._parents[n]=i,this._sizes[i]+=this._sizes[n]):n!=i&&(this._parents[i]=n,this._sizes[n]+=this._sizes[i],this._ranks[n]==this._ranks[i]&&(this._ranks[n]+=1)),this},r.exports=e},{}],43:[function(t,r){"use strict";function e(t){this.directed=void 0===t?!0:!!t,this.adjList=Object.create(null),this.vertices=new n}var n=t("./set"),i=function(t){return""+t};e.prototype.addVertex=function(t){if(t=i(t),this.vertices.contains(t))throw new Error('Vertex "'+t+'" has already been added');this.vertices.add(t),this.adjList[t]=Object.create(null)},e.prototype.addEdge=function(t,r,e){t=i(t),r=i(r),e=void 0===e?1:e,this.adjList[t]||this.addVertex(t),this.adjList[r]||this.addVertex(r),this.adjList[t][r]=(this.adjList[t][r]||0)+e,this.directed||(this.adjList[r][t]=(this.adjList[r][t]||0)+e)},e.prototype.neighbors=function(t){return Object.keys(this.adjList[i(t)])},e.prototype.edge=function(t,r){return this.adjList[i(t)][i(r)]},r.exports=e},{"./set":49}],44:[function(t,r){"use strict";function e(t){this._table=new Array(t||64),this._items=0,Object.defineProperty(this,"capacity",{get:function(){return this._table.length}}),Object.defineProperty(this,"size",{get:function(){return this._items}})}var n=t("./linked_list");e.prototype.hash=function(t){"string"!=typeof t&&(t=JSON.stringify(t));for(var r=0,e=0;e<t.length;e++)r=(r<<5)-r+t.charCodeAt(e),r&=r;return r},e.prototype.get=function(t){var r,e=this._position(t);return(r=this._findInList(this._table[e],t))?r.value.v:void 0},e.prototype.put=function(t,r){var e=this._position(t);this._table[e]||(this._table[e]=new n);var i={k:t,v:r},o=this._findInList(this._table[e],t);o?o.value=i:(this._table[e].add(i),this._items++,this._items===this.capacity&&this._increaseCapacity())},e.prototype.del=function(t){var r,e=this._position(t);(r=this._findInList(this._table[e],t))&&(this._table[e].delNode(r),this._items--)},e.prototype._position=function(t){return Math.abs(this.hash(t))%this.capacity},e.prototype._findInList=function(t,r){for(var e=t&&t.head;e;){if(e.value.k===r)return e;e=e.next}},e.prototype._increaseCapacity=function(){var t=this._table;this._table=new Array(2*this.capacity),this._items=0;for(var r=0;r<t.length;r++)for(var e=t[r]&&t[r].head;e;)this.put(e.value.k,e.value.v),e=e.next},e.prototype.forEach=function(t){for(var r=function(r){r.forEach(function(r){t(r.k,r.v)})},e=0;e<this._table.length;e++)this._table[e]&&r(this._table[e])},r.exports=e},{"./linked_list":46}],45:[function(t,r){"use strict";function e(t){this._elements=[null],this._comparator=new i(t),Object.defineProperty(this,"n",{get:function(){return this._elements.length-1}.bind(this)})}function n(t){e.call(this,t),this._comparator.reverse()}var i=t("../util/comparator");e.prototype._swap=function(t,r){var e=this._elements[t];this._elements[t]=this._elements[r],this._elements[r]=e},e.prototype.isEmpty=function(){return 0===this.n},e.prototype.insert=function(t){this._elements.push(t),this._siftUp()},e.prototype.extract=function(){var t=this._elements[1],r=this._elements.pop();return this.n&&(this._elements[1]=r,this._siftDown()),t},e.prototype._siftUp=function(){var t,r;for(t=this.n;t>1&&(r=t>>1)&&this._comparator.greaterThan(this._elements[r],this._elements[t]);t=r)this._swap(r,t)},e.prototype._siftDown=function(t){var r;for(t=t||1;(r=t<<1)<=this.n&&(r+1<=this.n&&this._comparator.lessThan(this._elements[r+1],this._elements[r])&&r++,!this._comparator.lessThan(this._elements[t],this._elements[r]));t=r)this._swap(t,r)},e.prototype.heapify=function(t){t&&(this._elements=t,this._elements.unshift(null));for(var r=this.n>>1;r>0;r--)this._siftDown(r)},e.prototype.forEach=function(t){var r,e=[];for(r=0;r<this._elements.length;r++)e.push(this._elements[r]);for(r=this.n;r>0;r--)t(this.extract());this._elements=e},n.prototype=new e,r.exports={MinHeap:e,MaxHeap:n}},{"../util/comparator":57}],46:[function(t,r){"use strict";function e(){this._length=0,this.head=null,this.tail=null,Object.defineProperty(this,"length",{get:function(){return this._length}.bind(this)})}function n(t){this.value=t,this.prev=null,this.next=null}e.prototype.isEmpty=function(){return 0===this.length},e.prototype.add=function(t,r){if(r>this.length||0>r)throw new Error("Index out of bounds");var e=new n(t);if(void 0!==r&&r<this.length){var i,o;0===r?(o=this.head,this.head=e):(o=this.getNode(r),i=o.prev,i.next=e,e.prev=i),o.prev=e,e.next=o}else this.head||(this.head=e),this.tail&&(this.tail.next=e,e.prev=this.tail),this.tail=e;this._length++},e.prototype.get=function(t){return this.getNode(t).value},e.prototype.getNode=function(t){if(t>=this.length||0>t)throw new Error("Index out of bounds");for(var r=this.head,e=1;t>=e;e++)r=r.next;return r},e.prototype.del=function(t){if(t>=this.length||0>t)throw new Error("Index out of bounds");this.delNode(this.getNode(t))},e.prototype.delNode=function(t){t===this.tail?this.tail=t.prev:t.next.prev=t.prev,t===this.head?this.head=t.next:t.prev.next=t.next,this._length--},e.prototype.forEach=function(t){for(var r=this.head;r;)t(r.value),r=r.next},r.exports=e},{}],47:[function(t,r){"use strict";function e(t){var r=this;n.call(this,function(t,e){return r.priority(t)<r.priority(e)?-1:1}),this._priority={},t=t||{},Object.keys(t).forEach(function(e){r.insert(e,t[e])})}var n=t("./heap").MinHeap;e.prototype=new n,e.prototype.insert=function(t,r){return void 0!==this._priority[t]?this.changePriority(t,r):(this._priority[t]=r,void n.prototype.insert.call(this,t))},e.prototype.extract=function(t){var r=n.prototype.extract.call(this);return t?r&&{item:r,priority:this._priority[r]}:r},e.prototype.priority=function(t){return this._priority[t]},e.prototype.changePriority=function(t,r){this._priority[t]=r,this.heapify()},r.exports=e},{"./heap":45}],48:[function(t,r){"use strict";function e(){this._elements=new n,Object.defineProperty(this,"length",{get:function(){return this._elements.length}.bind(this)})}var n=t("./linked_list");e.prototype.isEmpty=function(){return this._elements.isEmpty()},e.prototype.push=function(t){this._elements.add(t)},e.prototype.pop=function(){if(this.isEmpty())throw new Error("Empty queue");var t=this._elements.get(0);return this._elements.del(0),t},e.prototype.peek=function(){if(this.isEmpty())throw new Error("Empty queue");return this._elements.get(0)},e.prototype.forEach=function(t){this._elements.forEach(t)},r.exports=e},{"./linked_list":46}],49:[function(t,r){"use strict";var e=t("./hash_table"),n=function(){this._elements=new e(arguments.length),this.add.apply(this,arguments),Object.defineProperty(this,"size",{get:function(){return this._elements.size}})};n.prototype.add=function(){for(var t=0;t<arguments.length;t++)this._elements.put(arguments[t],!0);return this},n.prototype.remove=function(){for(var t=0;t<arguments.length;t++)this._elements.del(arguments[t]);return this},n.prototype.contains=function(t){return void 0!==this._elements.get(t)},n.prototype.forEach=function(t){this._elements.forEach(t)},r.exports=n},{"./hash_table":44}],50:[function(t,r){"use strict";function e(){n.call(this)}var n=t("./queue");e.prototype=new n,e.prototype.push=function(t){this._elements.add(t,0)},r.exports=e},{"./queue":48}],51:[function(t,r){"use strict";r.exports={topologicalSort:t("./algorithms/graph/topological_sort"),dijkstra:t("./algorithms/graph/dijkstra"),SPFA:t("./algorithms/graph/SPFA"),bellmanFord:t("./algorithms/graph/bellman_ford"),eulerPath:t("./algorithms/graph/euler_path"),depthFirstSearch:t("./algorithms/graph/depth_first_search"),kruskal:t("./algorithms/graph/kruskal"),breadthFirstSearch:t("./algorithms/graph/breadth_first_search"),bfsShortestPath:t("./algorithms/graph/bfs_shortest_path"),prim:t("./algorithms/graph/prim"),floydWarshall:t("./algorithms/graph/floyd_warshall")}},{"./algorithms/graph/SPFA":1,"./algorithms/graph/bellman_ford":2,"./algorithms/graph/bfs_shortest_path":3,"./algorithms/graph/breadth_first_search":4,"./algorithms/graph/depth_first_search":5,"./algorithms/graph/dijkstra":6,"./algorithms/graph/euler_path":7,"./algorithms/graph/floyd_warshall":8,"./algorithms/graph/kruskal":9,"./algorithms/graph/prim":10,"./algorithms/graph/topological_sort":11}],52:[function(t,r){"use strict";var e={DataStructure:t("./data_structures"),Graph:t("./graph"),Math:t("./math"),Search:t("./search"),Sorting:t("./sorting"),String:t("./string")};r.exports=e},{"./data_structures":40,"./graph":51,"./math":53,"./search":54,"./sorting":55,"./string":56}],53:[function(t,r){"use strict";r.exports={fibonacci:t("./algorithms/math/fibonacci"),fisherYates:t("./algorithms/math/fisher_yates"),gcd:t("./algorithms/math/gcd"),extendedEuclidean:t("./algorithms/math/extended_euclidean"),newtonSqrt:t("./algorithms/math/newton_sqrt"),reservoirSampling:t("./algorithms/math/reservoir_sampling"),fastPower:t("./algorithms/math/fast_power"),nextPermutation:t("./algorithms/math/next_permutation"),powerSet:t("./algorithms/math/power_set"),shannonEntropy:t("./algorithms/math/shannon_entropy")}},{"./algorithms/math/extended_euclidean":12,"./algorithms/math/fast_power":13,"./algorithms/math/fibonacci":14,"./algorithms/math/fisher_yates":15,"./algorithms/math/gcd":16,"./algorithms/math/newton_sqrt":17,"./algorithms/math/next_permutation":18,"./algorithms/math/power_set":19,"./algorithms/math/reservoir_sampling":20,"./algorithms/math/shannon_entropy":21}],54:[function(t,r){"use strict";r.exports={bfs:t("./algorithms/search/bfs"),binarySearch:t("./algorithms/search/binarysearch"),dfs:t("./algorithms/search/dfs")}},{"./algorithms/search/bfs":22,"./algorithms/search/binarysearch":23,"./algorithms/search/dfs":24}],55:[function(t,r){"use strict";r.exports={bubbleSort:t("./algorithms/sorting/bubble_sort"),countingSort:t("./algorithms/sorting/counting_sort"),heapSort:t("./algorithms/sorting/heap_sort"),mergeSort:t("./algorithms/sorting/merge_sort"),quicksort:t("./algorithms/sorting/quicksort"),selectionSort:t("./algorithms/sorting/selection_sort"),radixSort:t("./algorithms/sorting/radix_sort"),insertionSort:t("./algorithms/sorting/insertion_sort"),shellSort:t("./algorithms/sorting/shell_sort")}},{"./algorithms/sorting/bubble_sort":25,"./algorithms/sorting/counting_sort":26,"./algorithms/sorting/heap_sort":27,"./algorithms/sorting/insertion_sort":28,"./algorithms/sorting/merge_sort":29,"./algorithms/sorting/quicksort":30,"./algorithms/sorting/radix_sort":31,"./algorithms/sorting/selection_sort":32,"./algorithms/sorting/shell_sort":33}],56:[function(t,r){"use strict";r.exports={levenshtein:t("./algorithms/string/levenshtein"),rabinKarp:t("./algorithms/string/rabin_karp"),knuthMorrisPratt:t("./algorithms/string/knuth_morris_pratt"),huffman:t("./algorithms/string/huffman"),hamming:t("./algorithms/string/hamming"),longestCommonSubsequence:t("./algorithms/string/longest_common_subsequence")}},{"./algorithms/string/hamming":34,"./algorithms/string/huffman":35,"./algorithms/string/knuth_morris_pratt":36,"./algorithms/string/levenshtein":37,"./algorithms/string/longest_common_subsequence":38,"./algorithms/string/rabin_karp":39}],57:[function(t,r){"use strict";function e(t){t&&(this.compare=t)}e.prototype.compare=function(t,r){return t==r?0:r>t?-1:1},e.prototype.lessThan=function(t,r){return this.compare(t,r)<0},e.prototype.lessThanOrEqual=function(t,r){return this.lessThan(t,r)||this.equal(t,r)},e.prototype.greaterThan=function(t,r){return this.compare(t,r)>0},e.prototype.greaterThanOrEqual=function(t,r){return this.greaterThan(t,r)||this.equal(t,r)},e.prototype.equal=function(t,r){return 0===this.compare(t,r)
},e.prototype.reverse=function(){var t=this.compare;this.compare=function(r,e){return t(e,r)}},r.exports=e},{}]},{},[52])(52)})}({},function(){return this}());<commit_msg>bundle<commit_after>/* algorithms.js v0.8.1 | (c) 2014 <NAME> | https://github.com/felipernb/algorithms.js/blob/master/LICENSE */
!function(t,r){r.true=t,!function(e){if("object"==typeof t&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var n;"undefined"!=typeof window?n=window:"undefined"!=typeof r?n=r:"undefined"!=typeof self&&(n=self),n.algorithms=e()}}(function(){return function t(r,e,n){function i(s,a){if(!e[s]){if(!r[s]){var u="function"==typeof require&&require;if(!a&&u)return u(s,!0);if(o)return o(s,!0);var h=new Error("Cannot find module '"+s+"'");throw h.code="MODULE_NOT_FOUND",h}var c=e[s]={exports:{}};r[s][0].call(c.exports,function(t){var e=r[s][1][t];return i(e?e:t)},c,c.exports,t,r,e,n)}return e[s].exports}for(var o="function"==typeof require&&require,s=0;s<n.length;s++)i(n[s]);return i}({1:[function(t,r){"use strict";function e(t,r){var e={},n={},i={},o={},s={},a=0,u=1;e[r]=0,i[0]=r,o[r]=!0,s[r]=1,t.vertices.forEach(function(t){t!==r&&(e[t]=1/0,o[t]=!1,s[t]=0)});for(var h;a!=u;){h=i[a++],o[h]=!1;for(var c=t.neighbors(h),f=0;f<c.length;f++){var l=c[f],p=e[h]+t.edge(h,l);if(p<e[l]&&(e[l]=p,n[l]=h,!o[l]&&(i[u++]=l,o[l]=!0,s[l]++,s[l]>t.vertices.size)))return{distance:{}}}}return{distance:e,previous:n}}r.exports=e},{}],2:[function(t,r){"use strict";var e=function(t,r){var e={},n={},i=[],o=0;t.vertices.forEach(function(r){t.neighbors(r).forEach(function(e){i.push({source:r,target:e,weight:t.edge(r,e)})}),e[r]=1/0,++o}),e[r]=0;var s,a,u,h=i.length;for(u=0;o>u;++u){for(var c=!1,f=0;h>f;f++)s=e[i[f].source]+i[f].weight,a=e[i[f].target],a>s&&(c=!0,e[i[f].target]=s,n[i[f].target]=i[f].source);if(!c)break}return u==o?{distance:{}}:{distance:e,previous:n}};r.exports=e},{}],3:[function(t,r){"use strict";var e=t("./breadth_first_search"),n=function(t,r){var n={},i={};return n[r]=0,e(t,r,{onTraversal:function(t,r){n[r]=n[t]+1,i[r]=t}}),{distance:n,previous:i}};r.exports=n},{"./breadth_first_search":4}],4:[function(t,r){"use strict";var e=t("../../data_structure/queue"),n=function(t,r){t=t||{},t.allowTraversal=t.allowTraversal||function(){var t=r.reduce(function(t,r){return t[r]=!0,t},{});return function(r,e){return t[e]?!1:(t[e]=!0,!0)}}();var e=function(){};return t.onTraversal=t.onTraversal||e,t.enterVertex=t.enterVertex||e,t.leaveVertex=t.leaveVertex||e,t},i=function(t,r,i){var o=new e;o.push(r),i=n(i,[r]);for(var s,a=function(t){i.allowTraversal(s,t)&&(i.onTraversal(s,t),o.push(t))};!o.isEmpty();)s=o.pop(),i.enterVertex(s),t.neighbors(s).forEach(a),i.leaveVertex(s)};r.exports=i},{"../../data_structure/queue":49}],5:[function(t,r){"use strict";var e=function(t,r){t=t||{},t.allowTraversal=t.allowTraversal||function(){var t={};return r.forEach(function(r){t[r]=!0}),function(r,e){return t[e]?!1:(t[e]=!0,!0)}}();var e=function(){};return t.beforeTraversal=t.beforeTraversal||e,t.afterTraversal=t.afterTraversal||e,t.enterVertex=t.enterVertex||e,t.leaveVertex=t.leaveVertex||e,t},n=function(t,r,n){i(t,r,e(n,[r]))},i=function t(r,e,n){n.enterVertex(e),r.neighbors(e).forEach(function(i){n.allowTraversal(e,i)&&(n.beforeTraversal(e,i),t(r,i,n),n.afterTraversal(e,i))}),n.leaveVertex(e)};r.exports=n},{}],6:[function(t,r){"use strict";function e(t,r){var e={},i={},o=new n;e[r]=0,t.vertices.forEach(function(t){t!==r&&(e[t]=1/0),o.insert(t,e[t])});for(var s,a=function(r){var n=e[s]+t.edge(s,r);n<e[r]&&(e[r]=n,i[r]=s,o.changePriority(r,e[r]))};!o.isEmpty();)s=o.extract(),t.neighbors(s).forEach(a);return{distance:e,previous:i}}var n=t("../../data_structure/priority_queue");r.exports=e},{"../../data_structure/priority_queue":48}],7:[function(t,r){"use strict";var e=t("../../data_structure/graph"),n=t("../../algorithms/graph/depth_first_search"),i=function(t){var r={};if(t.vertices.forEach(function(e){r[e]=t.neighbors(e).length}),t.directed)t.vertices.forEach(function(e){t.neighbors(e).forEach(function(t){r[t]-=1})});else{var e=!1;t.vertices.forEach(function(t){r[t]%=2,r[t]&&(e&&(r[t]=-1),e=!0)})}var n,i,o;return t.vertices.forEach(function(t){if(1==r[t]){if(n)throw new Error("Duplicate start vertex.");n=t}else if(-1==r[t]){if(i)throw new Error("Duplicate finish vertex.");i=t}else{if(r[t])throw new Error("Unexpected vertex degree for "+t);o||(o=t)}}),n||i||(n=i=o),{start:n,finish:i}},o=function(t){if(!t.vertices.size)return[];var r=i(t),o=[r.finish],s=new e(t.directed);return t.vertices.forEach(s.addVertex.bind(s)),n(t,r.start,{allowTraversal:function(t,r){return!s.edge(t,r)},beforeTraversal:function(t,r){s.addEdge(t,r)},afterTraversal:function(t){o.push(t)}}),t.vertices.forEach(function(r){if(s.neighbors(r).length<t.neighbors(r).length)throw new Error("There is no euler path for a disconnected graph.")}),o.reverse()};r.exports=o},{"../../algorithms/graph/depth_first_search":5,"../../data_structure/graph":44}],8:[function(t,r){"use strict";var e=function(t){var r=Object.create(null);t.vertices.forEach(function(e){r[e]=Object.create(null),t.vertices.forEach(function(n){r[e][n]=e===n?0:void 0!==t.edge(e,n)?t.edge(e,n):1/0})});var e=Object.create(null);t.vertices.forEach(function(t){e[t]=Object.create(null)}),t.vertices.forEach(function(n){t.vertices.forEach(function(i){t.vertices.forEach(function(t){var o=r[i][n]+r[n][t];o<r[i][t]&&(r[i][t]=o,e[i][t]=n)})})}),t.vertices.forEach(function(t){if(r[t][t]<0)throw new Error("The graph contains a negative-weighted cycle!")});var n=function(t,n){if(!Number.isFinite(r[t][n]))return null;var i=[t];return t!=n&&!function t(r,n){if(void 0===e[r][n])i.push(n);else{var o=e[r][n];t(r,o),t(o,n)}}(t,n),i};return{distance:r,path:n}};r.exports=e},{}],9:[function(t,r){"use strict";var e=t("../../data_structure/disjoint_set_forest"),n=t("../../data_structure/graph"),i=function(t){if(t.directed)throw new Error("Can't build MST of a directed graph.");var r=new e,i=new n(!1);t.vertices.forEach(i.addVertex.bind(i));var o=[];return t.vertices.forEach(function(r){t.neighbors(r).forEach(function(e){e>r&&o.push({ends:[r,e],weight:t.edge(r,e)})})}),o.sort(function(t,r){return t.weight-r.weight}).forEach(function(t){r.sameSubset(t.ends[0],t.ends[1])||(i.addEdge(t.ends[0],t.ends[1],t.weight),r.merge(t.ends[0],t.ends[1]))}),i};r.exports=i},{"../../data_structure/disjoint_set_forest":43,"../../data_structure/graph":44}],10:[function(t,r){"use strict";var e=t("../../data_structure/priority_queue"),n=t("../../data_structure/graph"),i=function(t){if(t.directed)throw new Error("Can't build MST of a directed graph.");var r=new n(!1),i=Object.create(null),o=new e;t.vertices.forEach(function(t){o.insert(t,1/0)});for(var s=function(r){var e=t.edge(u,r);e<o.priority(r)&&(o.changePriority(r,e),i[r]=u)};!o.isEmpty();){var a=o.extract(!0),u=a.item,h=a.priority;i[u]?r.addEdge(i[u],u,h):r.addVertex(u),t.neighbors(u).forEach(s)}return r};r.exports=i},{"../../data_structure/graph":44,"../../data_structure/priority_queue":48}],11:[function(t,r){"use strict";var e=t("../../data_structure/stack"),n=t("../../algorithms/graph/depth_first_search"),i=function(t){var r=new e,i={},o=0;return t.vertices.forEach(function(e){i[e]||n(t,e,{allowTraversal:function(t,r){return!i[r]},enterVertex:function(t){i[t]=++o},leaveVertex:function(t){r.push(t)}})}),r};r.exports=i},{"../../algorithms/graph/depth_first_search":5,"../../data_structure/stack":51}],12:[function(t,r){"use strict";var e=function(t,r){for(var e,n,i=0,o=1,s=1,a=0,u=r,h=t;0!==u;)e=Math.floor(h/u),n=u,u=h-e*u,h=n,n=i,i=o-e*i,o=n,n=s,s=a-e*s,a=n;return{x:o,y:a}};r.exports=e},{}],13:[function(t,r){"use strict";var e=function(t,r){return t*r},n=function(t,r,n,i){if(void 0===n&&(n=e,i=1),0>r||Math.floor(r)!=r)throw new Error("Power must be a positive integer or zero.");if(!r){if(void 0===i)throw new Error("The power is zero, but identity value not set.");return i}for(var o,s=function(t){o=void 0===o?t:n(o,t)},a=t;r;r>>>=1,a=n(a,a))1&r&&s(a);return o};r.exports=n},{}],14:[function(t,r){"use strict";var e=t("./fast_power"),n=function(t){return 2>t?t:n(t-1)+n(t-2)},i=function(t){for(var r=0,e=1,n=t,i=1;t>i;i++)n=e+r,r=e,e=n;return n},o=function(){var t=[0,1],r=function(e){return void 0===t[e]&&(t[e]=r(e-1)+r(e-2)),t[e]};return r}(),s=function(t){var r=(1+Math.sqrt(5))/2;return Math.floor(Math.pow(r,t)/Math.sqrt(5)+.5)},a=function(t){var r=[[1,1],[1,0]],n=function(t,r){return[[t[0][0]*r[0][0]+t[0][1]*r[1][0],t[0][0]*r[0][1]+t[0][1]*r[1][1]],[t[1][0]*r[0][0]+t[1][1]*r[1][0],t[1][0]*r[0][1]+t[1][1]*r[1][1]]]},i=e(r,t,n,[[1,0],[0,1]]);return i[0][1]};i.exponential=n,i.withMemoization=o,i.direct=s,i.logarithmic=a,r.exports=i},{"./fast_power":13}],15:[function(t,r){"use strict";var e=function(t){for(var r=t.length-1;r>0;r--){var e=Math.floor(Math.random()*(r+1)),n=t[r];t[r]=t[e],t[e]=n}};r.exports=e},{}],16:[function(t,r){"use strict";var e=function(t,r){var e=t;for(t=Math.max(t,r),r=Math.min(e,r);0!==r;)e=r,r=t%r,t=e;return t},n=function(t,r){if(0===t)return r;if(0===r)return t;for(var e=0;0===(1&(t|r));++e)t>>=1,r>>=1;for(;0===(1&t);)t>>=1;var n;do{for(;0===(1&r);)r>>=1;t>r&&(n=r,r=t,t=n),r-=t}while(0!==r);return t<<e};e.binary=n,r.exports=e},{}],17:[function(t,r){"use strict";var e=function(t,r,e){r=r||1e-7,e=e||1e7;var n,i,o=t,s=0,a=0;do a++,i=(o-s)/2+s,n=i*i,t>n?s=i:o=i;while(Math.abs(n-t)>r&&e>a);var u=Math.round(i);return u*u===t&&(i=u),i};r.exports=e},{}],18:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){if(!t.length)return!1;for(var n=new e(r),i=t.length-1;i&&n.greaterThanOrEqual(t[i-1],t[i]);)i-=1;if(!i)return!1;for(var o=t[--i],s=t.length-1;n.lessThanOrEqual(t[s],o);)s-=1;t[i]=t[s],t[s]=o;for(var a=i,u=t.length;++a<--u;){var h=t[a];t[a]=t[u],t[u]=h}return!0};r.exports=n},{"../../util/comparator":58}],19:[function(t,r){"use strict";var e=function(t){if(0===t.length)return[];for(var r=[],e=[],n=0;n<t.length;n++)e[n]=!0;for(n=0;n<Math.pow(2,t.length);n++){r.push([]);for(var i=0;i<t.length;i++)n%Math.pow(2,i)===0&&(e[i]=!e[i]),e[i]&&r[n].push(t[i])}return r},n=function(t){if(0===t.length)return[];if(1==t.length)return[[],[t[0]]];var r=[],e=t[0];return t.splice(0,1),n(t).forEach(function(t){r.push(t);var n=[e];n.push.apply(n,t),r.push(n)}),r},i=e;i.recursive=n,r.exports=i},{}],20:[function(t,r){"use strict";var e=function(t,r){if(r>t.length)throw new Error("Sample size exceeds the total number of elements.");for(var e=t.slice(0,r),n=r;n<t.length;++n){var i=Math.floor(Math.random()*(n+1));r>i&&(e[i]=t[n])}return e};r.exports=e},{}],21:[function(t,r){"use strict";var e=function(t){var r=t.reduce(function(t,r){return t[r]=t[r]+1||1,t},{}),e=Object.keys(r).map(function(e){return r[e]/t.length});return e.reduce(function(t,r){return t-r*Math.log(r)},0)*Math.LOG2E};r.exports=e},{}],22:[function(t,r){"use strict";var e=t("../../data_structure/queue.js"),n=function(t,r){var n=new e;n.push(t);for(var i;!n.isEmpty();)i=n.pop(),r(i.value),i.left&&n.push(i.left),i.right&&n.push(i.right)};r.exports=n},{"../../data_structure/queue.js":49}],23:[function(t,r){"use strict";var e=function(t,r){for(var e=0,n=t.length-1;n>=e;){var i=(n-e>>1)+e;if(t[i]===r)return i;t[i]<r?e=i+1:n=i-1}return-1};r.exports=e},{}],24:[function(t,r){"use strict";var e=function(t,r){t&&(e(t.left,r),r(t.value),e(t.right,r))},n=function(t,r){t&&(r(t.value),n(t.left,r),n(t.right,r))},i=function(t,r){t&&(i(t.left,r),i(t.right,r),r(t.value))};e.preOrder=n,e.postOrder=i,r.exports=e},{}],25:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=t.length,o=i-1,s=!1,a=0;i-1>a;a++){for(var u=0,h=0;o>h;h++)if(n.greaterThan(t[h],t[h+1])){var c=t[h];t[h]=t[h+1],t[h+1]=c,u=h,s=!0}if(!s)return t;o=u}return t};r.exports=n},{"../../util/comparator":58}],26:[function(t,r){"use strict";var e=function(t){for(var r=n(t),e=[],i=t.length,o=0;i>o;o++){var s=t[o].key;void 0===e[s]&&(e[s]=[]),e[s].push(t[o])}t=[];var a=0;for(o=0;r>=o;o++)if(void 0!==e[o])for(var u=e[o].length,h=0;u>h;h++)t[a++]=e[o][h];return t},n=function(t){for(var r=t[0].key,e=t.length,n=1;e>n;n++)t[n].key>r&&(r=t[n].key);return r};r.exports=e},{}],27:[function(t,r){"use strict";var e=t("../../data_structure/heap").MinHeap,n=function(t,r){var n=new e(r);n.heapify(t);for(var i=[];!n.isEmpty();)i.push(n.extract());return i};r.exports=n},{"../../data_structure/heap":46}],28:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=1,o=t.length;o>i;i++){for(var s=t[i],a=i;a>0&&n.lessThan(s,t[a-1]);)t[a]=t[a-1],a--;t[a]=s}return t};r.exports=n},{"../../util/comparator":58}],29:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){var n=new e(r);return function t(r){if(r.length>1){var e=r.length>>1,o=t(r.slice(0,e)),s=t(r.slice(e));r=i(o,s,n)}return r}(t)},i=function(t,r,e){for(var n=0,i=0,o=[];n<t.length&&i<r.length;)o.push(e.lessThan(t[n],r[i])?t[n++]:r[i++]);return o.concat(n<t.length?t.slice(n):r.slice(i))};r.exports=n},{"../../util/comparator":58}],30:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){var n=new e(r);return function t(r,e,o){if(o>e){var s=i(r,n,e,o);t(r,e,s-1),t(r,s+1,o)}return r}(t,0,t.length-1)},i=function(t,r,e,n){o(t,Math.floor(Math.random()*(n-e))+e,n);for(var i=n,s=e,a=e;n>a;a++)r.lessThan(t[a],t[i])&&(o(t,a,s),s++);return o(t,s,i),s},o=function(t,r,e){var n=t[e];t[e]=t[r],t[r]=n};r.exports=n},{"../../util/comparator":58}],31:[function(t,r){"use strict";var e=function(t){for(var r=i(t),e=0===r?1:1+Math.floor(Math.log(r)/Math.log(10)),o=0;e>o;o++)t=n(t,o);return t},n=function(t,r){for(var e=t.length,n=[],i=0;10>i;i++)n[i]=[];for(i=0;e>i;i++){var o=parseInt((t[i].key/Math.pow(10,r)).toFixed(r))%10;n[o].push(t[i])}var s=0;for(i=0;10>i;i++)for(var a=n[i].length,u=0;a>u;u++)t[s++]=n[i][u];return t},i=function(t){for(var r,e=1;e<t.length;e++)(void 0===r||t[e].key>r)&&(r=t[e].key);return r};r.exports=e},{}],32:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=t.length,o=0;i-1>o;o++){for(var s=o,a=o+1;i>a;a++)n.greaterThan(t[s],t[a])&&(s=a);if(s!=o){var u=t[o];t[o]=t[s],t[s]=u}}return t};r.exports=n},{"../../util/comparator":58}],33:[function(t,r){"use strict";var e=t("../../util/comparator"),n=function(t,r){for(var n=new e(r),i=0,o=t.length-1,s=parseInt((o-i+1)/2),a=0,u=0,h=0;s>=1;){for(a=i+s;o>=a;a+=1){for(h=t[a],u=a-s;u>=i&&n.greaterThan(t[u],h);)t[u+s]=t[u],u-=s;t[u+s]=h}s=parseInt(s/2)}return t};r.exports=n},{"../../util/comparator":58}],34:[function(t,r){"use strict";var e=function(t,r){if(t.length!=r.length)throw new Error("Strings must be equal in length");for(var e=0,n=0;n<t.length;n++)t[n]!=r[n]&&e++;return e};r.exports=e},{}],35:[function(t,r){"use strict";var e={},n=(-1>>>0).toString(2).length,i=function(t){var r=[],e=0,i=0;return t.split("").forEach(function(t){e=e<<1|t,i+=1,i==n&&(r.push(e),e=i=0)}),i?r.push(e,i):r.push(n),r},o=function(t){if(!t.length)return"";if(1==t.length)throw new Error("Compressed array must be either empty or at least 2 blocks big.");var r=new Array(n+1).join(0),e=t.slice(0,-2).map(function(t){return(r+(t>>>0).toString(2)).slice(-r.length)}).join(""),i=t.slice(-1)[0],o=t.slice(-2)[0];return e+=(r+(o>>>0).toString(2)).slice(-i)};e.encode=function(t,r){if(!t.length)return{encoding:{},value:r?[]:""};var e={};t.split("").forEach(function(t){e[t]=(e[t]||0)+1});var n=Object.keys(e).map(function(t){return{char:t,count:e[t]}}),o=function(t,r){return t.count-r.count},s=function(t,r){return t&&(r&&t.count<r.count||!r)};n.sort(o);for(var a=[],u=0,h=0,c=function(){return s(n[u],a[h])?n[u++]:a[h++]},f=n.length;f>1;--f){var l=c(),p=c();l.code="0",p.code="1";var g={count:l.count+p.count,parts:[l,p]};a.push(g)}var d=c();d.code=n.length>1?"":"0",function t(r){if(r.parts){var e=r.parts[0],n=r.parts[1];e.code+=r.code,n.code+=r.code,t(e),t(n)}}(d);var v=n.reduce(function(t,r){return t[r.char]=r.code.split("").reverse().join(""),t},{}),_=t.split("").map(function(t){return v[t]}).join("");return{encoding:v,value:r?i(_):_}},e.decode=function(t,r){Array.isArray(r)&&(r=o(r));var e=Object.keys(t).reduce(function(r,e){return r[t[e]]=e,r},{}),n=[],i=r.split("").reduce(function(t,r){t+=r;var i=e[t];return i&&(n.push(i),t=""),t},"");if(i)throw new Error("Invalid string to decode.");return n.join("")},r.exports=e},{}],36:[function(t,r){"use strict";var e=function(t,r){for(var e=t.length,i=r.length,o=0,s=0,a=n(r);e>o+s;)if(r[s]===t[o+s]){if(s===i-1)return o;++s}else a[s]>=0?(s=a[s],o=o+s-a[s]):(s=0,++o);return e},n=function(t){var r=t.length,e=[],n=2,i=0;for(e[0]=-1,e[1]=0;r>n;)t[n-1]===t[i]?(++i,e[n]=i,++n):i>0?i=e[i]:(e[n]=0,++n);return e};r.exports=e},{}],37:[function(t,r){"use strict";var e=function(t,r){var e,n,i=[];for(e=0;e<=t.length;e++)i[e]=[],i[e][0]=e;for(n=0;n<=r.length;n++)i[0][n]=n;for(e=1;e<=t.length;e++)for(n=1;n<=r.length;n++)i[e][n]=Math.min(i[e-1][n-1],i[e-1][n],i[e][n-1])+(t[e-1]!=r[n-1]?1:0);return i[t.length][r.length]};r.exports=e},{}],38:[function(t,r){"use strict";var e=function(t,r){var e,n,i=new Array(t.length+1);for(e=0;e<=t.length;e++)i[e]=new Int32Array(r.length+1);for(e=1;e<=t.length;e++)for(n=1;n<=r.length;n++)i[e][n]=t[e-1]==r[n-1]?i[e-1][n-1]+1:Math.max(i[e][n-1],i[e-1][n]);e=t.length,n=r.length;for(var o="";0!==i[e][n];)t[e-1]===r[n-1]?(o=t[e-1]+o,e--,n--):i[e-1][n]>i[e][n-1]?e--:n--;return o};r.exports=e},{}],39:[function(t,r){"use strict";var e=function(t,r){var e,n,i=new Array(t.length+1);for(e=0;e<=t.length+1;e++)i[e]=new Int32Array(r.length+1);var o={},s=0;for(e=1;e<=t.length;e++)for(n=1;n<=r.length;n++)t[e-1]==r[n-1]?(i[e][n]=i[e-1][n-1]+1,i[e][n]>s&&(o.i=e,o.j=n,s=i[e][n])):i[e][n]=0;var a="";return s&&(a=t.substring(o.i-s,o.i)),a};r.exports=e},{}],40:[function(t,r){"use strict";var e=997,n=function(t,r){if(0===r.length)return 0;for(var n,o=i(r),s=t.substring(0,r.length),a=r.length;a<=t.length;a++)if(void 0===n?n=i(s):(n-=s.charCodeAt(0)*Math.pow(e,r.length-1),n*=e,n+=t.charCodeAt(a),s=s.substring(1)+t[a]),o===n&&r===s)return a===r.length?0:a-r.length+1;return-1},i=function(t){for(var r=0,n=0;n<t.length;n++)r+=t.charCodeAt(n)*Math.pow(e,t.length-n-1);return r};r.exports=n},{}],41:[function(t,r){"use strict";r.exports={BST:t("./data_structure/bst"),Graph:t("./data_structure/graph"),HashTable:t("./data_structure/hash_table"),Heap:t("./data_structure/heap"),LinkedList:t("./data_structure/linked_list"),PriorityQueue:t("./data_structure/priority_queue"),Queue:t("./data_structure/queue"),Stack:t("./data_structure/stack"),Set:t("./data_structure/set"),DisjointSetForest:t("./data_structure/disjoint_set_forest")}},{"./data_structure/bst":42,"./data_structure/disjoint_set_forest":43,"./data_structure/graph":44,"./data_structure/hash_table":45,"./data_structure/heap":46,"./data_structure/linked_list":47,"./data_structure/priority_queue":48,"./data_structure/queue":49,"./data_structure/set":50,"./data_structure/stack":51}],42:[function(t,r){"use strict";function e(t){this.root=null,this._size=0,this._comparator=new i(t),Object.defineProperty(this,"size",{get:function(){return this._size}.bind(this)})}function n(t,r){this.value=t,this.parent=r,this.left=null,this.right=null}var i=t("../util/comparator");e.prototype.insert=function(t,r){if(!r){if(!this.root)return this.root=new n(t),void this._size++;r=this.root}var e=this._comparator.lessThan(t,r.value)?"left":"right";r[e]?this.insert(t,r[e]):(r[e]=new n(t,r),this._size++)},e.prototype.contains=function(t){return!!this._find(t)},e.prototype._find=function(t,r){if(!r){if(!this.root)return!1;r=this.root}return r.value===t?r:this._comparator.lessThan(t,r.value)?r.left&&this._find(t,r.left):this._comparator.greaterThan(t,r.value)?r.right&&this._find(t,r.right):void 0},e.prototype._replaceNodeInParent=function(t,r){var e=t.parent;e?(e[t===e.left?"left":"right"]=r,r&&(r.parent=e)):this.root=r},e.prototype._findMin=function(t){for(var r=t;r.left;)r=r.left;return r},e.prototype.remove=function(t){var r=this._find(t);if(!r)throw new Error("Item not found in the tree");if(r.left&&r.right){var e=this._findMin(r.right);this.remove(e.value),r.value=e.value}else this._replaceNodeInParent(r,r.left||r.right),this._size--},r.exports=e},{"../util/comparator":58}],43:[function(t,r){"use strict";function e(){this._parents={},this._ranks={},this._sizes={}}e.prototype._introduce=function(t){t in this._parents||(this._parents[t]=t,this._ranks[t]=0,this._sizes[t]=1)},e.prototype.sameSubset=function(t){this._introduce(t);var r=this.root(t);return[].slice.call(arguments,1).every(function(t){return this._introduce(t),this.root(t)==r}.bind(this))},e.prototype.root=function(t){return this._introduce(t),this._parents[t]!=t&&(this._parents[t]=this.root(this._parents[t])),this._parents[t]},e.prototype.size=function(t){return this._introduce(t),this._sizes[this.root(t)]},e.prototype.merge=function t(r,e){arguments.length>2&&t.apply(this,[].slice.call(arguments,1)),this._introduce(r),this._introduce(e);var n=this.root(r),i=this.root(e);return this._ranks[n]<this._ranks[i]?(this._parents[n]=i,this._sizes[i]+=this._sizes[n]):n!=i&&(this._parents[i]=n,this._sizes[n]+=this._sizes[i],this._ranks[n]==this._ranks[i]&&(this._ranks[n]+=1)),this},r.exports=e},{}],44:[function(t,r){"use strict";function e(t){this.directed=void 0===t?!0:!!t,this.adjList=Object.create(null),this.vertices=new n}var n=t("./set"),i=function(t){return""+t};e.prototype.addVertex=function(t){if(t=i(t),this.vertices.contains(t))throw new Error('Vertex "'+t+'" has already been added');this.vertices.add(t),this.adjList[t]=Object.create(null)},e.prototype.addEdge=function(t,r,e){t=i(t),r=i(r),e=void 0===e?1:e,this.adjList[t]||this.addVertex(t),this.adjList[r]||this.addVertex(r),this.adjList[t][r]=(this.adjList[t][r]||0)+e,this.directed||(this.adjList[r][t]=(this.adjList[r][t]||0)+e)},e.prototype.neighbors=function(t){return Object.keys(this.adjList[i(t)])},e.prototype.edge=function(t,r){return this.adjList[i(t)][i(r)]},r.exports=e},{"./set":50}],45:[function(t,r){"use strict";function e(t){this._table=new Array(t||64),this._items=0,Object.defineProperty(this,"capacity",{get:function(){return this._table.length}}),Object.defineProperty(this,"size",{get:function(){return this._items}})}var n=t("./linked_list");e.prototype.hash=function(t){"string"!=typeof t&&(t=JSON.stringify(t));for(var r=0,e=0;e<t.length;e++)r=(r<<5)-r+t.charCodeAt(e),r&=r;return r},e.prototype.get=function(t){var r,e=this._position(t);return(r=this._findInList(this._table[e],t))?r.value.v:void 0},e.prototype.put=function(t,r){var e=this._position(t);this._table[e]||(this._table[e]=new n);var i={k:t,v:r},o=this._findInList(this._table[e],t);o?o.value=i:(this._table[e].add(i),this._items++,this._items===this.capacity&&this._increaseCapacity())},e.prototype.del=function(t){var r,e=this._position(t);(r=this._findInList(this._table[e],t))&&(this._table[e].delNode(r),this._items--)},e.prototype._position=function(t){return Math.abs(this.hash(t))%this.capacity},e.prototype._findInList=function(t,r){for(var e=t&&t.head;e;){if(e.value.k===r)return e;e=e.next}},e.prototype._increaseCapacity=function(){var t=this._table;this._table=new Array(2*this.capacity),this._items=0;for(var r=0;r<t.length;r++)for(var e=t[r]&&t[r].head;e;)this.put(e.value.k,e.value.v),e=e.next},e.prototype.forEach=function(t){for(var r=function(r){r.forEach(function(r){t(r.k,r.v)})},e=0;e<this._table.length;e++)this._table[e]&&r(this._table[e])},r.exports=e},{"./linked_list":47}],46:[function(t,r){"use strict";function e(t){this._elements=[null],this._comparator=new i(t),Object.defineProperty(this,"n",{get:function(){return this._elements.length-1}.bind(this)})}function n(t){e.call(this,t),this._comparator.reverse()}var i=t("../util/comparator");e.prototype._swap=function(t,r){var e=this._elements[t];this._elements[t]=this._elements[r],this._elements[r]=e},e.prototype.isEmpty=function(){return 0===this.n},e.prototype.insert=function(t){this._elements.push(t),this._siftUp()},e.prototype.extract=function(){var t=this._elements[1],r=this._elements.pop();return this.n&&(this._elements[1]=r,this._siftDown()),t},e.prototype._siftUp=function(){var t,r;for(t=this.n;t>1&&(r=t>>1)&&this._comparator.greaterThan(this._elements[r],this._elements[t]);t=r)this._swap(r,t)},e.prototype._siftDown=function(t){var r;for(t=t||1;(r=t<<1)<=this.n&&(r+1<=this.n&&this._comparator.lessThan(this._elements[r+1],this._elements[r])&&r++,!this._comparator.lessThan(this._elements[t],this._elements[r]));t=r)this._swap(t,r)},e.prototype.heapify=function(t){t&&(this._elements=t,this._elements.unshift(null));for(var r=this.n>>1;r>0;r--)this._siftDown(r)},e.prototype.forEach=function(t){var r,e=[];for(r=0;r<this._elements.length;r++)e.push(this._elements[r]);for(r=this.n;r>0;r--)t(this.extract());this._elements=e},n.prototype=new e,r.exports={MinHeap:e,MaxHeap:n}},{"../util/comparator":58}],47:[function(t,r){"use strict";function e(){this._length=0,this.head=null,this.tail=null,Object.defineProperty(this,"length",{get:function(){return this._length}.bind(this)})}function n(t){this.value=t,this.prev=null,this.next=null}e.prototype.isEmpty=function(){return 0===this.length},e.prototype.add=function(t,r){if(r>this.length||0>r)throw new Error("Index out of bounds");var e=new n(t);if(void 0!==r&&r<this.length){var i,o;0===r?(o=this.head,this.head=e):(o=this.getNode(r),i=o.prev,i.next=e,e.prev=i),o.prev=e,e.next=o}else this.head||(this.head=e),this.tail&&(this.tail.next=e,e.prev=this.tail),this.tail=e;this._length++},e.prototype.get=function(t){return this.getNode(t).value},e.prototype.getNode=function(t){if(t>=this.length||0>t)throw new Error("Index out of bounds");for(var r=this.head,e=1;t>=e;e++)r=r.next;return r},e.prototype.del=function(t){if(t>=this.length||0>t)throw new Error("Index out of bounds");this.delNode(this.getNode(t))},e.prototype.delNode=function(t){t===this.tail?this.tail=t.prev:t.next.prev=t.prev,t===this.head?this.head=t.next:t.prev.next=t.next,this._length--},e.prototype.forEach=function(t){for(var r=this.head;r;)t(r.value),r=r.next},r.exports=e},{}],48:[function(t,r){"use strict";function e(t){var r=this;n.call(this,function(t,e){return r.priority(t)<r.priority(e)?-1:1}),this._priority={},t=t||{},Object.keys(t).forEach(function(e){r.insert(e,t[e])})}var n=t("./heap").MinHeap;e.prototype=new n,e.prototype.insert=function(t,r){return void 0!==this._priority[t]?this.changePriority(t,r):(this._priority[t]=r,void n.prototype.insert.call(this,t))},e.prototype.extract=function(t){var r=n.prototype.extract.call(this);return t?r&&{item:r,priority:this._priority[r]}:r},e.prototype.priority=function(t){return this._priority[t]},e.prototype.changePriority=function(t,r){this._priority[t]=r,this.heapify()},r.exports=e},{"./heap":46}],49:[function(t,r){"use strict";function e(){this._elements=new n,Object.defineProperty(this,"length",{get:function(){return this._elements.length}.bind(this)})}var n=t("./linked_list");e.prototype.isEmpty=function(){return this._elements.isEmpty()},e.prototype.push=function(t){this._elements.add(t)},e.prototype.pop=function(){if(this.isEmpty())throw new Error("Empty queue");var t=this._elements.get(0);return this._elements.del(0),t},e.prototype.peek=function(){if(this.isEmpty())throw new Error("Empty queue");return this._elements.get(0)},e.prototype.forEach=function(t){this._elements.forEach(t)},r.exports=e},{"./linked_list":47}],50:[function(t,r){"use strict";var e=t("./hash_table"),n=function(){this._elements=new e(arguments.length),this.add.apply(this,arguments),Object.defineProperty(this,"size",{get:function(){return this._elements.size}})};n.prototype.add=function(){for(var t=0;t<arguments.length;t++)this._elements.put(arguments[t],!0);return this},n.prototype.remove=function(){for(var t=0;t<arguments.length;t++)this._elements.del(arguments[t]);return this},n.prototype.contains=function(t){return void 0!==this._elements.get(t)},n.prototype.forEach=function(t){this._elements.forEach(t)},r.exports=n},{"./hash_table":45}],51:[function(t,r){"use strict";function e(){n.call(this)}var n=t("./queue");e.prototype=new n,e.prototype.push=function(t){this._elements.add(t,0)},r.exports=e},{"./queue":49}],52:[function(t,r){"use strict";r.exports={topologicalSort:t("./algorithms/graph/topological_sort"),dijkstra:t("./algorithms/graph/dijkstra"),SPFA:t("./algorithms/graph/SPFA"),bellmanFord:t("./algorithms/graph/bellman_ford"),eulerPath:t("./algorithms/graph/euler_path"),depthFirstSearch:t("./algorithms/graph/depth_first_search"),kruskal:t("./algorithms/graph/kruskal"),breadthFirstSearch:t("./algorithms/graph/breadth_first_search"),bfsShortestPath:t("./algorithms/graph/bfs_shortest_path"),prim:t("./algorithms/graph/prim"),floydWarshall:t("./algorithms/graph/floyd_warshall")}},{"./algorithms/graph/SPFA":1,"./algorithms/graph/bellman_ford":2,"./algorithms/graph/bfs_shortest_path":3,"./algorithms/graph/breadth_first_search":4,"./algorithms/graph/depth_first_search":5,"./algorithms/graph/dijkstra":6,"./algorithms/graph/euler_path":7,"./algorithms/graph/floyd_warshall":8,"./algorithms/graph/kruskal":9,"./algorithms/graph/prim":10,"./algorithms/graph/topological_sort":11}],53:[function(t,r){"use strict";var e={DataStructure:t("./data_structure"),Graph:t("./graph"),Math:t("./math"),Search:t("./search"),Sorting:t("./sorting"),String:t("./string")};r.exports=e},{"./data_structure":41,"./graph":52,"./math":54,"./search":55,"./sorting":56,"./string":57}],54:[function(t,r){"use strict";r.exports={fibonacci:t("./algorithms/math/fibonacci"),fisherYates:t("./algorithms/math/fisher_yates"),gcd:t("./algorithms/math/gcd"),extendedEuclidean:t("./algorithms/math/extended_euclidean"),newtonSqrt:t("./algorithms/math/newton_sqrt"),reservoirSampling:t("./algorithms/math/reservoir_sampling"),fastPower:t("./algorithms/math/fast_power"),nextPermutation:t("./algorithms/math/next_permutation"),powerSet:t("./algorithms/math/power_set"),shannonEntropy:t("./algorithms/math/shannon_entropy")}},{"./algorithms/math/extended_euclidean":12,"./algorithms/math/fast_power":13,"./algorithms/math/fibonacci":14,"./algorithms/math/fisher_yates":15,"./algorithms/math/gcd":16,"./algorithms/math/newton_sqrt":17,"./algorithms/math/next_permutation":18,"./algorithms/math/power_set":19,"./algorithms/math/reservoir_sampling":20,"./algorithms/math/shannon_entropy":21}],55:[function(t,r){"use strict";r.exports={bfs:t("./algorithms/search/bfs"),binarySearch:t("./algorithms/search/binarysearch"),dfs:t("./algorithms/search/dfs")}},{"./algorithms/search/bfs":22,"./algorithms/search/binarysearch":23,"./algorithms/search/dfs":24}],56:[function(t,r){"use strict";r.exports={bubbleSort:t("./algorithms/sorting/bubble_sort"),countingSort:t("./algorithms/sorting/counting_sort"),heapSort:t("./algorithms/sorting/heap_sort"),mergeSort:t("./algorithms/sorting/merge_sort"),quicksort:t("./algorithms/sorting/quicksort"),selectionSort:t("./algorithms/sorting/selection_sort"),radixSort:t("./algorithms/sorting/radix_sort"),insertionSort:t("./algorithms/sorting/insertion_sort"),shellSort:t("./algorithms/sorting/shell_sort")}},{"./algorithms/sorting/bubble_sort":25,"./algorithms/sorting/counting_sort":26,"./algorithms/sorting/heap_sort":27,"./algorithms/sorting/insertion_sort":28,"./algorithms/sorting/merge_sort":29,"./algorithms/sorting/quicksort":30,"./algorithms/sorting/radix_sort":31,"./algorithms/sorting/selection_sort":32,"./algorithms/sorting/shell_sort":33}],57:[function(t,r){"use strict";r.exports={levenshtein:t("./algorithms/string/levenshtein"),rabinKarp:t("./algorithms/string/rabin_karp"),knuthMorrisPratt:t("./algorithms/string/knuth_morris_pratt"),huffman:t("./algorithms/string/huffman"),hamming:t("./algorithms/string/hamming"),longestCommonSubsequence:t("./algorithms/string/longest_common_subsequence"),longestCommonSubstring:t("./algorithms/string/longest_common_substring")}},{"./algorithms/string/hamming":34,"./algorithms/string/huffman":35,"./algorithms/string/knuth_morris_pratt":36,"./algorithms/string/levenshtein":37,"./algorithms/string/longest_common_subsequence":38,"./algorithms/string/longest_common_substring":39,"./algorithms/string/rabin_karp":40}],58:[function(t,r){"use strict";function e(t){t&&(this.compare=t)}e.prototype.compare=function(t,r){return t==r?0:r>t?-1:1
},e.prototype.lessThan=function(t,r){return this.compare(t,r)<0},e.prototype.lessThanOrEqual=function(t,r){return this.lessThan(t,r)||this.equal(t,r)},e.prototype.greaterThan=function(t,r){return this.compare(t,r)>0},e.prototype.greaterThanOrEqual=function(t,r){return this.greaterThan(t,r)||this.equal(t,r)},e.prototype.equal=function(t,r){return 0===this.compare(t,r)},e.prototype.reverse=function(){var t=this.compare;this.compare=function(r,e){return t(e,r)}},r.exports=e},{}]},{},[53])(53)})}({},function(){return this}());
{'fraction_non_alphanumeric': 0.3055666615408273, 'fraction_numerical': 0.021713055512840227, 'mean_word_length': 12.394644696189495, 'pattern_counts': {'":': 175, '<': 107, '<?xml version=': 0, '>': 180, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3200166', 'n_tokens_mistral': 29285, 'n_tokens_neox': 28674, 'n_words': 1245}