$Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node::VERSION
=
'112.0_55'
;
$Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node::VERSION
=
'112.055'
;
sub
new {
my
$caller
=
shift
;
my
$class
=
ref
(
$caller
) ||
$caller
;
my
(
$tree
,
$interval
) =
@_
;
throw
'Node constructor takes (tree, interval) as arguments'
unless
$tree
and
$interval
;
my
$self
=
bless
({
tree
=>
$tree
,
intervals
=> [
$interval
],
key
=>
$interval
->start,
max
=>
$interval
->end,
parent
=>
undef
,
height
=> 0,
left
=>
undef
,
right
=>
undef
},
$class
);
return
$self
;
}
sub
tree {
return
shift
->{tree};
}
sub
key {
my
$self
=
shift
;
$self
->{key} =
shift
if
(
@_
);
return
$self
->{key};
}
sub
intervals {
return
shift
->{intervals};
}
sub
add_interval {
push
@{
shift
->{intervals}},
shift
;
}
sub
parent {
my
$self
=
shift
;
if
(
@_
) {
$self
->{parent} =
shift
;
weaken(
$self
->{parent});
}
return
$self
->{parent};
}
sub
height {
my
$self
=
shift
;
$self
->{height} =
shift
if
(
@_
);
return
$self
->{height};
}
sub
left {
my
$self
=
shift
;
$self
->{left} =
shift
if
(
@_
);
return
$self
->{left};
}
sub
right {
my
$self
=
shift
;
$self
->{right} =
shift
if
(
@_
);
return
$self
->{right};
}
sub
search {
my
(
$self
,
$i
) =
@_
;
return
[]
if
$i
->start >
$self
->{max};
my
$results
= [];
if
(
$self
->left and
$self
->left->{max} >=
$i
->start) {
push
@{
$results
}, @{
$self
->left->search(
$i
)};
}
push
@{
$results
}, @{
$self
->_overlapping_intervals(
$i
)};
return
$results
if
$i
->end <
$self
->key;
push
@{
$results
}, @{
$self
->right->search(
$i
)}
if
$self
->right;
return
$results
;
}
sub
search_by_key {
my
(
$self
,
$key
) =
@_
;
if
(
$self
->key ==
$key
) {
return
$self
;
}
elsif
(
$key
<
$self
->key) {
return
$self
->left->search_by_key(
$key
)
if
$self
->left;
}
else
{
return
$self
->right->search_by_key(
$key
)
if
$self
->right;
}
}
sub
insert {
my
(
$self
,
$i
) =
@_
;
if
(
$i
->start <
$self
->key) {
unless
(
defined
$self
->left) {
$self
->left(Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node->new(
$self
->tree,
$i
));
$self
->left->parent(
$self
);
}
else
{
$self
->left->insert(
$i
);
}
}
else
{
unless
(
defined
$self
->right) {
$self
->right(Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node->new(
$self
->tree,
$i
));
$self
->right->parent(
$self
);
}
else
{
$self
->right->insert(
$i
);
}
}
$self
->{max} =
$i
->end
if
$self
->{max} <
$i
->end;
$self
->_update_height;
$self
->_rebalance;
}
sub
remove {
my
(
$self
,
$node
) =
@_
;
return
unless
$node
;
my
$parent
=
$self
->parent;
if
(
$node
->key <
$self
->key) {
return
$self
->left->remove(
$node
)
if
$self
->left;
return
;
}
elsif
(
$node
->key >
$self
->key) {
return
$self
->right->remove(
$node
)
if
$self
->right;
return
;
}
else
{
if
(
$self
->left and
$self
->right) {
my
$lowest
=
$self
->right->_lowest;
$self
->key(
$lowest
->key);
$self
->{intervals} =
$lowest
->{intervals};
return
$self
->right->remove(
$self
);
}
elsif
(
$parent
->left ==
$self
) {
if
(
$self
->right) {
$parent
->left(
$self
->right);
$self
->right->parent(
$parent
);
}
else
{
$parent
->left(
$self
->left);
$self
->left->parent(
$parent
)
if
$self
->left
}
$parent
->_update_parents_max;
$parent
->_update_height;
$parent
->_rebalance;
return
$self
;
}
elsif
(
$parent
->right ==
$self
) {
if
(
$self
->right) {
$parent
->right(
$self
->right);
$self
->right->parent(
$parent
);
}
else
{
$parent
->right(
$self
->left);
$self
->left->parent(
$parent
)
if
$self
->left;
}
$parent
->_update_parents_max;
$parent
->_update_height;
$parent
->_rebalance;
return
$self
;
}
}
}
sub
_height {
my
$node
=
shift
;
return
-1
unless
$node
;
return
$node
->height;
}
sub
_lowest {
my
$self
=
shift
;
return
$self
unless
$self
->left;
return
$self
->left->_lowest;
}
sub
_highest_end {
my
$self
=
shift
;
my
$high
=
$self
->{intervals}[0]->end;
map
{
$high
=
$_
->end
if
$high
<
$_
->end } @{
$self
->{intervals}};
return
$high
;
}
sub
_update_height {
my
$self
=
shift
;
$self
->height(List::Util::max
$self
->left?
$self
->left->height:0,
$self
->right?
$self
->right->height:0 + 1);
}
sub
_update_parents_max {
my
$self
=
shift
;
my
$high
=
$self
->_highest_end;
if
(
$self
->left and
$self
->right) {
$self
->{max} = max
$self
->left->{max},
$self
->right-{max},
$high
;
}
elsif
(
$self
->left and !
$self
->right) {
$self
->{max} = max
$self
->left->{max},
$high
;
}
elsif
(!
$self
->left and
$self
->right) {
$self
->{max} = max
$self
->right->{max},
$high
;
}
else
{
$self
->{max} =
$high
;
}
$self
->parent->_update_parents_max
if
$self
->parent;
}
sub
_rebalance {
my
$self
=
shift
;
my
(
$left
,
$right
) = (
$self
->left,
$self
->right);
if
(_height(
$left
) - _height(
$right
) >= 2) {
if
(_height(
$left
->left) >= _height(
$left
->right)) {
$self
->_right_rotate;
$self
->_update_max_right_rotate;
}
else
{
$left
->_left_rotate;
$self
->_right_rotate;
$self
->_update_max_right_rotate;
}
}
elsif
(_height(
$right
) - _height(
$left
) >= 2) {
if
(_height(
$right
->right) >= _height(
$right
->left)) {
$self
->_left_rotate;
$self
->_update_max_left_rotate;
}
else
{
$right
->_right_rotate;
$self
->_left_rotate;
$self
->_update_max_left_rotate;
}
}
}
sub
_left_rotate {
my
$self
=
shift
;
my
$right
=
$self
->right;
$right
->parent(
$self
->parent);
unless
(
defined
$right
->parent) {
$self
->tree->root(
$right
);
}
else
{
if
(
$right
->parent->left ==
$self
) {
$right
->parent->left(
$right
);
}
elsif
(
$right
->parent->right ==
$self
) {
$right
->parent->right(
$right
);
}
}
$self
->right(
$right
->left);
$self
->right->parent(
$self
)
if
$self
->right;
$right
->left(
$self
);
$self
->parent(
$right
);
$self
->_update_height;
$right
->_update_height;
}
sub
_update_max_left_rotate {
my
$self
=
shift
;
my
$parent
=
$self
->parent;
my
$parent_right
=
$parent
->right;
if
(
$parent_right
) {
my
$parent_right_high
=
$parent_right
->_highest_end;
if
(!
$parent_right
->left and
$parent_right
->right) {
$parent_right
->{max} = max
$parent_right_high
,
$parent_right
->right->{max};
}
elsif
(
$parent_right
->left and !
$parent_right
->right) {
$parent_right
->{max} = max
$parent_right_high
,
$parent_right
->left->{max};
}
elsif
(!
$parent_right
->left and !
$parent_right
->right) {
$parent_right
->{max} =
$parent_right_high
;
}
else
{
$parent_right
->{max} = max
$parent_right_high
,
$parent_right
->left->{max},
$parent_right
->right->{max};
}
}
my
$high
=
$self
->_highest_end;
if
(!
$self
->left and
$self
->right) {
$self
->{max} = max
$high
,
$self
->right->{max};
}
elsif
(
$self
->left and !
$self
->right) {
$self
->{max} = max
$high
,
$self
->left->{max};
}
elsif
(!
$self
->left and !
$self
->right) {
$self
->{max} =
$high
;
}
else
{
$self
->{max} = max
$high
,
$self
->left->{max},
$self
->right->{max};
}
$parent
->{max} = max
$parent
->left?
$parent
->left->{max}:0,
$parent
->right?
$parent
->right->{max}:0,
$parent
->_highest_end
if
$parent
;
}
sub
_right_rotate {
my
$self
=
shift
;
my
$left
=
$self
->left;
$left
->parent(
$self
->parent);
unless
(
defined
$left
->parent) {
$self
->tree->root(
$left
);
}
else
{
if
(
$left
->parent->left ==
$self
) {
$left
->parent->left(
$left
);
}
elsif
(
$left
->parent->right ==
$self
) {
$left
->parent->right(
$left
);
}
}
$self
->left(
$left
->right);
$self
->left->parent(
$self
)
if
$self
->left;
$left
->right(
$self
);
$self
->parent(
$left
);
$self
->_update_height;
$left
->_update_height;
}
sub
_update_max_right_rotate {
my
$self
=
shift
;
my
$parent
=
$self
->parent;
my
$parent_left
=
$parent
->left;
if
(
$parent_left
) {
my
$parent_left_high
=
$parent_left
->_highest_end;
if
(!
$parent_left
->left and
$parent_left
->right) {
$parent_left
->{max} = max
$parent_left_high
,
$parent_left
->right->{max};
}
elsif
(
$parent_left
->left and !
$parent_left
->right) {
$parent_left
->{max} = max
$parent_left_high
,
$parent_left
->left->{max};
}
elsif
(!
$parent_left
->left and !
$parent_left
->right) {
$parent_left
->{max} =
$parent_left_high
;
}
else
{
$parent_left
->{max} = max
$parent_left_high
,
$parent_left
->left->{max},
$parent_left
->right->{max};
}
}
my
$high
=
$self
->_highest_end;
if
(!
$self
->left and
$self
->right) {
$self
->{max} = max
$high
,
$self
->right->{max};
}
elsif
(
$self
->left and !
$self
->right) {
$self
->{max} = max
$high
,
$self
->left->{max};
}
elsif
(!
$self
->left and !
$self
->right) {
$self
->{max} =
$high
;
}
else
{
$self
->{max} = max
$high
,
$self
->left->{max},
$self
->right->{max};
}
$parent
->{max} = max
$parent
->left?
$parent
->left->{max}:0,
$parent
->right?
$parent
->right->{max}:0,
$parent
->_highest_end
if
$parent
;
}
sub
_overlapping_intervals {
my
(
$self
,
$i
) =
@_
;
my
$results
= [];
if
(
$self
->key <=
$i
->end and
$i
->start <=
$self
->_highest_end) {
map
{
push
@{
$results
},
$_
if
$i
->start <=
$_
->end } @{
$self
->{intervals}}
}
return
$results
;
}
1;