You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ra...@apache.org on 2018/06/27 14:51:37 UTC
[09/51] [partial] mahout git commit: MAHOUT-2042 and MAHOUT-2045
Delete directories which were moved/no longer in use
http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/Sorting.java
----------------------------------------------------------------------
diff --git a/math/src/main/java/org/apache/mahout/math/Sorting.java b/math/src/main/java/org/apache/mahout/math/Sorting.java
deleted file mode 100644
index 93293ac..0000000
--- a/math/src/main/java/org/apache/mahout/math/Sorting.java
+++ /dev/null
@@ -1,2297 +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.
- */
-
-package org.apache.mahout.math;
-
-import java.io.Serializable;
-import java.util.Comparator;
-
-import com.google.common.base.Preconditions;
-import org.apache.mahout.math.function.ByteComparator;
-import org.apache.mahout.math.function.CharComparator;
-import org.apache.mahout.math.function.DoubleComparator;
-import org.apache.mahout.math.function.FloatComparator;
-import org.apache.mahout.math.function.IntComparator;
-import org.apache.mahout.math.function.LongComparator;
-import org.apache.mahout.math.function.ShortComparator;
-
-public final class Sorting {
-
- /* Specifies when to switch to insertion sort */
- private static final int SIMPLE_LENGTH = 7;
- static final int SMALL = 7;
-
- private Sorting() {}
-
- private static <T> int med3(T[] array, int a, int b, int c, Comparator<T> comp) {
- T x = array[a];
- T y = array[b];
- T z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(byte[] array, int a, int b, int c, ByteComparator comp) {
- byte x = array[a];
- byte y = array[b];
- byte z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(char[] array, int a, int b, int c, CharComparator comp) {
- char x = array[a];
- char y = array[b];
- char z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(double[] array, int a, int b, int c,
- DoubleComparator comp) {
- double x = array[a];
- double y = array[b];
- double z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(float[] array, int a, int b, int c,
- FloatComparator comp) {
- float x = array[a];
- float y = array[b];
- float z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(int[] array, int a, int b, int c, IntComparator comp) {
- int x = array[a];
- int y = array[b];
- int z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- /**
- * This is used for 'external' sorting. The comparator takes <em>indices</em>,
- * not values, and compares the external values found at those indices.
- * @param a
- * @param b
- * @param c
- * @param comp
- * @return
- */
- private static int med3(int a, int b, int c, IntComparator comp) {
- int comparisonab = comp.compare(a, b);
- int comparisonac = comp.compare(a, c);
- int comparisonbc = comp.compare(b, c);
- return comparisonab < 0
- ? (comparisonbc < 0 ? b : (comparisonac < 0 ? c : a))
- : (comparisonbc > 0 ? b : (comparisonac > 0 ? c : a));
- }
-
- private static int med3(long[] array, int a, int b, int c, LongComparator comp) {
- long x = array[a];
- long y = array[b];
- long z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- private static int med3(short[] array, int a, int b, int c,
- ShortComparator comp) {
- short x = array[a];
- short y = array[b];
- short z = array[c];
- int comparisonxy = comp.compare(x, y);
- int comparisonxz = comp.compare(x, z);
- int comparisonyz = comp.compare(y, z);
- return comparisonxy < 0 ? (comparisonyz < 0 ? b
- : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
- : (comparisonxz > 0 ? c : a));
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code byte} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparison that determines the sort.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(byte[] array, int start, int end,
- ByteComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void checkBounds(int arrLength, int start, int end) {
- if (start > end) {
- // K0033=Start index ({0}) is greater than end index ({1})
- throw new IllegalArgumentException("Start index " + start
- + " is greater than end index " + end);
- }
- if (start < 0) {
- throw new ArrayIndexOutOfBoundsException("Array index out of range "
- + start);
- }
- if (end > arrLength) {
- throw new ArrayIndexOutOfBoundsException("Array index out of range "
- + end);
- }
- }
-
- private static void quickSort0(int start, int end, byte[] array, ByteComparator comp) {
- byte temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- byte partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
-
- /**
- * Sorts some external data with QuickSort.
- *
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparator.
- * @param swap an object that can exchange the positions of two items.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(int start, int end, IntComparator comp, Swapper swap) {
- checkBounds(end + 1, start, end);
- quickSort0(start, end, comp, swap);
- }
-
- private static void quickSort0(int start, int end, IntComparator comp, Swapper swap) {
- int length = end - start;
- if (length < 7) {
- insertionSort(start, end, comp, swap);
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- // for lots of data, bottom, middle and top are medians near the beginning, middle or end of the data
- int skosh = length / 8;
- bottom = med3(bottom, bottom + skosh, bottom + (2 * skosh), comp);
- middle = med3(middle - skosh, middle, middle + skosh, comp);
- top = med3(top - (2 * skosh), top - skosh, top, comp);
- }
- middle = med3(bottom, middle, top, comp);
- }
-
- int partitionIndex = middle; // an index, not a value.
-
- // regions from a to b and from c to d are what we will recursively sort
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (b <= c) {
- // copy all values equal to the partition value to before a..b. In the process, advance b
- // as long as values less than the partition or equal are found, also stop when a..b collides with c..d
- int comparison;
- while (b <= c && (comparison = comp.compare(b, partitionIndex)) <= 0) {
- if (comparison == 0) {
- if (a == partitionIndex) {
- partitionIndex = b;
- } else if (b == partitionIndex) {
- partitionIndex = a;
- }
- swap.swap(a, b);
- a++;
- }
- b++;
- }
- // at this point [start..a) has partition values, [a..b) has values < partition
- // also, either b>c or v[b] > partition value
-
- while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
- if (comparison == 0) {
- if (c == partitionIndex) {
- partitionIndex = d;
- } else if (d == partitionIndex) {
- partitionIndex = c;
- }
- swap.swap(c, d);
-
- d--;
- }
- c--;
- }
- // now we also know that [d..end] contains partition values,
- // [c..d) contains values > partition value
- // also, either b>c or (v[b] > partition OR v[c] < partition)
-
- if (b <= c) {
- // v[b] > partition OR v[c] < partition
- // swapping will let us continue to grow the two regions
- if (c == partitionIndex) {
- partitionIndex = b;
- } else if (b == partitionIndex) {
- partitionIndex = d;
- }
- swap.swap(b, c);
- b++;
- c--;
- }
- }
- // now we know
- // b = c+1
- // [start..a) and [d..end) contain partition value
- // all of [a..b) are less than partition
- // all of [c..d) are greater than partition
-
- // shift [a..b) to beginning
- length = Math.min(a - start, b - a);
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- swap.swap(l, h);
- l++;
- h++;
- }
-
- // shift [c..d) to end
- length = Math.min(d - c, end - 1 - d);
- l = b;
- h = end - length;
- while (length-- > 0) {
- swap.swap(l, h);
- l++;
- h++;
- }
-
- // recurse left and right
- length = b - a;
- if (length > 0) {
- quickSort0(start, start + length, comp, swap);
- }
-
- length = d - c;
- if (length > 0) {
- quickSort0(end - length, end, comp, swap);
- }
- }
-
- /**
- * In-place insertion sort that is fast for pre-sorted data.
- *
- * @param start Where to start sorting (inclusive)
- * @param end Where to stop (exclusive)
- * @param comp Sort order.
- * @param swap How to swap items.
- */
- private static void insertionSort(int start, int end, IntComparator comp, Swapper swap) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(j - 1, j) > 0; j--) {
- swap.swap(j - 1, j);
- }
- }
- }
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code char} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(char[] array, int start, int end, CharComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, char[] array, CharComparator comp) {
- char temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- char partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code double} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparison.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- * @see Double#compareTo(Double)
- */
- public static void quickSort(double[] array, int start, int end, DoubleComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, double[] array, DoubleComparator comp) {
- double temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- double partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(partionValue, array[b])) >= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code float} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparator.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(float[] array, int start, int end, FloatComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, float[] array, FloatComparator comp) {
- float temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- float partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(partionValue, array[b])) >= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code int} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparator.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(int[] array, int start, int end, IntComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, int[] array, IntComparator comp) {
- int temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- int partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the {@code long} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparator.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(long[] array, int start, int end, LongComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, long[] array, LongComparator comp) {
- long temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- long partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in a specified order.
- *
- * @param array
- * the array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @param comp
- * the comparator.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static <T> void quickSort(T[] array, int start, int end, Comparator<T> comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static final class ComparableAdaptor<T extends Comparable<? super T>>
- implements Comparator<T>, Serializable {
-
- @Override
- public int compare(T o1, T o2) {
- return o1.compareTo(o2);
- }
-
- }
-
- /**
- * Sort the specified range of an array of object that implement the Comparable
- * interface.
- * @param <T> The type of object.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static <T extends Comparable<? super T>> void quickSort(T[] array, int start, int end) {
- quickSort(array, start, end, new ComparableAdaptor<T>());
- }
-
- private static <T> void quickSort0(int start, int end, T[] array, Comparator<T> comp) {
- T temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- T partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Sorts the specified range in the array in ascending numerical order.
- *
- * @param array
- * the {@code short} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void quickSort(short[] array, int start, int end, ShortComparator comp) {
- Preconditions.checkNotNull(array);
- checkBounds(array.length, start, end);
- quickSort0(start, end, array, comp);
- }
-
- private static void quickSort0(int start, int end, short[] array, ShortComparator comp) {
- short temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
- comp);
- middle = med3(array, middle - length, middle, middle + length, comp);
- top = med3(array, top - (2 * length), top - length, top, comp);
- }
- middle = med3(array, bottom, middle, top, comp);
- }
- short partionValue = array[middle];
- int a = start;
- int b = a;
- int c = end - 1;
- int d = c;
- while (true) {
- int comparison;
- while (b <= c && (comparison = comp.compare(array[b], partionValue)) < 0) {
- if (comparison == 0) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && (comparison = comp.compare(array[c], partionValue)) > 0) {
- if (comparison == 0) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- quickSort0(start, start + length, array, comp);
- }
- if ((length = d - c) > 0) {
- quickSort0(end - length, end, array, comp);
- }
- }
-
- /**
- * Perform a merge sort on the specified range of an array.
- *
- * @param <T> the type of object in the array.
- * @param array the array.
- * @param start first index.
- * @param end last index (exclusive).
- * @param comp comparator object.
- */
- @SuppressWarnings("unchecked") // required to make the temp array work, afaict.
- public static <T> void mergeSort(T[] array, int start, int end, Comparator<T> comp) {
- checkBounds(array.length, start, end);
- int length = end - start;
- if (length <= 0) {
- return;
- }
-
- T[] out = (T[]) new Object[array.length];
- System.arraycopy(array, start, out, start, length);
- mergeSort(out, array, start, end, comp);
- }
-
- /**
- * Perform a merge sort of the specific range of an array of objects that implement
- * Comparable.
- * @param <T> the type of the objects in the array.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static <T extends Comparable<? super T>> void mergeSort(T[] array, int start, int end) {
- mergeSort(array, start, end, new ComparableAdaptor<T>());
- }
-
- /**
- * Performs a sort on the section of the array between the given indices using
- * a mergesort with exponential search algorithm (in which the merge is
- * performed by exponential search). n*log(n) performance is guaranteed and in
- * the average case it will be faster then any mergesort in which the merge is
- * performed by linear search.
- *
- * @param in
- * - the array for sorting.
- * @param out
- * - the result, sorted array.
- * @param start
- * the start index
- * @param end
- * the end index + 1
- * @param c
- * - the comparator to determine the order of the array.
- */
- private static <T> void mergeSort(T[] in, T[] out, int start, int end, Comparator<T> c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- T current = out[i];
- T prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- T fromVal = in[start];
- T rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- /**
- * Finds the place of specified range of specified sorted array, where the
- * element should be inserted for getting sorted array. Uses exponential
- * search algorithm.
- *
- * @param arr
- * - the array with already sorted range
- * @param val
- * - object to be inserted
- * @param l
- * - the start index
- * @param r
- * - the end index
- * @param bnd
- * - possible values 0,-1. "-1" - val is located at index more then
- * elements equals to val. "0" - val is located at index less then
- * elements equals to val.
- * @param c
- * - the comparator used to compare Objects
- */
- private static <T> int find(T[] arr, T val, int bnd, int l, int r, Comparator<T> c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final ByteComparator NATURAL_BYTE_COMPARISON = new ByteComparator() {
- @Override
- public int compare(byte o1, byte o2) {
- return o1 - o2;
- }
- };
-
- /**
- * Perform a merge sort on a range of a byte array, using numerical order.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(byte[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_BYTE_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a byte array using a specified ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(byte[] array, int start, int end, ByteComparator comp) {
- checkBounds(array.length, start, end);
- byte[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- private static void mergeSort(byte[] in, byte[] out, int start, int end, ByteComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- byte current = out[i];
- byte prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- byte fromVal = in[start];
- byte rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(byte[] arr, byte val, int bnd, int l, int r, ByteComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final CharComparator NATURAL_CHAR_COMPARISON = new CharComparator() {
- @Override
- public int compare(char o1, char o2) {
- return o1 - o2;
- }
- };
-
- /**
- * Perform a merge sort on a range of a char array, using numerical order.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(char[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_CHAR_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a char array using a specified ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(char[] array, int start, int end, CharComparator comp) {
- checkBounds(array.length, start, end);
- char[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- private static void mergeSort(char[] in, char[] out, int start, int end, CharComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- char current = out[i];
- char prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- char fromVal = in[start];
- char rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(char[] arr, char val, int bnd, int l, int r, CharComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final ShortComparator NATURAL_SHORT_COMPARISON = new ShortComparator() {
- @Override
- public int compare(short o1, short o2) {
- return o1 - o2;
- }
- };
-
- /**
- * Perform a merge sort on a range of a short array, using numerical order.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(short[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_SHORT_COMPARISON);
- }
-
- public static void mergeSort(short[] array, int start, int end, ShortComparator comp) {
- checkBounds(array.length, start, end);
- short[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
-
- /**
- * Perform a merge sort on a range of a short array using a specified ordering.
- * @param in the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param c the comparator object.
- */
- private static void mergeSort(short[] in, short[] out, int start, int end, ShortComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- short current = out[i];
- short prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- short fromVal = in[start];
- short rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(short[] arr, short val, int bnd, int l, int r, ShortComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final IntComparator NATURAL_INT_COMPARISON = new IntComparator() {
- @Override
- public int compare(int o1, int o2) {
- return o1 < o2 ? -1 : o1 > o2 ? 1 : 0;
- }
- };
-
- public static void mergeSort(int[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_INT_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a int array using numerical order.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(int[] array, int start, int end, IntComparator comp) {
- checkBounds(array.length, start, end);
- int[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- /**
- * Perform a merge sort on a range of a int array using a specified ordering.
- * @param in the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param c the comparator object.
- */
- private static void mergeSort(int[] in, int[] out, int start, int end, IntComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- int current = out[i];
- int prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- int fromVal = in[start];
- int rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(int[] arr, int val, int bnd, int l, int r, IntComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
-
- private static final LongComparator NATURAL_LONG_COMPARISON = new LongComparator() {
- @Override
- public int compare(long o1, long o2) {
- return o1 < o2 ? -1 : o1 > o2 ? 1 : 0;
- }
- };
-
- /**
- * Perform a merge sort on a range of a long array using numerical order.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(long[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_LONG_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a long array using a specified ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(long[] array, int start, int end, LongComparator comp) {
- checkBounds(array.length, start, end);
- long[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- private static void mergeSort(long[] in, long[] out, int start, int end, LongComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- long current = out[i];
- long prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- long fromVal = in[start];
- long rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(long[] arr, long val, int bnd, int l, int r, LongComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final FloatComparator NATURAL_FLOAT_COMPARISON = new FloatComparator() {
- @Override
- public int compare(float o1, float o2) {
- return Float.compare(o1, o2);
- }
- };
-
- /**
- * Perform a merge sort on a range of a float array using Float.compare for an ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(float[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_FLOAT_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a float array using a specified ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(float[] array, int start, int end, FloatComparator comp) {
- checkBounds(array.length, start, end);
- float[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- private static void mergeSort(float[] in, float[] out, int start, int end, FloatComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- float current = out[i];
- float prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- float fromVal = in[start];
- float rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(float[] arr, float val, int bnd, int l, int r, FloatComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- private static final DoubleComparator NATURAL_DOUBLE_COMPARISON = new DoubleComparator() {
- @Override
- public int compare(double o1, double o2) {
- return Double.compare(o1, o2);
- }
- };
-
-
- /**
- * Perform a merge sort on a range of a double array using a Double.compare as an ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- */
- public static void mergeSort(double[] array, int start, int end) {
- mergeSort(array, start, end, NATURAL_DOUBLE_COMPARISON);
- }
-
- /**
- * Perform a merge sort on a range of a double array using a specified ordering.
- * @param array the array.
- * @param start the first index.
- * @param end the last index (exclusive).
- * @param comp the comparator object.
- */
- public static void mergeSort(double[] array, int start, int end, DoubleComparator comp) {
- checkBounds(array.length, start, end);
- double[] out = Arrays.copyOf(array, array.length);
- mergeSort(out, array, start, end, comp);
- }
-
- private static void mergeSort(double[] in, double[] out, int start, int end, DoubleComparator c) {
- int len = end - start;
- // use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = start + 1; i < end; i++) {
- double current = out[i];
- double prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
- out[j--] = prev;
- } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (end + start) >>> 1;
- mergeSort(out, in, start, med, c);
- mergeSort(out, in, med, end, c);
-
- // merging
-
- // if arrays are already sorted - no merge
- if (c.compare(in[med - 1], in[med]) <= 0) {
- System.arraycopy(in, start, out, start, len);
- return;
- }
- int r = med;
- int i = start;
-
- // use merging with exponential search
- do {
- double fromVal = in[start];
- double rVal = in[r];
- if (c.compare(fromVal, rVal) <= 0) {
- int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
- int toCopy = l_1 - start + 1;
- System.arraycopy(in, start, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- start = l_1 + 1;
- } else {
- int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- start++;
- r = r_1 + 1;
- }
- } while ((end - r) > 0 && (med - start) > 0);
-
- // copy rest of array
- if ((end - r) <= 0) {
- System.arraycopy(in, start, out, i, med - start);
- } else {
- System.arraycopy(in, r, out, i, end - r);
- }
- }
-
- private static int find(double[] arr, double val, int bnd, int l, int r, DoubleComparator c) {
- int m = l;
- int d = 1;
- while (m <= r) {
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- break;
- }
- m += d;
- d <<= 1;
- }
- while (l <= r) {
- m = (l + r) >>> 1;
- if (c.compare(val, arr[m]) > bnd) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- return l - 1;
- }
-
- /**
- * Transforms two consecutive sorted ranges into a single sorted range. The initial ranges are {@code [first,}
- * middle)</code> and {@code [middle, last)}, and the resulting range is {@code [first, last)}. Elements in
- * the first input range will precede equal elements in the second.
- */
- static void inplaceMerge(int first, int middle, int last, IntComparator comp, Swapper swapper) {
- if (first >= middle || middle >= last) {
- return;
- }
- if (last - first == 2) {
- if (comp.compare(middle, first) < 0) {
- swapper.swap(first, middle);
- }
- return;
- }
- int firstCut;
- int secondCut;
- if (middle - first > last - middle) {
- firstCut = first + (middle - first) / 2;
- secondCut = lowerBound(middle, last, firstCut, comp);
- } else {
- secondCut = middle + (last - middle) / 2;
- firstCut = upperBound(first, middle, secondCut, comp);
- }
-
- // rotate(firstCut, middle, secondCut, swapper);
- // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods
- // are "static private")
- // speedup = 1.7
- // begin inline
- int first2 = firstCut;
- int middle2 = middle;
- int last2 = secondCut;
- if (middle2 != first2 && middle2 != last2) {
- int first1 = first2;
- int last1 = middle2;
- while (first1 < --last1) {
- swapper.swap(first1++, last1);
- }
- first1 = middle2;
- last1 = last2;
- while (first1 < --last1) {
- swapper.swap(first1++, last1);
- }
- first1 = first2;
- last1 = last2;
- while (first1 < --last1) {
- swapper.swap(first1++, last1);
- }
- }
- // end inline
-
- middle = firstCut + (secondCut - middle);
- inplaceMerge(first, firstCut, middle, comp, swapper);
- inplaceMerge(middle, secondCut, last, comp, swapper);
- }
-
- /**
- * Performs a binary search on an already-sorted range: finds the first position where an element can be inserted
- * without violating the ordering. Sorting is by a user-supplied comparison function.
- *
- * @param first Beginning of the range.
- * @param last One past the end of the range.
- * @param x Element to be searched for.
- * @param comp Comparison function.
- * @return The largest index i such that, for every j in the range <code>[first, i)</code>,
- * <code></code></codeA>{@code comp.apply(array[j], x)</code> is {@code true}.
- * @see Sorting#upperBound
- */
- static int lowerBound(int first, int last, int x, IntComparator comp) {
- int len = last - first;
- while (len > 0) {
- int half = len / 2;
- int middle = first + half;
- if (comp.compare(middle, x) < 0) {
- first = middle + 1;
- len -= half + 1;
- } else {
- len = half;
- }
- }
- return first;
- }
-
- /**
- * Sorts the specified range of elements according to the order induced by the specified comparator. All elements in
- * the range must be <i>mutually comparable</i> by the specified comparator (that is, <tt>c.compare(a, b)</tt> must
- * not throw an exception for any indexes <tt>a</tt> and <tt>b</tt> in the range).<p>
- *
- * 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.
- *
- * @param fromIndex the index of the first element (inclusive) to be sorted.
- * @param toIndex the index of the last element (exclusive) to be sorted.
- * @param c the comparator to determine the order of the generic data.
- * @param swapper an object that knows how to swap the elements at any two indexes (a,b).
- * @see IntComparator
- * @see Swapper
- */
- public static void mergeSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
- /*
- We retain the same method signature as quickSort.
- Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
- Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary
- arrays.
- A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
- */
- int length = toIndex - fromIndex;
-
- // Insertion sort on smallest arrays
- if (length < SMALL) {
- for (int i = fromIndex; i < toIndex; i++) {
- for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
- swapper.swap(j, j - 1);
- }
- }
- return;
- }
-
- // Recursively sort halves
- int mid = (fromIndex + toIndex) / 2;
- mergeSort(fromIndex, mid, c, swapper);
- mergeSort(mid, toIndex, c, swapper);
-
- // If list is already sorted, nothing left to do. This is an
- // optimization that results in faster sorts for nearly ordered lists.
- if (c.compare(mid - 1, mid) <= 0) {
- return;
- }
-
- // Merge sorted halves
- inplaceMerge(fromIndex, mid, toIndex, c, swapper);
- }
-
- /**
- * Performs a binary search on an already-sorted range: finds the last position where an element can be inserted
- * without violating the ordering. Sorting is by a user-supplied comparison function.
- *
- * @param first Beginning of the range.
- * @param last One past the end of the range.
- * @param x Element to be searched for.
- * @param comp Comparison function.
- * @return The largest index i such that, for every j in the range <code>[first, i)</code>, {@code comp.apply(x,}
- * array[j])</code> is {@code false}.
- * @see Sorting#lowerBound
- */
- static int upperBound(int first, int last, int x, IntComparator comp) {
- int len = last - first;
- while (len > 0) {
- int half = len / 2;
- int middle = first + half;
- if (comp.compare(x, middle) < 0) {
- len = half;
- } else {
- first = middle + 1;
- len -= half + 1;
- }
- }
- return first;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java
----------------------------------------------------------------------
diff --git a/math/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java b/math/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java
deleted file mode 100644
index eeffc78..0000000
--- a/math/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java
+++ /dev/null
@@ -1,220 +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.
- */
-
-package org.apache.mahout.math;
-
-import org.apache.mahout.math.flavor.TraversingStructureEnum;
-
-/**
- * sparse matrix with general element values whose columns are accessible quickly. Implemented as a column array of
- * SparseVectors.
- *
- * @deprecated tons of inconsistences. Use transpose view of SparseRowMatrix for fast column-wise iteration.
- */
-public class SparseColumnMatrix extends AbstractMatrix {
-
- private Vector[] columnVectors;
-
- /**
- * Construct a matrix of the given cardinality with the given data columns
- *
- * @param columns a RandomAccessSparseVector[] array of columns
- * @param columnVectors
- */
- public SparseColumnMatrix(int rows, int columns, Vector[] columnVectors) {
- this(rows, columns, columnVectors, false);
- }
-
- public SparseColumnMatrix(int rows, int columns, Vector[] columnVectors, boolean shallow) {
- super(rows, columns);
- if (shallow) {
- this.columnVectors = columnVectors;
- } else {
- this.columnVectors = columnVectors.clone();
- for (int col = 0; col < columnSize(); col++) {
- this.columnVectors[col] = this.columnVectors[col].clone();
- }
- }
- }
-
- /**
- * Construct a matrix of the given cardinality
- *
- * @param rows # of rows
- * @param columns # of columns
- */
- public SparseColumnMatrix(int rows, int columns) {
- super(rows, columns);
- this.columnVectors = new RandomAccessSparseVector[columnSize()];
- for (int col = 0; col < columnSize(); col++) {
- this.columnVectors[col] = new RandomAccessSparseVector(rowSize());
- }
- }
-
- @Override
- public Matrix clone() {
- SparseColumnMatrix clone = (SparseColumnMatrix) super.clone();
- clone.columnVectors = new Vector[columnVectors.length];
- for (int i = 0; i < columnVectors.length; i++) {
- clone.columnVectors[i] = columnVectors[i].clone();
- }
- return clone;
- }
-
- /**
- * Abstracted out for the iterator
- *
- * @return {@link #numCols()}
- */
- @Override
- public int numSlices() {
- return numCols();
- }
-
- @Override
- public double getQuick(int row, int column) {
- return columnVectors[column] == null ? 0.0 : columnVectors[column].getQuick(row);
- }
-
- @Override
- public Matrix like() {
- return new SparseColumnMatrix(rowSize(), columnSize());
- }
-
- @Override
- public Matrix like(int rows, int columns) {
- return new SparseColumnMatrix(rows, columns);
- }
-
- @Override
- public void setQuick(int row, int column, double value) {
- if (columnVectors[column] == null) {
- columnVectors[column] = new RandomAccessSparseVector(rowSize());
- }
- columnVectors[column].setQuick(row, value);
- }
-
- @Override
- public int[] getNumNondefaultElements() {
- int[] result = new int[2];
- result[COL] = columnVectors.length;
- for (int col = 0; col < columnSize(); col++) {
- result[ROW] = Math.max(result[ROW], columnVectors[col]
- .getNumNondefaultElements());
- }
- return result;
- }
-
- @Override
- public Matrix viewPart(int[] offset, int[] size) {
- if (offset[ROW] < 0) {
- throw new IndexException(offset[ROW], columnVectors[COL].size());
- }
- if (offset[ROW] + size[ROW] > columnVectors[COL].size()) {
- throw new IndexException(offset[ROW] + size[ROW], columnVectors[COL].size());
- }
- if (offset[COL] < 0) {
- throw new IndexException(offset[COL], columnVectors.length);
- }
- if (offset[COL] + size[COL] > columnVectors.length) {
- throw new IndexException(offset[COL] + size[COL], columnVectors.length);
- }
- return new MatrixView(this, offset, size);
- }
-
- @Override
- public Matrix assignColumn(int column, Vector other) {
- if (rowSize() != other.size()) {
- throw new CardinalityException(rowSize(), other.size());
- }
- if (column < 0 || column >= columnSize()) {
- throw new IndexException(column, columnSize());
- }
- columnVectors[column].assign(other);
- return this;
- }
-
- @Override
- public Matrix assignRow(int row, Vector other) {
- if (columnSize() != other.size()) {
- throw new CardinalityException(columnSize(), other.size());
- }
- if (row < 0 || row >= rowSize()) {
- throw new IndexException(row, rowSize());
- }
- for (int col = 0; col < columnSize(); col++) {
- columnVectors[col].setQuick(row, other.getQuick(col));
- }
- return this;
- }
-
- @Override
- public Vector viewColumn(int column) {
- if (column < 0 || column >= columnSize()) {
- throw new IndexException(column, columnSize());
- }
- return columnVectors[column];
- }
-
- @Override
- public Matrix transpose() {
- SparseRowMatrix srm = new SparseRowMatrix(columns, rows);
- for (int i = 0; i < columns; i++) {
- Vector col = columnVectors[i];
- if (col.getNumNonZeroElements() > 0)
- // this should already be optimized
- srm.assignRow(i, col);
- }
- return srm;
- }
-
- @Override
- public String toString() {
- int row = 0;
- int maxRowsToDisplay = 10;
- int maxColsToDisplay = 20;
- int colsToDisplay = maxColsToDisplay;
-
- if(maxColsToDisplay > columnSize()){
- colsToDisplay = columnSize();
- }
-
- StringBuilder s = new StringBuilder("{\n");
- for (MatrixSlice next : this.transpose()) {
- if (row < maxRowsToDisplay) {
- s.append(" ")
- .append(next.index())
- .append(" =>\t")
- .append(new VectorView(next.vector(), 0, colsToDisplay))
- .append('\n');
- row++;
- }
- }
-
- String returnString = s.toString();
- if (maxColsToDisplay <= columnSize()) {
- returnString = returnString.replace("}", " ... }");
- }
-
- if (maxRowsToDisplay <= rowSize()) {
- return returnString + "... }";
- } else {
- return returnString + "}";
- }
- }
-
-}
http://git-wip-us.apache.org/repos/asf/mahout/blob/e0573de3/math/src/main/java/org/apache/mahout/math/SparseMatrix.java
----------------------------------------------------------------------
diff --git a/math/src/main/java/org/apache/mahout/math/SparseMatrix.java b/math/src/main/java/org/apache/mahout/math/SparseMatrix.java
deleted file mode 100644
index a75ac55..0000000
--- a/math/src/main/java/org/apache/mahout/math/SparseMatrix.java
+++ /dev/null
@@ -1,245 +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.
- */
-
-package org.apache.mahout.math;
-
-import it.unimi.dsi.fastutil.ints.Int2ObjectMap.Entry;
-import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
-import it.unimi.dsi.fastutil.objects.ObjectIterator;
-
-import java.util.Iterator;
-import java.util.Map;
-
-import org.apache.mahout.math.flavor.MatrixFlavor;
-import org.apache.mahout.math.function.DoubleDoubleFunction;
-import org.apache.mahout.math.function.Functions;
-import org.apache.mahout.math.list.IntArrayList;
-
-import com.google.common.collect.AbstractIterator;
-
-/** Doubly sparse matrix. Implemented as a Map of RandomAccessSparseVector rows */
-public class SparseMatrix extends AbstractMatrix {
-
- private Int2ObjectOpenHashMap<Vector> rowVectors;
-
- /**
- * Construct a matrix of the given cardinality with the given row map
- *
- * @param rows no of rows
- * @param columns no of columns
- * @param rowVectors a {@code Map<Integer, RandomAccessSparseVector>} of rows
- */
- public SparseMatrix(int rows, int columns, Map<Integer, Vector> rowVectors) {
- this(rows, columns, rowVectors, false);
- }
-
- public SparseMatrix(int rows, int columns, Map<Integer, Vector> rowVectors, boolean shallow) {
-
- // Why this is passing in a map? iterating it is pretty inefficient as opposed to simple lists...
- super(rows, columns);
- this.rowVectors = new Int2ObjectOpenHashMap<>();
- if (shallow) {
- for (Map.Entry<Integer, Vector> entry : rowVectors.entrySet()) {
- this.rowVectors.put(entry.getKey().intValue(), entry.getValue());
- }
- } else {
- for (Map.Entry<Integer, Vector> entry : rowVectors.entrySet()) {
- this.rowVectors.put(entry.getKey().intValue(), entry.getValue().clone());
- }
- }
- }
-
- /**
- * Construct a matrix with specified number of rows and columns.
- */
- public SparseMatrix(int rows, int columns) {
- super(rows, columns);
- this.rowVectors = new Int2ObjectOpenHashMap<>();
- }
-
- @Override
- public Matrix clone() {
- SparseMatrix clone = new SparseMatrix(numRows(), numCols());
- for (MatrixSlice slice : this) {
- clone.rowVectors.put(slice.index(), slice.clone());
- }
- return clone;
- }
-
- @Override
- public int numSlices() {
- return rowVectors.size();
- }
-
- public Iterator<MatrixSlice> iterateNonEmpty() {
- final int[] keys = rowVectors.keySet().toIntArray();
- return new AbstractIterator<MatrixSlice>() {
- private int slice;
- @Override
- protected MatrixSlice computeNext() {
- if (slice >= rowVectors.size()) {
- return endOfData();
- }
- int i = keys[slice];
- Vector row = rowVectors.get(i);
- slice++;
- return new MatrixSlice(row, i);
- }
- };
- }
-
- @Override
- public double getQuick(int row, int column) {
- Vector r = rowVectors.get(row);
- return r == null ? 0.0 : r.getQuick(column);
- }
-
- @Override
- public Matrix like() {
- return new SparseMatrix(rowSize(), columnSize());
- }
-
- @Override
- public Matrix like(int rows, int columns) {
- return new SparseMatrix(rows, columns);
- }
-
- @Override
- public void setQuick(int row, int column, double value) {
- Vector r = rowVectors.get(row);
- if (r == null) {
- r = new RandomAccessSparseVector(columnSize());
- rowVectors.put(row, r);
- }
- r.setQuick(column, value);
- }
-
- @Override
- public int[] getNumNondefaultElements() {
- int[] result = new int[2];
- result[ROW] = rowVectors.size();
- for (Vector row : rowVectors.values()) {
- result[COL] = Math.max(result[COL], row.getNumNondefaultElements());
- }
- return result;
- }
-
- @Override
- public Matrix viewPart(int[] offset, int[] size) {
- if (offset[ROW] < 0) {
- throw new IndexException(offset[ROW], rowSize());
- }
- if (offset[ROW] + size[ROW] > rowSize()) {
- throw new IndexException(offset[ROW] + size[ROW], rowSize());
- }
- if (offset[COL] < 0) {
- throw new IndexException(offset[COL], columnSize());
- }
- if (offset[COL] + size[COL] > columnSize()) {
- throw new IndexException(offset[COL] + size[COL], columnSize());
- }
- return new MatrixView(this, offset, size);
- }
-
- @Override
- public Matrix assign(Matrix other, DoubleDoubleFunction function) {
- //TODO generalize to other kinds of functions
- if (Functions.PLUS.equals(function) && other instanceof SparseMatrix) {
- int rows = rowSize();
- if (rows != other.rowSize()) {
- throw new CardinalityException(rows, other.rowSize());
- }
- int columns = columnSize();
- if (columns != other.columnSize()) {
- throw new CardinalityException(columns, other.columnSize());
- }
-
- SparseMatrix otherSparse = (SparseMatrix) other;
- for(ObjectIterator<Entry<Vector>> fastIterator = otherSparse.rowVectors.int2ObjectEntrySet().fastIterator();
- fastIterator.hasNext();) {
- final Entry<Vector> entry = fastIterator.next();
- final int rowIndex = entry.getIntKey();
- Vector row = rowVectors.get(rowIndex);
- if (row == null) {
- rowVectors.put(rowIndex, entry.getValue().clone());
- } else {
- row.assign(entry.getValue(), Functions.PLUS);
- }
- }
- return this;
- } else {
- return super.assign(other, function);
- }
- }
-
- @Override
- public Matrix assignColumn(int column, Vector other) {
- if (rowSize() != other.size()) {
- throw new CardinalityException(rowSize(), other.size());
- }
- if (column < 0 || column >= columnSize()) {
- throw new IndexException(column, columnSize());
- }
- for (int row = 0; row < rowSize(); row++) {
- double val = other.getQuick(row);
- if (val != 0.0) {
- Vector r = rowVectors.get(row);
- if (r == null) {
- r = new RandomAccessSparseVector(columnSize());
- rowVectors.put(row, r);
- }
- r.setQuick(column, val);
- }
- }
- return this;
- }
-
- @Override
- public Matrix assignRow(int row, Vector other) {
- if (columnSize() != other.size()) {
- throw new CardinalityException(columnSize(), other.size());
- }
- if (row < 0 || row >= rowSize()) {
- throw new IndexException(row, rowSize());
- }
- rowVectors.put(row, other);
- return this;
- }
-
- @Override
- public Vector viewRow(int row) {
- if (row < 0 || row >= rowSize()) {
- throw new IndexException(row, rowSize());
- }
- Vector res = rowVectors.get(row);
- if (res == null) {
- res = new RandomAccessSparseVector(columnSize());
- rowVectors.put(row, res);
- }
- return res;
- }
-
- /** special method necessary for efficient serialization */
- public IntArrayList nonZeroRowIndices() {
- return new IntArrayList(rowVectors.keySet().toIntArray());
- }
-
- @Override
- public MatrixFlavor getFlavor() {
- return MatrixFlavor.SPARSEROWLIKE;
- }
-}