SortAndPruneComposites xref

View Javadoc

    1   /**
    2    * Copyright (c) 2004-2011 QOS.ch
    3    * All rights reserved.
    4    *
    5    * Permission is hereby granted, free  of charge, to any person obtaining
    6    * a  copy  of this  software  and  associated  documentation files  (the
    7    * "Software"), to  deal in  the Software without  restriction, including
    8    * without limitation  the rights to  use, copy, modify,  merge, publish,
    9    * distribute,  sublicense, and/or sell  copies of  the Software,  and to
    10   * permit persons to whom the Software  is furnished to do so, subject to
    11   * the following conditions:
    12   *
    13   * The  above  copyright  notice  and  this permission  notice  shall  be
    14   * included in all copies or substantial portions of the Software.
    15   *
    16   * THE  SOFTWARE IS  PROVIDED  "AS  IS", WITHOUT  WARRANTY  OF ANY  KIND,
    17   * EXPRESS OR  IMPLIED, INCLUDING  BUT NOT LIMITED  TO THE  WARRANTIES OF
    18   * MERCHANTABILITY,    FITNESS    FOR    A   PARTICULAR    PURPOSE    AND
    19   * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
    20   * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
    21   * OF CONTRACT, TORT OR OTHERWISE,  ARISING FROM, OUT OF OR IN CONNECTION
    22   * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
    23   *
    24   */
    25  package org.slf4j.profiler;
    26
    27  import java.util.ArrayList;
    28  import java.util.Arrays;
    29
    30  public class SortAndPruneComposites {
    31
    32      static String NESTED_PROFILER_NAME = "SORT_AND_PRUNE";
    33
    34      final int[] originalArray;
    35      final int originalArrrayLength;
    36
    37      public SortAndPruneComposites(int[] randomArray) {
    38          this.originalArray = randomArray;
    39          this.originalArrrayLength = randomArray.length;
    40
    41      }
    42
    43      public int[] sortAndPruneComposites() {
    44          // retrieve previously registered profiler named "SORT_AND_PRUNE"
    45          ProfilerRegistry profilerRegistry = ProfilerRegistry.getThreadContextInstance();
    46          Profiler sortProfiler = profilerRegistry.get(NESTED_PROFILER_NAME);
    47
    48          // start a new stopwatch called SORT
    49          sortProfiler.start("SORT");
    50          int[] sortedArray = sort();
    51          // start a new stopwatch called PRUNE_COMPOSITES
    52          sortProfiler.start("PRUNE_COMPOSITES");
    53          int result[] = pruneComposites(sortedArray);
    54
    55          return result;
    56      }
    57
    58      private int[] sort() {
    59          int[] sortedArray = new int[originalArrrayLength];
    60          System.arraycopy(originalArray, 0, sortedArray, 0, originalArrrayLength);
    61          Arrays.sort(sortedArray);
    62          return sortedArray;
    63      }
    64
    65      int[] pruneComposites(int[] sortedArray) {
    66          ArrayList<Integer> primesArray = new ArrayList<Integer>();
    67          for (int i = 0; i < originalArrrayLength; i++) {
    68              int n = sortedArray[i];
    69              if (isPrime(n)) {
    70                  primesArray.add(n);
    71              }
    72          }
    73          int resultSize = primesArray.size();
    74          int[] result = new int[resultSize];
    75
    76          for (int i = 0; i < resultSize; i++) {
    77              result[i] = primesArray.get(i);
    78          }
    79          return result;
    80      }
    81
    82      public boolean isPrime(int n) {
    83          if (n < 2) {
    84              return false;
    85          }
    86          if (n % 2 == 0) {
    87              return false;
    88          }
    89          for (int i = 3; i * i <= n; i += 2) {
    90              if (n % i == 0) {
    91                  return false;
    92              }
    93          }
    94          return true;
    95      }
    96  }