001/**
002 * Copyright (c) 2004-2011 QOS.ch
003 * All rights reserved.
004 *
005 * Permission is hereby granted, free  of charge, to any person obtaining
006 * a  copy  of this  software  and  associated  documentation files  (the
007 * "Software"), to  deal in  the Software without  restriction, including
008 * without limitation  the rights to  use, copy, modify,  merge, publish,
009 * distribute,  sublicense, and/or sell  copies of  the Software,  and to
010 * permit persons to whom the Software  is furnished to do so, subject to
011 * the following conditions:
012 *
013 * The  above  copyright  notice  and  this permission  notice  shall  be
014 * included in all copies or substantial portions of the Software.
015 *
016 * THE  SOFTWARE IS  PROVIDED  "AS  IS", WITHOUT  WARRANTY  OF ANY  KIND,
017 * EXPRESS OR  IMPLIED, INCLUDING  BUT NOT LIMITED  TO THE  WARRANTIES OF
018 * MERCHANTABILITY,    FITNESS    FOR    A   PARTICULAR    PURPOSE    AND
019 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
020 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
021 * OF CONTRACT, TORT OR OTHERWISE,  ARISING FROM, OUT OF OR IN CONNECTION
022 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
023 *
024 */
025package org.slf4j.profiler;
026
027import java.util.ArrayList;
028import java.util.Arrays;
029
030public class SortAndPruneComposites {
031
032    static String NESTED_PROFILER_NAME = "SORT_AND_PRUNE";
033
034    final int[] originalArray;
035    final int originalArrrayLength;
036
037    public SortAndPruneComposites(int[] randomArray) {
038        this.originalArray = randomArray;
039        this.originalArrrayLength = randomArray.length;
040
041    }
042
043    public int[] sortAndPruneComposites() {
044        // retrieve previously registered profiler named "SORT_AND_PRUNE"
045        ProfilerRegistry profilerRegistry = ProfilerRegistry.getThreadContextInstance();
046        Profiler sortProfiler = profilerRegistry.get(NESTED_PROFILER_NAME);
047
048        // start a new stopwatch called SORT
049        sortProfiler.start("SORT");
050        int[] sortedArray = sort();
051        // start a new stopwatch called PRUNE_COMPOSITES
052        sortProfiler.start("PRUNE_COMPOSITES");
053        int[] result = pruneComposites(sortedArray);
054
055        return result;
056    }
057
058    private int[] sort() {
059        int[] sortedArray = new int[originalArrrayLength];
060        System.arraycopy(originalArray, 0, sortedArray, 0, originalArrrayLength);
061        Arrays.sort(sortedArray);
062        return sortedArray;
063    }
064
065    int[] pruneComposites(int[] sortedArray) {
066        ArrayList<Integer> primesArray = new ArrayList<>();
067        for (int i = 0; i < originalArrrayLength; i++) {
068            int n = sortedArray[i];
069            if (isPrime(n)) {
070                primesArray.add(n);
071            }
072        }
073        int resultSize = primesArray.size();
074        int[] result = new int[resultSize];
075
076        for (int i = 0; i < resultSize; i++) {
077            result[i] = primesArray.get(i);
078        }
079        return result;
080    }
081
082    public boolean isPrime(int n) {
083        if (n < 2) {
084            return false;
085        }
086        if (n % 2 == 0) {
087            return false;
088        }
089        for (int i = 3; i * i <= n; i += 2) {
090            if (n % i == 0) {
091                return false;
092            }
093        }
094        return true;
095    }
096}