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