I got a small rpg game where a interface List implements the class Inventar and Questlog. Now I am supposed to change the chained list to an AVL tree. I talked to constudents, because I am absolutlly lost how to do that and they said that I should edit the Inventar and Questlog code. From Github I got an AVL tree code.
List.java:
public interface List<T> {
/**
* Ueberprueft ob die Liste leer ist
*
* @return true, Liste ist leer
*/
boolean isEmpty();
/**
* Gibt die Laenge der Liste zurueck
*
* @return die Laenge
*/
int length();
/**
* Prueft ob ein Item in der Liste ist
*
* @param x das Item
*
* @return true, x ist in der Liste enthalten
*/
boolean isInList(T x);
/**
* Gibt das erste Item der Liste zurueck
*
* @return das erste Item
*
* @throws IllegalStateException wenn die Liste leer ist
*/
T firstItem() throws IllegalStateException;
/**
* Gibt das i-te Item der Liste zurueck
*
* @param i der Index
*
* @return das i-te Item
*
* @throws IndexOutOfBoundsException wenn i < 0 oder i >= length()
*/
T getItem(int i) throws IndexOutOfBoundsException;
/**
* Fuegt ein Element sortiert in die Liste ein
*
* @param x das Item
*
* @return die geanderte Liste
*/
List<T> insert(T x);
/**
* Fuegt ein Element an das Ende der Liste ein
*
* @param x das Item
*
* @return die geanderte Liste
*/
List<T> append(T x);
/**
* Loescht das erste vorkommen des Items x
*
* @param x das Item
*
* @return die geanderte Liste
*/
List<T> delete(T x);
/**
* Loescht das erste Element der Liste
*
* @return die geanderte Liste
*/
List<T> delete();
}
Inventar.java:
import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
/**
* The type Inventar.
*
* @author Alexander Ohnesorge 4571306 Gruppe 12c
* @author Felix Rostock 4571238 Gruppe 12c
*/
public class Inventar implements List<Item> {
/**
* The inventar reference.
*/
private static Inventar ref;
/**
* The Item.
*/
private Item item;
/**
* The Next.
*/
private Inventar next;
/**
* Ueberprueft ob die Liste leer ist
*
* @return true, Liste ist leer
*/
public boolean isEmpty() {
return next == null;
}
/**
* Gibt das erste Item der Liste zurueck
*
* @return das erste Item
*
* IllegalStateException wenn die Liste leer ist
*/
public Item firstItem() {
if (isEmpty()) {
throw new IllegalStateException("emtpy");
}
return next.item;
}
/**
* Gibt das i-te Item der Liste zurueck
*
* @param i der Index
*
* @return das i-te Item
*
* IndexOutOfBoundsException wenn i < 0 oder i >= length()
*/
public Item getItem(int i) {
if (i < 0 || i >= length()) {
throw new IndexOutOfBoundsException(String.format("%d / %d", i, length()));
}
if (i <= 0) {
return firstItem();
}
return next.getItem(--i);
}
/**
* Gibt die Laenge der Liste zurueck
*
* @return die Laenge
*/
public int length() {
if (isEmpty()) {
return 0;
}
return 1 + next.length();
}
/**
* Fuegt ein Element sortiert in die Liste ein
*
* @param x das Item
*
* @return die geanderte Liste
*/
public Inventar insert(Item x) {
if (isEmpty() || x.compareTo(firstItem()) <= 0) {
Inventar l = new Inventar();
l.item = x;
l.next = next;
next = l;
return this;
}
return next.insert(x);
}
/**
* Fuegt ein Element an das Ende der Liste ein
*
* @param x das Item
*
* @return die geanderte Liste
*/
public Inventar append(Item x) {
if (isEmpty()) {
return insert(x);
}
return next.append(x);
}
/**
* Loescht das erste vorkommen des Items x
*
* @param x das Item
*
* @return die geanderte Liste
*/
public Inventar delete(Item x) {
Inventar l = find(x);
if (l != null) {
l.next = l.next.next;
}
return this;
}
/**
* Loescht das erste Element der Liste
*
* @return die geanderte Liste
*/
public Inventar delete() {
if (!isEmpty()) {
next = next.next;
}
return this;
}
/**
* Find inventar.
*
* @param x the x
*
* @return the inventar
*/
private Inventar find(Item x) {
if (isEmpty()) {
return null;
} else if (firstItem().equals(x)) {
return this;
}
return next.find(x);
}
/**
* Prueft ob ein Item in der Liste ist
*
* @param x das Item
*
* @return true, x ist in der Liste enthalten
*/
public boolean isInList(Item x) {
return (find(x) != null);
}
/**
* To string.
*
* @return the string
*/
public String toString() {
int length = length();
StringBuilder string = new StringBuilder();
for (int i = 0; i < length; i++) {
string.append(i);
string.append(" - ");
string.append(getItem(i));
string.append("\n");
}
return string.toString();
}
/**
* import the csv file.
*
*/
public static void importCsv() {
BufferedReader br;
if (ref == null) {
ref = new Inventar();
} else {
ref.delete();
}
try {
//br = Files.newBufferedReader(Paths.get("C:\\Users\\Alexander\\Documents\\NetBeansProjects\\RPG\\src\\item.csv"));
br = Files.newBufferedReader(Paths.get("D:\\Eigene Dateien\\workspace\\rolegame\\src\\item.csv"));
String titels = br.readLine();
String line2 = null;
while (( line2 = br.readLine()) != null) {
String[] splitted = line2.split(", ");
Item item = null;
if ( splitted.length == 3 ) {
item = new Item(splitted[0], new Double(splitted[1]), new Double(splitted[2]));
}
if ( item == null) {
System.out.println("Item-Liste fehlerhaft");
} else {
ref.insert(item);
}
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* Accessor for the Reference Inventar
*
* @return ref
*/
public static Inventar getRef() {
return ref;
}
}
And now the sample AVL tree (already tried to fit it):
import java.util.LinkedList;
import java.util.Queue;
/**
* @author antonio081014
* @time Jul 5, 2013, 9:31:32 PM
*/
public class AVLTree<Item extends Comparable<Item>> implements List<Item> {
Node<Item> root;
public AVLTree() {
root = null;
}
public Item Maximum() {
Node<Item> local = root;
if (local == null)
return null;
while (local.getRight() != null) {
local = local.getRight();
}
return local.getData();
}
public Item Minimum() {
Node<Item> local = root;
if (local == null)
return null;
while (local.getLeft() != null) {
local = local.getLeft();
}
return local.getData();
}
private int depth(Node<Item> node) {
if (node == null)
return 0;
return node.getDepth();
// 1 + Math.max(depth(node.getLeft()), depth(node.getRight()));
}
public Node<Item> insert(Item data) {
root = insert(root, data);
switch (balanceNumber(root)) {
case 1:
root = rotateLeft(root);
break;
case -1:
root = rotateRight(root);
break;
default:
break;
}
return root;
}
public Node<Item> insert(Node<Item> node, Item data) {
if (node == null)
return new Node<Item>(data);
if (node.getData().compareTo(data) > 0) {
node = new Node<Item>(node.getData(), insert(node.getLeft(), data),
node.getRight());
// node.setLeft(insert(node.getLeft(), data));
} else if (node.getData().compareTo(data) < 0) {
// node.setRight(insert(node.getRight(), data));
node = new Node<Item>(node.getData(), node.getLeft(), insert(
node.getRight(), data));
}
// After insert the new node, check and rebalance the current node if
// necessary.
switch (balanceNumber(node)) {
case 1:
node = rotateLeft(node);
break;
case -1:
node = rotateRight(node);
break;
default:
return node;
}
return node;
}
private int balanceNumber(Node<Item> node) {
int L = depth(node.getLeft());
int R = depth(node.getRight());
if (L - R >= 2)
return -1;
else if (L - R <= -2)
return 1;
return 0;
}
private Node<Item> rotateLeft(Node<Item> node) {
Node<Item> q = node;
Node<Item> p = q.getRight();
Node<Item> c = q.getLeft();
Node<Item> a = p.getLeft();
Node<Item> b = p.getRight();
q = new Node<Item>(q.getData(), c, a);
p = new Node<Item>(p.getData(), q, b);
return p;
}
private Node<Item> rotateRight(Node<Item> node) {
Node<Item> q = node;
Node<Item> p = q.getLeft();
Node<Item> c = q.getRight();
Node<Item> a = p.getLeft();
Node<Item> b = p.getRight();
q = new Node<Item>(q.getData(), b, c);
p = new Node<Item>(p.getData(), a, q);
return p;
}
public boolean search(Item data) {
Node<Item> local = root;
while (local != null) {
if (local.getData().compareTo(data) == 0)
return true;
else if (local.getData().compareTo(data) > 0)
local = local.getLeft();
else
local = local.getRight();
}
return false;
}
public String toString() {
return root.toString();
}
public void PrintTree() {
root.level = 0;
Queue<Node<Item>> queue = new LinkedList<Node<Item>>();
queue.add(root);
while (!queue.isEmpty()) {
Node<Item> node = queue.poll();
System.out.println(node);
int level = node.level;
Node<Item> left = node.getLeft();
Node<Item> right = node.getRight();
if (left != null) {
left.level = level + 1;
queue.add(left);
}
if (right != null) {
right.level = level + 1;
queue.add(right);
}
}
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public int length() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isInList(Item x) {
// TODO Auto-generated method stub
return false;
}
@Override
public Item firstItem() throws IllegalStateException {
// TODO Auto-generated method stub
return null;
}
@Override
public Item getItem(int i) throws IndexOutOfBoundsException {
// TODO Auto-generated method stub
return null;
}
@Override
public List<Item> append(Item x) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<Item> delete(Item x) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<Item> delete() {
// TODO Auto-generated method stub
return null;
}
}
Node.java
/**
* @author antonio081014
* @time Jul 5, 2013, 9:31:32 PM
*/
public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
private T data;
private Node<T> left;
private Node<T> right;
public int level;
private int depth;
public Node(T data) {
this(data, null, null);
}
public Node(T data, Node<T> left, Node<T> right) {
super();
this.data = data;
this.left = left;
this.right = right;
if (left == null && right == null)
setDepth(1);
else if (left == null)
setDepth(right.getDepth() + 1);
else if (right == null)
setDepth(left.getDepth() + 1);
else
setDepth(Math.max(left.getDepth(), right.getDepth()) + 1);
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
/**
* @return the depth
*/
public int getDepth() {
return depth;
}
/**
* @param depth
* the depth to set
*/
public void setDepth(int depth) {
this.depth = depth;
}
@Override
public int compareTo(Node<T> o) {
return this.data.compareTo(o.data);
}
@Override
public String toString() {
return "Level " + level + ": " + data;
}
}
Best regards!