final class DataSet {
private final int x;
private final int nextX;
public DataSet(int x, int nextX) {
this.x = x;
this.nextX = nextX;
}
public int getX() {
return x;
}
public int getNextX() {
return nextX;
}
public String toString() {
return "x: " + x + " nextX: " + nextX;
}
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + nextX;
result = prime * result + x;
return result;
}
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DataSet other = (DataSet) obj;
if (nextX != other.nextX)
return false;
if (x != other.x)
return false;
return true;
}
}
public final class NextGreatestElement {
private NextGreatestElement() {
public static List<DataSet> getNextGreatestElement(int[] a) {
final List<DataSet> dataSetList = new ArrayList<DataSet>();
final Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && stack.peek() < a[i]) {
dataSetList.add(new DataSet(stack.pop(), a[i]));
}
stack.push(a[i]);
}
while (!stack.isEmpty()) {
dataSetList.add(new DataSet(stack.pop(), -1));
}
return dataSetList;
}
}
public class NextGreatestElementTest {
public void test1() {
int[] a1 = {2, 3, 4, 5};
List<DataSet> ds1 = new ArrayList<DataSet>();
ds1.add(new DataSet(2, 3));
ds1.add(new DataSet(3, 4));
ds1.add(new DataSet(4, 5));
ds1.add(new DataSet(5, -1));
assertEquals(ds1, NextGreatestElement.getNextGreatestElement(a1));
}
public void test2() {
int[] a2 = {3, 2, 1};
List<DataSet> ds2 = new ArrayList<DataSet>();
ds2.add(new DataSet(1, -1));
ds2.add(new DataSet(2, -1));
ds2.add(new DataSet(3, -1));
assertEquals(ds2, NextGreatestElement.getNextGreatestElement(a2));
}
}