common
Class Util

java.lang.Object
  common.Util

public class Util
extends java.lang.Object

Provides common utilities to FOMIE programs.

Nested Class Summary

static class

Util.InversePolynomialSampler A sampler of nonnegative reals following an inverse polynomial density 1/((x+\delta)^n), \delta > 0.

Field Summary

static double

TOLERANCE Maximum difference that we are willing to ignore between two floating-point values.

Constructor Summary

Util()

Method Summary

static java.lang.String	abbreviation(java.lang.String description) Given a string description, returns description if its length is no greater than 10, or description + "..." otherwise.
static int	choose(int n, int k) Returns (n choose k) = n! / (n-k)! k!.
static <T> java.util.List<T>	concat(java.util.List<? extends T> list1, java.util.List<? extends T> list2) Returns an unmodifiable list equal to the concatenation of the two given lists.
static <T> java.util.Collection<T>	disjointUnion(java.util.Collection<? extends T> s1, java.util.Collection<? extends T> s2) Returns an unmodifiable collection equal to the union of the two given collections, which are assumed to be disjoint.
static int	factorial(int n) Returns the factorial of n.
static void	fatalError(java.lang.String msg) Prints error message and exits.
static void	fatalError(java.lang.String msg, boolean trace) Prints error message, optionally prints stack trace, and exits.
static void	fatalError(java.lang.Throwable e) Prints the error message and stack trace for the given exception, and exits the program, returning code 1.
static void	fatalError(java.lang.Throwable e, boolean trace) Prints the error message for the given exception, and optionally prints a stack trace.
static void	fatalErrorWithoutStack(java.lang.String msg) Prints error message without printing stack trace, and exits.
static java.lang.Object	findFirst(java.util.Collection c, UnaryFunction f) Returns the first element x in c such that f(x) != null, or null if there is no such element.
static java.lang.Object	findFirst(java.util.Collection c, UnaryPredicate p) Returns the first element x in c satisfying p, or null if there is no such element.
static java.util.Iterator	getAscendingIntegerIterator(int lower) Returns an iterator over the integers greater than or equal to lower, in ascending order.
static java.util.Iterator	getDescendingIntegerIterator(int upper) Returns an iterator over the integers less than or equal to upper, in descending order.
static java.lang.Object	getFirst(java.util.Collection c) Returns the first element in a collection (according to its iterator).
static java.util.Iterator	getIntegerIterator() Returns an iterator over all integers, in order by magnitude, with positive integers coming before negative integers of the same magnitude.
static java.util.Iterator	getIntegerRangeIterator(int lower, int upper) Returns an iterator over the integers in the range from lower to upper, inclusive.
static int	getNumLines(java.io.File file) Returns the number of lines in the given file.
static void	initRandom(boolean randomize) Initializes the random number generator using either the clock time or a fixed seed.
static <T> java.util.Set<T>	intersection(java.util.Set<? extends T> s1, java.util.Set<? extends T> s2) Returns an unmodifiable set equal to the intersection of the two given sets.
static java.lang.String	join(java.lang.String str1, java.lang.String str2) Returns the string formed by concatenating the two given strings, with a space in between if both strings are non-empty.
static double	logFactorial(int n) Returns the log of the factorial of n.
static double	logPartialFactorial(int n, int m) Returns log(n! / (n-m)!), that is, the log of the product of the first m factors in the factorial of n.
static double	logSum(double a, double b) Addition in the log domain.
static double	mean(java.util.Collection values) Returns the mean of a collection of objects assumed to be Numbers.
static int	multichoose(int n, int k) Returns the number of ways to make k choices from a set of n bins, where the same bin may be chosen multiple times.
static java.lang.String	normalize(java.lang.String input) Given a string, returns a version of that string where all letters have been converted to lower case, and all characters that are not letters or digits have been removed.
static int	randInt(int n) Returns a pseudorandom integer sampled uniformly from {0, ..., n-1} Assumes n > 0
static double	random() Returns a pseudorandom number uniformly distributed in the range [0, 1).
static java.util.List	sampleWithoutReplacement(java.util.List list, int n) Returns a list of min(list.size(), n) objects sampled without replacement from list.
static int	sampleWithProbs(double[] probs) Returns an integer in the range {0, ..., probs.length - 1}, according to the distribution specified by probs.
static int	sampleWithWeights(double[] weights, double sum) Returns an integer in the range {0, ..., probs.length - 1}, according to the given weights.
static void	setVerbose(boolean v) Sets a flag indicating whether the program should print extra status messages.
static void	shuffle(java.util.List list) Randomly shuffles the given list, in a way such that all permutations are equally likely.
static boolean	signifGreaterThan(double x, double y) Returns true if x is greater than y by at least Util.TOLERANCE.
static boolean	signifLessThan(double x, double y) Returns true if x is less than y by at least Util.TOLERANCE.
static java.lang.String	spannedSubstring(java.lang.String str, int begin1, int end1, int begin2, int end2) Returns the substring of str from substringPairBegin(begin1, end1, begin2, end2) to substringPairEnd(begin1, end1, begin2, end2).
static int	substringPairBegin(int begin1, int end1, int begin2, int end2) Given two substrings defined by "begin" and "end" indices in some original string, returns the index of the first character that is in either of these two strings, or 0 if both strings are empty.
static int	substringPairEnd(int begin1, int end1, int begin2, int end2) Given two substrings defined by "begin" and "end" indices in some original string, returns one plus the index of the last character that is in one of these two strings, or 0 if both strings are empty.
static SetWithDistrib	uniformDistrib(IndexedSet s)
static java.lang.Object	uniformSample(java.util.Set set) Uniformly sample from a set.
static double	variance(java.util.Collection values) Returns the variance of a collection of objects assumed to be Numbers.
static boolean	verbose() Returns true if the program should print extra status messages.
static boolean	withinTol(double x, double y) Returns true if the two given values differ by no more than Util.TOLERANCE.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

TOLERANCE

public static final double TOLERANCE

Maximum difference that we are willing to ignore between two floating-point values. For instance, the sum of some probabilities may not be exactly 1.0, but this may just be due to floating-point inaccuracies, so we may want to consider it "close enough" to 1.0.

See Also:

Constant Field Values

Constructor Detail

Util

public Util()

Method Detail

initRandom

public static void initRandom(boolean randomize)

Initializes the random number generator using either the clock time or a fixed seed. If the fixed seed is used, the behavior of the program will be repeatable across runs.

Parameters:

randomize - set seed using clock time rather than fixed value

uniformSample

public static java.lang.Object uniformSample(java.util.Set set)

Uniformly sample from a set.

random

public static double random()

Returns a pseudorandom number uniformly distributed in the range [0, 1). This method must not be called before initRandom() is called.

randInt

public static int randInt(int n)

Returns a pseudorandom integer sampled uniformly from {0, ..., n-1} Assumes n > 0

sampleWithProbs

public static int sampleWithProbs(double[] probs)

Returns an integer in the range {0, ..., probs.length - 1}, according to the distribution specified by probs. If probs has length 0, returns -1.

sampleWithWeights

public static int sampleWithWeights(double[] weights,
                                    double sum)

Returns an integer in the range {0, ..., probs.length - 1}, according to the given weights. If weights has length 0, returns -1.

sampleWithoutReplacement

public static java.util.List sampleWithoutReplacement(java.util.List list,
                                                      int n)

Returns a list of min(list.size(), n) objects sampled without replacement from list.

shuffle

public static void shuffle(java.util.List list)

Randomly shuffles the given list, in a way such that all permutations are equally likely.

logPartialFactorial

public static double logPartialFactorial(int n,
                                         int m)

Returns log(n! / (n-m)!), that is, the log of the product of the first m factors in the factorial of n.

factorial

public static int factorial(int n)

Returns the factorial of n.

logFactorial

public static double logFactorial(int n)

Returns the log of the factorial of n. This may be faster than just calling Math.log(Util.factorial(n)).

choose

public static int choose(int n,
                         int k)

Returns (n choose k) = n! / (n-k)! k!.

multichoose

public static int multichoose(int n,
                              int k)

Returns the number of ways to make k choices from a set of n bins, where the same bin may be chosen multiple times. This is (n + k - 1) choose (n - 1).

logSum

public static double logSum(double a,
                            double b)

Addition in the log domain. Returns an approximation to ln(e^a + e^b). Just doing it naively might lead to underflow if a and b are very negative. Without loss of generality, let b-10, calculates it in the standard way. Otherwise, rewrite it as a + ln(1 + e^(b-a)) and approximate that by the first-order Taylor expansion to be a + (e^(b-a)). So if b is much smaller than a, there will still be underflow in the last term, but in that case, the error is small relative to the final answer.

withinTol

public static boolean withinTol(double x,
                                double y)

Returns true if the two given values differ by no more than Util.TOLERANCE.

signifGreaterThan

public static boolean signifGreaterThan(double x,
                                        double y)

Returns true if x is greater than y by at least Util.TOLERANCE.

signifLessThan

public static boolean signifLessThan(double x,
                                     double y)

Returns true if x is less than y by at least Util.TOLERANCE.

fatalError

public static void fatalError(java.lang.Throwable e)

Prints the error message and stack trace for the given exception, and exits the program, returning code 1.

fatalError

public static void fatalError(java.lang.Throwable e,
                              boolean trace)

Prints the error message for the given exception, and optionally prints a stack trace. Then exits the program with return code 1.

fatalError

public static void fatalError(java.lang.String msg)

Prints error message and exits.

Parameters:

msg - the error message

fatalError

public static void fatalError(java.lang.String msg,
                              boolean trace)

Prints error message, optionally prints stack trace, and exits.

Parameters:

msg - the error message

trace - if true, print a stack trace

fatalErrorWithoutStack

public static void fatalErrorWithoutStack(java.lang.String msg)

Prints error message without printing stack trace, and exits.

Parameters:

msg - the error message

verbose

public static boolean verbose()

Returns true if the program should print extra status messages. This value is false unless it has been set to true using setVerbose.

setVerbose

public static void setVerbose(boolean v)

Sets a flag indicating whether the program should print extra status messages. If this message is not called, the flag defaults to false.

substringPairBegin

public static int substringPairBegin(int begin1,
                                     int end1,
                                     int begin2,
                                     int end2)

Given two substrings defined by "begin" and "end" indices in some original string, returns the index of the first character that is in either of these two strings, or 0 if both strings are empty.

Parameters:

begin1 - index of first char in substring 1

end1 - one plus index of last char in substring 1

begin2 - index of first char in substring 2

end2 - one plus index of last char in substring 2

spannedSubstring

public static java.lang.String spannedSubstring(java.lang.String str,
                                                int begin1,
                                                int end1,
                                                int begin2,
                                                int end2)

Returns the substring of str from substringPairBegin(begin1, end1, begin2, end2) to substringPairEnd(begin1, end1, begin2, end2).

substringPairEnd

public static int substringPairEnd(int begin1,
                                   int end1,
                                   int begin2,
                                   int end2)

Given two substrings defined by "begin" and "end" indices in some original string, returns one plus the index of the last character that is in one of these two strings, or 0 if both strings are empty.

Parameters:

begin1 - index of first char in substring 1

end1 - one plus index of last char in substring 1

begin2 - index of first char in substring 2

end2 - one plus index of last char in substring 2

join

public static java.lang.String join(java.lang.String str1,
                                    java.lang.String str2)

Returns the string formed by concatenating the two given strings, with a space in between if both strings are non-empty.

normalize

