001/*
002 * Sonar, open source software quality management tool.
003 * Copyright (C) 2008-2012 SonarSource
004 * mailto:contact AT sonarsource DOT com
005 *
006 * Sonar is free software; you can redistribute it and/or
007 * modify it under the terms of the GNU Lesser General Public
008 * License as published by the Free Software Foundation; either
009 * version 3 of the License, or (at your option) any later version.
010 *
011 * Sonar is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014 * Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public
017 * License along with Sonar; if not, write to the Free Software
018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
019 */
020package org.sonar.duplications.index;
021
022public final class DataUtils {
023
024  public interface Sortable {
025
026    /**
027     * @return the number of elements.
028     */
029    int size();
030
031    /**
032     * Swaps elements in positions i and j.
033     */
034    void swap(int i, int j);
035
036    /**
037     * @return true if element in position i less than in position j.
038     */
039    boolean isLess(int i, int j);
040
041  }
042
043  /**
044   * Value for search must be stored in position {@link Sortable#size() size}.
045   */
046  public static int binarySearch(Sortable data) {
047    int value = data.size();
048    int lower = 0;
049    int upper = data.size();
050    while (lower < upper) {
051      int mid = (lower + upper) >> 1;
052      if (data.isLess(mid, value)) {
053        lower = mid + 1;
054      } else {
055        upper = mid;
056      }
057    }
058    return lower;
059  }
060
061  public static void sort(Sortable data) {
062    quickSort(data, 0, data.size() - 1);
063  }
064
065  private static void bubbleSort(Sortable data, int left, int right) {
066    for (int i = right; i > left; i--) {
067      for (int j = left; j < i; j++) {
068        if (data.isLess(j + 1, j)) {
069          data.swap(j, j + 1);
070        }
071      }
072    }
073  }
074
075  private static int partition(Sortable data, int i, int j) {
076    // can be selected randomly
077    int pivot = i + (j - i) / 2;
078    while (i <= j) {
079      while (data.isLess(i, pivot)) {
080        i++;
081      }
082      while (data.isLess(pivot, j)) {
083        j--;
084      }
085      if (i <= j) {
086        data.swap(i, j);
087        if (i == pivot) {
088          pivot = j;
089        } else if (j == pivot) {
090          pivot = i;
091        }
092        i++;
093        j--;
094      }
095    }
096    return i;
097  }
098
099  private static void quickSort(Sortable data, int low, int high) {
100    if (high - low < 5) {
101      bubbleSort(data, low, high);
102      return;
103    }
104    int i = partition(data, low, high);
105    if (low < i - 1) {
106      quickSort(data, low, i - 1);
107    }
108    if (i < high) {
109      quickSort(data, i, high);
110    }
111  }
112
113  private DataUtils() {
114  }
115
116}