SortedList.java

import java.util.Arrays;
import java.util.Iterator;

/**
 * 
 * @author khayyamsaleem 2017S CS284 -- Data Structures.
 *  A SortedList class that
 *         demonstrates the usage of a linked list
 * @param <E>
 *            a comparable element of our list
 */
public class SortedList<E extends Comparable<E>> implements Iterable<E> {
    private Node<E> head; // head of the list
    private int size; // size of the list

    /**
     * Making sorted lists iterable
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node<E> current = head;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public E next() {
                Node<E> x = current;
                current = current.next;
                return x.data;
            }

        };
    }

    /**
     * 
     * @author khayyamsaleem
     *
     * @param <E>
     *            a comparable object
     */
    private static class Node<E> {
        private E data; // our element
        private Node<E> next; // reference to the next element

        /**
         * Constructor for a node
         * 
         * @param data
         *            element in node
         */
        public Node(E data) {
            if (data == null) {
                throw new IllegalArgumentException();
            }
            this.data = data;
            this.next = null;
        }
    }

    /**
     * Constructor that creates an instance of a Sorted list
     */
    public SortedList() {
        this.head = null;
        this.size = 0;
    }

    /**
     * Constructor that creates a Sorted List from an array of elements
     * 
     * @param objs
     *            array of elements
     */
    @SuppressWarnings("unchecked")
    public SortedList(Object[] objs) {
        if (objs.length == 0 || objs == null) {
            throw new IllegalArgumentException();
        }
        for (Object elem : objs) {
            this.add((E) elem);
        }
    }

    /**
     * method to show size of list
     * 
     * @return size of SortedList
     */
    public int size() {
        return this.size;
    }

    /**
     * tells whether or not the list is empty
     * 
     * @return true if empty, false otherwise
     */
    public boolean isEmpty() {
        return (this.size == 0);
    }

    /**
     * Adds element at correct position in Sorted List
     * 
     * @param elem
     *            element to add
     * @return true if successful add, false otherwise
     */
    public boolean add(E elem) {
        if (elem == null) {
            throw new IllegalArgumentException();
        }
        if (this.isEmpty()) {
            this.head = new Node<E>(elem);
            this.size++;
            return true;
        }
        Node<E> n = new Node<E>(elem);
        Node<E> prev = null;
        Node<E> curr = this.head;
        while (curr != null) {
            if (elem.compareTo(curr.data) > 0) {
                prev = curr;
                curr = curr.next;
            } else {
                break;
            }
        }
        if (prev == null) {
            Node<E> oldH = this.head;
            this.head = n;
            n.next = oldH;
        } else {
            prev.next = n;
            n.next = curr;
        }
        this.size++;
        return true;
    }

    /**
     * returns element at given index in list
     * 
     * @param index
     *            index of element to return
     * @return element
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int i = 0;
        Node<E> curr = head;
        while (curr != null) {
            if (index == i) {
                assert (curr != null);
                return curr.data;
            } else {
                curr = curr.next;
                i++;
            }
        }
        return null; // something went wrong
    }

    /**
     * gets first element in list (head)
     * 
     * @return element at index 0
     */
    public E get() {
        if (this.isEmpty()) {
            return null;
        }
        return this.head.data;
    }

    /**
     * gets last element in list
     * 
     * @return last element of list
     */
    public E getLast() {
        if (this.isEmpty()) {
            return null;
        }
        return this.get(this.size - 1);
    }

