001/*----------------------------------------------------------------------------*/
002/* Copyright (c) FIRST 2008-2017. 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/*----------------------------------------------------------------------------*/
007
008package edu.wpi.first.wpilibj.util;
009
010import java.util.Vector;
011
012/**
013 * A vector that is sorted.
014 */
015public class SortedVector extends Vector {
016
017  /**
018   * Interface used to determine the order to place sorted objects.
019   */
020  public interface Comparator {
021
022    /**
023     * Compare the given two objects.
024     *
025     * <p>Should return -1, 0, or 1 if the first object is less than, equal to, or greater than the
026     * second, respectively.
027     *
028     * @param object1 First object to compare
029     * @param object2 Second object to compare
030     * @return -1, 0, or 1.
031     */
032    int compare(Object object1, Object object2);
033  }
034
035  private final Comparator m_comparator;
036
037  /**
038   * Create a new sorted vector and use the given comparator to determine order.
039   *
040   * @param comparator The comparator to use to determine what order to place the elements in this
041   *                   vector.
042   */
043  public SortedVector(Comparator comparator) {
044    m_comparator = comparator;
045  }
046
047  /**
048   * Adds an element in the Vector, sorted from greatest to least.
049   *
050   * @param element The element to add to the Vector
051   */
052  public void addElement(Object element) {
053    int highBound = size();
054    int lowBound = 0;
055    while (highBound - lowBound > 0) {
056      int index = (highBound + lowBound) / 2;
057      int result = m_comparator.compare(element, elementAt(index));
058      if (result < 0) {
059        lowBound = index + 1;
060      } else if (result > 0) {
061        highBound = index;
062      } else {
063        lowBound = index;
064        highBound = index;
065      }
066    }
067    insertElementAt(element, lowBound);
068  }
069
070  /**
071   * Sort the vector.
072   */
073  public void sort() {
074    Object[] array = new Object[size()];
075    copyInto(array);
076    removeAllElements();
077    for (int i = 0; i < array.length; i++) {
078      addElement(array[i]);
079    }
080  }
081}