//=====================================================================
// File:    DataList.java
// Class:   DataList
// Package: AFLPcore
//
// Author:  James J. Benham
// Date:    August 10, 1998
// Contact: james_benham@hmc.edu
//
// Genographer v1.0 - Computer assisted scoring of gels.
// Copyright (C) 1998  Montana State University
// 
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; version 2
// of the License.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// The GNU General Public License is distributed in the file GPL
//=====================================================================

package AFLPcore;

import java.util.Vector;

/**
 * This is an expandable list that can be used to store objects of type
 * <code>Data</code>. The capacity will be increased automatically as needed.
 * The whole list can be duplicated as well as matched to another list.
 * Additionally, if all of the elements in the list are of type 
 * <code>SortableData</code> the list can be searched easily. However, 
 * since the searches are Binary Searches, the list must be kept ordered.
 * To do this, simply add elemenets using the <code>include</code> method,
 * which will keep the list ordered. Finally, even more options are
 * available by calling methods in the super class, however, these should
 * only be used if this class does not offer a similar feature. 
 *
 * @author James J. Benham
 * @version 1.0.0
 * @date August 10, 1998
 */

public class DataList extends Vector
{
  private boolean isSearchable;

  /**
   * Constructs an empty DataList.
   */
  public DataList()
  {
    super();

    // initial we can search/sort an empty list.
    isSearchable = true;
  }

  /**
   * Constructs an empty DataList with the specified initial capacity. 
   *
   * @param capacity  the initial capacity of the DataList. 
   */
  public DataList(int capacity)
  {
    super(capacity);

    // initial we can search/sort an empty list.
    isSearchable = true;
  }

  /**
   * Constructs an empty DataList with the specified initial capacity and 
   * capacity increment.
   *
   * @param capacity  the initial capacity of the DataList.
   * @param increment the amount by which the capacity is increased when 
   *       the DataList overflows. 
   */
  public DataList(int capacity, int increment)
  {
    super(capacity, increment);

    // initial we can search/sort an empty list.
    isSearchable = true;
  }

  /**
   * Adds the specified data to the list.
   *
   * @param dt the data to add.
   */
  public void addData(Data dt)
  {
    // if every element added is sortable, then we can still search the
    // list.
    isSearchable = (isSearchable && (dt instanceof SortableData));

    addElement(dt);
  }

  /**
   * Retrieve the data at the specified index.
   *
   * @param index  the location of the desired data.
   * 
   * @exception ArrayIndexOutOfBoundsException  if the index is not valid.
   */
  public Data dataAt(int index)
  {
    return (Data) elementAt(index);
  }

  /**
   * Places the given data in the list so that the order of the list is
   * maintained. This should be used if any searching of the list is to be
   * done, since the serach algorithm assumes the list is sorted. Note that
   * this works fine for the first element of a list.
   *
   * @param newData  the data to be added to the list
   *
   * @exception ListNotSearchableError  occurs when the list containes 
   *    data that cannot be ordered.
   */
  public void include(SortableData newData)
  {
    // See if the list is empty
    if ( size() == 0)
      addElement(newData);
    else if( newData.getSearchKey() < 
          ((SortableData) elementAt(0)).getSearchKey())
      {
     // see if it is the smallest element in the list, and if it is,
     // add it to the beginnning.
     insertElementAt(newData, 0);
      }
    else
      {
     // It's not the smallest element, so find the location to insert it
     // at with find. The find will return an insertIndex that points
     // to the closest value which is less than the given search term.
     // Since insertElementAt shifts everything up one, starting with
     // the specified index, add one to the insertIndex.
     SearchReturn searchResult = find(newData.getSearchKey());
     insertElementAt(newData, searchResult.insertIndex + 1);
      }
  }

