← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/mozc/oneiric

« back to all changes in this revision

Viewing changes to third_party/gtest/samples/prime_tables.h

  • Committer: Bazaar Package Importer
  • Author(s): Nobuhiro Iwamatsu
  • Date: 2010-07-14 03:26:47 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100714032647-13qjisj6m8cm8jdx
Tags: 0.12.410.102-1
http://bugs.debian.org/588971
http://bugs.debian.org/588972
* New upstream release (Closes: #588971).
  - Add mozc-server, mozc-utils-gui and scim-mozc packages.
* Update debian/rules.
  Add --gypdir option to build_mozc.py.
* Update debian/control.
  - Bumped standards-version to 3.9.0.
  - Update description.
* Add mozc icon (Closes: #588972).
* Add patch which revises issue 18.
  ibus_mozc_issue18.patch
* kFreeBSD build support.
  support_kfreebsd.patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/gtest/samples/prime_tables.h
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_