    /**
     * removes first element from Sorted List and returns it
     * 
     * @return first element of list
     */
    public E removeFirst() {
        if (this.isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> ret = this.head;
        this.head = this.head.next;
        this.size--;
        return ret.data;
    }

    /**
     * removes last element from sorted list and returns it
     * 
     * @return last element of list
     */
    public E removeLast() {
        if (this.isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        if (this.size() == 1) {
            this.head = null;
            this.size = 0;
        }
        Node<E> curr = this.head;
        while (curr.next.next != null) {
            curr = curr.next;
        }
        Node<E> ret = curr.next;
        curr.next = null;
        this.size--;
        return ret.data;
    }

    /**
     * removes element at a given index in sorted list
     * 
     * @param index
     *            index of element to remove
     * @return element that was removed
     */
    public E remove(int index) {
        if (index < 0 || index > this.size() - 1) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0 || this.size() == 1) {
            return this.removeFirst();
        }
        if (index == this.size() - 1) {
            return this.removeLast();
        }
        int count = 0;
        Node<E> curr = this.head;
        while (count != index - 1) {
            curr = curr.next;
            count++;
        }
        Node<E> ret = curr.next;
        curr.next = curr.next.next;
        this.size--;
        return ret.data;
    }

    /**
     * Removes all repeats from a sorted list
     * 
     * @return true if successful, false otherwise
     */
    public boolean removeDups() {
        if(this.isEmpty()){
            throw new IllegalArgumentException();
        }
        if(this.size() == 1){
            return true;
        }
        Node<E> curr = this.head;
        while(curr.next != null){
            if(curr.data.compareTo(curr.next.data) == 0){
                curr.next = curr.next.next;
                size--;
            } else {
                curr = curr.next;
            }
        }
        return true;
    }

    /**
     * merges two sorted lists
     * 
     * @param sl
     *            SortedList to merge with operand
     * @return true if successful, false otherwise
     */
    public boolean merge(SortedList<E> sl) {
    	if(this.isEmpty() || sl.isEmpty()){
    		throw new IllegalArgumentException();
    	}
        for(int i = 0; i < this.size; i++){
            this.add(sl.get(i));
        }
        return true;
    }
    
    /**
     * checks if a given sortedlist is a subsequence of another
     * 
     * @param sl
     *            sorted list to check against operand
     * @return true if it is a subsequence, false otherwise
     */
    public boolean match(SortedList<E> sl) {
        if (sl.isEmpty()) {
            return true;
        }
        if (this.isEmpty()) {
            return false;
        }
        Node<E> slcurr = sl.head;
        Node<E> curr = this.head;
        while (curr.data.compareTo(slcurr.data) != 0) {
            curr = curr.next;
        }
        while (slcurr != null) {
            if (curr.data.compareTo(slcurr.data) != 0) {
                return false;
            }
            curr = curr.next;
            slcurr = slcurr.next;
        }
        return true;
    }

    /**
     * returns string representation of list: [ e1 e2 e3 e4 ]
     * 
     * @return string representation of list
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node<E> curr = this.head;
        while (curr.next != null) {
            sb.append(curr.data.toString());
            sb.append(", ");
            curr = curr.next;
        }
        sb.append(curr.data.toString());
        sb.append(" ]");
        return sb.toString();
    }

    public static void main(String[] args) {

        //		Object[] x = new Integer[] { 7, 19, 8, 12, 4, 5, 3, 1 };
        //		SortedList<Integer> i = new SortedList<Integer>(x);

        SortedList<String> s = new SortedList<String>();
        String[] students = new String[] { "tbarrett", "ddelaus", "ddigeronimo", "jgarner", "egarrahy", "agrochan",
            "lguzman", "shill", "mkoroluk", "clapolla", "rlittell", "lloposky", "mmroczkowski", "jnarsu", "eoh",
            "gpadriga", "npena", "jramaswamy", "kredmond", "jrodriguez", "ksaleem", "asingh", "jsmeyers",
            "msnajder", "rstern", "hzhou" };
        for (String student : students) {
            s.add(student);
        }

        System.out.println("Students: " + s);
        System.out.println("Number of Students: " + students.length);

        String[] one = Arrays.copyOfRange(students, 0, (int) Math.floor(students.length / 2));
        String[] two = Arrays.copyOfRange(students, (int) Math.floor(students.length / 2), students.length);
        SortedList<String> s1 = new SortedList<String>();
        SortedList<String> s2 = new SortedList<String>();
        for (String stud : one) {
            s1.add(stud);
        }
        for (String stud : two) {
            s2.add(stud);
        }
        System.out.println(s1);
        System.out.println(s2);

        //		SortedList<Integer> matchtest = new SortedList<Integer>();
        //		matchtest.add(3);
        //		matchtest.add(4);

        //		System.out.println(i.match(matchtest));

        //		Object[] x = new Integer[] {1, 1, 8, 8, 1, 3, 6, 4, 4, 5, 5, 11, 2, 7};
        //		SortedList<Integer> dups = new SortedList<Integer>(x);
        //		System.out.println(dups);
        //		dups.removeDups();
        //		System.out.println(dups);
        //		s1.merge(s2);
        System.out.println(s1);
    }

}