//Norman Pestaina    COP3337
//Example program:   Partially-filled Arrays
//                
//    Objective: Understanding Arrays, References
//
//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.).
//
//A QuickList is queried via these methods:
//    String getTitle()
//    String[] getItems()
//    boolean contains(String item)
//A QuickList is updated via these methods:
//    boolean add(String item)
//    boolean delete(String item)
//
public class QuickList
{
   //Default initial capacity of this QuickList
   private static final int DEFAULT_CAPACITY = 4;
   
   //Default title for this QuickList
   private static final String DEFAULT_TITLE = "Quick List";

   //InstanceVariables
   private String title;   //Title of this QuickList
   private String[] items;	//Storage for the items in this QuickList
   private int itemCount;  //# items currently stored in this QuickList
      
   //Constructor
   public QuickList(String title, int capacity)
   {
      this.title = title;
      
      if (capacity < DEFAULT_CAPACITY)
         capacity = DEFAULT_CAPACITY;
      this.items = new String[capacity];
      
      this.itemCount = 0;
   }
   
   //Constructor
   public QuickList(int capacity)
   {
      this(DEFAULT_TITLE, capacity);
   }
   
   //Constructor
   public QuickList(String title)
   {
      this(title, DEFAULT_CAPACITY);
   }
   
   //Constructor
   public QuickList()
   {
      this(DEFAULT_TITLE, DEFAULT_CAPACITY);
   }
   
   //Accessor      
   public String getTitle()
   {
      return this.title;
   }
     
   //Accessor
   public String[] getItems()
   {
      //Create an array of the appropriate size
      String[] items = new String[this.itemCount];
      
      //Copy data from the store
      for (int i = 0; i < items.length; i++)
         items[i] = this.items[i];
               
      return items;
   }

   //Override
   public String toString()
   {
      String image = this.title + " " + this.itemCount + " Items";
      for (String item : this.getItems())
         image = image + "\n" + item;
         
      return image;
   }
   
   //Inspector
   //Answer if an item is stored in a Quicklist
   // @param item: an item to be searched/matched in this QuickList
   // @return true if this Quicklist contains a matching item
   //         false if this QuickList contains NO matching item
   public boolean contains(String item)
   { 
      return this.indexOf(item) != -1;
   }
   
   //Mutator
   //Add an item into a QuickList (does not store duplicates)
   // @param item: an item to be added into this Quicklist
   // @return true if the item is added
   //         false if the item is NOT added (it's a duplicate)
   public boolean add(String item)
   {
      //A QuickList does not duplicate entries
      if (this.indexOf(item) != -1)
         return false;
      
      //Extend the store if currently filled
      if (this.itemCount == this.items.length) 
         extendStore();
      
      //Store a new item
      this.items[this.itemCount] = item;  //Append
      this.itemCount++;
      //this.insert(item);
            
      return true;
   }
      
   //Mutator
   //Delete/Remove an item from a Quicklist
   // @param item: the item to be matched and deleted from this QuickList
   // @return true if the item is deleted
   //         false if the item is NOT deleted (no matching item)
   public boolean delete(String item)
   {
      //Locate the item to be deleted
      int goner = this.indexOf(item);
      
      //Cannot delete an item that's not in store
      if (goner == -1)
         return false;
      
      //Shift higher-placed items down 1 place   
      for (int move = goner + 1; move < this.itemCount; move++)
          this.items[move - 1] = this.items[move];
      
      //Update the count
      this.itemCount--;
      
      return true;
   }
   
   //================================= Helper Methods ==========
   
   //Return the index of an item in the store
   // or -1 if the item is not stored
	private int indexOf(String item)
	{
      for (int index = 0; index < this.itemCount; index++)
         if ( this.items[index].equalsIgnoreCase(item) )
            return index;
             
		return -1; 
    
      //return this.linearSearch(item);
      //return this.binarySearch(item);
	}
	   
   //Increase the capacity of the store by DEFAULT_SIZE locations
	private void extendStore()
	{
      //Allocate new extended storage
      String[] newStore = new String[this.items.length + DEFAULT_CAPACITY];
               
      //Copy any items from the old store into the new store
      for (int k = 0; k < this.items.length; k++)
         newStore[k] = this.items[k];
      
      //Re-assign the new storage to replace the old storage  
      this.items = newStore;
	}   

   //**************************************************************
   //****************** 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.itemCount - 1;
      
      while ( index >= 0 && !this.items[index].equalsIgnoreCase(target))
         index = index - 1;
         
      return index;
   }
   
   //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.itemCount - 1;
      
      while ( loIndex <= hiIndex )
      {
         int middle = (loIndex + hiIndex) /2;
         int comparison = this.items[middle].compareToIgnoreCase(target);
             
         if ( comparison == 0 )
            return middle;
            
         if ( comparison < 0 )
            loIndex = middle + 1;
         else
            hiIndex = middle - 1;
      }
      return -1;
   }
   
   //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.itemCount - 1;
      while (index >= 0 && this.items[index].compareTo(item) > 0)
      {
         this.items[index + 1] = this.items[index];
         index = index - 1;
      }
      this.items[index + 1] = item;
   }
   
}