//=====================================================================
// 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
* Data
. 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
* SortableData
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 include
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 SortableData
element which is less than or
* equal to the given value. All of the data in the list
* must be of type SortableData
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, must be sorted. Therefore, data should be added with
* the includeData
instead of the addData
* 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.
* null
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 SortableData
, which can be ordered, but
* simple Data
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, must be sorted. Therefore, data
* should be added with the include
instead of the
* addData
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));
}
}