http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/jet/random/sampling/RandomSampler.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/jet/random/sampling/RandomSampler.java b/math/src/main/java/org/apache/mahout/math/jet/random/sampling/RandomSampler.java deleted file mode 100644 index 6804547..0000000 --- a/math/src/main/java/org/apache/mahout/math/jet/random/sampling/RandomSampler.java +++ /dev/null @@ -1,503 +0,0 @@ -/* -Copyright � 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.jet.random.sampling; - -import org.apache.mahout.common.RandomUtils; - -import java.util.Random; - -/** - * Space and time efficiently computes a sorted <i>Simple Random Sample Without Replacement - * (SRSWOR)</i>, that is, a sorted set of <tt>n</tt> random numbers from an interval of <tt>N</tt> numbers; - * Example: Computing <tt>n=3</tt> random numbers from the interval <tt>[1,50]</tt> may yield - * the sorted random set <tt>(7,13,47)</tt>. - * Since we are talking about a set (sampling without replacement), no element will occur more than once. - * Each number from the <tt>N</tt> numbers has the same probability to be included in the <tt>n</tt> chosen numbers. - * - * <p><b>Problem:</b> This class solves problems including the following: <i> - * Suppose we have a file containing 10^12 objects. - * We would like to take a truly random subset of 10^6 objects and do something with it, - * for example, compute the sum over some instance field, or whatever. - * How do we choose the subset? In particular, how do we avoid multiple equal elements? - * How do we do this quick and without consuming excessive memory? - * How do we avoid slowly jumping back and forth within the file? </i> - * - * <p><b>Sorted Simple Random Sample Without Replacement (SRSWOR):</b> - * What are the exact semantics of this class? What is a SRSWOR? In which sense exactly is a returned set "random"? - * It is random in the sense, that each number from the <tt>N</tt> numbers has the - * same probability to be included in the <tt>n</tt> chosen numbers. - * For those who think in implementations rather than abstract interfaces: - * <i>Suppose, we have an empty list. - * We pick a random number between 1 and 10^12 and add it to the list only if it was not - * already picked before, i.e. if it is not already contained in the list. - * We then do the same thing again and again until we have eventually collected 10^6 distinct numbers. - * Now we sort the set ascending and return it.</i> - * <dl> - * <dt>It is exactly in this sense that this class returns "random" sets. - * <b>Note, however, that the implementation of this class uses a technique orders of magnitudes - * better (both in time and space) than the one outlined above.</b></dt></dl> - * - * <p><b>Performance:</b> Space requirements are zero. Running time is <tt>O(n)</tt> on average, - * <tt>O(N)</tt> in the worst case. - * <h2>Performance (200Mhz Pentium Pro, JDK 1.2, NT)</h2> - * <center> - * <table border="1" summary="performance table"> - * <tr> - * <td align="center" width="20%">n</td> - * <td align="center" width="20%">N</td> - * <td align="center" width="20%">Speed [seconds]</td> - * </tr> - * <tr> - * <td align="center" width="20%">10<sup>3</sup></td> - * <td align="center" width="20%">1.2*10<sup>3</sup></td> - * <td align="center" width="20">0.0014</td> - * </tr> - * <tr> - * <td align="center" width="20%">10<sup>3</sup></td> - * <td align="center" width="20%">10<sup>7</sup></td> - * <td align="center" width="20">0.006</td> - * </tr> - * <tr> - * <td align="center" width="20%">10<sup>5</sup></td> - * <td align="center" width="20%">10<sup>7</sup></td> - * <td align="center" width="20">0.7</td> - * </tr> - * <tr> - * <td align="center" width="20%">9.0*10<sup>6</sup></td> - * <td align="center" width="20%">10<sup>7</sup></td> - * <td align="center" width="20">8.5</td> - * </tr> - * <tr> - * <td align="center" width="20%">9.9*10<sup>6</sup></td> - * <td align="center" width="20%">10<sup>7</sup></td> - * <td align="center" width="20">2.0 (samples more than 95%)</td> - * </tr> - * <tr> - * <td align="center" width="20%">10<sup>4</sup></td> - * <td align="center" width="20%">10<sup>12</sup></td> - * <td align="center" width="20">0.07</td> - * </tr> - * <tr> - * <td align="center" width="20%">10<sup>7</sup></td> - * <td align="center" width="20%">10<sup>12</sup></td> - * <td align="center" width="20">60</td> - * </tr> - * </table> - * </center> - * - * <p><b>Scalability:</b> This random sampler is designed to be scalable. In iterator style, - * it is able to compute and deliver sorted random sets stepwise in units called <i>blocks</i>. - * Example: Computing <tt>n=9</tt> random numbers from the interval <tt>[1,50]</tt> in - * 3 blocks may yield the blocks <tt>(7,13,14), (27,37,42), (45,46,49)</tt>. - * (The maximum of a block is guaranteed to be less than the minimum of its successor block. - * Every block is sorted ascending. No element will ever occur twice, both within a block and among blocks.) - * A block can be computed and retrieved with method <tt>nextBlock</tt>. - * Successive calls to method <tt>nextBlock</tt> will deliver as many random numbers as required. - * - * <p>Computing and retrieving samples in blocks is useful if you need very many random - * numbers that cannot be stored in main memory at the same time. - * For example, if you want to compute 10^10 such numbers you can do this by computing - * them in blocks of, say, 500 elements each. - * You then need only space to keep one block of 500 elements (i.e. 4 KB). - * When you are finished processing the first 500 elements you call <tt>nextBlock</tt> to - * fill the next 500 elements into the block, process them, and so on. - * If you have the time and need, by using such blocks you can compute random sets - * up to <tt>n=10^19</tt> random numbers. - * - * <p>If you do not need the block feature, you can also directly call - * the static methods of this class without needing to construct a <tt>RandomSampler</tt> instance first. - * - * <p><b>Random number generation:</b> By default uses <tt>MersenneTwister</tt>, a very - * strong random number generator, much better than <tt>java.util.Random</tt>. - * You can also use other strong random number generators of Paul Houle's RngPack package. - * For example, <tt>Ranecu</tt>, <tt>Ranmar</tt> and <tt>Ranlux</tt> are strong well - * analyzed research grade pseudo-random number generators with known periods. - * - * <p><b>Implementation:</b> after J.S. Vitter, An Efficient Algorithm for Sequential Random Sampling, - * ACM Transactions on Mathematical Software, Vol 13, 1987. - * Paper available <A HREF="http://www.cs.duke.edu/~jsv";> here</A>. - */ -public final class RandomSampler { - - private RandomSampler() { - } - - /** - * Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>. Since - * we are talking about a random set, no element will occur more than once. - * - * <p>Running time is <tt>O(count)</tt>, on average. Space requirements are zero. - * - * <p>Numbers are filled into the specified array starting at index <tt>fromIndex</tt> to the right. The array is - * returned sorted ascending in the range filled with numbers. - * - * @param n the total number of elements to choose (must be >= 0). - * @param N the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. - * @param count the number of elements to be filled into <tt>values</tt> by this call (must be >= 0 and - * <=<tt>n</tt>). Normally, you will set <tt>count=n</tt>. - * @param low the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. Hint: If - * <tt>low==0</tt>, then draws random numbers from the interval <tt>[0,N-1]</tt>. - * @param values the array into which the random numbers are to be filled; must have a length <tt>>= - * count+fromIndex</tt>. - * @param fromIndex the first index within <tt>values</tt> to be filled with numbers (inclusive). - * @param randomGenerator a random number generator. - */ - private static void rejectMethodD(long n, long N, int count, long low, long[] values, int fromIndex, - Random randomGenerator) { - /* This algorithm is applicable if a large percentage (90%..100%) of N shall be sampled. - In such cases it is more efficient than sampleMethodA() and sampleMethodD(). - The idea is that it is more efficient to express - sample(n,N,count) in terms of reject(N-n,N,count) - and then invert the result. - For example, sampling 99% turns into sampling 1% plus inversion. - - This algorithm is the same as method sampleMethodD(...) with the exception that sampled elements are rejected, - and not sampled elements included in the result set. - */ - n = N - n; // IMPORTANT !!! - - //long threshold; - long chosen = -1 + low; - - //long negalphainv = - // -13; //tuning paramter, determines when to switch from method D to method A. Dependent on programming - // language, platform, etc. - - double nreal = n; - double ninv = 1.0 / nreal; - double Nreal = N; - double Vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - long qu1 = -n + 1 + N; - double qu1real = -nreal + 1.0 + Nreal; - //threshold = -negalphainv * n; - - long S; - while (n > 1 && count > 0) { //&& threshold<N) { - double nmin1inv = 1.0 / (-1.0 + nreal); - double negSreal; - while (true) { - double X; - while (true) { // step D2: generate U and X - X = Nreal * (-Vprime + 1.0); - S = (long) X; - if (S < qu1) { - break; - } - Vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - } - double U = randomGenerator.nextDouble(); - negSreal = -S; - - //step D3: Accept? - double y1 = Math.exp(Math.log(U * Nreal / qu1real) * nmin1inv); - Vprime = y1 * (-X / Nreal + 1.0) * qu1real / (negSreal + qu1real); - if (Vprime <= 1.0) { - break; - } //break inner loop - - //step D4: Accept? - double top = -1.0 + Nreal; - long limit; - double bottom; - if (n - 1 > S) { - bottom = -nreal + Nreal; - limit = -S + N; - } else { - bottom = -1.0 + negSreal + Nreal; - limit = qu1; - } - double y2 = 1.0; - for (long t = N - 1; t >= limit; t--) { - y2 *= top / bottom; - top--; - bottom--; - } - if (Nreal / (-X + Nreal) >= y1 * Math.exp(Math.log(y2) * nmin1inv)) { - // accept ! - Vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * nmin1inv); - break; //break inner loop - } - Vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - } - - //step D5: reject the (S+1)st record ! - int iter = count; //int iter = (int) (Math.min(S,count)); - if (S < iter) { - iter = (int) S; - } - - count -= iter; - while (--iter >= 0) { - values[fromIndex++] = ++chosen; - } - chosen++; - - N -= S + 1; - Nreal = negSreal - 1.0 + Nreal; - n--; - nreal--; - ninv = nmin1inv; - qu1 = -S + qu1; - qu1real = negSreal + qu1real; - //threshold += negalphainv; - } //end while - - - if (count > 0) { //special case n==1 - //reject the (S+1)st record ! - S = (long) (N * Vprime); - - int iter = count; //int iter = (int) (Math.min(S,count)); - if (S < iter) { - iter = (int) S; - } - - count -= iter; - while (--iter >= 0) { - values[fromIndex++] = ++chosen; - } - - chosen++; - - // fill the rest - while (--count >= 0) { - values[fromIndex++] = ++chosen; - } - } - } - - /** - * Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>. Since - * we are talking about a random set, no element will occur more than once. - * - * <p>Running time is <tt>O(count)</tt>, on average. Space requirements are zero. - * - * <p>Numbers are filled into the specified array starting at index <tt>fromIndex</tt> to the right. The array is - * returned sorted ascending in the range filled with numbers. - * - * <p><b>Random number generation:</b> By default uses <tt>MersenneTwister</tt>, a very strong random number - * generator, much better than <tt>java.util.Random</tt>. You can also use other strong random number generators of - * Paul Houle's RngPack package. For example, <tt>Ranecu</tt>, <tt>Ranmar</tt> and <tt>Ranlux</tt> are strong well - * analyzed research grade pseudo-random number generators with known periods. - * - * @param n the total number of elements to choose (must be <tt>n >= 0</tt> and <tt>n <= N</tt>). - * @param N the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. - * @param count the number of elements to be filled into <tt>values</tt> by this call (must be >= 0 and - * <=<tt>n</tt>). Normally, you will set <tt>count=n</tt>. - * @param low the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. Hint: If - * <tt>low==0</tt>, then draws random numbers from the interval <tt>[0,N-1]</tt>. - * @param values the array into which the random numbers are to be filled; must have a length <tt>>= - * count+fromIndex</tt>. - * @param fromIndex the first index within <tt>values</tt> to be filled with numbers (inclusive). - * @param randomGenerator a random number generator. Set this parameter to <tt>null</tt> to use the default random - * number generator. - */ - public static void sample(long n, long N, int count, long low, long[] values, int fromIndex, - Random randomGenerator) { - if (n <= 0 || count <= 0) { - return; - } - if (count > n) { - throw new IllegalArgumentException("count must not be greater than n"); - } - if (randomGenerator == null) { - randomGenerator = RandomUtils.getRandom(); - } - - if (count == N) { // rare case treated quickly - long val = low; - int limit = fromIndex + count; - for (int i = fromIndex; i < limit; i++) { - values[i] = val++; - } - return; - } - - if (n < N * 0.95) { // || Math.min(count,N-n)>maxTmpMemoryAllowed) { - sampleMethodD(n, N, count, low, values, fromIndex, randomGenerator); - } else { // More than 95% of all numbers shall be sampled. - rejectMethodD(n, N, count, low, values, fromIndex, randomGenerator); - } - - - } - - /** - * Computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>. Since we are - * talking about a random set, no element will occur more than once. - * - * <p>Running time is <tt>O(N)</tt>, on average. Space requirements are zero. - * - * <p>Numbers are filled into the specified array starting at index <tt>fromIndex</tt> to the right. The array is - * returned sorted ascending in the range filled with numbers. - * - * @param n the total number of elements to choose (must be >= 0). - * @param N the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. - * @param count the number of elements to be filled into <tt>values</tt> by this call (must be >= 0 and - * <=<tt>n</tt>). Normally, you will set <tt>count=n</tt>. - * @param low the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. Hint: If - * <tt>low==0</tt>, then draws random numbers from the interval <tt>[0,N-1]</tt>. - * @param values the array into which the random numbers are to be filled; must have a length <tt>>= - * count+fromIndex</tt>. - * @param fromIndex the first index within <tt>values</tt> to be filled with numbers (inclusive). - * @param randomGenerator a random number generator. - */ - private static void sampleMethodA(long n, long N, int count, long low, long[] values, int fromIndex, - Random randomGenerator) { - long chosen = -1 + low; - - double top = N - n; - double Nreal = N; - long S; - while (n >= 2 && count > 0) { - double V = randomGenerator.nextDouble(); - S = 0; - double quot = top / Nreal; - while (quot > V) { - S++; - top--; - Nreal--; - quot *= top / Nreal; - } - chosen += S + 1; - values[fromIndex++] = chosen; - count--; - Nreal--; - n--; - } - - if (count > 0) { - // special case n==1 - S = (long) (Math.round(Nreal) * randomGenerator.nextDouble()); - chosen += S + 1; - values[fromIndex] = chosen; - } - } - - /** - * Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>. Since - * we are talking about a random set, no element will occur more than once. - * - * <p>Running time is <tt>O(count)</tt>, on average. Space requirements are zero. - * - * <p>Numbers are filled into the specified array starting at index <tt>fromIndex</tt> to the right. The array is - * returned sorted ascending in the range filled with numbers. - * - * @param n the total number of elements to choose (must be >= 0). - * @param N the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. - * @param count the number of elements to be filled into <tt>values</tt> by this call (must be >= 0 and - * <=<tt>n</tt>). Normally, you will set <tt>count=n</tt>. - * @param low the interval to choose random numbers from is <tt>[low,low+N-1]</tt>. Hint: If - * <tt>low==0</tt>, then draws random numbers from the interval <tt>[0,N-1]</tt>. - * @param values the array into which the random numbers are to be filled; must have a length <tt>>= - * count+fromIndex</tt>. - * @param fromIndex the first index within <tt>values</tt> to be filled with numbers (inclusive). - * @param randomGenerator a random number generator. - */ - private static void sampleMethodD(long n, long N, int count, long low, long[] values, int fromIndex, - Random randomGenerator) { - long chosen = -1 + low; - - double nreal = n; - double ninv = 1.0 / nreal; - double Nreal = N; - double vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - long qu1 = -n + 1 + N; - double qu1real = -nreal + 1.0 + Nreal; - long negalphainv = -13; - //tuning paramter, determines when to switch from method D to method A. Dependent on programming - // language, platform, etc. - long threshold = -negalphainv * n; - - long S; - while (n > 1 && count > 0 && threshold < N) { - double nmin1inv = 1.0 / (-1.0 + nreal); - double negSreal; - while (true) { - double X; - while (true) { // step D2: generate U and X - X = Nreal * (-vprime + 1.0); - S = (long) X; - if (S < qu1) { - break; - } - vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - } - double U = randomGenerator.nextDouble(); - negSreal = -S; - - //step D3: Accept? - double y1 = Math.exp(Math.log(U * Nreal / qu1real) * nmin1inv); - vprime = y1 * (-X / Nreal + 1.0) * qu1real / (negSreal + qu1real); - if (vprime <= 1.0) { - break; - } //break inner loop - - //step D4: Accept? - double top = -1.0 + Nreal; - long limit; - double bottom; - if (n - 1 > S) { - bottom = -nreal + Nreal; - limit = -S + N; - } else { - bottom = -1.0 + negSreal + Nreal; - limit = qu1; - } - double y2 = 1.0; - for (long t = N - 1; t >= limit; t--) { - y2 *= top / bottom; - top--; - bottom--; - } - if (Nreal / (-X + Nreal) >= y1 * Math.exp(Math.log(y2) * nmin1inv)) { - // accept ! - vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * nmin1inv); - break; //break inner loop - } - vprime = Math.exp(Math.log(randomGenerator.nextDouble()) * ninv); - } - - //step D5: select the (S+1)st record ! - chosen += S + 1; - values[fromIndex++] = chosen; - /* - // invert - for (int iter=0; iter<S && count > 0; iter++) { - values[fromIndex++] = ++chosen; - count--; - } - chosen++; - */ - count--; - - N -= S + 1; - Nreal = negSreal - 1.0 + Nreal; - n--; - nreal--; - ninv = nmin1inv; - qu1 = -S + qu1; - qu1real = negSreal + qu1real; - threshold += negalphainv; - } //end while - - - if (count > 0) { - if (n > 1) { //faster to use method A to finish the sampling - sampleMethodA(n, N, count, chosen + 1, values, fromIndex, randomGenerator); - } else { - //special case n==1 - S = (long) (N * vprime); - chosen += S + 1; - values[fromIndex++] = chosen; - } - } - } - -}
http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/jet/stat/Gamma.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/jet/stat/Gamma.java b/math/src/main/java/org/apache/mahout/math/jet/stat/Gamma.java deleted file mode 100644 index 3ab61a6..0000000 --- a/math/src/main/java/org/apache/mahout/math/jet/stat/Gamma.java +++ /dev/null @@ -1,681 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.jet.stat; - -import org.apache.mahout.math.jet.math.Constants; -import org.apache.mahout.math.jet.math.Polynomial; - -/** Partially deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */ -public final class Gamma { - - private static final double MAXSTIR = 143.01608; - - private Gamma() { - } - - /** - * Returns the beta function of the arguments. - * <pre> - * - - - * | (a) | (b) - * beta( a, b ) = -----------. - * - - * | (a+b) - * </pre> - * @param alpha - * @param beta - * @return The beta function for given values of alpha and beta. - */ - public static double beta(double alpha, double beta) { - double y; - if (alpha < 40 && beta < 40) { - y = gamma(alpha + beta); - if (y == 0.0) { - return 1.0; - } - - if (alpha > beta) { - y = gamma(alpha) / y; - y *= gamma(beta); - } else { - y = gamma(beta) / y; - y *= gamma(alpha); - } - } else { - y = Math.exp(logGamma(alpha) + logGamma(beta) - logGamma(alpha + beta)); - } - - return y; - } - - /** Returns the Gamma function of the argument. */ - public static double gamma(double x) { - - double[] pCoefficient = { - 1.60119522476751861407E-4, - 1.19135147006586384913E-3, - 1.04213797561761569935E-2, - 4.76367800457137231464E-2, - 2.07448227648435975150E-1, - 4.94214826801497100753E-1, - 9.99999999999999996796E-1 - }; - double[] qCoefficient = { - -2.31581873324120129819E-5, - 5.39605580493303397842E-4, - -4.45641913851797240494E-3, - 1.18139785222060435552E-2, - 3.58236398605498653373E-2, - -2.34591795718243348568E-1, - 7.14304917030273074085E-2, - 1.00000000000000000320E0 - }; -//double MAXGAM = 171.624376956302725; -//double LOGPI = 1.14472988584940017414; - - double p; - double z; - - double q = Math.abs(x); - - if (q > 33.0) { - if (x < 0.0) { - p = Math.floor(q); - if (p == q) { - throw new ArithmeticException("gamma: overflow"); - } - //int i = (int) p; - z = q - p; - if (z > 0.5) { - p += 1.0; - z = q - p; - } - z = q * Math.sin(Math.PI * z); - if (z == 0.0) { - throw new ArithmeticException("gamma: overflow"); - } - z = Math.abs(z); - z = Math.PI / (z * stirlingFormula(q)); - - return -z; - } else { - return stirlingFormula(x); - } - } - - z = 1.0; - while (x >= 3.0) { - x -= 1.0; - z *= x; - } - - while (x < 0.0) { - if (x == 0.0) { - throw new ArithmeticException("gamma: singular"); - } - if (x > -1.0e-9) { - return z / ((1.0 + 0.5772156649015329 * x) * x); - } - z /= x; - x += 1.0; - } - - while (x < 2.0) { - if (x == 0.0) { - throw new ArithmeticException("gamma: singular"); - } - if (x < 1.0e-9) { - return z / ((1.0 + 0.5772156649015329 * x) * x); - } - z /= x; - x += 1.0; - } - - if ((x == 2.0) || (x == 3.0)) { - return z; - } - - x -= 2.0; - p = Polynomial.polevl(x, pCoefficient, 6); - q = Polynomial.polevl(x, qCoefficient, 7); - return z * p / q; - - } - - /** - * Returns the regularized Incomplete Beta Function evaluated from zero to <tt>xx</tt>; formerly named <tt>ibeta</tt>. - * - * See http://en.wikipedia.org/wiki/Incomplete_beta_function#Incomplete_beta_function - * - * @param alpha the alpha parameter of the beta distribution. - * @param beta the beta parameter of the beta distribution. - * @param xx the integration end point. - */ - public static double incompleteBeta(double alpha, double beta, double xx) { - - if (alpha <= 0.0) { - throw new ArithmeticException("incompleteBeta: Domain error! alpha must be > 0, but was " + alpha); - } - - if (beta <= 0.0) { - throw new ArithmeticException("incompleteBeta: Domain error! beta must be > 0, but was " + beta); - } - - if (xx <= 0.0) { - return 0.0; - } - - if (xx >= 1.0) { - return 1.0; - } - - double t; - if ((beta * xx) <= 1.0 && xx <= 0.95) { - t = powerSeries(alpha, beta, xx); - return t; - } - - double w = 1.0 - xx; - - /* Reverse a and b if x is greater than the mean. */ - double xc; - double x; - double b; - double a; - boolean flag = false; - if (xx > (alpha / (alpha + beta))) { - flag = true; - a = beta; - b = alpha; - xc = xx; - x = w; - } else { - a = alpha; - b = beta; - xc = w; - x = xx; - } - - if (flag && (b * x) <= 1.0 && x <= 0.95) { - t = powerSeries(a, b, x); - t = t <= Constants.MACHEP ? 1.0 - Constants.MACHEP : 1.0 - t; - return t; - } - - /* Choose expansion for better convergence. */ - double y = x * (a + b - 2.0) - (a - 1.0); - w = y < 0.0 ? incompleteBetaFraction1(a, b, x) : incompleteBetaFraction2(a, b, x) / xc; - - /* Multiply w by the factor - a b _ _ _ - x (1-x) | (a+b) / ( a | (a) | (b) ) . */ - - y = a * Math.log(x); - t = b * Math.log(xc); - if ((a + b) < Constants.MAXGAM && Math.abs(y) < Constants.MAXLOG && Math.abs(t) < Constants.MAXLOG) { - t = Math.pow(xc, b); - t *= Math.pow(x, a); - t /= a; - t *= w; - t *= gamma(a + b) / (gamma(a) * gamma(b)); - if (flag) { - t = t <= Constants.MACHEP ? 1.0 - Constants.MACHEP : 1.0 - t; - } - return t; - } - /* Resort to logarithms. */ - y += t + logGamma(a + b) - logGamma(a) - logGamma(b); - y += Math.log(w / a); - t = y < Constants.MINLOG ? 0.0 : Math.exp(y); - - if (flag) { - t = t <= Constants.MACHEP ? 1.0 - Constants.MACHEP : 1.0 - t; - } - return t; - } - - /** Continued fraction expansion #1 for incomplete beta integral; formerly named <tt>incbcf</tt>. */ - static double incompleteBetaFraction1(double a, double b, double x) { - - double k1 = a; - double k2 = a + b; - double k3 = a; - double k4 = a + 1.0; - double k5 = 1.0; - double k6 = b - 1.0; - double k7 = k4; - double k8 = a + 2.0; - - double pkm2 = 0.0; - double qkm2 = 1.0; - double pkm1 = 1.0; - double qkm1 = 1.0; - double ans = 1.0; - double r = 1.0; - int n = 0; - double thresh = 3.0 * Constants.MACHEP; - do { - double xk = -(x * k1 * k2) / (k3 * k4); - double pk = pkm1 + pkm2 * xk; - double qk = qkm1 + qkm2 * xk; - pkm2 = pkm1; - pkm1 = pk; - qkm2 = qkm1; - qkm1 = qk; - - xk = (x * k5 * k6) / (k7 * k8); - pk = pkm1 + pkm2 * xk; - qk = qkm1 + qkm2 * xk; - pkm2 = pkm1; - pkm1 = pk; - qkm2 = qkm1; - qkm1 = qk; - - if (qk != 0) { - r = pk / qk; - } - double t; - if (r != 0) { - t = Math.abs((ans - r) / r); - ans = r; - } else { - t = 1.0; - } - - if (t < thresh) { - return ans; - } - - k1 += 1.0; - k2 += 1.0; - k3 += 2.0; - k4 += 2.0; - k5 += 1.0; - k6 -= 1.0; - k7 += 2.0; - k8 += 2.0; - - if ((Math.abs(qk) + Math.abs(pk)) > Constants.BIG) { - pkm2 *= Constants.BIG_INVERSE; - pkm1 *= Constants.BIG_INVERSE; - qkm2 *= Constants.BIG_INVERSE; - qkm1 *= Constants.BIG_INVERSE; - } - if ((Math.abs(qk) < Constants.BIG_INVERSE) || (Math.abs(pk) < Constants.BIG_INVERSE)) { - pkm2 *= Constants.BIG; - pkm1 *= Constants.BIG; - qkm2 *= Constants.BIG; - qkm1 *= Constants.BIG; - } - } while (++n < 300); - - return ans; - } - - /** Continued fraction expansion #2 for incomplete beta integral; formerly named <tt>incbd</tt>. */ - static double incompleteBetaFraction2(double a, double b, double x) { - - double k1 = a; - double k2 = b - 1.0; - double k3 = a; - double k4 = a + 1.0; - double k5 = 1.0; - double k6 = a + b; - double k7 = a + 1.0; - double k8 = a + 2.0; - - double pkm2 = 0.0; - double qkm2 = 1.0; - double pkm1 = 1.0; - double qkm1 = 1.0; - double z = x / (1.0 - x); - double ans = 1.0; - double r = 1.0; - int n = 0; - double thresh = 3.0 * Constants.MACHEP; - do { - double xk = -(z * k1 * k2) / (k3 * k4); - double pk = pkm1 + pkm2 * xk; - double qk = qkm1 + qkm2 * xk; - pkm2 = pkm1; - pkm1 = pk; - qkm2 = qkm1; - qkm1 = qk; - - xk = (z * k5 * k6) / (k7 * k8); - pk = pkm1 + pkm2 * xk; - qk = qkm1 + qkm2 * xk; - pkm2 = pkm1; - pkm1 = pk; - qkm2 = qkm1; - qkm1 = qk; - - if (qk != 0) { - r = pk / qk; - } - double t; - if (r != 0) { - t = Math.abs((ans - r) / r); - ans = r; - } else { - t = 1.0; - } - - if (t < thresh) { - return ans; - } - - k1 += 1.0; - k2 -= 1.0; - k3 += 2.0; - k4 += 2.0; - k5 += 1.0; - k6 += 1.0; - k7 += 2.0; - k8 += 2.0; - - if ((Math.abs(qk) + Math.abs(pk)) > Constants.BIG) { - pkm2 *= Constants.BIG_INVERSE; - pkm1 *= Constants.BIG_INVERSE; - qkm2 *= Constants.BIG_INVERSE; - qkm1 *= Constants.BIG_INVERSE; - } - if ((Math.abs(qk) < Constants.BIG_INVERSE) || (Math.abs(pk) < Constants.BIG_INVERSE)) { - pkm2 *= Constants.BIG; - pkm1 *= Constants.BIG; - qkm2 *= Constants.BIG; - qkm1 *= Constants.BIG; - } - } while (++n < 300); - - return ans; - } - - /** - * Returns the Incomplete Gamma function; formerly named <tt>igamma</tt>. - * - * @param alpha the shape parameter of the gamma distribution. - * @param x the integration end point. - * @return The value of the unnormalized incomplete gamma function. - */ - public static double incompleteGamma(double alpha, double x) { - if (x <= 0 || alpha <= 0) { - return 0.0; - } - - if (x > 1.0 && x > alpha) { - return 1.0 - incompleteGammaComplement(alpha, x); - } - - /* Compute x**a * exp(-x) / gamma(a) */ - double ax = alpha * Math.log(x) - x - logGamma(alpha); - if (ax < -Constants.MAXLOG) { - return 0.0; - } - - ax = Math.exp(ax); - - /* power series */ - double r = alpha; - double c = 1.0; - double ans = 1.0; - - do { - r += 1.0; - c *= x / r; - ans += c; - } - while (c / ans > Constants.MACHEP); - - return ans * ax / alpha; - - } - - /** - * Returns the Complemented Incomplete Gamma function; formerly named <tt>igamc</tt>. - * - * @param alpha the shape parameter of the gamma distribution. - * @param x the integration start point. - */ - public static double incompleteGammaComplement(double alpha, double x) { - - if (x <= 0 || alpha <= 0) { - return 1.0; - } - - if (x < 1.0 || x < alpha) { - return 1.0 - incompleteGamma(alpha, x); - } - - double ax = alpha * Math.log(x) - x - logGamma(alpha); - if (ax < -Constants.MAXLOG) { - return 0.0; - } - - ax = Math.exp(ax); - - /* continued fraction */ - double y = 1.0 - alpha; - double z = x + y + 1.0; - double c = 0.0; - double pkm2 = 1.0; - double qkm2 = x; - double pkm1 = x + 1.0; - double qkm1 = z * x; - double ans = pkm1 / qkm1; - - double t; - do { - c += 1.0; - y += 1.0; - z += 2.0; - double yc = y * c; - double pk = pkm1 * z - pkm2 * yc; - double qk = qkm1 * z - qkm2 * yc; - if (qk != 0) { - double r = pk / qk; - t = Math.abs((ans - r) / r); - ans = r; - } else { - t = 1.0; - } - - pkm2 = pkm1; - pkm1 = pk; - qkm2 = qkm1; - qkm1 = qk; - if (Math.abs(pk) > Constants.BIG) { - pkm2 *= Constants.BIG_INVERSE; - pkm1 *= Constants.BIG_INVERSE; - qkm2 *= Constants.BIG_INVERSE; - qkm1 *= Constants.BIG_INVERSE; - } - } while (t > Constants.MACHEP); - - return ans * ax; - } - - /** Returns the natural logarithm of the gamma function; formerly named <tt>lgamma</tt>. */ - public static double logGamma(double x) { - double p; - double q; - double z; - - double[] aCoefficient = { - 8.11614167470508450300E-4, - -5.95061904284301438324E-4, - 7.93650340457716943945E-4, - -2.77777777730099687205E-3, - 8.33333333333331927722E-2 - }; - double[] bCoefficient = { - -1.37825152569120859100E3, - -3.88016315134637840924E4, - -3.31612992738871184744E5, - -1.16237097492762307383E6, - -1.72173700820839662146E6, - -8.53555664245765465627E5 - }; - double[] cCoefficient = { - /* 1.00000000000000000000E0, */ - -3.51815701436523470549E2, - -1.70642106651881159223E4, - -2.20528590553854454839E5, - -1.13933444367982507207E6, - -2.53252307177582951285E6, - -2.01889141433532773231E6 - }; - - if (x < -34.0) { - q = -x; - double w = logGamma(q); - p = Math.floor(q); - if (p == q) { - throw new ArithmeticException("lgam: Overflow"); - } - z = q - p; - if (z > 0.5) { - p += 1.0; - z = p - q; - } - z = q * Math.sin(Math.PI * z); - if (z == 0.0) { - throw new - ArithmeticException("lgamma: Overflow"); - } - z = Constants.LOGPI - Math.log(z) - w; - return z; - } - - if (x < 13.0) { - z = 1.0; - while (x >= 3.0) { - x -= 1.0; - z *= x; - } - while (x < 2.0) { - if (x == 0.0) { - throw new ArithmeticException("lgamma: Overflow"); - } - z /= x; - x += 1.0; - } - if (z < 0.0) { - z = -z; - } - if (x == 2.0) { - return Math.log(z); - } - x -= 2.0; - p = x * Polynomial.polevl(x, bCoefficient, 5) / Polynomial.p1evl(x, cCoefficient, 6); - return Math.log(z) + p; - } - - if (x > 2.556348e305) { - throw new ArithmeticException("lgamma: Overflow"); - } - - q = (x - 0.5) * Math.log(x) - x + 0.91893853320467274178; - //if ( x > 1.0e8 ) return( q ); - if (x > 1.0e8) { - return q; - } - - p = 1.0 / (x * x); - if (x >= 1000.0) { - q += ((7.9365079365079365079365e-4 * p - - 2.7777777777777777777778e-3) * p - + 0.0833333333333333333333) / x; - } else { - q += Polynomial.polevl(p, aCoefficient, 4) / x; - } - return q; - } - - /** - * Power series for incomplete beta integral; formerly named <tt>pseries</tt>. Use when b*x is small and x not too - * close to 1. - */ - private static double powerSeries(double a, double b, double x) { - - double ai = 1.0 / a; - double u = (1.0 - b) * x; - double v = u / (a + 1.0); - double t1 = v; - double t = u; - double n = 2.0; - double s = 0.0; - double z = Constants.MACHEP * ai; - while (Math.abs(v) > z) { - u = (n - b) * x / n; - t *= u; - v = t / (a + n); - s += v; - n += 1.0; - } - s += t1; - s += ai; - - u = a * Math.log(x); - if ((a + b) < Constants.MAXGAM && Math.abs(u) < Constants.MAXLOG) { - t = gamma(a + b) / (gamma(a) * gamma(b)); - s *= t * Math.pow(x, a); - } else { - t = logGamma(a + b) - logGamma(a) - logGamma(b) + u + Math.log(s); - s = t < Constants.MINLOG ? 0.0 : Math.exp(t); - } - return s; - } - - /** - * Returns the Gamma function computed by Stirling's formula; formerly named <tt>stirf</tt>. The polynomial STIR is - * valid for 33 <= x <= 172. - */ - static double stirlingFormula(double x) { - double[] coefficients = { - 7.87311395793093628397E-4, - -2.29549961613378126380E-4, - -2.68132617805781232825E-3, - 3.47222221605458667310E-3, - 8.33333333333482257126E-2, - }; - - double w = 1.0 / x; - double y = Math.exp(x); - - w = 1.0 + w * Polynomial.polevl(w, coefficients, 4); - - if (x > MAXSTIR) { - /* Avoid overflow in Math.pow() */ - double v = Math.pow(x, 0.5 * x - 0.25); - y = v * (v / y); - } else { - y = Math.pow(x, x - 0.5) / y; - } - y = Constants.SQTPI * y * w; - return y; - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/jet/stat/Probability.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/jet/stat/Probability.java b/math/src/main/java/org/apache/mahout/math/jet/stat/Probability.java deleted file mode 100644 index bcd1a86..0000000 --- a/math/src/main/java/org/apache/mahout/math/jet/stat/Probability.java +++ /dev/null @@ -1,203 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.jet.stat; - -import org.apache.mahout.math.jet.random.Normal; - -/** Partially deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */ -public final class Probability { - - private static final Normal UNIT_NORMAL = new Normal(0, 1, null); - - private Probability() { - } - - /** - * Returns the area from zero to <tt>x</tt> under the beta density function. - * <pre> - * x - * - - - * | (a+b) | | a-1 b-1 - * P(x) = ---------- | t (1-t) dt - * - - | | - * | (a) | (b) - - * 0 - * </pre> - * This function is identical to the incomplete beta integral function <tt>Gamma.incompleteBeta(a, b, x)</tt>. - * - * The complemented function is - * - * <tt>1 - P(1-x) = Gamma.incompleteBeta( b, a, x )</tt>; - */ - public static double beta(double a, double b, double x) { - return Gamma.incompleteBeta(a, b, x); - } - - /** - * Returns the integral from zero to <tt>x</tt> of the gamma probability density function. - * <pre> - * - * alpha - x - * beta | alpha-1 -beta t - * y = --------- | t e dt - * - | - * | (alpha) - 0 - * </pre> - * The incomplete gamma integral is used, according to the relation - * - * <tt>y = Gamma.incompleteGamma( alpha, beta*x )</tt>. - * - * See http://en.wikipedia.org/wiki/Gamma_distribution#Probability_density_function - * - * @param alpha the shape parameter of the gamma distribution. - * @param beta the rate parameter of the gamma distribution. - * @param x integration end point. - */ - public static double gamma(double alpha, double beta, double x) { - if (x < 0.0) { - return 0.0; - } - return Gamma.incompleteGamma(alpha, beta * x); - } - - /** - * Returns the sum of the terms <tt>0</tt> through <tt>k</tt> of the Negative Binomial Distribution. - * {@code - * k - * -- ( n+j-1 ) n j - * > ( ) p (1-p) - * -- ( j ) - * j=0 - * } - * In a sequence of Bernoulli trials, this is the probability that <tt>k</tt> or fewer failures precede the - * <tt>n</tt>-th success. <p> The terms are not computed individually; instead the incomplete beta integral is - * employed, according to the formula <p> <tt>y = negativeBinomial( k, n, p ) = Gamma.incompleteBeta( n, k+1, p - * )</tt>. - * - * All arguments must be positive, - * - * @param k end term. - * @param n the number of trials. - * @param p the probability of success (must be in <tt>(0.0,1.0)</tt>). - */ - public static double negativeBinomial(int k, int n, double p) { - if (p < 0.0 || p > 1.0) { - throw new IllegalArgumentException(); - } - if (k < 0) { - return 0.0; - } - - return Gamma.incompleteBeta(n, k + 1, p); - } - - /** - * Returns the area under the Normal (Gaussian) probability density function, integrated from minus infinity to - * <tt>x</tt> (assumes mean is zero, variance is one). - * {@code - * x - * - - * 1 | | 2 - * normal(x) = --------- | exp( - t /2 ) dt - * sqrt(2pi) | | - * - - * -inf. - * - * = ( 1 + erf(z) ) / 2 - * = erfc(z) / 2 - * } - * where <tt>z = x/sqrt(2)</tt>. Computation is via the functions <tt>errorFunction</tt> and - * <tt>errorFunctionComplement</tt>. - * <p> - * Computed using method 26.2.17 from Abramovitz and Stegun (see http://www.math.sfu.ca/~cbm/aands/page_932.htm - * and http://en.wikipedia.org/wiki/Normal_distribution#Numerical_approximations_of_the_normal_cdf - */ - - public static double normal(double a) { - if (a < 0) { - return 1 - normal(-a); - } - double b0 = 0.2316419; - double b1 = 0.319381530; - double b2 = -0.356563782; - double b3 = 1.781477937; - double b4 = -1.821255978; - double b5 = 1.330274429; - double t = 1 / (1 + b0 * a); - return 1 - UNIT_NORMAL.pdf(a) * t * (b1 + t * (b2 + t * (b3 + t * (b4 + t * b5)))); - } - - /** - * Returns the area under the Normal (Gaussian) probability density function, integrated from minus infinity to - * <tt>x</tt>. - * {@code - * x - * - - * 1 | | 2 - * normal(x) = --------- | exp( - (t-mean) / 2v ) dt - * sqrt(2pi*v)| | - * - - * -inf. - * - * } - * where <tt>v = variance</tt>. Computation is via the functions <tt>errorFunction</tt>. - * - * @param mean the mean of the normal distribution. - * @param variance the variance of the normal distribution. - * @param x the integration limit. - */ - public static double normal(double mean, double variance, double x) { - return normal((x - mean) / Math.sqrt(variance)); - } - - /** - * Returns the sum of the first <tt>k</tt> terms of the Poisson distribution. - * <pre> - * k j - * -- -m m - * > e -- - * -- j! - * j=0 - * </pre> - * The terms are not summed directly; instead the incomplete gamma integral is employed, according to the relation <p> - * <tt>y = poisson( k, m ) = Gamma.incompleteGammaComplement( k+1, m )</tt>. - * - * The arguments must both be positive. - * - * @param k number of terms. - * @param mean the mean of the poisson distribution. - */ - public static double poisson(int k, double mean) { - if (mean < 0) { - throw new IllegalArgumentException(); - } - if (k < 0) { - return 0.0; - } - return Gamma.incompleteGammaComplement(k + 1, mean); - } - -} http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/jet/stat/package-info.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/jet/stat/package-info.java b/math/src/main/java/org/apache/mahout/math/jet/stat/package-info.java deleted file mode 100644 index 1d4d7bd..0000000 --- a/math/src/main/java/org/apache/mahout/math/jet/stat/package-info.java +++ /dev/null @@ -1,5 +0,0 @@ -/** - * Tools for basic and advanced statistics: Estimators, Gamma functions, Beta functions, Probabilities, - * Special integrals, etc. - */ -package org.apache.mahout.math.jet.stat; http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/list/AbstractList.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/list/AbstractList.java b/math/src/main/java/org/apache/mahout/math/list/AbstractList.java deleted file mode 100644 index c672f40..0000000 --- a/math/src/main/java/org/apache/mahout/math/list/AbstractList.java +++ /dev/null @@ -1,247 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - /* -Copyright � 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.list; - -import org.apache.mahout.math.PersistentObject; - -/** - * Abstract base class for resizable lists holding objects or primitive data types such as - * {@code int}, {@code float}, etc. - * First see the <a href="package-summary.html">package summary</a> and javadoc - * <a href="package-tree.html">tree view</a> to get the broad picture. - * <p> - * <b>Note that this implementation is not synchronized.</b> - * - * @author [email protected] - * @version 1.0, 09/24/99 - * @see java.util.ArrayList - * @see java.util.Vector - * @see java.util.Arrays - */ -public abstract class AbstractList extends PersistentObject { - - public abstract int size(); - - public boolean isEmpty() { - return size() == 0; - } - - /** - * Inserts <tt>length</tt> dummy elements before the specified position into the receiver. Shifts the element - * currently at that position (if any) and any subsequent elements to the right. <b>This method must set the new size - * to be <tt>size()+length</tt></b>. - * - * @param index index before which to insert dummy elements (must be in [0,size]).. - * @param length number of dummy elements to be inserted. - * @throws IndexOutOfBoundsException if <tt>index < 0 || index > size()</tt>. - */ - protected abstract void beforeInsertDummies(int index, int length); - - /** Checks if the given index is in range. */ - protected static void checkRange(int index, int theSize) { - if (index >= theSize || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + theSize); - } - } - - /** - * Checks if the given range is within the contained array's bounds. - * - * @throws IndexOutOfBoundsException if <tt>to!=from-1 || from<0 || from>to || to>=size()</tt>. - */ - protected static void checkRangeFromTo(int from, int to, int theSize) { - if (to == from - 1) { - return; - } - if (from < 0 || from > to || to >= theSize) { - throw new IndexOutOfBoundsException("from: " + from + ", to: " + to + ", size=" + theSize); - } - } - - /** - * Removes all elements from the receiver. The receiver will be empty after this call returns, but keep its current - * capacity. - */ - public void clear() { - removeFromTo(0, size() - 1); - } - - /** - * Sorts the receiver into ascending order. This sort is guaranteed to be <i>stable</i>: equal elements will not be - * reordered as a result of the sort.<p> - * - * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low - * sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) - * performance, and can approach linear performance on nearly sorted lists. - * - * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one - * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because - * those methods automatically choose the best sorting algorithm. - */ - public final void mergeSort() { - mergeSortFromTo(0, size() - 1); - } - - /** - * Sorts the receiver into ascending order. This sort is guaranteed to be <i>stable</i>: equal elements will not be - * reordered as a result of the sort.<p> - * - * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low - * sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) - * performance, and can approach linear performance on nearly sorted lists. - * - * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one - * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because - * those methods automatically choose the best sorting algorithm. - * - * @param from the index of the first element (inclusive) to be sorted. - * @param to the index of the last element (inclusive) to be sorted. - * @throws IndexOutOfBoundsException if <tt>(from<0 || from>to || to>=size()) && to!=from-1</tt>. - */ - public abstract void mergeSortFromTo(int from, int to); - - /** - * Sorts the receiver into ascending order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley - * and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 - * (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to - * degrade to quadratic performance. - * - * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one - * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because - * those methods automatically choose the best sorting algorithm. - */ - public final void quickSort() { - quickSortFromTo(0, size() - 1); - } - - /** - * Sorts the specified range of the receiver into ascending order. The sorting algorithm is a tuned quicksort, - * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and - * Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets - * that cause other quicksorts to degrade to quadratic performance. - * - * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one - * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because - * those methods automatically choose the best sorting algorithm. - * - * @param from the index of the first element (inclusive) to be sorted. - * @param to the index of the last element (inclusive) to be sorted. - * @throws IndexOutOfBoundsException if <tt>(from<0 || from>to || to>=size()) && to!=from-1</tt>. - */ - public abstract void quickSortFromTo(int from, int to); - - /** - * Removes the element at the specified position from the receiver. Shifts any subsequent elements to the left. - * - * @param index the index of the element to removed. - * @throws IndexOutOfBoundsException if <tt>index < 0 || index >= size()</tt>. - */ - public void remove(int index) { - removeFromTo(index, index); - } - - /** - * Removes from the receiver all elements whose index is between <code>from</code>, inclusive and <code>to</code>, - * inclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by - * <tt>(to - from + 1)</tt> elements. - * - * @param fromIndex index of first element to be removed. - * @param toIndex index of last element to be removed. - * @throws IndexOutOfBoundsException if <tt>(from<0 || from>to || to>=size()) && to!=from-1</tt>. - */ - public abstract void removeFromTo(int fromIndex, int toIndex); - - /** Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on. */ - public abstract void reverse(); - - /** - * Sets the size of the receiver. If the new size is greater than the current size, new null or zero items are added - * to the end of the receiver. If the new size is less than the current size, all components at index newSize and - * greater are discarded. This method does not release any superfluos internal memory. Use method <tt>trimToSize</tt> - * to release superfluos internal memory. - * - * @param newSize the new size of the receiver. - * @throws IndexOutOfBoundsException if <tt>newSize < 0</tt>. - */ - public void setSize(int newSize) { - if (newSize < 0) { - throw new IndexOutOfBoundsException("newSize:" + newSize); - } - - int currentSize = size(); - if (newSize != currentSize) { - if (newSize > currentSize) { - beforeInsertDummies(currentSize, newSize - currentSize); - } else if (newSize < currentSize) { - removeFromTo(newSize, currentSize - 1); - } - } - } - - /** - * Sorts the receiver into ascending order. - * - * The sorting algorithm is dynamically chosen according to the characteristics of the data set. - * - * This implementation simply calls <tt>sortFromTo(...)</tt>. Override <tt>sortFromTo(...)</tt> if you can determine - * which sort is most appropriate for the given data set. - */ - public final void sort() { - sortFromTo(0, size() - 1); - } - - /** - * Sorts the specified range of the receiver into ascending order. - * - * The sorting algorithm is dynamically chosen according to the characteristics of the data set. This default - * implementation simply calls quickSort. Override this method if you can determine which sort is most appropriate for - * the given data set. - * - * @param from the index of the first element (inclusive) to be sorted. - * @param to the index of the last element (inclusive) to be sorted. - * @throws IndexOutOfBoundsException if <tt>(from<0 || from>to || to>=size()) && to!=from-1</tt>. - */ - public void sortFromTo(int from, int to) { - quickSortFromTo(from, to); - } - - /** - * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluos internal memory. An - * application can use this operation to minimize the storage of the receiver. <p> This default implementation does - * nothing. Override this method in space efficient implementations. - */ - public void trimToSize() { - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/list/AbstractObjectList.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/list/AbstractObjectList.java b/math/src/main/java/org/apache/mahout/math/list/AbstractObjectList.java deleted file mode 100644 index a1a5899..0000000 --- a/math/src/main/java/org/apache/mahout/math/list/AbstractObjectList.java +++ /dev/null @@ -1,80 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.list; - -import java.util.Collection; - -/** - Abstract base class for resizable lists holding objects or primitive data types such as <code>int</code>, - <code>float</code>, etc.First see the <a href="package-summary.html">package summary</a> and - javadoc <a href="package-tree.html">tree view</a> to get the broad picture. - <p> - <b>Note that this implementation is not synchronized.</b> - - @author [email protected] - @version 1.0, 09/24/99 - @see java.util.ArrayList - @see java.util.Vector - @see java.util.Arrays - */ -public abstract class AbstractObjectList<T> extends AbstractList { - - /** - * Appends all of the elements of the specified Collection to the receiver. - * - * @throws ClassCastException if an element in the collection is not of the same parameter type of the receiver. - */ - public void addAllOf(Collection<T> collection) { - this.beforeInsertAllOf(size(), collection); - } - - /** - * Inserts all elements of the specified collection before the specified position into the receiver. Shifts the - * element currently at that position (if any) and any subsequent elements to the right (increases their indices). - * - * @param index index before which to insert first element from the specified collection. - * @param collection the collection to be inserted - * @throws ClassCastException if an element in the collection is not of the same parameter type of the - * receiver. - * @throws IndexOutOfBoundsException if <tt>index < 0 || index > size()</tt>. - */ - public void beforeInsertAllOf(int index, Collection<T> collection) { - this.beforeInsertDummies(index, collection.size()); - this.replaceFromWith(index, collection); - } - - /** - * Replaces the part of the receiver starting at <code>from</code> (inclusive) with all the elements of the specified - * collection. Does not alter the size of the receiver. Replaces exactly <tt>Math.max(0,Math.min(size()-from, - * other.size()))</tt> elements. - * - * @param from the index at which to copy the first element from the specified collection. - * @param other Collection to replace part of the receiver - * @throws IndexOutOfBoundsException if <tt>index < 0 || index >= size()</tt>. - */ - public abstract void replaceFromWith(int from, Collection<T> other); -} http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java b/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java deleted file mode 100644 index c41141f..0000000 --- a/math/src/main/java/org/apache/mahout/math/list/ObjectArrayList.java +++ /dev/null @@ -1,419 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ -/* -Copyright � 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.list; - -import org.apache.mahout.math.function.ObjectProcedure; - -import java.util.Collection; - -/** - Resizable list holding <code>${valueType}</code> elements; implemented with arrays. -*/ - -public class ObjectArrayList<T> extends AbstractObjectList<T> { - - /** - * The array buffer into which the elements of the list are stored. The capacity of the list is the length of this - * array buffer. - */ - private Object[] elements; - private int size; - - /** Constructs an empty list. */ - public ObjectArrayList() { - this(10); - } - - /** - * Constructs a list containing the specified elements. The initial size and capacity of the list is the length of the - * array. - * - * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if - * subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing. - * - * @param elements the array to be backed by the the constructed list - */ - public ObjectArrayList(T[] elements) { - elements(elements); - } - - /** - * Constructs an empty list with the specified initial capacity. - * - * @param initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new - * internal memory. - */ - @SuppressWarnings("unchecked") - public ObjectArrayList(int initialCapacity) { - elements = new Object[initialCapacity]; - size = 0; - } - - /** - * Appends the specified element to the end of this list. - * - * @param element element to be appended to this list. - */ - public void add(T element) { - // overridden for performance only. - if (size == elements.length) { - ensureCapacity(size + 1); - } - elements[size++] = element; - } - - /** - * Inserts the specified element before the specified position into the receiver. Shifts the element currently at that - * position (if any) and any subsequent elements to the right. - * - * @param index index before which the specified element is to be inserted (must be in [0,size]). - * @param element element to be inserted. - * @throws IndexOutOfBoundsException index is out of range (<tt>index < 0 || index > size()</tt>). - */ - public void beforeInsert(int index, T element) { - // overridden for performance only. - if (size == index) { - add(element); - return; - } - if (index > size || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); - } - ensureCapacity(size + 1); - System.arraycopy(elements, index, elements, index + 1, size - index); - elements[index] = element; - size++; - } - - - /** - * Returns a deep copy of the receiver. - * - * @return a deep copy of the receiver. - */ - @SuppressWarnings("unchecked") - @Override - public Object clone() { - // overridden for performance only. - return new ObjectArrayList<>((T[]) elements.clone()); - } - - /** - * Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result. - * - * @return a deep copy of the receiver. - */ - @SuppressWarnings("unchecked") - public ObjectArrayList<T> copy() { - return (ObjectArrayList<T>) clone(); - } - - /** - * Returns the elements currently stored, including invalid elements between size and capacity, if any. - * - * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if - * subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing. - * - * @return the elements currently stored. - */ - @SuppressWarnings("unchecked") - public <Q> Q[] elements() { - return (Q[])elements; - } - - /** - * Sets the receiver's elements to be the specified array (not a copy of it). - * - * The size and capacity of the list is the length of the array. <b>WARNING:</b> For efficiency reasons and to keep - * memory usage low, <b>the array is not copied</b>. So if subsequently you modify the specified array directly via - * the [] operator, be sure you know what you're doing. - * - * @param elements the new elements to be stored. - */ - public void elements(T[] elements) { - this.elements = elements; - this.size = elements.length; - } - - /** - * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new - * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. - * - * @param minCapacity the desired minimum capacity. - */ - public void ensureCapacity(int minCapacity) { - elements = org.apache.mahout.math.Arrays.ensureCapacity(elements, minCapacity); - } - - /** - * Compares the specified Object with the receiver. Returns true if and only if the specified Object is also an - * ArrayList of the same type, both Lists have the same size, and all corresponding pairs of elements in the two Lists - * are identical. In other words, two Lists are defined to be equal if they contain the same elements in the same - * order. - * - * @param otherObj the Object to be compared for equality with the receiver. - * @return true if the specified Object is equal to the receiver. - */ - @Override - @SuppressWarnings("unchecked") - public boolean equals(Object otherObj) { //delta - // overridden for performance only. - if (!(otherObj instanceof ObjectArrayList)) { - return super.equals(otherObj); - } - if (this == otherObj) { - return true; - } - if (otherObj == null) { - return false; - } - ObjectArrayList<?> other = (ObjectArrayList<?>) otherObj; - if (size() != other.size()) { - return false; - } - - Object[] theElements = elements(); - Object[] otherElements = other.elements(); - for (int i = size(); --i >= 0;) { - if (theElements[i] != otherElements[i]) { - return false; - } - } - return true; - } - - /** - * Applies a procedure to each element of the receiver, if any. Starts at index 0, moving rightwards. - * - * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise - * continues. - * @return <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise. - */ - @SuppressWarnings("unchecked") - public boolean forEach(ObjectProcedure<T> procedure) { - T[] theElements = (T[]) elements; - int theSize = size; - - for (int i = 0; i < theSize;) { - if (!procedure.apply(theElements[i++])) { - return false; - } - } - return true; - } - - /** - * Returns the element at the specified position in the receiver. - * - * @param index index of element to return. - * @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()). - */ - @SuppressWarnings("unchecked") - public T get(int index) { - // overridden for performance only. - if (index >= size || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); - } - return (T) elements[index]; - } - - /** - * Returns the element at the specified position in the receiver; <b>WARNING:</b> Does not check preconditions. - * Provided with invalid parameters this method may return invalid elements without throwing any exception! <b>You - * should only use this method when you are absolutely sure that the index is within bounds.</b> Precondition - * (unchecked): <tt>index >= 0 && index < size()</tt>. - * - * @param index index of element to return. - */ - @SuppressWarnings("unchecked") - public T getQuick(int index) { - return (T) elements[index]; - } - - /** - * Returns the index of the first occurrence of the specified element. Returns <code>-1</code> if the receiver does - * not contain this element. Searches between <code>from</code>, inclusive and <code>to</code>, inclusive. Tests for - * identity. - * - * @param element element to search for. - * @param from the leftmost search position, inclusive. - * @param to the rightmost search position, inclusive. - * @return the index of the first occurrence of the element in the receiver; returns <code>-1</code> if the element is - * not found. - * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to || - * to>=size())</tt>). - */ - public int indexOfFromTo(T element, int from, int to) { - // overridden for performance only. - if (size == 0) { - return -1; - } - checkRangeFromTo(from, to, size); - - Object[] theElements = elements; - for (int i = from; i <= to; i++) { - if (element == theElements[i]) { - return i; - } //found - } - return -1; //not found - } - - /** - * Returns the index of the last occurrence of the specified element. Returns <code>-1</code> if the receiver does not - * contain this element. Searches beginning at <code>to</code>, inclusive until <code>from</code>, inclusive. Tests - * for identity. - * - * @param element element to search for. - * @param from the leftmost search position, inclusive. - * @param to the rightmost search position, inclusive. - * @return the index of the last occurrence of the element in the receiver; returns <code>-1</code> if the element is - * not found. - * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to || - * to>=size())</tt>). - */ - public int lastIndexOfFromTo(T element, int from, int to) { - // overridden for performance only. - if (size == 0) { - return -1; - } - checkRangeFromTo(from, to, size); - - Object[] theElements = elements; - for (int i = to; i >= from; i--) { - if (element == theElements[i]) { - return i; - } //found - } - return -1; //not found - } - - /** - * Returns a new list of the part of the receiver between <code>from</code>, inclusive, and <code>to</code>, - * inclusive. - * - * @param from the index of the first element (inclusive). - * @param to the index of the last element (inclusive). - * @return a new list - * @throws IndexOutOfBoundsException index is out of range (<tt>size()>0 && (from<0 || from>to || - * to>=size())</tt>). - */ - @SuppressWarnings("unchecked") - public AbstractObjectList<T> partFromTo(int from, int to) { - if (size == 0) { - return new ObjectArrayList<>(0); - } - - checkRangeFromTo(from, to, size); - - Object[] part = new Object[to - from + 1]; - System.arraycopy(elements, from, part, 0, to - from + 1); - return new ObjectArrayList<>((T[]) part); - } - - /** Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on. */ - @Override - public void reverse() { - // overridden for performance only. - int limit = size / 2; - int j = size - 1; - - Object[] theElements = elements; - for (int i = 0; i < limit;) { //swap - Object tmp = theElements[i]; - theElements[i++] = theElements[j]; - theElements[j--] = tmp; - } - } - - /** - * Replaces the element at the specified position in the receiver with the specified element. - * - * @param index index of element to replace. - * @param element element to be stored at the specified position. - * @throws IndexOutOfBoundsException index is out of range (index < 0 || index >= size()). - */ - public void set(int index, T element) { - // overridden for performance only. - if (index >= size || index < 0) { - throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); - } - elements[index] = element; - } - - /** - * Replaces the element at the specified position in the receiver with the specified element; <b>WARNING:</b> Does not - * check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any - * exception! <b>You should only use this method when you are absolutely sure that the index is within bounds.</b> - * Precondition (unchecked): {@code index >= 0 && index < size()}. - * - * @param index index of element to replace. - * @param element element to be stored at the specified position. - */ - public void setQuick(int index, T element) { - elements[index] = element; - } - - /** - * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An - * application can use this operation to minimize the storage of the receiver. - */ - @Override - public void trimToSize() { - elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size()); - } - - @Override - public void removeFromTo(int fromIndex, int toIndex) { - throw new UnsupportedOperationException(); - } - - @Override - public void replaceFromWith(int from, Collection<T> other) { - throw new UnsupportedOperationException(); - } - - @Override - protected void beforeInsertDummies(int index, int length) { - throw new UnsupportedOperationException(); - } - - @Override - public void mergeSortFromTo(int from, int to) { - throw new UnsupportedOperationException(); - } - - @Override - public void quickSortFromTo(int from, int to) { - throw new UnsupportedOperationException(); - } - - @Override - public int size() { - return size; - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java ---------------------------------------------------------------------- diff --git a/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java b/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java deleted file mode 100644 index 1a765eb..0000000 --- a/math/src/main/java/org/apache/mahout/math/list/SimpleLongArrayList.java +++ /dev/null @@ -1,102 +0,0 @@ -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math.list; - -/** - Resizable list holding <code>long</code> elements; implemented with arrays; not efficient; just to - demonstrate which methods you must override to implement a fully functional list. - */ -public class SimpleLongArrayList extends AbstractLongList { - - /** - * The array buffer into which the elements of the list are stored. The capacity of the list is the length of this - * array buffer. - */ - private long[] elements; - - /** Constructs an empty list. */ - public SimpleLongArrayList() { - this(10); - } - - /** - * Constructs a list containing the specified elements. The initial size and capacity of the list is the length of the - * array. - * - * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if - * subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing. - * - * @param elements the array to be backed by the the constructed list - */ - public SimpleLongArrayList(long[] elements) { - elements(elements); - } - - /** - * Constructs an empty list with the specified initial capacity. - * - * @param initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new - * internal memory. - */ - private SimpleLongArrayList(int initialCapacity) { - if (initialCapacity < 0) { - throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); - } - - this.elements(new long[initialCapacity]); - size = 0; - } - - /** - * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new - * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. - * - * @param minCapacity the desired minimum capacity. - */ - @Override - public void ensureCapacity(int minCapacity) { - elements = org.apache.mahout.math.Arrays.ensureCapacity(elements, minCapacity); - } - - /** - * Returns the element at the specified position in the receiver; <b>WARNING:</b> Does not check preconditions. - * Provided with invalid parameters this method may return invalid elements without throwing any exception! <b>You - * should only use this method when you are absolutely sure that the index is within bounds.</b> Precondition - * (unchecked): <tt>index >= 0 && index < size()</tt>. - * - * @param index index of element to return. - */ - @Override - protected long getQuick(int index) { - return elements[index]; - } - - /** - * Replaces the element at the specified position in the receiver with the specified element; <b>WARNING:</b> Does not - * check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any - * exception! <b>You should only use this method when you are absolutely sure that the index is within bounds.</b> - * Precondition (unchecked): <tt>index >= 0 && index < size()</tt>. - * - * @param index index of element to replace. - * @param element element to be stored at the specified position. - */ - @Override - protected void setQuick(int index, long element) { - elements[index] = element; - } - - /** - * Trims the capacity of the receiver to be the receiver's current size. An application can use this operation to - * minimize the storage of the receiver. - */ - @Override - public void trimToSize() { - elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size()); - } -}
