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  }