//Example program: 
//                
//Objective: ArrayList, Insertion, Search
//
//A QuickList object provides the client with the ability to create
// and maintain a list of String items (shopping-list, address-list,
// CD-titles, friends names, FIU classes completed, etc.).
import java.util.*;
public class QuickList
{
   //Default title for this QuickList
   private static final String DEFAULT_TITLE = "Quick List";

   //InstanceVariables
   private String title;   //Title of this QuickList
   private ArrayList<String> items;	//Storage for the items in this QuickList
      
   //Constructor
   public QuickList(String title)
   {
      this.title = title;
      this.items = new ArrayList<>();      
   }
      
   
   //Constructor
   public QuickList()
   {
      this(DEFAULT_TITLE);
   }
   
   //Accessor      
   public String getTitle()
   {
      return this.title;
   }
      
   //Accessor
   public String[] getItems()
   {
      //Create an array of the appropriate size
      String[] items = new String[this.items.size()];
      
      //Copy data from the items
      for (int i = 0; i < items.length; i++)
         items[i] = this.items.get(i);
               
      return items;
   }

   //Override
   public String toString()
   {
      String image = this.title + " " + this.items.size() + " Items";
      for (String item : this.items)
         image = image + "\n" + item;
         
      return image;
   }
	
   //Inspector
   public boolean contains(String item)
   { 
      return this.indexOf(item) != -1;
   }
 
   //Mutator
   public boolean add(String item)
   {
      //Duplicates are not added
      if (this.indexOf(item) != -1)
         return false;
      
      //Store a new item
      this.items.add(item);
      return true;
   }
      
   //Mutator
   public boolean delete(String item)
   {
      //Locate the item to be deleted
      int index = this.indexOf(item);
      
      //Cannot delete an item that's not in items
      if (index == -1)
         return false;
      
      //Remove the item from the store
      this.items.remove(index);
      return true;
   }
    
   //Helper Method
   // @param item: An item to be matched against the stored items
   // @return the index of a stored item that matches the parameter
   //         or -1 if no stored item matches the parameter
	private int indexOf(String item)
	{  
      return this.linearSearch(item);
	}
   
   //******************************************************************
   //********************** Array Algorithms **************************
   
   //LinearSearch
   // Sequential scan of the elements of an array
   // Return the index of an element matching a given target
   // Return -1 if no element matches the given target
   //@param target: the value to be matched with an array element
   private int linearSearch(String target)
   {
      int index = this.items.size() -1;
      while (index > -1 && !this.items.get(index).equalsIgnoreCase(target))
         index--;
             
		return index;
   }
   
   //Insertion
   // Add an item into a sorted array (ascending order)
   // while preserving the ordering of the array elements
   private void insert(String item)
   {
      int index = this.items.size() - 1;
      while (index >= 0 && this.items.get(index).compareToIgnoreCase(item) > 0)
         index = index - 1;
      this.items.add(index + 1, item);
   }
      
   //Binary Search
   // Search the elements of a sorted array (ascending order)
   // Return the index of an element matching a given target
   // Return -1 if no element matches the given target
   //@param target: the value to be matched with an array element
   private int binarySearch(String target)
   {
      int loIndex = 0;
      int hiIndex = this.items.size() - 1;
      
      while (loIndex <= hiIndex)
      {
         int middle = (loIndex + hiIndex) / 2;
         int comparison = target.compareToIgnoreCase( this.items.get(middle) );
         
         if (comparison == 0)
            return middle;
            
         if (comparison < 0)
            hiIndex = middle - 1;
         else
            loIndex = middle + 1;
      }
      return -1;
   }   
}