]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
1 | // Copyright 2008 Google Inc. |
2 | // All Rights Reserved. | |
3 | // | |
4 | // Redistribution and use in source and binary forms, with or without | |
5 | // modification, are permitted provided that the following conditions are | |
6 | // met: | |
7 | // | |
8 | // * Redistributions of source code must retain the above copyright | |
9 | // notice, this list of conditions and the following disclaimer. | |
10 | // * Redistributions in binary form must reproduce the above | |
11 | // copyright notice, this list of conditions and the following disclaimer | |
12 | // in the documentation and/or other materials provided with the | |
13 | // distribution. | |
14 | // * Neither the name of Google Inc. nor the names of its | |
15 | // contributors may be used to endorse or promote products derived from | |
16 | // this software without specific prior written permission. | |
17 | // | |
18 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
19 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
20 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
21 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
22 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
23 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
24 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
25 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
26 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
27 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
28 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
29 | // | |
30 | // Author: wan@google.com (Zhanyong Wan) | |
31 | // Author: vladl@google.com (Vlad Losev) | |
32 | ||
33 | // This provides interface PrimeTable that determines whether a number is a | |
34 | // prime and determines a next prime number. This interface is used | |
35 | // in Google Test samples demonstrating use of parameterized tests. | |
36 | ||
37 | #ifndef GTEST_SAMPLES_PRIME_TABLES_H_ | |
38 | #define GTEST_SAMPLES_PRIME_TABLES_H_ | |
39 | ||
40 | #include <algorithm> | |
41 | ||
42 | // The prime table interface. | |
43 | class PrimeTable { | |
44 | public: | |
45 | virtual ~PrimeTable() {} | |
46 | ||
47 | // Returns true iff n is a prime number. | |
48 | virtual bool IsPrime(int n) const = 0; | |
49 | ||
50 | // Returns the smallest prime number greater than p; or returns -1 | |
51 | // if the next prime is beyond the capacity of the table. | |
52 | virtual int GetNextPrime(int p) const = 0; | |
53 | }; | |
54 | ||
55 | // Implementation #1 calculates the primes on-the-fly. | |
56 | class OnTheFlyPrimeTable : public PrimeTable { | |
57 | public: | |
58 | virtual bool IsPrime(int n) const { | |
59 | if (n <= 1) return false; | |
60 | ||
61 | for (int i = 2; i*i <= n; i++) { | |
62 | // n is divisible by an integer other than 1 and itself. | |
63 | if ((n % i) == 0) return false; | |
64 | } | |
65 | ||
66 | return true; | |
67 | } | |
68 | ||
69 | virtual int GetNextPrime(int p) const { | |
70 | for (int n = p + 1; n > 0; n++) { | |
71 | if (IsPrime(n)) return n; | |
72 | } | |
73 | ||
74 | return -1; | |
75 | } | |
76 | }; | |
77 | ||
78 | // Implementation #2 pre-calculates the primes and stores the result | |
79 | // in an array. | |
80 | class PreCalculatedPrimeTable : public PrimeTable { | |
81 | public: | |
82 | // 'max' specifies the maximum number the prime table holds. | |
83 | explicit PreCalculatedPrimeTable(int max) | |
84 | : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) { | |
85 | CalculatePrimesUpTo(max); | |
86 | } | |
87 | virtual ~PreCalculatedPrimeTable() { delete[] is_prime_; } | |
88 | ||
89 | virtual bool IsPrime(int n) const { | |
90 | return 0 <= n && n < is_prime_size_ && is_prime_[n]; | |
91 | } | |
92 | ||
93 | virtual int GetNextPrime(int p) const { | |
94 | for (int n = p + 1; n < is_prime_size_; n++) { | |
95 | if (is_prime_[n]) return n; | |
96 | } | |
97 | ||
98 | return -1; | |
99 | } | |
100 | ||
101 | private: | |
102 | void CalculatePrimesUpTo(int max) { | |
103 | ::std::fill(is_prime_, is_prime_ + is_prime_size_, true); | |
104 | is_prime_[0] = is_prime_[1] = false; | |
105 | ||
106 | for (int i = 2; i <= max; i++) { | |
107 | if (!is_prime_[i]) continue; | |
108 | ||
109 | // Marks all multiples of i (except i itself) as non-prime. | |
110 | for (int j = 2*i; j <= max; j += i) { | |
111 | is_prime_[j] = false; | |
112 | } | |
113 | } | |
114 | } | |
115 | ||
116 | const int is_prime_size_; | |
117 | bool* const is_prime_; | |
118 | ||
119 | // Disables compiler warning "assignment operator could not be generated." | |
120 | void operator=(const PreCalculatedPrimeTable& rhs); | |
121 | }; | |
122 | ||
123 | #endif // GTEST_SAMPLES_PRIME_TABLES_H_ |