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/29 16:10:55 UTC
[11/18] mahout git commit: MAHOUT-2033 Fixed Map-Reduce Refactor
http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/Sorting.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/Sorting.java b/core/src/main/java/org/apache/mahout/math/Sorting.java
deleted file mode 100644
index da8f258..0000000
--- a/core/src/main/java/org/apache/mahout/math/Sorting.java
+++ /dev/null
@@ -1,2299 +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.
-// */
-//
-// Note From Trevo: These Comporators all seem to be MR related.
-//
-//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/49ad8cb4/core/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java b/core/src/main/java/org/apache/mahout/math/SparseColumnMatrix.java
deleted file mode 100644
index eeffc78..0000000
--- a/core/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 + "}";
- }
- }
-
-}