


export default class FlatQueue{

constructor(){
this.ids=[];
this.values=[];
this.length=0;
}

clear(){
this.length=0;
}

push(id,value){
let pos=this.length++;

while(pos>0){
let parent=(pos+1>>>1)-1;
let parentValue=this.values[parent];
if(value>=parentValue)break;
this.ids[pos]=this.ids[parent];
this.values[pos]=parentValue;
pos=parent;
}

this.ids[pos]=id;
this.values[pos]=value;
}

pop(){
if(this.length===0)return undefined;

let top=this.ids[0];
this.length--;

if(this.length>0){
let id=this.ids[0]=this.ids[this.length];
let value=this.values[0]=this.values[this.length];
let halfLength=this.length>>1;
let pos=0;

while(pos<halfLength){
let left=(pos<<1)+1;
let right=left+1;
let bestIndex=this.ids[left];
let bestValue=this.values[left];
let rightValue=this.values[right];

if(right<this.length&&rightValue<bestValue){
left=right;
bestIndex=this.ids[right];
bestValue=rightValue;
}
if(bestValue>=value)break;

this.ids[pos]=bestIndex;
this.values[pos]=bestValue;
pos=left;
}

this.ids[pos]=id;
this.values[pos]=value;
}

return top;
}

peek(){
if(this.length===0)return undefined;
return this.ids[0];
}

peekValue(){
if(this.length===0)return undefined;
return this.values[0];
}

shrink(){
this.ids.length=this.values.length=this.length;
}}