<?xml version="1.0" encoding="UTF-8"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml" lang="en"><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8"/><link rel="stylesheet" href="../jacoco-resources/report.css" type="text/css"/><link rel="shortcut icon" href="../jacoco-resources/report.gif" type="image/gif"/><title>IntervalRBTree.java</title><link rel="stylesheet" href="../jacoco-resources/prettify.css" type="text/css"/><script type="text/javascript" src="../jacoco-resources/prettify.js"></script></head><body onload="window['PR_TAB_WIDTH']=4;prettyPrint()"><div class="breadcrumb" id="breadcrumb"><span class="info"><a href="../jacoco-sessions.html" class="el_session">Sessions</a></span><a href="../index.html" class="el_report">MTAS</a> > <a href="index.source.html" class="el_package">mtas.codec.tree</a> > <span class="el_source">IntervalRBTree.java</span></div><h1>IntervalRBTree.java</h1><pre class="source lang-java linenums">package mtas.codec.tree;
import java.util.ArrayList;
import java.util.HashMap;
import mtas.codec.util.CodecSearchTree.MtasTreeHit;
/**
* The Class IntervalRBTree.
*
* @param <T> the generic type
*/
<span class="pc bpc" id="L13" title="1 of 2 branches missed.">public class IntervalRBTree<T> extends IntervalTree<T, IntervalRBTreeNode<T>> {</span>
/** The index. */
private final HashMap<String, IntervalRBTreeNode<T>> index;
/**
* Instantiates a new interval RB tree.
*/
public IntervalRBTree() {
<span class="fc" id="L22"> super();</span>
<span class="fc" id="L23"> index = new HashMap<>();</span>
<span class="fc" id="L24"> }</span>
/**
* Instantiates a new interval RB tree.
*
* @param positionsHits the positions hits
*/
public IntervalRBTree(ArrayList<IntervalTreeNodeData<T>> positionsHits) {
<span class="fc" id="L32"> this();</span>
<span class="fc bfc" id="L33" title="All 2 branches covered."> for (IntervalTreeNodeData<T> positionsHit : positionsHits) {</span>
<span class="fc" id="L34"> addRange(positionsHit.start, positionsHit.end, positionsHit.list);</span>
<span class="fc" id="L35"> }</span>
<span class="fc" id="L36"> close();</span>
<span class="fc" id="L37"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.IntervalTree#addRangeEmpty(int, int)
*/
@Override
final protected void addRangeEmpty(int left, int right) {
<span class="nc" id="L46"> String key = left + "_" + right;</span>
<span class="nc bnc" id="L47" title="All 2 branches missed."> if (index.containsKey(key)) {</span>
// do nothing (empty...)
} else {
<span class="nc" id="L50"> root = addRange(root, left, right, null);</span>
<span class="nc" id="L51"> root.color = IntervalRBTreeNode.BLACK;</span>
}
<span class="nc" id="L53"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.IntervalTree#addSinglePoint(int, java.util.ArrayList)
*/
@Override
final protected void addSinglePoint(int position,
ArrayList<MtasTreeHit<T>> list) {
<span class="nc" id="L63"> addRange(position, position, list);</span>
<span class="nc" id="L64"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.IntervalTree#addRange(int, int, java.util.ArrayList)
*/
@Override
final protected void addRange(int left, int right,
ArrayList<MtasTreeHit<T>> list) {
<span class="fc" id="L74"> String key = left + "_" + right;</span>
<span class="pc bpc" id="L75" title="1 of 2 branches missed."> if (index.containsKey(key)) {</span>
<span class="nc" id="L76"> index.get(key).addList(list);</span>
} else {
<span class="fc" id="L78"> root = addRange(root, left, right, list);</span>
<span class="fc" id="L79"> root.color = IntervalRBTreeNode.BLACK;</span>
}
<span class="fc" id="L81"> }</span>
/**
* Adds the range.
*
* @param n the n
* @param left the left
* @param right the right
* @param list the list
* @return the interval RB tree node
*/
private IntervalRBTreeNode<T> addRange(IntervalRBTreeNode<T> n, Integer left,
Integer right, ArrayList<MtasTreeHit<T>> list) {
<span class="fc" id="L94"> IntervalRBTreeNode<T> localN = n;</span>
<span class="fc bfc" id="L95" title="All 2 branches covered."> if (localN == null) {</span>
<span class="fc" id="L96"> String key = left.toString() + "_" + right.toString();</span>
<span class="fc" id="L97"> localN = new IntervalRBTreeNode<>(left, right, IntervalRBTreeNode.RED, 1);</span>
<span class="fc" id="L98"> localN.addList(list);</span>
<span class="fc" id="L99"> index.put(key, localN);</span>
<span class="fc" id="L100"> } else {</span>
<span class="pc bpc" id="L101" title="1 of 2 branches missed."> if (left <= localN.left) {</span>
<span class="nc" id="L102"> localN.leftChild = addRange(localN.leftChild, left, right, list);</span>
<span class="nc" id="L103"> updateMaxMin(localN, localN.leftChild);</span>
} else {
<span class="fc" id="L105"> localN.rightChild = addRange(localN.rightChild, left, right, list);</span>
<span class="fc" id="L106"> updateMaxMin(localN, localN.rightChild);</span>
}
<span class="fc bfc" id="L108" title="All 4 branches covered."> if (isRed(localN.rightChild) && !isRed(localN.leftChild)) {</span>
<span class="fc" id="L109"> localN = rotateLeft(localN);</span>
}
<span class="pc bpc" id="L111" title="1 of 4 branches missed."> if (isRed(localN.leftChild) && isRed(localN.leftChild.leftChild)) {</span>
<span class="nc" id="L112"> localN = rotateRight(localN);</span>
}
<span class="fc bfc" id="L114" title="All 4 branches covered."> if (isRed(localN.leftChild) && isRed(localN.rightChild)) {</span>
<span class="fc" id="L115"> flipColors(localN);</span>
}
<span class="fc" id="L117"> localN.n = size(localN.leftChild) + size(localN.rightChild) + 1;</span>
}
<span class="fc" id="L119"> return localN;</span>
}
/**
* Update max min.
*
* @param n the n
* @param c the c
*/
private void updateMaxMin(IntervalRBTreeNode<T> n, IntervalRBTreeNode<T> c) {
<span class="pc bpc" id="L129" title="1 of 2 branches missed."> if (c != null) {</span>
<span class="pc bpc" id="L130" title="1 of 2 branches missed."> if (n.max < c.max) {</span>
<span class="fc" id="L131"> n.max = c.max;</span>
}
<span class="pc bpc" id="L133" title="1 of 2 branches missed."> if (n.min > c.min) {</span>
<span class="nc" id="L134"> n.min = c.min;</span>
}
}
<span class="fc" id="L137"> }</span>
// make a left-leaning link lean to the right
/**
* Rotate right.
*
* @param n the n
* @return the interval RB tree node
*/
private IntervalRBTreeNode<T> rotateRight(IntervalRBTreeNode<T> n) {
<span class="nc bnc" id="L147" title="All 6 branches missed."> assert (n != null) && isRed(n.leftChild);</span>
<span class="nc" id="L148"> IntervalRBTreeNode<T> x = n.leftChild;</span>
<span class="nc" id="L149"> n.leftChild = x.rightChild;</span>
<span class="nc" id="L150"> x.rightChild = n;</span>
<span class="nc" id="L151"> x.color = x.rightChild.color;</span>
<span class="nc" id="L152"> x.rightChild.color = IntervalRBTreeNode.RED;</span>
<span class="nc" id="L153"> x.n = n.n;</span>
<span class="nc" id="L154"> n.n = size(n.leftChild) + size(n.rightChild) + 1;</span>
<span class="nc" id="L155"> setMaxMin(n);</span>
<span class="nc" id="L156"> setMaxMin(x);</span>
<span class="nc" id="L157"> return x;</span>
}
// make a right-leaning link lean to the left
/**
* Rotate left.
*
* @param n the n
* @return the interval RB tree node
*/
private IntervalRBTreeNode<T> rotateLeft(IntervalRBTreeNode<T> n) {
<span class="pc bpc" id="L168" title="3 of 6 branches missed."> assert (n != null) && isRed(n.rightChild);</span>
<span class="fc" id="L169"> IntervalRBTreeNode<T> x = n.rightChild;</span>
<span class="fc" id="L170"> n.rightChild = x.leftChild;</span>
<span class="fc" id="L171"> x.leftChild = n;</span>
<span class="fc" id="L172"> x.color = x.leftChild.color;</span>
<span class="fc" id="L173"> x.leftChild.color = IntervalRBTreeNode.RED;</span>
<span class="fc" id="L174"> x.n = n.n;</span>
<span class="fc" id="L175"> n.n = size(n.leftChild) + size(n.rightChild) + 1;</span>
<span class="fc" id="L176"> setMaxMin(n);</span>
<span class="fc" id="L177"> setMaxMin(x);</span>
<span class="fc" id="L178"> return x;</span>
}
// flip the colors of a node and its two children
/**
* Flip colors.
*
* @param n the n
*/
private void flipColors(IntervalRBTreeNode<T> n) {
// n must have opposite color of its two children
<span class="pc bpc" id="L189" title="4 of 8 branches missed."> assert (n != null) && (n.leftChild != null) && (n.rightChild != null);</span>
<span class="pc bpc" id="L190" title="4 of 8 branches missed."> assert (!isRed(n) && isRed(n.leftChild) && isRed(n.rightChild))</span>
<span class="nc bnc" id="L191" title="All 6 branches missed."> || (isRed(n) && !isRed(n.leftChild) && !isRed(n.rightChild));</span>
<span class="fc" id="L192"> n.color ^= 1;</span>
<span class="fc" id="L193"> n.leftChild.color ^= 1;</span>
<span class="fc" id="L194"> n.rightChild.color ^= 1;</span>
<span class="fc" id="L195"> }</span>
/**
* Checks if is red.
*
* @param n the n
* @return true, if is red
*/
private boolean isRed(IntervalRBTreeNode<T> n) {
<span class="fc bfc" id="L204" title="All 2 branches covered."> if (n == null) {</span>
<span class="fc" id="L205"> return false;</span>
}
<span class="fc bfc" id="L207" title="All 2 branches covered."> return n.color == IntervalRBTreeNode.RED;</span>
}
/**
* Size.
*
* @param n the n
* @return the int
*/
private int size(IntervalRBTreeNode<T> n) {
<span class="fc bfc" id="L217" title="All 2 branches covered."> if (n == null)</span>
<span class="fc" id="L218"> return 0;</span>
<span class="fc" id="L219"> return n.n;</span>
}
/**
* Sets the max min.
*
* @param n the new max min
*/
private void setMaxMin(IntervalRBTreeNode<T> n) {
<span class="fc" id="L228"> n.min = n.left;</span>
<span class="fc" id="L229"> n.max = n.right;</span>
<span class="fc bfc" id="L230" title="All 2 branches covered."> if (n.leftChild != null) {</span>
<span class="fc" id="L231"> n.min = Math.min(n.min, n.leftChild.min);</span>
<span class="fc" id="L232"> n.max = Math.max(n.max, n.leftChild.max);</span>
}
<span class="fc bfc" id="L234" title="All 2 branches covered."> if (n.rightChild != null) {</span>
<span class="fc" id="L235"> n.min = Math.min(n.min, n.rightChild.min);</span>
<span class="fc" id="L236"> n.max = Math.max(n.max, n.rightChild.max);</span>
}
<span class="fc" id="L238"> }</span>
}
</pre><div class="footer"><span class="right">Created with <a href="http://www.jacoco.org/jacoco">JaCoCo</a> 0.7.9.201702052155</span></div></body></html>