source: branches/MetisMQI/src/main/java/weka/clusterers/forOPTICSAndDBScan/Databases/SequentialDatabase.java

/*
 *    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; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    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., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    Copyright (C) 2004
 *    & Matthias Schubert (schubert@dbs.ifi.lmu.de)
 *    & Zhanna Melnikova-Albrecht (melnikov@cip.ifi.lmu.de)
 *    & Rainer Holzmann (holzmann@cip.ifi.lmu.de)
 */

package weka.clusterers.forOPTICSAndDBScan.Databases;

import weka.clusterers.forOPTICSAndDBScan.DataObjects.DataObject;
import weka.clusterers.forOPTICSAndDBScan.Utils.EpsilonRange_ListElement;
import weka.clusterers.forOPTICSAndDBScan.Utils.PriorityQueue;
import weka.clusterers.forOPTICSAndDBScan.Utils.PriorityQueueElement;
import weka.core.Instances;
import weka.core.RevisionHandler;
import weka.core.RevisionUtils;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.TreeMap;

/**
 * <p>
 * SequentialDatabase.java <br/>
 * Authors: Rainer Holzmann, Zhanna Melnikova-Albrecht, Matthias Schubert <br/>
 * Date: Aug 20, 2004 <br/>
 * Time: 1:23:38 PM <br/>
 * $ Revision 1.4 $ <br/>
 * </p>
 *
 * @author Matthias Schubert (schubert@dbs.ifi.lmu.de)
 * @author Zhanna Melnikova-Albrecht (melnikov@cip.ifi.lmu.de)
 * @author Rainer Holzmann (holzmann@cip.ifi.lmu.de)
 * @version $Revision: 1.4 $
 */
