naderman

class SkipListTask {	public static void main(String[] args) {		String[] data = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P"};		int[] order = {0, 3, 8, 7, 14, 2, 1, 12, 4, 5, 11, 10, 15, 9, 6, 13};		SkipList list = new SkipList(5);		for (int i = 0; i < order.length; i++) {			list.insert(order[i], data[order[i]]);		}		list.visualize();		System.out.println(list.visualize(2));		list.delete(2);		list.delete(3);		list.visualize();		System.out.println(list.visualize(2));		System.out.println(list.visualize(11));	}}class DoublyLinkedListItem {	private Object value;	private DoublyLinkedListItem next;	private DoublyLinkedListItem prev;	public DoublyLinkedListItem(Object newValue) {		value = newValue;	}	public Object getValue() {		return value;	}	public DoublyLinkedListItem getPrev() {		return prev;	}	public void setPrev(DoublyLinkedListItem newPrev) {		prev = newPrev;	}	public DoublyLinkedListItem getNext() {		return next;	}	public void setNext(DoublyLinkedListItem newNext) {		next = newNext;	}}class DoublyLinkedList {	private DoublyLinkedListItem head;	public DoublyLinkedList() {		head = new DoublyLinkedListItem(null);	}	public DoublyLinkedListItem searchItem(Object value) {		DoublyLinkedListItem prev = head;		while (prev.getNext() != null && prev.getNext().getValue() != value) {			prev = prev.getNext();		}		if (prev.getNext() != null) {			return prev.getNext();		}		return null;	}	public void insert(DoublyLinkedListItem newItem, DoublyLinkedListItem after) {		if (after == null) {			after = head;		}		newItem.setNext(after.getNext());		newItem.setPrev(after);		if (after.getNext() != null) {			after.getNext().setPrev(newItem);		}		after.setNext(newItem);	}	public void insert(DoublyLinkedListItem newItem) {		insert(newItem, head);	}	public DoublyLinkedListItem insert(Object value) {		DoublyLinkedListItem newItem = new DoublyLinkedListItem(value);		insert(newItem);		return newItem;	}	public DoublyLinkedListItem insertAfter(Object value, DoublyLinkedListItem after) {		DoublyLinkedListItem newItem = new DoublyLinkedListItem(value);		insert(newItem, after);		return newItem;	}	public DoublyLinkedListItem append(Object value) {		DoublyLinkedListItem lastItem = head;		while (head.getNext() != null) {			lastItem = head.getNext();		}		return insertAfter(value, lastItem);	}	public void delete(DoublyLinkedListItem delete) {		if (delete != null) {			if (delete.getPrev() != null) {				delete.getPrev().setNext(delete.getNext());			}			if (delete.getNext() != null) {				delete.getNext().setPrev(delete.getPrev());			}		}	}}class SkipListItem {	private int key;	private String value;	private DoublyLinkedList levelList;	public SkipListItem(int newKey, String newValue) {		key = newKey;		value = newValue;		levelList = new DoublyLinkedList();	}	public int getKey() {		return key;	}	public String getValue() {		return value;	}	public DoublyLinkedList getLevelList() {		return levelList;	}}class LinkedSkipListItem {	private SkipListItem data;	private DoublyLinkedList itemList;	private DoublyLinkedListItem itemListPosition;	private DoublyLinkedListItem levelListPosition;	public LinkedSkipListItem(SkipListItem newData) {		data = newData;	}	public void setItemListPosition(DoublyLinkedList newItemList, DoublyLinkedListItem newItemListPosition) {		itemListPosition = newItemListPosition;		itemList = newItemList;	}	public DoublyLinkedListItem getItemListPosition() {		return itemListPosition;	}	public void setLevelListPosition(DoublyLinkedListItem newLevelListPosition) {		levelListPosition = newLevelListPosition;	}	public DoublyLinkedListItem getLevelListPosition() {		return levelListPosition;	}	public DoublyLinkedList getItemList() {		return itemList;	}	public SkipListItem getData() {		return data;	}}class SkipList {	private LinkedSkipListItem head;	private SkipListItem headData;	private int maxHeight;	private int[][][] highlight;	public SkipList(int newMaxHeight) {		maxHeight = newMaxHeight;		headData = new SkipListItem(Integer.MIN_VALUE, "");		head = new LinkedSkipListItem(headData);		DoublyLinkedListItem levelListPosition = head.getData().getLevelList().append(head);		head.setLevelListPosition(levelListPosition);		DoublyLinkedList itemList = new DoublyLinkedList();		DoublyLinkedListItem itemListPosition = itemList.append(head);		head.setItemListPosition(itemList, itemListPosition);	}	private LinkedSkipListItem searchPrev(int key) {		LinkedSkipListItem p = head;		while (true) {			// go through the items in this level until we reach the end or find a bigger key			while (p.getItemListPosition().getNext() != null && ((LinkedSkipListItem) p.getItemListPosition().getNext().getValue()).getData().getKey() < key) {				p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();			}			// if we reached level zero we need to stop			if (p.getLevelListPosition().getNext() == null) {				break;			}			// otherwise keep searching in the next level			p = (LinkedSkipListItem) p.getLevelListPosition().getNext().getValue();		}		return p;	}	private int getRandomHeight() {		int height = 0;		while (Math.random() < 0.5 && height < maxHeight) {			height++;		}		return height;	}	public void insert(int key, String value) {		int height = getRandomHeight();		SkipListItem data = new SkipListItem(key, value);		LinkedSkipListItem p = searchPrev(key);		LinkedSkipListItem item;		for (int i = 0; i <= height; i++) {			item = new LinkedSkipListItem(data);			item.setItemListPosition(p.getItemList(), p.getItemList().insertAfter(item, p.getItemListPosition()));			item.setLevelListPosition(item.getData().getLevelList().insert(item));			// find a high enough item that has to point to the inserted item			if (i < height && p.getLevelListPosition().getPrev().getValue() == null) {				while (p.getItemListPosition().getPrev().getValue() != null && p.getLevelListPosition().getPrev().getValue() == null) {					p = (LinkedSkipListItem) p.getItemListPosition().getPrev().getValue();				}				// we reached head without finding a high enough item, so we have to increase the height				if (p.getLevelListPosition().getPrev().getValue() == null) {					LinkedSkipListItem newHeadItem = new LinkedSkipListItem(headData);					DoublyLinkedList newItemList = new DoublyLinkedList();					newHeadItem.setItemListPosition(newItemList, newItemList.append(newHeadItem));					newHeadItem.setLevelListPosition(p.getData().getLevelList().insert(newHeadItem));					head = newHeadItem;					p = newHeadItem;				}				else {					p = (LinkedSkipListItem) p.getLevelListPosition().getPrev().getValue();				}			}			else if (i < height) {				p = (LinkedSkipListItem) p.getLevelListPosition().getPrev().getValue();			}		}	}	public void delete(int key) {		LinkedSkipListItem p = searchPrev(key);		if (p.getItemListPosition().getNext().getValue() == null) {			return;		}		p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();		LinkedSkipListItem top;		while (p != null) {			// if only head is left at this level remove the level completely			if (p.getItemListPosition().getPrev().getValue() == null && p.getItemListPosition().getNext() == null) {				LinkedSkipListItem headItem = (LinkedSkipListItem) p.getItemListPosition().getPrev().getValue();				if (head == headItem) {					head = (LinkedSkipListItem) headItem.getLevelListPosition().getNext().getValue();				}				headItem.getItemList().delete(headItem.getItemListPosition());				headItem.getData().getLevelList().delete(headItem.getLevelListPosition());			}			// get the item at a higher level			top = (LinkedSkipListItem) p.getLevelListPosition().getPrev().getValue();			p.getItemList().delete(p.getItemListPosition());			p.getData().getLevelList().delete(p.getLevelListPosition());			p = top;		}	}	public int getHeight() {		int height = 1;		LinkedSkipListItem p = head;		while (p.getLevelListPosition().getNext() != null) {			p = (LinkedSkipListItem) p.getLevelListPosition().getNext().getValue();			height++;		}		return height;	}	public int getWidth() {		int width = 1;		LinkedSkipListItem p = head;		while (p.getLevelListPosition().getNext() != null) {			p = (LinkedSkipListItem) p.getLevelListPosition().getNext().getValue();		}		while (p.getItemListPosition().getNext() != null) {			p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();			width++;		}		return width;	}	public String visualize(int key) {		System.out.println("Searching for key " + key + ":");		highlight = new int[getHeight()][getWidth()][5];		int i = highlight.length - 1;		int j = 0;		System.out.println(i + "/" + j);		highlight[i][j][0] = 1;				LinkedSkipListItem p = head;		while (true) {			// go through the items in this level until we reach the end or find a bigger key			while (p.getItemListPosition().getNext() != null && ((LinkedSkipListItem) p.getItemListPosition().getNext().getValue()).getData().getKey() < key) {				highlight[i][j][2] = 1;				p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();				// calculate the distance to head at zero level				int distance = 0;				LinkedSkipListItem q = p;				while (q.getLevelListPosition().getNext() != null) {					q = (LinkedSkipListItem) q.getLevelListPosition().getNext().getValue();				}				while (q.getItemListPosition().getPrev().getValue() != null) {					q = (LinkedSkipListItem) q.getItemListPosition().getPrev().getValue();					distance++;				}				j = distance;				System.out.println(i + "/" + j);				highlight[i][j][4] = 1;				highlight[i][j][0] = 1;			}			// if we reached level zero we need to stop			if (p.getLevelListPosition().getNext() == null) {				break;			}			// otherwise keep searching in the next level			p = (LinkedSkipListItem) p.getLevelListPosition().getNext().getValue();			System.out.println(i + "/" + j);			highlight[i][j][3] = 1;			i--;			System.out.println(i + "/" + j);			highlight[i][j][1] = 1;			highlight[i][j][0] = 1;		}		if (p.getItemListPosition().getNext().getValue() == null) {			return null;		}		highlight[i][j][2] = 1;		j++;		System.out.println(i + "/" + j);		highlight[i][j][4] = 1;		highlight[i][j][0] = 1;		p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();		visualize();		highlight = null;		if (p.getData().getKey() == key) {			return p.getData().getValue();		}		else {			return null;		}	}	public void visualize() {		LinkedSkipListItem p = head;		LinkedSkipListItem q;		int i, j, k;		int maxKey = 0;		int[][][] net = new int[getHeight()][getWidth()][5];		for (i = 0; i < net.length; i++) {			for (j = 0; j < net[i].length; j++) {				net[i][j][1] = Integer.MAX_VALUE;			}		}		while (p.getLevelListPosition().getNext() != null) {			p = (LinkedSkipListItem) p.getLevelListPosition().getNext().getValue();		}		i = 0;		while (p != null) {			q = p;			j = 0;			while (q != null) {				net[j][i][0] = q.getData().getKey();				// 1 == top, 2 == right, 3 == bottom, 4 == left				net[j][i][1] = (q.getLevelListPosition().getPrev().getValue() == null) ? 0 : 1;				net[j][i][2] = (q.getItemListPosition().getNext() == null) ? 0 : 1;				net[j][i][3] = (q.getLevelListPosition().getNext() == null) ? 0 : 1;				net[j][i][4] = (q.getItemListPosition().getPrev().getValue() == null) ? 0 : 1;				if (net[j][i][0] > maxKey) {					maxKey = net[j][i][0];				}				q = (LinkedSkipListItem) q.getLevelListPosition().getPrev().getValue();				j++;			}			if (p.getItemListPosition().getNext() == null) {				break;			}			p = (LinkedSkipListItem) p.getItemListPosition().getNext().getValue();			i++;		}		maxKey = Integer.toString(maxKey).length();		maxKey = (maxKey < 3) ? 3 : maxKey;		String border = "";		String noborder = "";		String hiborder = "";		for (k = 0; k < maxKey; k++) {			border += "-";			noborder += " ";			hiborder += "*";		}		for (i = net.length - 1 ; i >= 0; i--) {			for (j = 0; j < net[i].length; j++) {				System.out.print(noborder + ((net[i][j][1] == 1) ? (((highlight != null && highlight[i][j][1] == 1)) ? "*" : "|") : " ") + "   ");			}			System.out.println();			for (j = 0; j < net[i].length; j++) {				if (net[i][j][1] != Integer.MAX_VALUE) {					if (highlight != null && highlight[i][j][0] == 1) {						System.out.print(" *" + hiborder + "* ");					}					else {						System.out.print(" +" + border + "+ ");					}				}				else {					System.out.print("  " + noborder + "  ");				}			}			System.out.println();			int fill = 0;			for (j = 0; j < net[i].length; j++) {				if (net[i][j][1] != Integer.MAX_VALUE) {					fill = 0;					System.out.print((net[i][j][4] == 1) ? ((highlight != null && highlight[i][j][4] == 1) ? "*" : "-") : " ");					System.out.print((highlight != null && highlight[i][j][0] == 1) ? "*" : "|");					if (net[i][j][0] == Integer.MIN_VALUE) {						for (k = 0; k < maxKey - 3; k++) {							System.out.print(" ");						}						System.out.print("-oo");					}					else {						for (k = 0; k < maxKey - Integer.toString(net[i][j][0]).length(); k++) {							System.out.print(" ");						}						System.out.print(net[i][j][0]);					}					System.out.print((highlight != null && highlight[i][j][0] == 1) ? "*" : "|");					if (net[i][j][2] == 1) {						if (highlight != null && highlight[i][j][2] == 1) {							System.out.print("*");							fill = 2;						}						else {							System.out.print("-");							fill = 1;						}					}					else {						System.out.print(" ");					}				}				else if (fill == 1) {					System.out.print("--" + border + "--");				}				else if (fill == 2) {					System.out.print("**" + hiborder + "**");				}				else {					System.out.print("  " + noborder + "  ");				}			}			System.out.println();			for (j = 0; j < net[i].length; j++) {				if (net[i][j][1] != Integer.MAX_VALUE) {					if (highlight != null && highlight[i][j][0] == 1) {						System.out.print(" *" + hiborder + "* ");					}					else {						System.out.print(" +" + border + "+ ");					}				}				else {					System.out.print("  " + noborder + "  ");				}			}			System.out.println();			for (j = 0; j < net[i].length; j++) {				System.out.print(noborder + ((net[i][j][3] == 1) ? (((highlight != null && highlight[i][j][3] == 1)) ? "*" : "|") : " ") + "   ");			}			System.out.println();		}	}}