  /** 
   * Gives the <code>SortableData</code> element which is less than or
   * equal to the given value. All of the data in the list 
   * must be of type <code>SortableData</code> for this method to work.  If
   * unsortable data has been added to the list, an error will be
   * thrown. Also, the search algorithm is a binary search, so the
   * List, <b>must be sorted</b>. Therefore, data  should be added with
   * the <code>includeData</code> instead of the <code>addData</code>
   * method.
   *
   * @param key  the value to compare to
   *
   * @return the object which has a search value <= the key such that
   *      no other object in the list exists that is greater than the
   *      returned object, but still less than or equal to the key.
   *      <code>null</code> if no such peak exists.
   *
   * @exception ListNotSearchableError  Given when some of the data is not
   *   ordered and therefor, the list cannot be searched.
   *
   * @see Data
   * @see SortableData
   * @see DataList#include */
  public SortableData findNearestUnder(double key)
  {
    // Doesn't exist if there is no data in here.
    if(isEmpty())
      return null;

    // Make sure it's not smaller than anything in the list
    // if it is, return null
    if(key < ((SortableData) elementAt(0)).getSearchKey() )
      return null;

    SearchReturn searchResult = find(key);
    
    // if we found it, than the nearest is it.
    if(searchResult.location != -1)
      return (SortableData) elementAt(searchResult.location);

    // Otherwise, the insert index contains the location of the value
    // immediately less than the value, so return it.
    return (SortableData) elementAt(searchResult.insertIndex);
  }

  /**
   * Finds the location of the specified key. All of the data in the list
   * must be of type <code>SortableData</code>, which can be ordered, but
   * simple <code>Data</code> cannot. If unsortable data has been added to
   * the list, an error will be thrown. Also, the search algorithm is a
   * binary search, so the List, <b>must be sorted</b>. Therefore, data
   * should be added with the <code>include</code> instead of the 
   * <code>addData</code> method.
   *
   * @param key  the value to search for
   *
   * @return an object with two values. The location variable will hold the
   *    index of the data with the key. It will be -1 if the data is not
   *    found. In that case, the insertIndex variable will hold the index
   *    where the data should be.
   *
   * @exception ListNotSearchableError  Given when some of the data is not
   *   ordered and therefor, the list cannot be searched.
   *
   * @see Data
   * @see SortableData
   * @see DataList#include
   */
  public SearchReturn find(double key)
  {
    // make sure that we can search the list
    if( !isSearchable )
      throw new ListNotSearchableError();

    SearchReturn searchResult = new SearchReturn();

    int bottom = 0;
    int top = this.size() - 1;
    int middle = 0;

    double midValue;

    while( bottom <= top )
      {
     middle = (bottom + top)/2;
     midValue = ((SortableData) elementAt(middle)).getSearchKey();
     
     if (key < midValue)
       {
         top = middle -1;
       }
     else if (key > midValue)
       {
         bottom = middle + 1;
         searchResult.insertIndex = middle;
       }
     else
       {
         searchResult.location = middle;
         return(searchResult);
       }
      }

    return(searchResult);    
  }

  /**
   * Creates a new list that is identical to this one with a completely
   * seperate copy of the data in the list. That is to say that not only
   * the list itself is cloned, but all of the data in the list as well.
   *
   * @return a list that is seperate but otherwise identical to this one.
   */
  public DataList completeClone()
  {
    DataList returnList = (DataList) clone();

    for(int i=0; i < size(); i++)
      {
     Data temp = (Data) ((Data) elementAt(i)).clone();
     returnList.setElementAt(temp, i);
      }

    return returnList;
  }

  /**
   * Copies the data in this list to the specified destination. This means
   * that the data in the destination will be discarded. Note that it 
   * simply causes the destination list to point to the same data. It does
   * not copy the data itself, only the references to the data.
   *
   * @param dest the destination list
   */
  public void copyList(DataList dest)
  {
    // empty the destination
    dest.removeAllElements();
    // copy the data over
    for(int i=0; i < size(); i++)
      dest.addElement(elementAt(i));
  }
}