001/*----------------------------------------------------------------------------*/
002/* Copyright (c) FIRST 2008-2012. All Rights Reserved.                        */
003/* Open Source Software - may be modified and shared by FRC teams. The code   */
004/* must be accompanied by the FIRST BSD license file in the root directory of */
005/* the project.                                                               */
006/*----------------------------------------------------------------------------*/
007package edu.wpi.first.wpilibj.util;
008
009import java.util.Vector;
010
011/**
012 *
013 * @author dtjones
014 */
015public class SortedVector extends Vector {
016
017    /**
018     * Interface used to determine the order to place sorted objects.
019     */
020    public static interface Comparator {
021
022        /**
023         * Compare the given two objects.
024         * @param object1 First object to compare
025         * @param object2 Second object to compare
026         * @return -1, 0, or 1 if the first object is less than, equal to, or
027         *  greater than the second, respectively
028         */
029        public int compare(Object object1, Object object2);
030    }
031    Comparator comparator;
032
033    /**
034     * Create a new sorted vector and use the given comparator to determine order.
035     * @param comparator The comparator to use to determine what order to place
036     * the elements in this vector.
037     */
038    public SortedVector(Comparator comparator) {
039        this.comparator = comparator;
040    }
041
042    /**
043     * Adds an element in the Vector, sorted from greatest to least.
044     * @param element The element to add to the Vector
045     */
046    public void addElement(Object element) {
047        int highBound = size();
048        int lowBound = 0;
049        while (highBound - lowBound > 0) {
050            int index = (highBound + lowBound) / 2;
051            int result = comparator.compare(element, elementAt(index));
052            if (result < 0) {
053                lowBound = index + 1;
054            } else if (result > 0) {
055                highBound = index;
056            } else {
057                lowBound = index;
058                highBound = index;
059            }
060        }
061        insertElementAt(element, lowBound);
062    }
063
064    /**
065     * Sort the vector.
066     */
067    public void sort() {
068        Object[] array = new Object[size()];
069        copyInto(array);
070        removeAllElements();
071        for (int i = 0; i < array.length; i++) {
072            addElement(array[i]);
073        }
074    }
075}