/**
 * Write a description of class OrderedArrayList here.
 *
 * @author MUHAMMAD AZRI BIN JASNI @ ABDUL RANI
 * @version 11/11/2012
 */
public class OrderedArrayList extends ArrayList
{
    //default constructor
    public OrderedArrayList()
    {
        super();
    }
    //normal constructor
    public OrderedArrayList(int size)
    {
        super(size);
    }

    public int seqSearch(Object item)
    {
        /*If the item is found, returns the location in the array where item is found
         * otherwise return -1;
           */
        int a = -1;
        for (int i=0;i<list.length;i++)
        {
            //System.out.println("Element:"+list[i]+" | Length:"+length);
            //if (list[i].toString().equals(item.toString()))
            if (list[i].equals(item))
            {
                a = i;
                break;
            }
        }
        return a;
    }

    public int binarySearch(Object item)
    {
        /*If the item is found, returns the location in the array where item is found
         * otherwise return -1;
           */
        int first = 0;
        int last = (length-1);
        int mid = -1;
        boolean found = false;
        while (first <= last && !found)
        //loop until end list or finally found
        {
            mid = (first+last)/2;
            if (list[mid]==item)
                found = true;
            else
                if ((Integer)item < (Integer) list[mid] )//item<list[mid]
                    first = mid+1;
                else
                    last = mid+1;
        }
        if (found)
            return mid;
        else
            return -1;
    }

    public void insert(Object item)
    {
        /*
        * method to insert item at the end of the list
        * however, first the list is searched to
        * see if the item to be inserted is already in the list.
        * postcondition: item is inserted and length++.
        * if insertItem is already in the list or the list is full,
        *     an appopriate message is displayed.
        */
        if (isFull())//check for full list
            System.err.println("Can't insert ["+item.toString()+"] in full list.");
        else if(isEmpty())//if empty, can instantly insert into list.
        {
            list[length] = item;
            ++length;
            //insertAtBack(item);//using ArrayList method, but remember the length already added in
        }
        //else if (binarySearch(item) != -1) //check if already exist
        else if (seqSearch(item)!=-1)
            System.err.println("["+item.toString()+"]Already in list.");
        else if ((Integer)item>=(Integer)list[length-1])//Input instantly if it is larger than last element.
        {
            list[length++] = item;
            //insertAtBack(item);//although this is slower
        }
        else
        {
           //because the previous statements false
           //this means the current item is smaller than last element
           //store this item before looping
           int current = length - 1;
           list[current+1] = list[current];
           list[current] = item;
           length++;
           //as it already been input into list, length of list increased
           //so, we only need to put it in its position
           while (current!=0)
           {
               //--current;
               if ((Integer)list[--current] > (Integer) item){

                    list[current + 1] = list[current];//move the checked element up
                    list[current] = item;//my ArrayList class don't have insertAt() method before this.
                    //and using method insertAt() cause error that not supposed to happened.
               }
               else
                    break;//since already reach element smaller than current item, break
           }
        }

    }
}