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     */
020    package org.sonar.duplications.index;
021    
022    public 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    }