arraylib.java

来自「用applet实现很多应用小程序」· Java 代码 · 共 1,332 行 · 第 1/3 页

package prefuse.util;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Comparator;
import java.util.Random;
import java.util.StringTokenizer;

/**
 * Library of supplementary array routines not 
 *  supported by the java.util.Arrays class.
 *
 * @author jeffrey heer
 */
public abstract class ArrayLib {
    
    /**
     * Arrays with lengths beneath this value will be insertion sorted.
     */
    public static final int SORT_THRESHOLD = 30;
    
    // ------------------------------------------------------------------------
    // Shuffle
    
    /**
     * Randomly permute the contents of an array.
     * @param a the array to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(int[] a, Random r) {
        shuffle(a, 0, a.length, r);
    }
    
    /**
     * Randomly permute the contents of a range an array.
     * @param a the array to shuffle
     * @param start the starting index of the range to shuffle
     * @param len then length of the range to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(int[] a, int start, int len, Random r) {
        for ( int i=start+len; --i>0; ) {
            int t = a[i], j = r.nextInt(i);
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    /**
     * Randomly permute the contents of an array.
     * @param a the array to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(long[] a, Random r) {
        shuffle(a, 0, a.length, r);
    }
    
    /**
     * Randomly permute the contents of a range an array.
     * @param a the array to shuffle
     * @param start the starting index of the range to shuffle
     * @param len then length of the range to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(long[] a, int start, int len, Random r) {
        for ( int i=start+len; i>1; --i ) {
            long t = a[i];
            int j = r.nextInt(i);
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    /**
     * Randomly permute the contents of an array.
     * @param a the array to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(float[] a, Random r) {
        shuffle(a, 0, a.length, r);
    }
    
    /**
     * Randomly permute the contents of a range an array.
     * @param a the array to shuffle
     * @param start the starting index of the range to shuffle
     * @param len then length of the range to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(float[] a, int start, int len, Random r) {
        for ( int i=start+len; i>1; --i ) {
            float t = a[i];
            int j = r.nextInt(i);
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    /**
     * Randomly permute the contents of an array.
     * @param a the array to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(double[] a, Random r) {
        shuffle(a, 0, a.length, r);
    }
    
    /**
     * Randomly permute the contents of a range an array.
     * @param a the array to shuffle
     * @param start the starting index of the range to shuffle
     * @param len then length of the range to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(double[] a, int start, int len, Random r) {
        for ( int i=start+len; i>1; --i ) {
            double t = a[i];
            int j = r.nextInt(i);
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    /**
     * Randomly permute the contents of an array.
     * @param a the array to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(Object[] a, Random r) {
        shuffle(a, 0, a.length, r);
    }
    
    /**
     * Randomly permute the contents of a range an array.
     * @param a the array to shuffle
     * @param start the starting index of the range to shuffle
     * @param len then length of the range to shuffle
     * @param r the source of randomness to use
     */
    public static final void shuffle(Object[] a, int start, int len, Random r) {
        for ( int i=start+len; i>1; --i ) {
            Object t = a[i];
            int j = r.nextInt(i);
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    // ------------------------------------------------------------------------
    // Max / Min / Sum
    
    /**
     * Find the maximum value in an array.
     * @param a the array
     * @return the maximum value in the array
     */
    public static final double max(double[] a) {
        double max = Double.NEGATIVE_INFINITY;
        for ( int i=0; i<a.length; ++i ) {
            if ( a[i] > max )
                max = a[i];
        }
        return max;
    }

    /**
     * Find the minimum value in an array.
     * @param a the array
     * @return the minimum value in the array
     */
    public static final double min(double[] a) {
        double min = Double.POSITIVE_INFINITY;
        for ( int i=0; i<a.length; ++i ) {
            if ( a[i] < min )
                min = a[i];
        }
        return min;
    }
    
    /**
     * Compute the sum of the values in an array.
     * @param a the array
     * @return the sum of the values in the array
     */
    public static final double sum(double[] a) {
        double sum = 0;
        for ( int i=0; i<a.length; ++i ) {
            sum += a[i];
        }
        return sum;
    }
    
    //// -----------------------------------------------
    //// -- Searching Functions ------------------------

    /**
     * Perform a binary search over a sorted array for the given key.
     * @param a the array to search
     * @param key the key to search for
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(int[] a, int key) {
        int x1 = 0;
        int x2 = a.length;
        int i = x2 / 2;
        while (x1 < x2) {
            if (a[i] == key) {
                return i;
            } else if (a[i] < key) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key. The range is assumed to start at index 0.
     * @param a the array to search
     * @param key the key to search for
     * @param length the the length of the range to search over.
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(int[] a, int key, int length) {
        int x1 = 0;
        int x2 = length;
        int i = x2 / 2;

        while (x1 < x2) {
            if (a[i] == key) {
                return i;
            } else if (a[i] < key) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key.
     * @param a the array to search
     * @param key the key to search for
     * @param begin the starting index of the range
     * @param end the ending index of the range, exclusive
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(int[] a, int key, int begin, int end) {
        int x1 = begin;
        int x2 = end;
        int i = x1 + (x2 - x1) / 2;

        while (x1 < x2) {
            if (a[i] == key) {
                return i;
            } else if (a[i] < key) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }

        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted array for the given key.
     * @param a the array to search
     * @param key the key to search for
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key) {
        int x1 = 0;
        int x2 = a.length;
        int i = x2 / 2, c;
        while (x1 < x2) {
            c = ((Comparable)a[i]).compareTo(key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key. The range is assumed to start at index 0.
     * @param a the array to search
     * @param key the key to search for
     * @param length the the length of the range to search over.
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key, int length) {
        int x1 = 0;
        int x2 = length;
        int i = x2 / 2, c;

        while (x1 < x2) {
            c = ((Comparable)a[i]).compareTo(key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key.
     * @param a the array to search
     * @param key the key to search for
     * @param begin the starting index of the range
     * @param end the ending index of the range, exclusive
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key, int begin, int end) {
        int x1 = begin;
        int x2 = end;
        int i = x1 + (x2 - x1) / 2, c;

        while (x1 < x2) {
            c = ((Comparable)a[i]).compareTo(key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }

        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted array for the given key.
     * @param a the array to search
     * @param key the key to search for
     * @param cp the comparator to use to compare key values
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key, Comparator cp) {
        int x1 = 0;
        int x2 = a.length;
        int i = x2 / 2, c;
        while (x1 < x2) {
            c = cp.compare(a[i], key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key. The range is assumed to start at index 0.
     * @param a the array to search
     * @param key the key to search for
     * @param cp the comparator to use to compare key values
     * @param length the the length of the range to search over.
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key, Comparator cp, int length) {
        int x1 = 0;
        int x2 = length;
        int i = x2 / 2, c;

        while (x1 < x2) {
            c = cp.compare(a[i], key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;
            } else {
                x2 = i;
            }
            i = x1 + (x2 - x1) / 2;
        }
        return -1*(i+1);
    }

    /**
     * Perform a binary search over a sorted range of an array for the given
     * key.
     * @param a the array to search
     * @param key the key to search for
     * @param cp the comparator to use to compare key values
     * @param begin the starting index of the range
     * @param end the ending index of the range, exclusive
     * @return the index of the given key if it exists in the array,
     * otherwise -1 times the index value at the insertion point that
     * would be used if the key were added to the array. 
     */
    public static final int binarySearch(Object[] a, Object key, Comparator cp, int begin, int end) {
        int x1 = begin;
        int x2 = end;
        int i = x1 + (x2 - x1) / 2, c;

        while (x1 < x2) {
            c = cp.compare(a[i], key);
            if (c == 0) {
                return i;
            } else if (c < 0) {
                x1 = i + 1;