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    /*----------------------------------------------------------------------------*/
007    package edu.wpi.first.wpilibj.util;
008    
009    import java.util.Vector;
010    
011    /**
012     *
013     * @author dtjones
014     */
015    public 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    }