Skip to content

Instantly share code, notes, and snippets.

@cdombroski
Created October 15, 2014 19:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save cdombroski/022459a9272e48cf1a7c to your computer and use it in GitHub Desktop.
package org.icanttype;
import java.util.Iterator;
import java.util.Random;
/**
* Created by chris.dombroski on 10/14/2014.
*/
public class SmartList<T extends Comparable<? super T>> {
private int count = 0;
private SmartListEntry<T> head;
private SmartListEntry<T> top;
public SmartList() {
head = null;
top = null;
}
public static void main(String... args) throws Exception {
Random r = new Random();
SmartList<Integer> list = new SmartList<>();
int numElements = r.nextInt(40) + 1;
for (int x = 0; x < numElements; x++) {
list.push(r.nextInt(2001) - 1000);
}
displayList(list);
int x = r.nextInt(2001) - 1000;
System.out.println("Removing values greater than: " + x);
list.removeGreater(x);
displayList(list);
int half = list.size() / 2;
for (int i = 0; i < half; i++) {
list.pop();
}
displayList(list);
}
private static void displayList(SmartList<Integer> list) {
System.out.print("Stack order:");
for (Iterator<Integer> i = list.stackOrder(); i.hasNext(); ) {
System.out.print(" " + i.next());
}
System.out.println();
System.out.print("Sorted order:");
for (Iterator<Integer> i = list.sortOrder(); i.hasNext(); ) {
System.out.print(" " + i.next());
}
System.out.println();
System.out.flush();
//DSutils.show(DSTreeParser.from(list.top), 50, 25);
}
public void push(T value) {
count++;
SmartListEntry<T> o = new SmartListEntry<>(value, head);
if (head != null) {
head.prev = o;
insertValue(o, top);
} else {
top = o;
}
head = o;
}
public T pop() {
SmartListEntry<T> rtrn = head;
removeNode(rtrn);
return rtrn.value;
}
public int size() {
return count;
}
public void removeGreater(T value) {
SmartListEntry<T> ptr = top;
while (ptr.value.compareTo(value) > 0 && ptr.left != null) {
ptr = ptr.left;
}
if (ptr.up != null) {
ptr.up.left = null;
ptr.up = null;
trimTree(top);
}
top = ptr;
while (ptr.value.compareTo(value) <= 0 && ptr.right != null) {
ptr = ptr.right;
}
while (ptr != null) {
while (ptr != null && ptr.value.compareTo(value) > 0) {
if (ptr.right != null) {
trimTree(ptr.right);
}
ptr = removeNode(ptr);
}
if (ptr != null && ptr.right!= null && ptr.right.value.compareTo(value) > 0) {
ptr = ptr.right;
} else {
ptr = null;
}
}
}
public Iterator<T> stackOrder() {
return new Iterator<T>() {
SmartListEntry<T> node = head;
@Override
public boolean hasNext() {
return node != null;
}
@Override
public T next() {
T val = node.value;
node = node.next;
return val;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public Iterator<T> sortOrder() {
return new Iterator<T>() {
int returned = 0;
SmartListEntry<T> node = top;
{
while (node.left != null) {
node = node.left;
}
}
@Override
public boolean hasNext() {
return node != null && returned < count;
}
@Override
public T next() {
returned++;
T val = node.value;
if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
} else if (node.up != null) {
node = node.up;
while (node.value.compareTo(val) < 0 && node.up != null) {
node = node.up;
}
if (node.value.compareTo(val) < 0) {
if (node.right != null && node.right.value.compareTo(val) > 0) {
node = node.right;
while (node.left != null) {
node = node.left;
}
} else {
node = null;
}
}
} else {
node = null;
}
return val;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private void trimTree(SmartListEntry<T> node) {
if (node.left != null) {
trimTree(node.left);
}
if (node.right != null) {
trimTree(node.right);
}
removeNode(node);
}
private SmartListEntry<T> removeNode(SmartListEntry<T> removed) {
count--;
//handle stack
if (removed.prev != null) {
removed.prev.next = removed.next;
if (removed.next != null) {
removed.next.prev = removed.prev;
}
} else {
head = removed.next;
if (removed.next != null) {
removed.next.prev = null;
}
}
//handle tree
SmartListEntry<T> nextNode;
if (removed.left == null && removed.right != null) {
nextNode = removed.right;
} else if (removed.right == null && removed.left != null) {
nextNode = removed.left;
} else if (removed.right != null) {
nextNode = removed.left;
insertValue(removed.right, removed.left);
} else {//no decedents
nextNode = null;
}
if (removed.up != null) {
if (nextNode != null) {
nextNode.up = removed.up;
}
if (removed.up.left == removed) {
removed.up.left = nextNode;
} else {
removed.up.right = nextNode;
}
}
return nextNode;
}
private void insertValue(SmartListEntry<T> value, SmartListEntry<T> node) {
if (value.value.compareTo(node.value) <= 0) {
if (node.left == null) {
node.left = value;
value.up = node;
} else {
insertValue(value, node.left);
}
} else {
if (node.right == null) {
node.right = value;
value.up = node;
} else {
insertValue(value, node.right);
}
}
}
private static class SmartListEntry<U> /*implements DSTreeNode*/ {
U value;
SmartListEntry<U> up;
SmartListEntry<U> left;
SmartListEntry<U> right;
SmartListEntry<U> prev;
SmartListEntry<U> next;
SmartListEntry(U value, SmartListEntry<U> next) {
this.value = value;
this.next = next;
}
/*@Override
public DSTreeNode[] DSgetChildren() {
if (left == null && right == null) {
return new DSTreeNode[0];
} else {
return new DSTreeNode[]{left, right};
}
}
@Override
public Object DSgetValue() {
return value;
}
@Override
public Color DSgetColor() {
return null;
}*/
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment