[03/52] [partial] mahout git commit: removed all files except for website directory

[vanstee]

http://git-wip-us.apache.org/repos/asf/mahout/blob/99a5358f/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/99a5358f/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/99a5358f/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;
-  }
-}