-
Notifications
You must be signed in to change notification settings - Fork 56
Class ApproximateMedian
Ori Roth edited this page Apr 2, 2017
·
3 revisions
public abstract class ApproximateMedian {
/*
* Forge (1)
*/
ApproximateMedian();
/*
* Type (2)
*/
abstract int position(int[] a);
final int value(int[] a);
/*
* Utilities (1)
*/
static ApproximateMedian[] $$$;
/*
* Nested types (4)
*/
final static class FirstElement extends ApproximateMedian { ... }
final static class LastElement extends ApproximateMedian { ... }
final static class Alternating extends ApproximateMedian { ... }
static abstract class HierarchicalMedian extends ApproximateMedian { ... }
} public static final class ApproximateMedian.FirstElement extends ApproximateMedian {
/*
* Forge (1)
*/
final static FirstElement $$;
/*
* Type (1)
*/
int position(int[] _);
} public static final class ApproximateMedian.LastElement extends ApproximateMedian {
/*
* Forge (1)
*/
final static LastElement $$;
/*
* Type (1)
*/
int position(int[] a);
} public static final class ApproximateMedian.Alternating extends ApproximateMedian {
/*
* Forge (1)
*/
final static Alternating $$;
/*
* Type (1)
*/
int position(int[] a);
} public abstract static class ApproximateMedian.HierarchicalMedian extends ApproximateMedian {
/*
* Forge (1)
*/
HierarchicalMedian();
/*
* Type (1)
*/
final int position(int[] a);
/*
* Utilities (1)
*/
static void median7(int[] a, int i1, int i2, int i3, int i4, int i5, int i6, int i7);
/*
* Nested types (3)
*/
final static class Sicilian extends HierarchicalMedian { ... }
final static class Fiver extends HierarchicalMedian { ... }
final static class Septer extends HierarchicalMedian { ... }
} public static final class ApproximateMedian.HierarchicalMedian.Sicilian extends HierarchicalMedian {
/*
* Forge (1)
*/
final static Sicilian $$;
}
```java
### Synopsis of Class ApproximateMedian.HierarchicalMedian.Fiver ###
```java
public static final class ApproximateMedian.HierarchicalMedian.Fiver extends HierarchicalMedian {
/*
* Forge (1)
*/
final static Fiver $$;
} public static final class ApproximateMedian.HierarchicalMedian.Septer extends HierarchicalMedian {
/*
* Forge (1)
*/
final static Septer $$;
} // SSDLPedia
package il.ac.technion.cs.cs236700.median;
import static il.ac.technion.cs.ssdl.utils.DBC.*;
import il.ac.technion.cs.ssdl.utils.Permutation;
import java.util.Arrays;
/**
* Abstract interface of algorithms for computing an approximate median.
* Implementations are by singleton classes implementing the
* abstract methods defined here. These collection of
* classes realizes the Strategy Design Pattern
*
* Author: Yossi Gil
*/
public abstract class ApproximateMedian {
/**
* Compute the location of the approximate median of an array of
* int values.
*
* a an array of values
* Return: an integer in the range 0,...,a.length-1 indicating
* the location in a in which the approximate median is
* found.
*/
public abstract int position(int a[]);
/**
* Compute the approximate median of an array of int
* values. Implementation relies on the template method pattern
*
* a an array of values
* Return: an approximate median of the values found in a
* approximate median can be found
*/
public final int value(final int a[]) {
return a[position(a)];
}
/**
* Repertoire of all different implementations
*/
public static ApproximateMedian $$$[] = {
//
ApproximateMedian.FirstElement.$$, //
ApproximateMedian.LastElement.$$, //
ApproximateMedian.Alternating.$$, //
ApproximateMedian.HierarchicalMedian.Sicilian.$$,//
ApproximateMedian.HierarchicalMedian.Fiver.$$, //
ApproximateMedian.HierarchicalMedian.Septer.$$, //
};
/**
* A singleton class, representing the algorithm of computing the
* approximate median by selecting the first element of the input
*
* Author: Yossi Gil
*/
public final static class FirstElement extends ApproximateMedian {
@Override public int position(final int[] _) {
unused(_);
return 0;
}
/**
* Singleton instance
*/
public static final FirstElement $$ = new FirstElement();
private FirstElement() {
// Forbid instantiation by clients
}
}
/**
* A singleton class, representing the algorithm of computing the
* approximate median by selecting the last element of the input
*
* Author: Yossi Gil
*/
public final static class LastElement extends ApproximateMedian {
@Override public int position(final int[] a) {
return a.length - 1;
}
/**
* Singleton instance
*/
public static final LastElement $$ = new LastElement();
private LastElement() {
// Forbid instantiation by clients
}
}
/**
* A singleton class, representing the algorithm of computing the
* approximate median by an alternating tournament, where the winner of each
* match is, alternately, either the smallest or the largest element in the
* pair.
*
* Author: Yossi Gil
*/
public final static class Alternating extends ApproximateMedian {
@Override public int position(final int[] a) {
int $ = 0;
boolean less = false;
for (int i = 0; i < a.length; i++) {
less = !less;
if (less) {
if (a[$] < a[i])
$ = i;
} else if (a[$] > a[i])
$ = i;
}
return $;
}
public static final Alternating $$ = new Alternating();
private Alternating() {
// Forbid instantiation by clients
}
}
/**
* Author: Yossi Gil
*/
/**
* Author: Yossi Gil, the Technion.
* See: 21/07/2008
*/
public abstract static class HierarchicalMedian extends ApproximateMedian {
@Override public final int position(final int[] a) {
return position(a, a.length);
}
/**
* Return the approximate median of a prefix of a given array
*
* a contains the values from which the approximate median is to
* be selected
* n only positions 0,...,length-1 are considered
* Return: the position at which the approximate median of the array is
* to be found
*/
final int position(final int[] a, final int n) {
if (n < 2 * d())
return smallRangePosition(a, n);
skipsMedian(a, n);
return position(a, shrink(a, n));
}
abstract int d();
abstract int smallRangePosition(final int[] a, final int n);
abstract void skipsMedian(final int[] a, final int n);
/**
* Shrink a given array of length n, to an array of length
* n/<tt>#d() + n % #d()</tt>. Shrinking is obtained
* by taking the n/<tt>#d()</tt> sized prefix of the input, and copying to
* the next n % <tt>#d()</tt> positions, the last
* n % <tt>#d()</tt> of the array.
*
* a input array
* n total array length
* Return: n/d() + n % d();
*/
final int shrink(final int[] a, final int n) {
final int d = d();
if (n % d == 0)
return n / d;
int i = n / d;
for (int j = i * d; j < n;)
Permutation.swap(a, i++, j++);
return i;
}
static void median3(final int[] a, final int i, final int j, final int k) {
if (a[i] < a[j]) {
if (a[j] < a[k]) // Order is: i,j,k
Permutation.swap(a, i, j);
else if (a[k] > a[i]) // Order is: k,i,k
Permutation.swap(a, i, k);
} else if (a[j] > a[k]) // i > j and j > k, therefore median is j
Permutation.swap(a, i, j);
else if (a[k] < a[i]) // Order is: j,k,i
Permutation.swap(a, i, k);
}
static void median5(final int[] a, final int i1, final int i2, final int i3, final int i4, final int i5) {
final int b[] = new int[] { a[i1], a[i2], a[i3], a[i4], a[i5] };
Arrays.sort(b);
if (b[2] == a[i2])
Permutation.swap(a, i1, i2);
else if (b[2] == a[i3])
Permutation.swap(a, i1, i3);
else if (b[2] == a[i4])
Permutation.swap(a, i1, i4);
else if (b[2] == a[i5])
Permutation.swap(a, i1, i5);
}
public static void median7(final int[] a, final int i1, final int i2, final int i3, final int i4, final int i5,
final int i6, final int i7) {
final int b[] = new int[] { a[i1], a[i2], a[i3], a[i4], a[i5], a[i6], a[i7] };
Arrays.sort(b);
if (b[3] == a[i2])
Permutation.swap(a, i1, i2);
else if (b[3] == a[i3])
Permutation.swap(a, i1, i3);
else if (b[3] == a[i4])
Permutation.swap(a, i1, i4);
else if (b[3] == a[i5])
Permutation.swap(a, i1, i5);
else if (b[3] == a[i6])
Permutation.swap(a, i1, i6);
else if (b[3] == a[i7])
Permutation.swap(a, i1, i7);
}
/**
* A singleton class, representing the algorithm of computing the
* median, by dividing the input into groups of three elements,
* computing the median of each, and carrying on recursively.
*
* Author: Yossi Gil, the Technion.
* See: 21/07/2008
*/
public final static class Sicilian extends HierarchicalMedian {
@Override int d() {
return 3;
}
@Override int smallRangePosition(final int[] a, final int n) {
nonnegative(n);
nonnull(a);
nonnull(a, "array must not be null");
require(n <= a.length || a.length == 0, "n = %d length = %d", n, a.length);
switch (n) {
case 0:
case 1:
case 2:
return 0;
case 3:
case 4:
median3(a, 0, 1, 2);
return 0;
case 5:
median5(a, 0, 1, 2, 3, 4);
return 0;
default:
unreachable("n = %d", n);
return -1;
}
}
@Override final void skipsMedian(final int[] a, final int n) {
final int third = n / 3;
final int two_thirds = third + third;
for (int i = 0; i < third; i++)
median3(a, i, i + third, i + two_thirds);
}
/**
* Singleton instance
*/
public static final Sicilian $$ = new Sicilian();
private Sicilian() {
// Forbid instantiation by clients
}
}
/**
* A singleton class, representing the algorithm of computing the
* median, by dividing the input into groups of five elements, computing
* the median of each, and carrying on recursively.
*
* Author: Yossi Gil, the Technion.
* See: 21/07/2008
*/
public final static class Fiver extends HierarchicalMedian {
@Override int d() {
return 5;
}
@Override int smallRangePosition(final int[] a, final int n) {
nonnegative(n);
require(n <= a.length || a.length == 0, "n = %d a.length = %d", n, a.length);
require(n <= 2 * d() - 1);
switch (n) {
case 0:
case 1:
case 2:
return 0;
case 3:
case 4:
median3(a, 0, 1, 2);
return 0;
case 5:
case 6:
median5(a, 0, 1, 2, 3, 4);
return 0;
case 7:
case 8:
median7(a, 0, 1, 2, 3, 4, 5, 6);
return 0;
case 9:
median3(a, 0, 3, 4);
median3(a, 1, 5, 6);
median3(a, 2, 7, 8);
median3(a, 0, 1, 2);
return 0;
default:
unreachable("n = %d", n);
return -1;
}
}
@Override final void skipsMedian(final int[] a, final int n) {
final int fifth = n / 5;
for (int i = 0; i < fifth; i++)
median5(a, i, i + fifth, i + fifth + fifth, i + fifth + fifth + fifth, i + fifth + fifth + fifth + fifth);
}
/**
* Singleton instance
*/
public static final Fiver $$ = new Fiver();
private Fiver() {
// Forbid instantiation by clients
}
}
/**
* A singleton class, representing the algorithm of computing the
* median, by dividing the input into groups of seven elements,
* computing the median of each, and carrying on recursively.
*
* Author: Yossi Gil, the Technion.
* See: 21/07/2008
*/
public final static class Septer extends HierarchicalMedian {
@Override int d() {
return 7;
}
@Override int smallRangePosition(final int[] a, final int n) {
nonnegative(n);
require(n <= a.length);
require(n <= 2 * d() - 1);
switch (n) {
case 0:
case 1:
case 2:
return 0;
case 3:
case 4:
median3(a, 0, 1, 2);
return 0;
case 5:
case 6:
median5(a, 0, 1, 2, 3, 4);
return 0;
case 7:
case 8:
median7(a, 0, 1, 2, 3, 4, 5, 6);
return 0;
case 9:
case 10:
median3(a, 0, 3, 4);
median3(a, 1, 5, 6);
median3(a, 2, 7, 8);
median3(a, 0, 1, 2);
return 0;
case 11:
case 12:
median3(a, 0, 7, 8);
median5(a, 1, 3, 4, 5, 6);
median3(a, 2, 9, 10);
median3(a, 0, 1, 2);
return 0;
case 13:
median5(a, 0, 3, 4, 5, 6);
median5(a, 1, 7, 8, 9, 10);
median3(a, 2, 11, 12);
median3(a, 0, 1, 2);
return 0;
default:
unreachable("n = %d", n);
return -1;
}
}
@Override final void skipsMedian(final int[] a, final int n) {
final int s = n / 7;
final int s2 = s + s;
final int s3 = s2 + s;
final int s4 = s3 + s;
final int s5 = s4 + s;
final int s6 = s5 + s;
for (int i = 0; i < s; i++)
median7(a, i, i + s, i + s2, i + s3, i + s4, i + s5, i + s6);
}
/**
* Singleton instance
*/
public static final Septer $$ = new Septer();
private Septer() {
// Forbid instantiation by clients
}
}
}
}| Metric | Value | Acronym | Explanation |
|---|---|---|---|
| LOC | 422 | Lines Of Code | Total number of lines in the code |
| SCC | 132 | SemiColons Count | Total number of semicolon tokens found in the code. |
| NOT | 2096 | Number Of Tokens | Comments, whitespace and text which cannot be made into a token not included. |
| VCC | 8057 | Visible Characters Count | The total number of non-white (i.e., not space, tab, newline, carriage return, form feed) characters. |
| CCC | 5080 | Code Characters Count | Total number of non-white characters in tokens. White space characters in string and character literals are not counted. |
| UIC | 65 | Unique Identifiers Count | The number of different identifiers found in the code |
| WHC | 13 | Weighted Horizontal Complexity | A heuritistic on horizontal complexity |
| Statistic | Value |
|---|---|
| Average token length | 2.4 |
| Tokens/line | 5 |
| Visible characters/line | 19 |
| Code characters/line | 12 |
| Semicolons/tokens | 6% |
| Comment text percentage | 36% |
| Token Kind | Occurrences |
|---|---|
| KEYWORD | 346 |
| OPERATOR | 111 |
| LITERAL | 177 |
| ID | 554 |
| PUNCTUATION | 908 |
| COMMENT | 37 |
| OTHER | 1105 |