<?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>MtasRBTree.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">MtasRBTree.java</span></div><h1>MtasRBTree.java</h1><pre class="source lang-java linenums">package mtas.codec.tree;
import java.util.HashMap;
import mtas.codec.tree.MtasTree;
import mtas.codec.tree.MtasRBTreeNode;
/**
* The Class MtasRBTree.
*/
<span class="pc bpc" id="L10" title="1 of 2 branches missed.">public class MtasRBTree extends MtasTree<MtasRBTreeNode> {</span>
/** The index. */
private final HashMap<String, MtasRBTreeNode> index;
/**
* Instantiates a new mtas RB tree.
*
* @param singlePoint the single point
* @param storePrefixId the store prefix id
*/
public MtasRBTree(boolean singlePoint, boolean storePrefixId) {
<span class="fc" id="L22"> super(singlePoint, storePrefixId);</span>
<span class="fc" id="L23"> index = new HashMap<>();</span>
<span class="fc" id="L24"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.MtasTree#addRangeEmpty(int, int)
*/
@Override
final protected void addRangeEmpty(int left, int right, int additionalId,
long additionalRef) {
<span class="nc" id="L34"> String key = left + "_" + right;</span>
<span class="nc bnc" id="L35" title="All 2 branches missed."> if (index.containsKey(key)) {</span>
// do nothing (empty...)
} else {
<span class="nc" id="L38"> root = addRange(root, left, right, additionalId, additionalRef, null,</span>
null);
<span class="nc" id="L40"> root.color = MtasRBTreeNode.BLACK;</span>
}
<span class="nc" id="L42"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.MtasTree#addSinglePoint(int, java.lang.Integer,
* java.lang.Long)
*/
@Override
final protected void addSinglePoint(int position, int additionalId,
long additionalRef, Integer id, Long ref) {
<span class="fc" id="L53"> addRange(position, position, additionalId, additionalRef, id, ref);</span>
<span class="fc" id="L54"> }</span>
/*
* (non-Javadoc)
*
* @see mtas.codec.tree.MtasTree#addRange(int, int, java.lang.Integer,
* java.lang.Long)
*/
@Override
final protected void addRange(int left, int right, int additionalId,
long additionalRef, Integer id, Long ref) {
<span class="fc" id="L65"> String key = left + "_" + right;</span>
<span class="fc bfc" id="L66" title="All 2 branches covered."> if (index.containsKey(key)) {</span>
<span class="fc" id="L67"> index.get(key).addIdAndRef(id, ref, additionalId, additionalRef);</span>
} else {
<span class="fc" id="L69"> root = addRange(root, left, right, additionalId, additionalRef, id, ref);</span>
<span class="fc" id="L70"> root.color = MtasRBTreeNode.BLACK;</span>
}
<span class="fc" id="L72"> }</span>
/**
* Adds the range.
*
* @param n the n
* @param left the left
* @param right the right
* @param additionalId the additional id
* @param additionalRef the additional ref
* @param id the id
* @param ref the ref
* @return the mtas RB tree node
*/
private MtasRBTreeNode addRange(MtasRBTreeNode n, Integer left, Integer right,
int additionalId, long additionalRef, Integer id, Long ref) {
<span class="fc" id="L88"> MtasRBTreeNode localN = n;</span>
<span class="fc bfc" id="L89" title="All 2 branches covered."> if (localN == null) {</span>
<span class="fc" id="L90"> String key = left.toString() + "_" + right.toString();</span>
<span class="fc" id="L91"> localN = new MtasRBTreeNode(left, right, MtasRBTreeNode.RED, 1);</span>
<span class="fc" id="L92"> localN.addIdAndRef(id, ref, additionalId, additionalRef);</span>
<span class="fc" id="L93"> index.put(key, localN);</span>
<span class="fc" id="L94"> } else {</span>
<span class="fc bfc" id="L95" title="All 2 branches covered."> if (left <= localN.left) {</span>
<span class="fc" id="L96"> localN.leftChild = addRange(localN.leftChild, left, right, additionalId,</span>
additionalRef, id, ref);
<span class="fc" id="L98"> updateMax(localN, localN.leftChild);</span>
} else {
<span class="fc" id="L100"> localN.rightChild = addRange(localN.rightChild, left, right,</span>
additionalId, additionalRef, id, ref);
<span class="fc" id="L102"> updateMax(localN, localN.rightChild);</span>
}
<span class="fc bfc" id="L104" title="All 4 branches covered."> if (isRed(localN.rightChild) && !isRed(localN.leftChild)) {</span>
<span class="fc" id="L105"> localN = rotateLeft(localN);</span>
}
<span class="fc bfc" id="L107" title="All 4 branches covered."> if (isRed(localN.leftChild) && isRed(localN.leftChild.leftChild)) {</span>
<span class="fc" id="L108"> localN = rotateRight(localN);</span>
}
<span class="fc bfc" id="L110" title="All 4 branches covered."> if (isRed(localN.leftChild) && isRed(localN.rightChild)) {</span>
<span class="fc" id="L111"> flipColors(localN);</span>
}
<span class="fc" id="L113"> localN.n = size(localN.leftChild) + size(localN.rightChild) + 1;</span>
}
<span class="fc" id="L115"> return localN;</span>
}
/**
* Update max.
*
* @param n the n
* @param c the c
*/
private void updateMax(MtasRBTreeNode n, MtasRBTreeNode c) {
<span class="pc bpc" id="L125" title="1 of 2 branches missed."> if (c != null) {</span>
<span class="fc bfc" id="L126" title="All 2 branches covered."> if (n.max < c.max) {</span>
<span class="fc" id="L127"> n.max = c.max;</span>
}
}
<span class="fc" id="L130"> }</span>
// make a left-leaning link lean to the right
/**
* Rotate right.
*
* @param n the n
* @return the mtas RB tree node
*/
private MtasRBTreeNode rotateRight(MtasRBTreeNode n) {
<span class="pc bpc" id="L140" title="3 of 6 branches missed."> assert (n != null) && isRed(n.leftChild);</span>
<span class="fc" id="L141"> MtasRBTreeNode x = n.leftChild;</span>
<span class="fc" id="L142"> n.leftChild = x.rightChild;</span>
<span class="fc" id="L143"> x.rightChild = n;</span>
<span class="fc" id="L144"> x.color = x.rightChild.color;</span>
<span class="fc" id="L145"> x.rightChild.color = MtasRBTreeNode.RED;</span>
<span class="fc" id="L146"> x.n = n.n;</span>
<span class="fc" id="L147"> n.n = size(n.leftChild) + size(n.rightChild) + 1;</span>
<span class="fc" id="L148"> setMax(n);</span>
<span class="fc" id="L149"> setMax(x);</span>
<span class="fc" id="L150"> return x;</span>
}
// make a right-leaning link lean to the left
/**
* Rotate left.
*
* @param n the n
* @return the mtas RB tree node
*/
private MtasRBTreeNode rotateLeft(MtasRBTreeNode n) {
<span class="pc bpc" id="L161" title="3 of 6 branches missed."> assert (n != null) && isRed(n.rightChild);</span>
<span class="fc" id="L162"> MtasRBTreeNode x = n.rightChild;</span>
<span class="fc" id="L163"> n.rightChild = x.leftChild;</span>
<span class="fc" id="L164"> x.leftChild = n;</span>
<span class="fc" id="L165"> x.color = x.leftChild.color;</span>
<span class="fc" id="L166"> x.leftChild.color = MtasRBTreeNode.RED;</span>
<span class="fc" id="L167"> x.n = n.n;</span>
<span class="fc" id="L168"> n.n = size(n.leftChild) + size(n.rightChild) + 1;</span>
<span class="fc" id="L169"> setMax(n);</span>
<span class="fc" id="L170"> setMax(x);</span>
<span class="fc" id="L171"> return x;</span>
}
// flip the colors of a node and its two children
/**
* Flip colors.
*
* @param n the n
*/
private void flipColors(MtasRBTreeNode n) {
// n must have opposite color of its two children
<span class="pc bpc" id="L182" title="4 of 8 branches missed."> assert (n != null) && (n.leftChild != null) && (n.rightChild != null);</span>
<span class="pc bpc" id="L183" title="4 of 8 branches missed."> assert (!isRed(n) && isRed(n.leftChild) && isRed(n.rightChild))</span>
<span class="nc bnc" id="L184" title="All 6 branches missed."> || (isRed(n) && !isRed(n.leftChild) && !isRed(n.rightChild));</span>
<span class="fc" id="L185"> n.color ^= 1;</span>
<span class="fc" id="L186"> n.leftChild.color ^= 1;</span>
<span class="fc" id="L187"> n.rightChild.color ^= 1;</span>
<span class="fc" id="L188"> }</span>
/**
* Checks if is red.
*
* @param n the n
* @return true, if is red
*/
private boolean isRed(MtasRBTreeNode n) {
<span class="fc bfc" id="L197" title="All 2 branches covered."> if (n == null) {</span>
<span class="fc" id="L198"> return false;</span>
}
<span class="fc bfc" id="L200" title="All 2 branches covered."> return n.color == MtasRBTreeNode.RED;</span>
}
/**
* Size.
*
* @param n the n
* @return the int
*/
private int size(MtasRBTreeNode n) {
<span class="fc bfc" id="L210" title="All 2 branches covered."> if (n == null)</span>
<span class="fc" id="L211"> return 0;</span>
<span class="fc" id="L212"> return n.n;</span>
}
/**
* Sets the max.
*
* @param n the new max
*/
private void setMax(MtasRBTreeNode n) {
<span class="fc" id="L221"> n.max = n.right;</span>
<span class="fc bfc" id="L222" title="All 2 branches covered."> if (n.leftChild != null) {</span>
<span class="fc" id="L223"> n.max = Math.max(n.max, n.leftChild.max);</span>
}
<span class="fc bfc" id="L225" title="All 2 branches covered."> if (n.rightChild != null) {</span>
<span class="fc" id="L226"> n.max = Math.max(n.max, n.rightChild.max);</span>
}
<span class="fc" id="L228"> }</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>