MtasRBTree.java.html
10.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<?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>