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

Commit03f4820

Browse files
committed
Test index.
1 parent3c0f1d6 commit03f4820

File tree

2 files changed

+31
-7
lines changed

2 files changed

+31
-7
lines changed

‎src/data-structures/size-balanced-tree.js

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -248,7 +248,19 @@
248248
returnNil;
249249
}
250250
returnfindNodeAtPos(this._root,pos);
251-
},
251+
};
252+
253+
exports.SBTree.prototype.getIndex=function(node){
254+
letindex=node.left.size;
255+
while(node!=this._root){
256+
letparent=node.parent;
257+
if(parent.right===node){
258+
index+=parent.left.size+1;
259+
}
260+
node=parent;
261+
}
262+
returnindex;
263+
};
252264

253265
exports.SBTree.prototype.insert=function(pos,value){
254266
if(pos>=this._root.size){

‎test/data-structures/size-balanced-tree.spec.js

Lines changed: 18 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -100,16 +100,16 @@ describe('SBTree', function () {
100100

101101
it('push and get 100000 elements, remove the array by always remove the first/last element',function(){
102102
varsTree=newSBTree();
103-
for(vari=0;i<2000000;++i){
103+
for(vari=0;i<200000;++i){
104104
sTree.push(i);
105105
}
106106
checkNil();
107-
for(vari=0;i<2000000;++i){
107+
for(vari=0;i<200000;++i){
108108
varnode=sTree.get(i);
109109
expect(node.value).toBe(i);
110110
}
111-
expect(sTree._root.height).toBe(21);
112-
for(vari=0;i<2000000;++i){
111+
expect(sTree._root.height).toBe(18);
112+
for(vari=0;i<200000;++i){
113113
expect(sTree.get(0).value).toBe(i);
114114
varnode=sTree.remove(0);// Always remove the first element;
115115
expect(node.value).toBe(i);
@@ -137,7 +137,6 @@ describe('SBTree', function () {
137137
varnode=sTree.get(i);
138138
expect(node.value).toBe(expectedArray[i]);
139139
}
140-
console.log(sTree._root.height);
141140
for(vari=0;i<90000;++i){
142141
varremovedPos=getRandomInt(0,sTree.size);
143142
sTree.remove(removedPos);
@@ -147,7 +146,20 @@ describe('SBTree', function () {
147146
varnode=sTree.get(i);
148147
expect(node.value).toBe(expectedArray[i]);
149148
}
150-
console.log(sTree._root.height);
151149
checkNil();
152150
});
151+
152+
it('test getIndex',function(){
153+
varsTree=newSBTree();
154+
for(leti=0;i<10000;++i){
155+
letkey=i.toString();
156+
sTree.push(key);
157+
}
158+
159+
for(leti=0;i<100;++i){
160+
letitem=sTree.get(i);
161+
expect(item.value).toBe(i.toString());
162+
expect(sTree.getIndex(item)).toBe(i);
163+
}
164+
});
153165
});

0 commit comments

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