Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdd8258a

Browse files
authored
Merge pull requestmgechev#116 from mgechev/segment-tree
feat(DataStructures): add segment tree
2 parentsc4ace61 +34217ff commitdd8258a

File tree

2 files changed

+194
-0
lines changed

2 files changed

+194
-0
lines changed

‎src/data-structures/segment-tree.js

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
/**
2+
* Implementation of a segment tree.
3+
*
4+
*@example
5+
* var SegmentTree = require('path-to-algorithms/src/data-structures'+
6+
* '/segment-tree').SegmentTree;
7+
*
8+
* var tree = SegmentTree.indexArray([-1, 2, 4, 0], Infinity, function (a, b) {
9+
* return Math.min(a, b);
10+
* });
11+
*
12+
*@public
13+
*@constructor
14+
*@param {any} placeholder A placeholder value dpendent on the aggregate.
15+
*@param {Function} aggregate Generates the values for the intermediate nodes.
16+
*@module data-structures/segment-tree
17+
*/
18+
(function(exports){
19+
20+
'use strict';
21+
22+
/**
23+
* SegmentTree constructor.
24+
*
25+
*@public
26+
*@constructor
27+
*@param {any} invalidValue Invalid value to be returned depending
28+
* on the aggregate.
29+
*@param {Function} aggregate Function to generate the intermediate
30+
* values in the tree.
31+
*/
32+
functionSegmentTree(invalidValue,aggregate){
33+
this._data=[];
34+
this._original=null;
35+
this._invalidValue=invalidValue;
36+
this._aggregate=aggregate;
37+
}
38+
39+
/**
40+
* Creates a segment tree using an array passed as element.
41+
*
42+
*@static
43+
*@public
44+
*@param {Array} array Array to be indexed.
45+
*@param {Function} aggregate Function used for generation of
46+
* intermediate nodes.
47+
*/
48+
SegmentTree.indexArray=function(array,placeholder,aggregate){
49+
varsegmentize=function(original,data,lo,hi,idx){
50+
if(lo===hi){
51+
data[idx]=original[lo];
52+
}else{
53+
varmid=Math.floor((lo+hi)/2);
54+
varleft=2*idx+1;
55+
varright=2*idx+2;
56+
segmentize(original,data,lo,mid,left);
57+
segmentize(original,data,mid+1,hi,right);
58+
data[idx]=aggregate(data[left],data[right]);
59+
}
60+
};
61+
varresult=[];
62+
if(array&&array.length){
63+
segmentize(array,result,0,array.length-1,0);
64+
}
65+
vartree=newSegmentTree(placeholder,aggregate);
66+
tree._data=result;
67+
tree._original=array;
68+
returntree;
69+
};
70+
71+
/**
72+
* Queries the SegmentTree in given range based on the set aggregate.
73+
*
74+
*@param {Number} start The start index of the interval.
75+
*@param {Number} end The end index of the interval.
76+
*/
77+
SegmentTree.prototype.query=function(start,end){
78+
if(start>end){
79+
thrownewError('The start index should be smaller by the end index');
80+
}
81+
varfindEl=function(originalArrayStart,originalArrayEnd,current){
82+
if(start>originalArrayEnd){
83+
returnthis._invalidValue;
84+
}
85+
if(end<originalArrayStart){
86+
returnthis._invalidValue;
87+
}
88+
if(start===originalArrayStart&&end===originalArrayEnd||
89+
originalArrayStart===originalArrayEnd){
90+
returnthis._data[current];
91+
}
92+
varoriginalArrayMid=
93+
Math.floor((originalArrayStart+originalArrayEnd)/2);
94+
returnthis._aggregate(
95+
findEl(originalArrayStart,originalArrayMid,2*current+1),
96+
findEl(originalArrayMid+1,originalArrayEnd,2*current+2)
97+
);
98+
}.bind(this);
99+
returnfindEl(0,this._original.length-1,0,this._aggregate);
100+
};
101+
102+
exports.SegmentTree=SegmentTree;
103+
104+
}(typeofwindow==='undefined' ?module.exports :window));
105+
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
'use strict';
2+
3+
varSegmentTree=require('../../src/data-structures/segment-tree.js')
4+
.SegmentTree;
5+
6+
vardefaultAggregate=function(a,b){
7+
returnMath.min(a,b);
8+
};
9+
10+
describe('Segment Tree',function(){
11+
12+
describe('indexing',function(){
13+
14+
it('should be a constructor function',function(){
15+
expect(typeofSegmentTree).toBe('function');
16+
});
17+
18+
it('should start with null original array',function(){
19+
expect(newSegmentTree()._original).toBe(null);
20+
});
21+
22+
it('should start with empty array as data',function(){
23+
expect(newSegmentTree()._data).not.toBe(null);
24+
expect(newSegmentTree()._data.length).toBe(0);
25+
});
26+
27+
it('should work with empty arrays',function(){
28+
vartree=SegmentTree.indexArray([],Infinity,defaultAggregate);
29+
expect(tree._data).toBeTruthy();
30+
expect(tree._data.length).toBe(0);
31+
});
32+
33+
it('should index arrays with one element',function(){
34+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
35+
expect(tree._data).toBeTruthy();
36+
expect(tree._data.length).toBe(1);
37+
});
38+
39+
it('should index any array',function(){
40+
vartree=SegmentTree.indexArray([1,2,3],Infinity,defaultAggregate);
41+
expect(tree._data).toEqual([1,1,3,1,2]);
42+
43+
tree=SegmentTree.indexArray([1,2,3,6],Infinity,defaultAggregate);
44+
expect(tree._data).toEqual([1,1,3,1,2,3,6]);
45+
});
46+
47+
});
48+
49+
describe('should find the proper value at given interval',function(){
50+
51+
it('should properly find the minimum when in range',function(){
52+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
53+
expect(tree.query(0,0)).toBe(1);
54+
55+
tree=SegmentTree.indexArray([1,2],Infinity,defaultAggregate);
56+
expect(tree.query(0,0)).toBe(1);
57+
expect(tree.query(0,1)).toBe(1);
58+
expect(tree.query(1,1)).toBe(2);
59+
60+
tree=SegmentTree.indexArray([1,-1,2],Infinity,defaultAggregate);
61+
expect(tree.query(0,2)).toBe(-1);
62+
expect(tree.query(0,1)).toBe(-1);
63+
expect(tree.query(1,1)).toBe(-1);
64+
expect(tree.query(1,2)).toBe(-1);
65+
expect(tree.query(2,2)).toBe(2);
66+
});
67+
68+
it('should properly find the minimum when outside range',function(){
69+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
70+
expect(tree.query(0,2)).toBe(1);
71+
72+
tree=SegmentTree.indexArray([1,2,3],Infinity,defaultAggregate);
73+
expect(tree.query(0,20)).toBe(1);
74+
expect(tree.query(2,20)).toBe(3);
75+
expect(Number.isFinite(tree.query(20,25))).toBe(false);
76+
});
77+
78+
it('should throw when the start index is bigger than end',function(){
79+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
80+
expect(function(){
81+
tree.query(2,1);
82+
}).toThrow();
83+
expect(function(){
84+
tree.query(1,1);
85+
}).not.toThrow();
86+
});
87+
});
88+
});
89+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp