/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
var list = new DoublyLinkedList<Integer>();
var tempList = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
var value = random.nextInt(10);
list.pushBack(value);
tempList.add(value);
}
System.
out.
println("Initial :" + list.
toString());
System.
out.
println("Expected:" + tempList.
toString()); System.
out.
println("Actual: " + list.
toString()); }
}
class Node<T> {
protected T data;
protected Node<T> next, prev;
public Node(T d, Node n, Node p) {
data = d;
next = n;
prev = p;
}
}
class DoublyLinkedList<T extends Comparable<T>> {
protected Node<T> front;
protected Node<T> back;
protected int size;
public void pushBack(T val) {
var nptr = new Node<T>(val, null, null);
if (front == null) {
front = nptr;
back = front;
} else {
nptr.prev = back;
back.next = nptr;
back = nptr;
}
size++;
}
@Override
var builder = new StringBuilder("[");
var curr = front;
while (curr != null) {
builder.append(curr.data).append(", ");
curr = curr.next;
}
builder.delete(builder.length() - 2, builder.length());
builder.append("]");
return builder.toString();
}
public void sort(Comparator<T> comparator) {
quickSort(front, back, comparator);
}
private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
if (end != null && begin != end && begin != end.next) {
var temp = partition(begin, end, comparator);
quickSort(begin, temp.prev, comparator);
quickSort(temp.next, end, comparator);
}
}
private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
var pivot = end.data;
var i = begin.prev;
Node<T> next;
for (var j = begin; j != end; j = next) {
next = j.next;
if (comparator.compare(j.data, pivot) < 0) {
i = (i == null) ? begin : i.next;
//swapData(i, j);
swapNodes(i, j);
i = j;
}
}
i = (i == null) ? begin : i.next;
//swapData(i, end);
swapNodes(i, end);
//return i;
return end;
}
private void swapData(Node<T> a, Node<T> b) {
var temp = a.data;
a.data = b.data;
b.data = temp;
}
private void swapNodes(Node<T> a, Node<T> b) {
if (a == b) return;
if (a == null || b == null) {
}
if (a.next == b) {
var before = a.prev;
var after = b.next;
link(before, b);
link(b, a);
link(a, after);
} else if (b.next == a) {
var before = b.prev;
var after = a.next;
link(before, a);
link(a, b);
link(b, after);
} else {
var aPrev = a.prev;
var aNext = a.next;
var bPrev = b.prev;
var bNext = b.next;
link(aPrev, b);
link(b, aNext);
link(bPrev, a);
link(a, bNext);
}
}
private void link(Node<T> a, Node<T> b) {
if (a != null)
a.next = b;
else
front = b;
if (b != null)
b.prev = a;
else
back = a;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCXZhciBsaXN0ID0gbmV3IERvdWJseUxpbmtlZExpc3Q8SW50ZWdlcj4oKTsKICAgICAgICB2YXIgdGVtcExpc3QgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CgogICAgICAgIHZhciByYW5kb20gPSBuZXcgUmFuZG9tKCk7CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTA7IGkrKykgewogICAgICAgICAgICB2YXIgdmFsdWUgPSByYW5kb20ubmV4dEludCgxMCk7CiAgICAgICAgICAgIGxpc3QucHVzaEJhY2sodmFsdWUpOwogICAgICAgICAgICB0ZW1wTGlzdC5hZGQodmFsdWUpOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkluaXRpYWwgOiIgKyBsaXN0LnRvU3RyaW5nKCkpOwoKICAgICAgICBsaXN0LnNvcnQoSW50ZWdlcjo6Y29tcGFyZSk7CiAgICAgICAgdGVtcExpc3Quc29ydChJbnRlZ2VyOjpjb21wYXJlKTsKICAgICAgICAKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkV4cGVjdGVkOiIgKyB0ZW1wTGlzdC50b1N0cmluZygpKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkFjdHVhbDogICIgKyBsaXN0LnRvU3RyaW5nKCkpOwoJfQp9CgpjbGFzcyBOb2RlPFQ+IHsKICAgIHByb3RlY3RlZCBUIGRhdGE7CgogICAgcHJvdGVjdGVkIE5vZGU8VD4gbmV4dCwgcHJldjsKICAgIAogICAgcHVibGljIE5vZGUoVCBkLCBOb2RlIG4sIE5vZGUgcCkgewogICAgICAgIGRhdGEgPSBkOwogICAgICAgIG5leHQgPSBuOwogICAgICAgIHByZXYgPSBwOwogICAgfQp9CgpjbGFzcyBEb3VibHlMaW5rZWRMaXN0PFQgZXh0ZW5kcyBDb21wYXJhYmxlPFQ+PiB7CiAgICBwcm90ZWN0ZWQgTm9kZTxUPiBmcm9udDsKICAgIHByb3RlY3RlZCBOb2RlPFQ+IGJhY2s7CiAgICBwcm90ZWN0ZWQgaW50IHNpemU7CgogICAgcHVibGljIHZvaWQgcHVzaEJhY2soVCB2YWwpIHsKICAgICAgICB2YXIgbnB0ciA9IG5ldyBOb2RlPFQ+KHZhbCwgbnVsbCwgbnVsbCk7CiAgICAgICAgaWYgKGZyb250ID09IG51bGwpIHsKICAgICAgICAgICAgZnJvbnQgPSBucHRyOwogICAgICAgICAgICBiYWNrID0gZnJvbnQ7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgbnB0ci5wcmV2ID0gYmFjazsKICAgICAgICAgICAgYmFjay5uZXh0ID0gbnB0cjsKICAgICAgICAgICAgYmFjayA9IG5wdHI7CiAgICAgICAgfQogICAgICAgIHNpemUrKzsKICAgIH0KICAgIAogICAgQE92ZXJyaWRlCiAgICBwdWJsaWMgU3RyaW5nIHRvU3RyaW5nKCkgewogICAgICAgIHZhciBidWlsZGVyID0gbmV3IFN0cmluZ0J1aWxkZXIoIlsiKTsKCiAgICAgICAgdmFyIGN1cnIgPSBmcm9udDsKICAgICAgICB3aGlsZSAoY3VyciAhPSBudWxsKSB7CiAgICAgICAgICAgIGJ1aWxkZXIuYXBwZW5kKGN1cnIuZGF0YSkuYXBwZW5kKCIsICIpOwogICAgICAgICAgICBjdXJyID0gY3Vyci5uZXh0OwogICAgICAgIH0KICAgICAgICBidWlsZGVyLmRlbGV0ZShidWlsZGVyLmxlbmd0aCgpIC0gMiwgYnVpbGRlci5sZW5ndGgoKSk7CiAgICAgICAgYnVpbGRlci5hcHBlbmQoIl0iKTsKCiAgICAgICAgcmV0dXJuIGJ1aWxkZXIudG9TdHJpbmcoKTsKICAgIH0KICAgIAogICAgcHVibGljIHZvaWQgc29ydChDb21wYXJhdG9yPFQ+IGNvbXBhcmF0b3IpIHsKCSAgICBxdWlja1NvcnQoZnJvbnQsIGJhY2ssIGNvbXBhcmF0b3IpOwoJfQoJCglwcml2YXRlIHZvaWQgcXVpY2tTb3J0KE5vZGU8VD4gYmVnaW4sIE5vZGU8VD4gZW5kLCBDb21wYXJhdG9yPFQ+IGNvbXBhcmF0b3IpIHsKCSAgICBpZiAoZW5kICE9IG51bGwgJiYgYmVnaW4gIT0gZW5kICYmIGJlZ2luICE9IGVuZC5uZXh0KSB7CgkgICAgICAgIHZhciB0ZW1wID0gcGFydGl0aW9uKGJlZ2luLCBlbmQsIGNvbXBhcmF0b3IpOwoJICAgICAgICBxdWlja1NvcnQoYmVnaW4sIHRlbXAucHJldiwgY29tcGFyYXRvcik7CgkgICAgICAgIHF1aWNrU29ydCh0ZW1wLm5leHQsIGVuZCwgY29tcGFyYXRvcik7CgkgICAgfQoJfQoJCglwcml2YXRlIE5vZGU8VD4gcGFydGl0aW9uKE5vZGU8VD4gYmVnaW4sIE5vZGU8VD4gZW5kLCBDb21wYXJhdG9yPFQ+IGNvbXBhcmF0b3IpIHsKCSAgICB2YXIgcGl2b3QgPSBlbmQuZGF0YTsKCQoJICAgIHZhciBpID0gYmVnaW4ucHJldjsKCSAgICBOb2RlPFQ+IG5leHQ7CgkKCSAgICBmb3IgKHZhciBqID0gYmVnaW47IGogIT0gZW5kOyBqID0gbmV4dCkgewoJICAgICAgICBuZXh0ID0gai5uZXh0OwoJICAgICAgICBpZiAoY29tcGFyYXRvci5jb21wYXJlKGouZGF0YSwgcGl2b3QpIDwgMCkgewoJICAgICAgICAgICAgaSA9IChpID09IG51bGwpID8gYmVnaW4gOiBpLm5leHQ7CgkKCSAgICAgICAgICAgIC8vc3dhcERhdGEoaSwgaik7CgkgICAgICAgICAgICBzd2FwTm9kZXMoaSwgaik7CgkgICAgICAgICAgICBpID0gajsKCSAgICAgICAgfQoJICAgIH0KCQoJICAgIGkgPSAoaSA9PSBudWxsKSA/IGJlZ2luIDogaS5uZXh0OwoJICAgIC8vc3dhcERhdGEoaSwgZW5kKTsKCSAgICBzd2FwTm9kZXMoaSwgZW5kKTsKCQoJICAgIC8vcmV0dXJuIGk7CgkgICAgcmV0dXJuIGVuZDsKCX0KCQoJcHJpdmF0ZSB2b2lkIHN3YXBEYXRhKE5vZGU8VD4gYSwgTm9kZTxUPiBiKSB7CgkgICAgdmFyIHRlbXAgPSBhLmRhdGE7CgkgICAgYS5kYXRhID0gYi5kYXRhOwoJICAgIGIuZGF0YSA9IHRlbXA7Cgl9CgkKCXByaXZhdGUgdm9pZCBzd2FwTm9kZXMoTm9kZTxUPiBhLCBOb2RlPFQ+IGIpIHsKCSAgICBpZiAoYSA9PSBiKSByZXR1cm47CgkKCSAgICBpZiAoYSA9PSBudWxsIHx8IGIgPT0gbnVsbCkgewoJICAgICAgICB0aHJvdyBuZXcgTnVsbFBvaW50ZXJFeGNlcHRpb24oKTsKCSAgICB9CgkKCSAgICBpZiAoYS5uZXh0ID09IGIpIHsKCSAgICAgICAgdmFyIGJlZm9yZSA9IGEucHJldjsKCSAgICAgICAgdmFyIGFmdGVyID0gYi5uZXh0OwoJCgkgICAgICAgIGxpbmsoYmVmb3JlLCBiKTsKCSAgICAgICAgbGluayhiLCBhKTsKCSAgICAgICAgbGluayhhLCBhZnRlcik7CgkgICAgfSBlbHNlIGlmIChiLm5leHQgPT0gYSkgewoJICAgICAgICB2YXIgYmVmb3JlID0gYi5wcmV2OwoJICAgICAgICB2YXIgYWZ0ZXIgPSBhLm5leHQ7CgkKCSAgICAgICAgbGluayhiZWZvcmUsIGEpOwoJICAgICAgICBsaW5rKGEsIGIpOwoJICAgICAgICBsaW5rKGIsIGFmdGVyKTsKCSAgICB9IGVsc2UgewoJICAgICAgICB2YXIgYVByZXYgPSBhLnByZXY7CgkgICAgICAgIHZhciBhTmV4dCA9IGEubmV4dDsKCSAgICAgICAgdmFyIGJQcmV2ID0gYi5wcmV2OwoJICAgICAgICB2YXIgYk5leHQgPSBiLm5leHQ7CgkKCSAgICAgICAgbGluayhhUHJldiwgYik7CgkgICAgICAgIGxpbmsoYiwgYU5leHQpOwoJICAgICAgICBsaW5rKGJQcmV2LCBhKTsKCSAgICAgICAgbGluayhhLCBiTmV4dCk7CgkgICAgfQoJfQoJCglwcml2YXRlIHZvaWQgbGluayhOb2RlPFQ+IGEsIE5vZGU8VD4gYikgewoJICAgIGlmIChhICE9IG51bGwpCgkgICAgICAgIGEubmV4dCA9IGI7CgkgICAgZWxzZQoJICAgICAgICBmcm9udCA9IGI7CgkgICAgaWYgKGIgIT0gbnVsbCkKCSAgICAgICAgYi5wcmV2ID0gYTsKCSAgICBlbHNlCgkgICAgICAgIGJhY2sgPSBhOwoJfSAKfQ==
Initial :[1, 1, 1, 3, 5, 2, 1, 6, 1, 4]
Expected:[1, 1, 1, 1, 1, 2, 3, 4, 5, 6]
Actual: [1, 1, 1, 3, 2, 1, 1, 4, 5, 6]