public static java.lang.String normalize(java.lang.String input)

Given a string, returns a version of that string where all letters have been converted to lower case, and all characters that are not letters or digits have been removed.

concat

public static <T> java.util.List<T> concat(java.util.List<? extends T> list1,
                                           java.util.List<? extends T> list2)

Returns an unmodifiable list equal to the concatenation of the two given lists.

disjointUnion

public static <T> java.util.Collection<T> disjointUnion(java.util.Collection<? extends T> s1,
                                                        java.util.Collection<? extends T> s2)

Returns an unmodifiable collection equal to the union of the two given collections, which are assumed to be disjoint. The iteration order is the iteration order of s1 followed by the iteration order of s2.

intersection

public static <T> java.util.Set<T> intersection(java.util.Set<? extends T> s1,
                                                java.util.Set<? extends T> s2)

Returns an unmodifiable set equal to the intersection of the two given sets.

uniformDistrib

public static SetWithDistrib uniformDistrib(IndexedSet s)

getNumLines

public static int getNumLines(java.io.File file)
                       throws java.io.IOException

Returns the number of lines in the given file. This is the number of times that BufferedReader's readLine method can be called on this file before it returns null.

Throws:

java.io.IOException

getIntegerRangeIterator

public static java.util.Iterator getIntegerRangeIterator(int lower,
                                                         int upper)

Returns an iterator over the integers in the range from lower to upper, inclusive. The iterator returns integers in ascending order. If lower is greater than upper, the iterator has no elements.

Returns:

Iterator over Integer

getAscendingIntegerIterator

public static java.util.Iterator getAscendingIntegerIterator(int lower)

Returns an iterator over the integers greater than or equal to lower, in ascending order. This iterator uses the mathematical rather than the computational notion of an integer, so its hasNext method never returns false, even when it has already iterated over Integer.MAX_VALUE. If this iterator's next method is called enough times, it will eventually throw an ArithmeticException indicating that the next integer cannot be represented.

Returns:

Iterator over Integer

getDescendingIntegerIterator

public static java.util.Iterator getDescendingIntegerIterator(int upper)

Returns an iterator over the integers less than or equal to upper, in descending order. This iterator uses the mathematical rather than the computational notion of an integer, so its hasNext method never returns false, even when it has already iterated over Integer.MIN_VALUE. If this iterator's next method is called enough times, it will eventually throw an ArithmeticException indicating that the next integer cannot be represented.

Returns:

Iterator over Integer

getIntegerIterator

public static java.util.Iterator getIntegerIterator()

Returns an iterator over all integers, in order by magnitude, with positive integers coming before negative integers of the same magnitude. The iterator uses the mathematical rather than computational notion of an integer, so its hasNext method always returns true, even when Integer.MAX_VALUE has already been returned (note that Integer.MAX_VALUE has a smaller magnitude than Integer.MIN_VALUE, so it will be reached first). If the iterator's next method is called enough times, it will eventually throw an ArithmeticException indicating that the next integer is not representable.

Returns:

Iterator over Integer

findFirst

public static java.lang.Object findFirst(java.util.Collection c,
                                         UnaryFunction f)

Returns the first element x in c such that f(x) != null, or null if there is no such element.

findFirst

public static java.lang.Object findFirst(java.util.Collection c,
                                         UnaryPredicate p)

Returns the first element x in c satisfying p, or null if there is no such element.

getFirst

public static java.lang.Object getFirst(java.util.Collection c)

Returns the first element in a collection (according to its iterator).

Throws:

java.util.NoSuchElementException - if collection is empty.

abbreviation

public static java.lang.String abbreviation(java.lang.String description)

Given a string description, returns description if its length is no greater than 10, or description + "..." otherwise.

mean

public static double mean(java.util.Collection values)

Returns the mean of a collection of objects assumed to be Numbers.

variance

public static double variance(java.util.Collection values)

Returns the variance of a collection of objects assumed to be Numbers.