connect a List with an AVL tree

312 views Asked by At

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!

0

There are 0 answers