CS61B_6-7

/** Double link list node */
public class DLinkeNode<Type> {
    Type item;
    DLinkeNode prev;
    DLinkeNode next;

    public DLinkeNode (Type val, DLinkeNode prevNode, DLinkeNode nextNode) {
        item = val;
        prev = prevNode;
        next = nextNode;
    }
}

/** Double link list */
import com.sun.security.jgss.GSSUtil;

public class DLList<Type> {
    private DLinkeNode head;
    private int size;

    public DLList (Type val) {
        head = new DLinkeNode(0, null,null);
        DLinkeNode node = new DLinkeNode(val, head, head);
        head.next = node;
        head.prev = node;
        size = 1;
    }

    /**
     * Add the item at the ith position
     * value of the added item is val
     *      */
    public void add(Type val, int i) {

        /** if i is out of the list's range */
        if (i <= 0 || i > size + 1) {
            System.out.println("Out of list range");
            return;
        }

        /** addLast */
        if (i == size + 1) {
             addLast(val);
             return;
        }

        DLinkeNode item = new DLinkeNode(val, null, null);
        DLinkeNode node = getNode(i);

        item.prev = node.prev;
        node.prev.next = item;
        item.next = node;
        node.prev = item;
        size += 1;

    }

    /** add a node at the end of the list, node's value is val */
    public void addLast(Type val) {
        size += 1;
        DLinkeNode item = new DLinkeNode(val, null, null);
        head.prev.next = item;
        item.prev = head.prev;
        head.prev = item;
        item.next = head;
    }

    /** Add a node at the  */
    public void addFirst(Type val) {
        size += 1;
        DLinkeNode item = new DLinkeNode(val, null, null);
        head.next.prev = item;
        item.next = head.next;
        head.next = item;
        item.prev = head;
    }

    /** Judge if i is larger than half of the size */
    private boolean isSmallEnough(int i) {
        if (i > size / 2) {
            return true;
        }
        return false;
    }

    /** Get the reference of the ith node */
    private DLinkeNode getNode(int i) {
        if (i <= 0 || i > size) {
            return null;
        }

        DLinkeNode node = head;

        if (isSmallEnough(i)) {
            node = node.prev;
            while (i != size) {
                node = node.prev;
                i += 1;
            }
        } else {
            while (i != 0) {
                node = node.next;
                i -= 1;
            }
        }
        return node;
    }

    /** Return the value of the ith item */
    public Type get (int i) {
        if (i <= 0 || i > size) {
            System.out.println("Getting out of the list range!!!");
            return null;
        }
        return (Type) getNode(i).item;
    }

    /** Return the value of the last node */
    public Type getLast() {
        if (size != 0) {
            return (Type) head.prev.item;
        }
        System.out.println("The list is empty!");
        return null;
    }

    /** Return the value of the first node */
    public Type getFirst() {
        if (size != 0) {
            return (Type) head.next.item;
        }
        System.out.println("The list is empty!");
        return null;
    }

    /** Change the ith node's value to val */
    public void change(Type val, int i) {
        DLinkeNode node = getNode(i);
        if (node != null) {
            node.item = val;
        }
    }

    /** Delete the ith node */
    public void delete(int i) {
        DLinkeNode node = getNode(i);
        if (node != null) {
            size -= 1;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
    }

    /** Return size of the list */
    public int getSize() {
        return size;
    }
}

public class AList<Item> implements List61B<Item> {
    private Item[] items;
    private int size;
    private int capacity;

    public AList() {
        items = (Item[]) new Object[100];
        size = 0;
        capacity = 100;
    }

    public void addLast(Item x) {
        if (size == items.length) {
            capacity *= 2;
            resize(capacity);
        }
        items[size] = x;
        size += 1;
    }

    @Override
    public void addFirst(Item x) {
        if (size == items.length) {
            capacity *= 2;
            resize(capacity);
        }
    }

    @Override
    public Item getFirst() {
        return items[0];
    }

    public Item getLast() {
        return items[size - 1];
    }

    public int size() {
        return size;
    }

    private void resize(int capacity) {
        Item [] a = (Item[]) new Object[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }

    public Item removeLast() {
//        int returnItem = getLast();
        Item returnItem = items[size - 1];
        size -= 1;
        return returnItem;
    }

    @Override
    public Item get(int i) {
        if (i < 0 || i > size) {
            System.out.println("Out of array range");
            return null;
        }
        return items[i];
    }

    @Override
    public void insert(Item x, int position) {

    }
}