public class SequentialDatabase
    implements Database, Serializable, RevisionHandler {

    /** for serialization */
    private static final long serialVersionUID = 787245523118665778L;

    /**
     * Internal, sorted Treemap for storing all the DataObjects
     */
    private TreeMap treeMap;

    /**
     * Holds the original instances delivered from WEKA
     */
    private Instances instances;

    /**
     * Holds the minimum value for each attribute
     */
    private double[] attributeMinValues;

    /**
     * Holds the maximum value for each attribute
     */
    private double[] attributeMaxValues;

    // *****************************************************************************************************************
    // constructors
    // *****************************************************************************************************************

    /**
     * Constructs a new sequential database and holds the original instances
     * @param instances
     */
    public SequentialDatabase(Instances instances) {
        this.instances = instances;
        treeMap = new TreeMap();
    }

    // *****************************************************************************************************************
    // methods
    // *****************************************************************************************************************

    /**
     * Select a dataObject from the database
     * @param key The key that is associated with the dataObject
     * @return dataObject
     */
    public DataObject getDataObject(String key) {
        return (DataObject) treeMap.get(key);
    }

    /**
     * Sets the minimum and maximum values for each attribute in different arrays
     * by walking through every DataObject of the database
     */
    public void setMinMaxValues() {
        attributeMinValues = new double[getInstances().numAttributes()];
        attributeMaxValues = new double[getInstances().numAttributes()];

        //Init
        for (int i = 0; i < getInstances().numAttributes(); i++) {
            attributeMinValues[i] = attributeMaxValues[i] = Double.NaN;
        }

        Iterator iterator = dataObjectIterator();
        while (iterator.hasNext()) {
            DataObject dataObject = (DataObject) iterator.next();
            for (int j = 0; j < getInstances().numAttributes(); j++) {
                if (Double.isNaN(attributeMinValues[j])) {
                    attributeMinValues[j] = dataObject.getInstance().value(j);
                    attributeMaxValues[j] = dataObject.getInstance().value(j);
                } else {
                    if (dataObject.getInstance().value(j) < attributeMinValues[j])
                        attributeMinValues[j] = dataObject.getInstance().value(j);
                    if (dataObject.getInstance().value(j) > attributeMaxValues[j])
                        attributeMaxValues[j] = dataObject.getInstance().value(j);
                }
            }
        }
    }

    /**
     * Returns the array of minimum-values for each attribute
     * @return attributeMinValues
     */
    public double[] getAttributeMinValues() {
        return attributeMinValues;
    }

    /**
     * Returns the array of maximum-values for each attribute
     * @return attributeMaxValues
     */
    public double[] getAttributeMaxValues() {
        return attributeMaxValues;
    }

    /**
     * Performs an epsilon range query for this dataObject
     * @param epsilon Specifies the range for the query
     * @param queryDataObject The dataObject that is used as query-object for epsilon range query
     * @return List with all the DataObjects that are within the specified range
     */
    public List epsilonRangeQuery(double epsilon, DataObject queryDataObject) {
        ArrayList epsilonRange_List = new ArrayList();
        Iterator iterator = dataObjectIterator();
        while (iterator.hasNext()) {
            DataObject dataObject = (DataObject) iterator.next();
            double distance = queryDataObject.distance(dataObject);
            if (distance < epsilon) {
                epsilonRange_List.add(dataObject);
            }
        }

        return epsilonRange_List;
    }

    /**
     * Emits the k next-neighbours and performs an epsilon-range-query at the parallel.
     * The returned list contains two elements:
     * At index=0 --> list with all k next-neighbours;
     * At index=1 --> list with all dataObjects within epsilon;
     * @param k number of next neighbours
     * @param epsilon Specifies the range for the query
     * @param dataObject the start object
     * @return list with the k-next neighbours (PriorityQueueElements) and a list
     *         with candidates from the epsilon-range-query (EpsilonRange_ListElements)
     */
    public List k_nextNeighbourQuery(int k, double epsilon, DataObject dataObject) {
        Iterator iterator = dataObjectIterator();

        List return_List = new ArrayList();
        List nextNeighbours_List = new ArrayList();
        List epsilonRange_List = new ArrayList();

        PriorityQueue priorityQueue = new PriorityQueue();

        while (iterator.hasNext()) {
            DataObject next_dataObject = (DataObject) iterator.next();
            double dist = dataObject.distance(next_dataObject);

            if (dist <= epsilon) epsilonRange_List.add(new EpsilonRange_ListElement(dist, next_dataObject));

            if (priorityQueue.size() < k) {
                priorityQueue.add(dist, next_dataObject);
            } else {
                if (dist < priorityQueue.getPriority(0)) {
                    priorityQueue.next(); //removes the highest distance
                    priorityQueue.add(dist, next_dataObject);
                }
            }
        }

        while (priorityQueue.hasNext()) {
            nextNeighbours_List.add(0, priorityQueue.next());
        }

        return_List.add(nextNeighbours_List);
        return_List.add(epsilonRange_List);
        return return_List;
    }

    /**
     * Calculates the coreDistance for the specified DataObject.
     * The returned list contains three elements:
     * At index=0 --> list with all k next-neighbours;
     * At index=1 --> list with all dataObjects within epsilon;
     * At index=2 --> coreDistance as Double-value
     * @param minPoints minPoints-many neighbours within epsilon must be found to have a non-undefined coreDistance
     * @param epsilon Specifies the range for the query
     * @param dataObject Calculate coreDistance for this dataObject
     * @return list with the k-next neighbours (PriorityQueueElements) and a list
     *         with candidates from the epsilon-range-query (EpsilonRange_ListElements) and
     *         the double-value for the calculated coreDistance
     */
    public List coreDistance(int minPoints, double epsilon, DataObject dataObject) {
        List list = k_nextNeighbourQuery(minPoints, epsilon, dataObject);

        if (((List) list.get(1)).size() < minPoints) {
            list.add(new Double(DataObject.UNDEFINED));
            return list;
        } else {
            List nextNeighbours_List = (List) list.get(0);
            PriorityQueueElement priorityQueueElement =
                    (PriorityQueueElement) nextNeighbours_List.get(nextNeighbours_List.size() - 1);
            if (priorityQueueElement.getPriority() <= epsilon) {
                list.add(new Double(priorityQueueElement.getPriority()));
                return list;
            } else {
                list.add(new Double(DataObject.UNDEFINED));
                return list;
            }
        }
    }

    /**
     * Returns the size of the database (the number of dataObjects in the database)
     * @return size
     */
    public int size() {
        return treeMap.size();
    }

    /**
     * Returns an iterator over all the keys
     * @return iterator
     */
    public Iterator keyIterator() {
        return treeMap.keySet().iterator();
    }

    /**
     * Returns an iterator over all the dataObjects in the database
     * @return iterator
     */
    public Iterator dataObjectIterator() {
        return treeMap.values().iterator();
    }

    /**
     * Tests if the database contains the dataObject_Query
     * @param dataObject_Query The query-object
     * @return true if the database contains dataObject_Query, else false
     */
    public boolean contains(DataObject dataObject_Query) {
        Iterator iterator = dataObjectIterator();
        while (iterator.hasNext()) {
            DataObject dataObject = (DataObject) iterator.next();
            if (dataObject.equals(dataObject_Query)) return true;
        }
        return false;
    }

    /**
     * Inserts a new dataObject into the database
     * @param dataObject
     */
    public void insert(DataObject dataObject) {
        treeMap.put(dataObject.getKey(), dataObject);
    }

    /**
     * Returns the original instances delivered from WEKA
     * @return instances
     */
    public Instances getInstances() {
        return instances;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 1.4 $");
    }
}