Ranks
Rank tests start from rank-transformed data.
- Let \(Y_1, \ldots, Y_n\).
- In the absence of ties \[R_i=R(Y_i) = \#\{Y_j: Y_j\leq Y_i; j=1,\ldots, n\}\]
- Smallest observation has rank 1, second smallest rank 2, … , largest observation gets rank \(n\)
[1] 244 206 242 278 236 188 212 186 198 160
[1] 9 5 8 10 7 3 6 2 4 1
Ties
Sometimes ties occur: two observations with identical values
withTies <- c(403, 507, 507, 610, 651, 651, 651, 830, 900)
rank(withTies)
[1] 1.0 2.5 2.5 4.0 6.0 6.0 6.0 8.0 9.0
Ties: 507 occurs twice, 651 occurs 3 times
If ties occur midranks are used.
midrank of observation \(Y_i\) becomes \[\begin{eqnarray*}
R_i &=& \frac{ \#\{Y_j: Y_j\leq Y_i\} + ( \#\{Y_j: Y_j < Y_i\} +1)}{2}.
\end{eqnarray*}\]
Ranks of pooled sample
- Let \(Y_{ij}\), \(i=1,\ldots, n_j\) be observations from two treatment groups \(j=1,2\).
- They can also be represented by \(Z_1,\ldots, Z_n\) (\(n=n_1+n_2\)), the outcomes of the pooled sample
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
group "1" "1" "1" "1" "1" "2" "2" "2" "2" "2"
cholest "244" "206" "242" "278" "236" "188" "212" "186" "198" "160"
[1] 244 206 242 278 236 188 212 186 198 160
[1] 9 5 8 10 7 3 6 2 4 1
Wilcoxon-Mann-Whitney Test
Simultaneously developed by Wilcoxon, and, Mann and Whitney: Wilcoxon-Mann-Whitney, Wilcoxon rank sum test or Mann-Whitney U test
Hypotheses
Under \(H_0\) the distributions of the two groups are equal \[H_0: f_1=f_2\]
Under the alternative \(H_1\) the distributions differ in location \[H_1: \mu_1\neq \mu_2\]
\(H_1\) assumes location-shift, we will relax this assumption later on.
Test statistic
Classic T-test: difference in sample means \(\bar{Y}_1-\bar{Y}_2\).
Here: Difference in sample means based on rank transformed data
Ranks based on the pooled sample (upon joining the observations from the two groups): \(R_{ij}=R(Y_{ij})\) is de rank of observation \(Y_{ij}\) in the pooled sample.
\[
T = \frac{1}{n_1}\sum_{i=1}^{n_1} R(Y_{i1}) - \frac{1}{n_2}\sum_{i=1}^{n_2} R(Y_{i2}) .
\]
Under \(H_0\) we expect the average rank of the first group to be close to that of the second group so \(T\) is close to zero.
Under \(H_1\) we expect the mean ranks to differ so that \(T\) deviates from zero.
It is sufficient to only calculate \[S_1=\sum_{i=1}^{n_1} R(Y_{i1})\].
\(S_1\) is the sum of the ranks of the first group: rank sum test.
This holds because \[
S_1+S_2 = \text{sum of all ranks} = 1+2+\cdots + n=\frac{1}{2}n(n+1).
\]
\(S_1\) (or \(S_2\)) is a good test statistic
Use permutations to determine the exact permutation distribution. (Permute the ranks between the groups)
For a given \(n\) and no ties the rank transformed data is always \[1, 2, \ldots, n\]
For given \(n_1\) en \(n_2\) the permutation distribution is always the same!
With current computing power this is not so important any more.
Standardized statistic
Often the standardized test statistic is used \[
T = \frac{S_1-\text{E}_{0}\left[S_1\right]}{\sqrt{\text{Var}_{0}\left[S_1\right]}},
\]
with \(\text{E}_{0}\left[S_1\right]\) and \(\text{Var}_{0}\left[S_1\right]\) the expect mean and variance of S1 under \(H_0\).
Under \(H_0\) \[
\text{E}_{0}\left[S_1\right]= \frac{1}{2}n_1(n+1) \;\;\;\;\text{ en }\;\;\;\; \text{Var}_{0}\left[S_1\right]=\frac{1}{12}n_1n_2(n+1).
\]
Under \(H_0\) and when \(\min(n_1,n_2)\rightarrow \infty\) \[
T = \frac{S_1-\text{E}_{0}\left[S_1\right]}{\sqrt{\text{Var}_{0}\left[S_1\right]}} \rightarrow N(0,1).
\]
Asymptotically the standardised statistic follows a standard normal distribution!
Cholesterol example
We illustrate the result for the cholesterol example using the R function wilcox.test
.
wilcox.test(cholest ~ group, data = chol)
Wilcoxon rank sum exact test
data: cholest by group
W = 24, p-value = 0.01587
alternative hypothesis: true location shift is not equal to 0
S1 <- sum(rank(chol$cholest)[chol$group == 1])
S1
[1] 39
S2 <- sum(rank(chol$cholest)[chol$group == 2])
S2
[1] 16
- Where does \(W=\) 24 comes from?
Mann and Whitney test
Mann and Whitney test in absence of ties: \[
U_1 = \sum_{i=1}^{n_1}\sum_{k=1}^{n_2} \text{I}\left\{Y_{i1}\geq Y_{k2}\right\}.
\]
with \(\text{I}\left\{.\right\}\) an indicator that equals 1 if the expression is true and is zero otherwise.
U counts how many times an observation of the first group is larger or equal to an observation from the second group.
y1 <- subset(chol, group == 1)$cholest
y2 <- subset(chol, group == 2)$cholest
u1Hlp <- sapply(y1, function(y1i, y2) {
y1i >= y2
}, y2 = y2)
colnames(u1Hlp) <- y1
rownames(u1Hlp) <- y2
244 206 242 278 236
188 TRUE TRUE TRUE TRUE TRUE
212 TRUE FALSE TRUE TRUE TRUE
186 TRUE TRUE TRUE TRUE TRUE
198 TRUE TRUE TRUE TRUE TRUE
160 TRUE TRUE TRUE TRUE TRUE
[1] 24
It can be shown that \(U_1 = S_1 - \frac{1}{2}n_1(n_1+1).\)
S1 - nGroups[1] * (nGroups[1] + 1) / 2
1
24
- \(U_1\) en \(S_1\) contain the same information
- \(U_1\) is also a rank statistic, and
- Exact test based on \(U_1\) and \(S_1\) are equivalent.
Probabilistic index
- \(U_1\) has a better interpretation feature
- Let \(Y_j\) a random observation from group \(j\) (\(j=1,2\)). Then \[\begin{eqnarray*}
\frac{1}{n_1n_2}\text{E}\left[U_1\right]
&=& \text{P}\left[Y_1 \geq Y_2\right].
\end{eqnarray*}\]
So we can estimate the probability by calculating the mean of all indicator variable values \(\text{I}\left\{Y_{i1}\geq Y_{k2}\right\}\). Note, that we did \(n_1 \times n_2\) comparisons
[1] 0.96
U1 / (nGroups[1] * nGroups[2])
1
0.96
Probability \(\text{P}\left[Y_1 \geq Y_2\right]\) is referred to as the probabilistic index.
It is the probability that a random observation of the first group is larger or equal than a random observation of the second group
If \(H_0\) holds \(\text{P}\left[Y_1 \geq Y_2\right]=\frac{1}{2}\).
R function wilcox.test
does not return the Wilcoxon rank sum statistic. It returns the Mann-Whitney statistic \(U_1\).
Lets revisit the result
wTest <- wilcox.test(cholest ~ group, data = chol)
wTest
Wilcoxon rank sum exact test
data: cholest by group
W = 24, p-value = 0.01587
alternative hypothesis: true location shift is not equal to 0
[1] 24
probInd <- wTest$statistic / prod(nGroups)
probInd
W
0.96
Because \(p=\) 0.0159 \(<0.05\) we conclude at the \(5\%\) significance level that the mean cholesterol level of hart patients is larger then that of healthy subjects.
- Note that we have assumed that the location-shift model is valid in this conclusion.
- We also know that higher cholesterol level are more likely for hart patients then for healthy subjects and this probability is \(U1/(n_1\times n_2)=\) 96%.
- We should assess the location shift assumption. But this is not possible with only 5 observations.
Without the location-shift assumption the conclusion in terms of the probabilistic index remains valid!
- So when we do not assume location shift we test for
\[H_0: F_1=F_2 \text{ vs } H_1: P[Y_1 \geq Y_2] \neq 0.5.\]
Conclusion
There is a significant difference in the distribution of the cholesterol concentration of hart patients two days upon a stroke and that of healthy subject (\(p=\) 0.0159). It is more likely to observe higher cholesterol levels for hart patients then for healthy subjects. The point estimator for this probability is 96%.
LS0tCnRpdGxlOiAiOS4gTm9ucGFyYW1ldHJpYyBTdGF0aXN0aWNzIC0gV2lsY294b24tTWFubi1XaXRobmV5IHRlc3QiCmF1dGhvcjogIkxpZXZlbiBDbGVtZW50IgpkYXRlOiAic3RhdE9taWNzLCBHaGVudCBVbml2ZXJzaXR5IChodHRwczovL3N0YXRvbWljcy5naXRodWIuaW8pIgotLS0KCjxhIHJlbD0ibGljZW5zZSIgaHJlZj0iaHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLXNhLzQuMCI+PGltZyBhbHQ9IkNyZWF0aXZlIENvbW1vbnMgTGljZW5zZSIgc3R5bGU9ImJvcmRlci13aWR0aDowIiBzcmM9Imh0dHBzOi8vaS5jcmVhdGl2ZWNvbW1vbnMub3JnL2wvYnktbmMtc2EvNC4wLzg4eDMxLnBuZyIgLz48L2E+CgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRSwgY2FjaGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldCgKICBpbmNsdWRlID0gVFJVRSwgY29tbWVudCA9IE5BLCBlY2hvID0gVFJVRSwKICBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRSwgY2FjaGUgPSBUUlVFCikKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoUm1pc2MpCnNldC5zZWVkKDE0MCkKYGBgCgoKIyBJbnRyb2R1Y3Rpb24KCkluZmVyZW5jZSB3YXMgb25seSBjb3JyZWN0IGlmIGRpc3RyaWJ1dGlvbmFsIGFzc3VtcHRpb25zIHdlcmUgc2F0aXNmaWVkCgotIGUuZyBOb3JtYWwgZGlzdHJpYnV0aW9uCi0gZXF1YWwgdmFyaWFuY2UKCi0gIFRoZSAkcCQtdmFsdWU6ICRcdGV4dHtQfV8wXGxlZnRbIFx2ZXJ0IFRcdmVydCBcZ2VxIFx2ZXJ0IHQgXHZlcnQgXHJpZ2h0XSQuCgoJLSBDYWxjdWxhdGVkIHVzaW5nIHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBvZiAkVCQgdGhhdCB3ZSBkZXJpdmVkIHVuZGVyIHRoZSBhc3N1bXB0aW9ucwoJLSBJbiBjb3JyZWN0IGlmIGFzc3VtcHRpb25zIGFyZSB2aW9sYXRlZAoKLSAgJDk1XCUkIENJIGFsc28gYnVpbGRzIHVwb24gdGhlc2UgYXNzdW1wdGlvbnMuIElmIHRoZXkgYXJlIGludmFsaWQgdGhlbiB0aGUgaW50ZXJ2YWxzIHdpbGwgbm90IGNvbnRhaW4gdGhlIHBvcHVsYXRpb24gcGFyYW1ldGVyIHdpdGggOTUlIHByb2JhYmlsaXR5LgoKLSBBc3ltcHRvdGljIHRoZW9yeSBpcyBtb3JlIGRpZmZpY3VsdCB0byBwbGFjZTogdGhlICR0JC10ZXN0IGlzIGFzeW1wdG90aWNhbGx5IG5vbi1wYXJhbWV0cmljIGJlY2F1c2UgZm9yIHZlcnkgbGFyZ2Ugc2FtcGxlcyB0aGUgZGlzdHJpYnV0aW9uYWwgYXNzdW1wdGlvbnMgb2Ygbm9ybWFsaXR5IGFyZSBubyBsb25nZXIgaW1wb3J0YW50LgoKLSBJZiBhc3N1bXB0aW9ucyBob2xkIHRoZSBwYXJhbWV0cmljIGFwcHJvYWNoCgoJLSBtb3JlIGVmZmljaWVudDogbGFyZ2VyIHBvd2VyIHdpdGggc2FtZSBzYW1wbGUgc2l6ZSArIHNtYWxsZXIgQ0kuCgktIG1vcmUgZmxleGlibGU6IGVhc2llciB0byBhbmFseXNlIGRhdGEgd2l0aCBjb21wbGV4IGRlc2lnbnMKCi0tLQoKIyMgQ2hvbGVzdGVyb2wgZXhhbXBsZQoKLSBDaG9sZXN0ZXJvbCBjb25jZW50cmF0aW9uIGluIGJsb29kIG1lYXN1cmVkIGZvcgogIC0gNSBwYXRpZW50cyAoZ3JvdXA9MSkgdHdvIGRheXMgdXBvbiBhIHN0cm9rZQogIC0gNSBoZWFsdGh5IHN1YmplY3QgKGdyb2VwPTIpLgoKLSBJcyBjaG9sZXN0ZXJvbCBjb25jZW50cmF0aW9uIG9mIGhhcnQgcGF0aWVudHMgYW5kIGhlYWx0aHkgc3ViamVjdHMgb24gYXZlcmFnZSBkaWZmZXJlbnQ/CgpgYGB7cn0KY2hvbCA8LSByZWFkX3RzdigiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0dUUEIvUFNMUzIwL21hc3Rlci9kYXRhL2Nob2wudHh0IikKY2hvbCRncm91cCA8LSBhcy5mYWN0b3IoY2hvbCRncm91cCkKbkdyb3VwcyA8LSB0YWJsZShjaG9sJGdyb3VwKQpuIDwtIHN1bShuR3JvdXBzKQpjaG9sCmBgYAoKLS0tCgoKYGBge3IsIGVjaG89RkFMU0UsIGZpZy5hbGlnbj0nY2VudGVyJ30KY2hvbCAlPiUgZ2dwbG90KGFlcyh4ID0gZ3JvdXAsIHkgPSBjaG9sZXN0KSkgKwogIGdlb21fYm94cGxvdChvdXRsaWVyLnNoYXBlID0gTkEpICsKICBnZW9tX3BvaW50KHBvc2l0aW9uID0gImppdHRlciIpCgpjaG9sICU+JSBnZ3Bsb3QoYWVzKHNhbXBsZSA9IGNob2xlc3QpKSArCiAgZ2VvbV9xcSgpICsKICBnZW9tX3FxX2xpbmUoKSArCiAgZmFjZXRfd3JhcCh+Z3JvdXApCmBgYAoKLSBQb3NzaWJseSBvdXRsaWVycwotIERpZmZpY3VsdCB0byBhc3Nlc3MgZGlzdHJpYnV0aW9uYWwgYXNzdW1wdGlvbnMgd2hlbiBvbmx5IDUgb2JzZXJ2YXRpb25zIGFyZSBhdmFpbGFibGUuCgoKIyBSYW5rIFRlc3RzCgotIEltcG9ydGFudCBncm91cCBvZiBub24tcGFyYW1ldHJpYyB0ZXN0CiAgLSBOb24tcGFyYW1ldHJpYywKICAtIEV4YWN0ICRwJC12YWx1ZXMgdXNpbmcgYSBwZXJtdXRhdGlvbiBudWxsIGRpc3RyaWJ1dGlvbi4KICAtIE5vIG5lZWQgZm9yIHNlcGFyYXRlIHBlcm11dGF0aW9uIGRpc3RyaWJ1dGlvbiBmb3IgZWFjaCBuZXcgZGF0YXNldC4KICAtIFBlcm11dGF0aW9uIG51bGwgZGlzdHJpYnV0aW9uIG9mIHJhbmsgdGVzdHMgb25seSBkZXBlbmRzIG9uIHNhbXBsZSBzaXplCiAgLSBSb2J1c3QgdG8gb3V0bGllcnMKCi0tLQoKIyBSYW5rcwoKUmFuayB0ZXN0cyBzdGFydCBmcm9tIHJhbmstdHJhbnNmb3JtZWQgZGF0YS4KCi0gTGV0ICRZXzEsIFxsZG90cywgWV9uJC4KLSBJbiB0aGUgYWJzZW5jZSBvZiAqdGllcyoKICAkJFJfaT1SKFlfaSkgPSBcI1x7WV9qOiBZX2pcbGVxIFlfaTsgaj0xLFxsZG90cywgblx9JCQKLSBTbWFsbGVzdCBvYnNlcnZhdGlvbiBoYXMgcmFuayAxLCBzZWNvbmQgc21hbGxlc3QgcmFuayAyLCAuLi4gLCBsYXJnZXN0IG9ic2VydmF0aW9uIGdldHMgcmFuayAkbiQKCmBgYHtyfQpjaG9sJGNob2xlc3QKcmFuayhjaG9sJGNob2xlc3QpCmBgYAoKLS0tCgojIyBUaWVzCgpTb21ldGltZXMgKnRpZXMqIG9jY3VyOiB0d28gb2JzZXJ2YXRpb25zIHdpdGggaWRlbnRpY2FsIHZhbHVlcwoKYGBge3J9CndpdGhUaWVzIDwtIGMoNDAzLCA1MDcsIDUwNywgNjEwLCA2NTEsIDY1MSwgNjUxLCA4MzAsIDkwMCkKcmFuayh3aXRoVGllcykKYGBgCgotIFRpZXM6IDUwNyBvY2N1cnMgdHdpY2UsIDY1MSBvY2N1cnMgMyB0aW1lcwotIElmIHRpZXMgb2NjdXIgKm1pZHJhbmtzKiBhcmUgdXNlZC4KCi0gKiptaWRyYW5rKiogb2Ygb2JzZXJ2YXRpb24gJFlfaSQgYmVjb21lcwogIFxiZWdpbntlcW5hcnJheSp9CiAgIFJfaSAmPSYgXGZyYWN7IFwjXHtZX2o6IFlfalxsZXEgWV9pXH0gKyAoIFwjXHtZX2o6IFlfaiA8IFlfaVx9ICsxKX17Mn0uCiAgIFxlbmR7ZXFuYXJyYXkqfQoKLS0tCgojIyBSYW5rcyBvZiBwb29sZWQgc2FtcGxlCgotIExldCAkWV97aWp9JCwgJGk9MSxcbGRvdHMsIG5faiQgYmUgb2JzZXJ2YXRpb25zIGZyb20gdHdvIHRyZWF0bWVudCBncm91cHMgJGo9MSwyJC4KLSBUaGV5IGNhbiBhbHNvIGJlIHJlcHJlc2VudGVkIGJ5ICRaXzEsXGxkb3RzLCBaX24kICgkbj1uXzErbl8yJCksIHRoZSBvdXRjb21lcyBvZiB0aGUgcG9vbGVkIHNhbXBsZQoKYGBge3J9CnQoY2hvbCkKeiA8LSBjaG9sJGNob2xlc3QKegpyYW5rKHopCmBgYAotLS0KCiMgV2lsY294b24tTWFubi1XaGl0bmV5IFRlc3QKCiBTaW11bHRhbmVvdXNseSBkZXZlbG9wZWQgYnkgV2lsY294b24sIGFuZCwgIE1hbm4gYW5kIFdoaXRuZXk6ICAqKldpbGNveG9uLU1hbm4tV2hpdG5leSoqLCAqKldpbGNveG9uIHJhbmsgc3VtIHRlc3QqKiAgb3IgKipNYW5uLVdoaXRuZXkgVSB0ZXN0KioKCiMjIEh5cG90aGVzZXMKClVuZGVyICRIXzAkIHRoZSBkaXN0cmlidXRpb25zIG9mIHRoZSB0d28gZ3JvdXBzIGFyZSBlcXVhbAokJEhfMDogZl8xPWZfMiQkCgoKVW5kZXIgdGhlIGFsdGVybmF0aXZlICRIXzEkIHRoZSBkaXN0cmlidXRpb25zIGRpZmZlciBpbiBsb2NhdGlvbiAkJEhfMTogXG11XzFcbmVxIFxtdV8yJCQKCiRIXzEkIGFzc3VtZXMgKipsb2NhdGlvbi1zaGlmdCoqLCB3ZSB3aWxsIHJlbGF4IHRoaXMgYXNzdW1wdGlvbiBsYXRlciBvbi4KCiMjIFRlc3Qgc3RhdGlzdGljCgpDbGFzc2ljIFQtdGVzdDogZGlmZmVyZW5jZSBpbiBzYW1wbGUgbWVhbnMgJFxiYXJ7WX1fMS1cYmFye1l9XzIkLgoKSGVyZTogRGlmZmVyZW5jZSBpbiBzYW1wbGUgbWVhbnMgYmFzZWQgb24gcmFuayB0cmFuc2Zvcm1lZCBkYXRhCgpSYW5rcyBiYXNlZCBvbiB0aGUgcG9vbGVkIHNhbXBsZSAodXBvbiBqb2luaW5nIHRoZSBvYnNlcnZhdGlvbnMgZnJvbSB0aGUgdHdvIGdyb3Vwcyk6ICRSX3tpan09UihZX3tpan0pJCBpcyBkZSByYW5rIG9mIG9ic2VydmF0aW9uICRZX3tpan0kIGluIHRoZSBwb29sZWQgc2FtcGxlLgoKXFsKICBUID0gXGZyYWN7MX17bl8xfVxzdW1fe2k9MX1ee25fMX0gUihZX3tpMX0pIC0gXGZyYWN7MX17bl8yfVxzdW1fe2k9MX1ee25fMn0gUihZX3tpMn0pIC4KXF0KCi0gVW5kZXIgJEhfMCQgd2UgZXhwZWN0IHRoZSBhdmVyYWdlIHJhbmsgb2YgdGhlIGZpcnN0IGdyb3VwIHRvIGJlIGNsb3NlIHRvIHRoYXQgb2YgdGhlIHNlY29uZCBncm91cCBzbyAkVCQgaXMgY2xvc2UgdG8gemVyby4KCi0gVW5kZXIgJEhfMSQgd2UgZXhwZWN0IHRoZSBtZWFuIHJhbmtzIHRvIGRpZmZlciBzbyB0aGF0ICRUJCBkZXZpYXRlcyBmcm9tIHplcm8uCgotIEl0IGlzIHN1ZmZpY2llbnQgdG8gb25seSBjYWxjdWxhdGUKICAkJFNfMT1cc3VtX3tpPTF9XntuXzF9IFIoWV97aTF9KSQkLgoKLSAkU18xJCBpcyB0aGUgc3VtIG9mIHRoZSByYW5rcyBvZiB0aGUgZmlyc3QgZ3JvdXA6ICpyYW5rIHN1bSB0ZXN0Ki4KCi0gVGhpcyBob2xkcyBiZWNhdXNlClxbCiAgU18xK1NfMiA9IFx0ZXh0e3N1bSBvZiBhbGwgcmFua3N9ID0gMSsyK1xjZG90cyArIG49XGZyYWN7MX17Mn1uKG4rMSkuClxdCgoKLSAkU18xJCAob3IgJFNfMiQpIGlzIGEgZ29vZCB0ZXN0IHN0YXRpc3RpYwoKLSBVc2UgcGVybXV0YXRpb25zIHRvIGRldGVybWluZSB0aGUgZXhhY3QgcGVybXV0YXRpb24gZGlzdHJpYnV0aW9uLiAoUGVybXV0ZSB0aGUgcmFua3MgYmV0d2VlbiB0aGUgZ3JvdXBzKQoKLSBGb3IgYSBnaXZlbiAkbiQgYW5kIG5vICp0aWVzKiB0aGUgcmFuayB0cmFuc2Zvcm1lZCBkYXRhIGlzIGFsd2F5cwogICQkMSwgMiwgXGxkb3RzLCBuJCQKLSBGb3IgZ2l2ZW4gJG5fMSQgZW4gJG5fMiQgdGhlIHBlcm11dGF0aW9uIGRpc3RyaWJ1dGlvbiBpcyBhbHdheXMgdGhlIHNhbWUhCi0gV2l0aCBjdXJyZW50IGNvbXB1dGluZyBwb3dlciB0aGlzIGlzIG5vdCBzbyBpbXBvcnRhbnQgYW55IG1vcmUuCgotLS0KCiMjIFN0YW5kYXJkaXplZCBzdGF0aXN0aWMKCk9mdGVuIHRoZSBzdGFuZGFyZGl6ZWQgdGVzdCBzdGF0aXN0aWMgaXMgdXNlZApcWwogIFQgPSBcZnJhY3tTXzEtXHRleHR7RX1fezB9XGxlZnRbU18xXHJpZ2h0XX17XHNxcnR7XHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdfX0sClxdCgotIHdpdGggJFx0ZXh0e0V9X3swfVxsZWZ0W1NfMVxyaWdodF0kIGFuZCAkXHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdJCB0aGUgZXhwZWN0IG1lYW4gYW5kIHZhcmlhbmNlIG9mIFMxIHVuZGVyICRIXzAkLgoKLSBVbmRlciAkSF8wJAogXFsKICAgXHRleHR7RX1fezB9XGxlZnRbU18xXHJpZ2h0XT0gXGZyYWN7MX17Mn1uXzEobisxKSBcO1w7XDtcO1x0ZXh0eyBlbiB9XDtcO1w7XDsgXHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdPVxmcmFjezF9ezEyfW5fMW5fMihuKzEpLgogXF0KCi0gVW5kZXIgJEhfMCQgYW5kIHdoZW4gJFxtaW4obl8xLG5fMilccmlnaHRhcnJvdyBcaW5mdHkkCiBcWwogICAgVCA9IFxmcmFje1NfMS1cdGV4dHtFfV97MH1cbGVmdFtTXzFccmlnaHRdfXtcc3FydHtcdGV4dHtWYXJ9X3swfVxsZWZ0W1NfMVxyaWdodF19fSBccmlnaHRhcnJvdyBOKDAsMSkuCiBcXQoKQXN5bXB0b3RpY2FsbHkgdGhlIHN0YW5kYXJkaXNlZCBzdGF0aXN0aWMgZm9sbG93cyBhIHN0YW5kYXJkIG5vcm1hbCBkaXN0cmlidXRpb24hCgotLS0KCiMjIENob2xlc3Rlcm9sIGV4YW1wbGUKCldlIGlsbHVzdHJhdGUgdGhlIHJlc3VsdCBmb3IgdGhlIGNob2xlc3Rlcm9sIGV4YW1wbGUgdXNpbmcgdGhlIFIgZnVuY3Rpb24gYHdpbGNveC50ZXN0YC4KYGBge3J9CndpbGNveC50ZXN0KGNob2xlc3QgfiBncm91cCwgZGF0YSA9IGNob2wpCmBgYAoKLSBXZSByZWplY3QgJEhfMCQgKCRwPSQgYHIgZm9ybWF0KHdpbGNveC50ZXN0KGNob2xlc3R+Z3JvdXAsZGF0YT1jaG9sKSRwLnZhbHVlLGRpZ2l0cz0yKWAgJDwwLjA1JCkKCi0gVGhlIG91dHB1dCBzaG93cyAkVz0kIGByIHdpbGNveC50ZXN0KGNob2xlc3R+Z3JvdXAsZGF0YT1jaG9sKSRzdGF0aXN0aWNgPwoKLSBMZXRzIGNhbGN1bGF0ZQpgYGB7cn0KUzEgPC0gc3VtKHJhbmsoY2hvbCRjaG9sZXN0KVtjaG9sJGdyb3VwID09IDFdKQpTMQpTMiA8LSBzdW0ocmFuayhjaG9sJGNob2xlc3QpW2Nob2wkZ3JvdXAgPT0gMl0pClMyCmBgYAoKLSBXaGVyZSBkb2VzICRXPSQgYHIgd2lsY294LnRlc3QoY2hvbGVzdH5ncm91cCxkYXRhPWNob2wpJHN0YXRpc3RpY2AgY29tZXMgZnJvbT8KCi0tLQoKIyMgTWFubiBhbmQgV2hpdG5leSB0ZXN0CgpNYW5uIGFuZCBXaGl0bmV5IHRlc3QgaW4gYWJzZW5jZSBvZiB0aWVzOgpcWwogVV8xID0gXHN1bV97aT0xfV57bl8xfVxzdW1fe2s9MX1ee25fMn0gXHRleHR7SX1cbGVmdFx7WV97aTF9XGdlcSBZX3trMn1ccmlnaHRcfS4KXF0KCi0gd2l0aCAkXHRleHR7SX1cbGVmdFx7LlxyaWdodFx9JCBhbiBpbmRpY2F0b3IgdGhhdCBlcXVhbHMgMSAgaWYgdGhlIGV4cHJlc3Npb24gaXMgdHJ1ZSBhbmQgaXMgemVybyBvdGhlcndpc2UuCgotIFUgY291bnRzIGhvdyBtYW55IHRpbWVzIGFuIG9ic2VydmF0aW9uIG9mIHRoZSBmaXJzdCBncm91cCBpcyBsYXJnZXIgb3IgZXF1YWwgdG8gYW4gb2JzZXJ2YXRpb24gZnJvbSB0aGUgc2Vjb25kIGdyb3VwLgoKYGBge3J9CnkxIDwtIHN1YnNldChjaG9sLCBncm91cCA9PSAxKSRjaG9sZXN0CnkyIDwtIHN1YnNldChjaG9sLCBncm91cCA9PSAyKSRjaG9sZXN0CnUxSGxwIDwtIHNhcHBseSh5MSwgZnVuY3Rpb24oeTFpLCB5MikgewogIHkxaSA+PSB5Mgp9LCB5MiA9IHkyKQpjb2xuYW1lcyh1MUhscCkgPC0geTEKcm93bmFtZXModTFIbHApIDwtIHkyCmBgYAoKYGBge3J9CnUxSGxwClUxIDwtIHN1bSh1MUhscCkKVTEKYGBgCgpJdCBjYW4gYmUgc2hvd24gdGhhdCAkVV8xID0gU18xIC0gXGZyYWN7MX17Mn1uXzEobl8xKzEpLiQKCmBgYHtyfQpTMSAtIG5Hcm91cHNbMV0gKiAobkdyb3Vwc1sxXSArIDEpIC8gMgpgYGAKCjEuICRVXzEkIGVuICRTXzEkIGNvbnRhaW4gdGhlIHNhbWUgaW5mb3JtYXRpb24KMi4gJFVfMSQgaXMgYWxzbyBhIHJhbmsgc3RhdGlzdGljLCBhbmQKMy4gRXhhY3QgdGVzdCBiYXNlZCBvbiAkVV8xJCBhbmQgJFNfMSQgYXJlIGVxdWl2YWxlbnQuCgotLS0KCiMjIFByb2JhYmlsaXN0aWMgaW5kZXgKCi0gJFVfMSQgaGFzIGEgYmV0dGVyIGludGVycHJldGF0aW9uIGZlYXR1cmUKLSBMZXQgJFlfaiQgYSByYW5kb20gb2JzZXJ2YXRpb24gZnJvbSBncm91cCAkaiQgKCRqPTEsMiQpLiBUaGVuClxiZWdpbntlcW5hcnJheSp9CiAgXGZyYWN7MX17bl8xbl8yfVx0ZXh0e0V9XGxlZnRbVV8xXHJpZ2h0XQogICAgICY9JiBcdGV4dHtQfVxsZWZ0W1lfMSBcZ2VxIFlfMlxyaWdodF0uClxlbmR7ZXFuYXJyYXkqfQoKU28gd2UgY2FuIGVzdGltYXRlIHRoZSBwcm9iYWJpbGl0eSBieSBjYWxjdWxhdGluZyB0aGUgbWVhbiBvZiBhbGwgaW5kaWNhdG9yIHZhcmlhYmxlIHZhbHVlcyAkXHRleHR7SX1cbGVmdFx7WV97aTF9XGdlcSBZX3trMn1ccmlnaHRcfSQuIE5vdGUsIHRoYXQgd2UgZGlkICRuXzEgXHRpbWVzIG5fMiQgY29tcGFyaXNvbnMKCmBgYHtyfQptZWFuKHUxSGxwKQpVMSAvIChuR3JvdXBzWzFdICogbkdyb3Vwc1syXSkKYGBgCgotIFByb2JhYmlsaXR5ICRcdGV4dHtQfVxsZWZ0W1lfMSBcZ2VxIFlfMlxyaWdodF0kIGlzIHJlZmVycmVkIHRvIGFzIHRoZSAqcHJvYmFiaWxpc3RpYyBpbmRleCouCi0gSXQgaXMgdGhlIHByb2JhYmlsaXR5IHRoYXQgYSByYW5kb20gb2JzZXJ2YXRpb24gb2YgdGhlIGZpcnN0IGdyb3VwIGlzIGxhcmdlciBvciBlcXVhbCB0aGFuIGEgcmFuZG9tIG9ic2VydmF0aW9uIG9mIHRoZSBzZWNvbmQgZ3JvdXAKLSBJZiAkSF8wJCBob2xkcyAkXHRleHR7UH1cbGVmdFtZXzEgXGdlcSBZXzJccmlnaHRdPVxmcmFjezF9ezJ9JC4KCi0gUiBmdW5jdGlvbiBgd2lsY294LnRlc3RgIGRvZXMgbm90IHJldHVybiB0aGUgV2lsY294b24gcmFuayBzdW0gc3RhdGlzdGljLiBJdCByZXR1cm5zIHRoZSBNYW5uLVdoaXRuZXkgc3RhdGlzdGljICRVXzEkLgotIExldHMgcmV2aXNpdCB0aGUgcmVzdWx0CmBgYHtyfQp3VGVzdCA8LSB3aWxjb3gudGVzdChjaG9sZXN0IH4gZ3JvdXAsIGRhdGEgPSBjaG9sKQp3VGVzdApVMQpwcm9iSW5kIDwtIHdUZXN0JHN0YXRpc3RpYyAvIHByb2Qobkdyb3VwcykKcHJvYkluZApgYGAKCkJlY2F1c2UgJHA9JCBgciBmb3JtYXQod1Rlc3QkcC52YWx1ZSxkaWdpdHM9MylgICQ8MC4wNSQgd2UgY29uY2x1ZGUgYXQgdGhlICQ1XCUkIHNpZ25pZmljYW5jZSBsZXZlbCB0aGF0IHRoZSBtZWFuIGNob2xlc3Rlcm9sIGxldmVsIG9mIGhhcnQgcGF0aWVudHMgaXMgbGFyZ2VyIHRoZW4gdGhhdCBvZiBoZWFsdGh5IHN1YmplY3RzLgoKICAtIE5vdGUgdGhhdCB3ZSBoYXZlIGFzc3VtZWQgdGhhdCB0aGUgbG9jYXRpb24tc2hpZnQgbW9kZWwgaXMgdmFsaWQgaW4gdGhpcyBjb25jbHVzaW9uLgogIC0gV2UgYWxzbyBrbm93IHRoYXQgaGlnaGVyIGNob2xlc3Rlcm9sIGxldmVsIGFyZSBtb3JlIGxpa2VseSBmb3IgaGFydCBwYXRpZW50cyB0aGVuIGZvciBoZWFsdGh5IHN1YmplY3RzIGFuZCB0aGlzIHByb2JhYmlsaXR5IGlzCiRVMS8obl8xXHRpbWVzIG5fMik9JCBgciBwcm9iSW5kKjEwMGAlLgogIC0gV2Ugc2hvdWxkIGFzc2VzcyB0aGUgbG9jYXRpb24gc2hpZnQgYXNzdW1wdGlvbi4gQnV0IHRoaXMgaXMgbm90IHBvc3NpYmxlIHdpdGggb25seSA1IG9ic2VydmF0aW9ucy4KCldpdGhvdXQgdGhlIGxvY2F0aW9uLXNoaWZ0IGFzc3VtcHRpb24gdGhlIGNvbmNsdXNpb24gaW4gdGVybXMgb2YgdGhlIHByb2JhYmlsaXN0aWMgaW5kZXggcmVtYWlucyB2YWxpZCEKCiAgLSBTbyB3aGVuIHdlIGRvIG5vdCBhc3N1bWUgbG9jYXRpb24gc2hpZnQgd2UgdGVzdCBmb3IKClxbSF8wOiBGXzE9Rl8yIFx0ZXh0eyB2cyB9IEhfMTogUFtZXzEgXGdlcSBZXzJdIFxuZXEgMC41LlxdCgoKIyMgQ29uY2x1c2lvbgoKVGhlcmUgaXMgYSBzaWduaWZpY2FudCBkaWZmZXJlbmNlIGluIHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIGNob2xlc3Rlcm9sIGNvbmNlbnRyYXRpb24gb2YgaGFydCBwYXRpZW50cyB0d28gZGF5cyB1cG9uIGEgc3Ryb2tlIGFuZCB0aGF0IG9mIGhlYWx0aHkgc3ViamVjdCAoJHA9JCBgciBmb3JtYXQod1Rlc3QkcC52YWx1ZSxkaWdpdHM9MylgKS4gSXQgaXMgbW9yZSBsaWtlbHkgdG8gb2JzZXJ2ZSBoaWdoZXIgY2hvbGVzdGVyb2wgbGV2ZWxzIGZvciBoYXJ0IHBhdGllbnRzIHRoZW4gZm9yIGhlYWx0aHkgc3ViamVjdHMuIFRoZSBwb2ludCBlc3RpbWF0b3IgZm9yIHRoaXMgcHJvYmFiaWxpdHkgaXMgYHIgcHJvYkluZCoxMDBgJS4K