The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Bio-EnsEMBL-112.0.0_58
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