/ 
Bio-EnsEMBL-112.0_56
River stage zero No dependents
/ Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node

LICENSE

Copyright [1999-2015] Wellcome Trust Sanger Institute and the EMBL-European Bioinformatics Institute Copyright [2016-2024] EMBL-European Bioinformatics Institute

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

CONTACT

Please email comments or questions to the public Ensembl
developers list at <http://lists.ensembl.org/mailman/listinfo/dev>.

Questions may also be sent to the Ensembl help desk at
<http://www.ensembl.org/Help/Contact>.

NAME

Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node

DESCRIPTION

Represents a node in the mutable interval tree pure perl implementation.

METHODS

METHODS

new

Arg [1]     : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::PP
              The tree to which the node belongs
Arg [2]     : Bio::EnsEMBL::Utils::Interval
Description : Constructor. Creates a new mutable tree instance node
              associated with the given interval
Returntype  : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node
Exceptions  : none
Caller      : general

tree

Arg []      : none
Example     : my $tree = $node->root;
Description : Returns the tree to which the node belongs
Returntype  : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::PP
Exceptions  : none
Caller      : general

key

Arg []      : none
Example     : my $key = $node->key;
Description : Returns the key associated with the node
Returntype  : scalar
Exceptions  : none
Caller      : general

intervals

Arg []      : none
Example     : my $intervals = $node->intervals;
Description : Returns the intervals associated with the node
Returntype  : Arrayref of Bio::EnsEMBL::Utils::Interval
Exceptions  : none
Caller      : general

add_interval

Arg []      : none
Description : Add an interval to the node's set of intervals
Returntype  : none
Exceptions  : none
Caller      : general

parent

Arg []      : none
Description : Return the parent of the node in the tree
Returntype  : none
Exceptions  : none
Caller      : general

height

Arg []      : none
Description : Return the height of the node
Returntype  : scalar, positive or 0
Exceptions  : none
Caller      : general

left

Arg []      : none
Description : Return the node's left child
Returntype  : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node
Exceptions  : none
Caller      : general
Arg []      : none
Description : Return the node's right child
Returntype  : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node
Exceptions  : none
Caller      : general
Arg [1]     : Bio::EnsEMBL::Utils::Interval
              The interval to search for overlaps in the tree
Description : Search the node and its successors for overlapping
              intervals with the query
Returntype  : Arrayref of Bio::EnsEMBL::Utils::Interval
Exceptions  : none
Caller      : general

search_by_key

Arg [1]     : scalar, $key
              The key to search the node for
Description : Searches for a node by a 'key' value
Returntype  : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node
Exceptions  : none
Caller      : general

insert

Arg [1]     : Bio::EnsEMBL::Utils::Interval
              The interval to insert
Description : Insert an interval in the node or in its successors
Returntype  : none
Exceptions  : none
Caller      : general

remove

Arg [1]     : Bio::EnsEMBL::Utils::Tree::Interval::Mutable::Node
              The node to remove from the tree
Description : Remove a node from the tree
Returntype  : none
Exceptions  : none
Caller      : general

PRIVATE METHODS

_height

Not a method since code could invoke method on undefined instances, e.g. _rebalance

_lowest

Returns the 'smallest' node in the tree

_rebalance

Rebalances the tree if the height value between two nodes of the same parent is greater than two. There are 4 cases that can happen:

Left-Left case: z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2

Left-Right case: z z x / \ / \ / \ y T4 Left Rotate (y) x T4 Right Rotate(z) y z / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ T1 x y T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2

Right-Right case: z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4

Right-Left case: z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z y / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ x T4 T2 y T1 T2 T3 T4 / \ / \ T2 T3 T3 T4