/*
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
Copyright 2015 Conrad Barski
*/
contract OrderStatisticTree {
function OrderStatisticTree() {
}
function update_count(uint value) private {
Node n=nodes[value];
n.count=1+nodes[n.children[false]].count+nodes[n.children[true]].count+n.dupes;
}
function update_counts(uint value) private {
uint parent=nodes[value].parent;
while (parent!=0) {
update_count(parent);
parent=nodes[parent].parent;
}
}
function update_height(uint value) private {
Node n=nodes[value];
uint height_left=nodes[n.children[false]].height;
uint height_right=nodes[n.children[true]].height;
if (height_left>height_right)
n.height=height_left+1;
else
n.height=height_right+1;
}
function balance_factor(uint value) constant private returns (int bf) {
Node n=nodes[value];
return int(nodes[n.children[false]].height)-int(nodes[n.children[true]].height);
}
function rotate(uint value,bool dir) private {
bool other_dir=!dir;
Node n=nodes[value];
bool side=n.side;
uint parent=n.parent;
uint value_new=n.children[other_dir];
Node n_new=nodes[value_new];
uint orphan=n_new.children[dir];
Node p=nodes[parent];
Node o=nodes[orphan];
p.children[side]=value_new;
n_new.side=side;
n_new.parent=parent;
n_new.children[dir]=value;
n.parent=value_new;
n.side=dir;
n.children[other_dir]=orphan;
o.parent=value;
o.side=other_dir;
update_height(value);
update_height(value_new);
update_count(value);
update_count(value_new);
}
function rebalance_insert(uint n_value) private {
update_height(n_value);
Node n=nodes[n_value];
uint p_value=n.parent;
if (p_value!=0) {
int p_bf=balance_factor(p_value);
bool side=n.side;
int sign;
if (side)
sign=-1;
else
sign=1;
if (p_bf == sign*2) {
if (balance_factor(n_value) == (-1 * sign))
rotate(n_value,side);
rotate(p_value,!side);
}
else if (p_bf != 0)
rebalance_insert(p_value);
}
}
function rebalance_delete(uint p_value,bool side) private{
if (p_value!=0) {
update_height(p_value);
int p_bf=balance_factor(p_value);
bool dir=side;
int sign;
if (side)
sign=1;
else
sign=-1;
int bf=balance_factor(p_value);
if (bf==(2*sign)) {
Node p=nodes[p_value];
uint s_value=p.children[!side];
int s_bf=balance_factor(s_value);
if (s_bf == (-1 * sign))
rotate(s_value,!side);
rotate(p_value,side);
if (s_bf!=0){
p=nodes[p_value];
rebalance_delete(p.parent,p.side);
}
}
else if (p_bf != sign){
p=nodes[p_value];
rebalance_delete(p.parent,p.side);
}
}
}
function fix_parents(uint parent,bool side) private {
if(parent!=0) {
update_count(parent);
update_counts(parent);
rebalance_delete(parent,side);
}
}
function insert_helper(uint p_value,bool side,uint value) private {
Node root=nodes[p_value];
uint c_value=root.children[side];
if (c_value==0){
root.children[side]=value;
Node child=nodes[value];
child.parent=p_value;
child.side=side;
child.height=1;
child.count=1;
update_counts(value);
rebalance_insert(value);
}
else if (c_value==value){
nodes[c_value].dupes++;
update_count(value);
update_counts(value);
}
else{
bool side_new=(value >= c_value);
insert_helper(c_value,side_new,value);
}
}
function insert(uint value) {
if (value==0)
nodes[value].dupes++;
else{
insert_helper(0,true,value);
}
}
function rightmost_leaf(uint value) constant private returns (uint leaf) {
uint child=nodes[value].children[true];
if (child!=0)
return rightmost_leaf(child);
else
return value;
}
function zero_out(uint value) private {
Node n=nodes[value];
n.parent=0;
n.side=false;
n.children[false]=0;
n.children[true]=0;
n.count=0;
n.height=0;
n.dupes=0;
}
function remove_branch(uint value,uint left,uint right) private {
uint ipn=rightmost_leaf(left);
Node i=nodes[ipn];
uint dupes=i.dupes;
remove_helper(ipn);
Node n=nodes[value];
uint parent=n.parent;
Node p=nodes[parent];
uint height=n.height;
bool side=n.side;
uint count=n.count;
right=n.children[true];
left=n.children[false];
p.children[side]=ipn;
i.parent=parent;
i.side=side;
i.count=count+dupes-n.dupes;
i.height=height;
i.dupes=dupes;
if (left!=0) {
i.children[false]=left;
nodes[left].parent=ipn;
}
if (right!=0) {
i.children[true]=right;
nodes[right].parent=ipn;
}
zero_out(value);
update_counts(ipn);
}
function remove_helper(uint value) private {
Node n=nodes[value];
uint parent=n.parent;
bool side=n.side;
Node p=nodes[parent];
uint left=n.children[false];
uint right=n.children[true];
if ((left == 0) && (right == 0)) {
p.children[side]=0;
zero_out(value);
fix_parents(parent,side);
}
else if ((left !=0) && (right != 0)) {
remove_branch(value,left,right);
}
else {
uint child=left+right;
Node c=nodes[child];
p.children[side]=child;
c.parent=parent;
c.side=side;
zero_out(value);
fix_parents(parent,side);
}
}
function remove(uint value){
Node n=nodes[value];
if (value==0){
if (n.dupes==0)
return;
}
else{
if (n.count==0)
return;
}
if (n.dupes>0) {
n.dupes--;
if(value!=0)
n.count--;
fix_parents(n.parent,n.side);
}
else
remove_helper(value);
}
function rank(uint value) constant returns (uint smaller){
if(value!=0){
smaller=nodes[0].dupes;
uint cur=nodes[0].children[true];
Node cur_node=nodes[cur];
while(true){
if (cur<=value){
if(cur uint) children;
uint parent;
bool side;
uint height;
uint count;
uint dupes;
}
mapping(uint => Node) nodes;
}