1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
// Copyright (c) 2000
// Kevin Atkinson
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without
// fee, provided that the above copyright notice appear in all copies
// and that both that copyright notice and this permission notice
// appear in supporting documentation. Kevin Atkinson makes no
// representations about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
#include <vector>
namespace aspeller {
class Primes {
private:
typedef std::vector<bool> Data;
Data data;
public:
typedef Data::size_type size_type;
typedef Data::size_type value_type;
Primes() {}
Primes(size_type s) {resize(s);}
size_type size() const {return data.size();}
void resize(size_type s);
bool operator[] (size_type pos) const {return data[pos];}
bool is_prime(size_type n) const;
size_type max_num() const {return (size()-1)*(size()-1);}
//
// Iterators
//
class const_reverse_iterator;
class const_iterator {
friend class Primes;
friend class const_reverse_iterator;
protected:
size_type pos;
const Primes* data;
const_iterator(const Primes *d, size_type p) {data = d; pos = p;}
public:
const_iterator() {}
size_type operator* () {return pos;}
const_iterator& operator++ () {
size_type size = data->size();
if (pos != size)
do {++pos;} while (pos != size && !(*data)[pos]);
return *this;
}
const_iterator operator++ (int) {
const_iterator temp = *this;
operator++();
return temp;
}
const_iterator& operator-- () {
if (pos != 0)
do {--pos;} while (pos != 0 && !(*data)[pos]);
return *this;
}
const_iterator operator-- (int) {
const_iterator temp = *this;
operator--();
return temp;
}
const_iterator& jump(size_type p) {
pos = p;
if (!(*data)[pos])
operator++();
return *this;
}
inline friend bool operator == (const const_iterator &rhs,
const const_iterator &lhs) {
return rhs.data == lhs.data && rhs.pos == lhs.pos;
}
};
typedef const_iterator iterator;
class const_reverse_iterator : private const_iterator {
friend class Primes;
protected:
const_reverse_iterator(const Primes *d, size_type p) {data = d; pos = p;}
public:
const_reverse_iterator() {}
const_reverse_iterator(const const_iterator &other) :
const_iterator(other) {}
size_type operator* () const {return pos;}
const_reverse_iterator& operator++ () {const_iterator::operator--(); return *this;}
const_reverse_iterator operator++ (int){return const_iterator::operator--(1);}
const_reverse_iterator& operator-- () {const_iterator::operator++(); return *this;}
const_reverse_iterator operator-- (int) {return const_iterator::operator++(1); return *this;}
const_reverse_iterator& jump(size_type p) {
pos = p;
if (!(*data)[pos])
operator++();
return *this;
}
inline friend bool operator == (const const_reverse_iterator &rhs,
const const_reverse_iterator &lhs) {
return rhs.data == lhs.data && rhs.pos == lhs.pos;
}
};
typedef const_reverse_iterator reverse_iterator;
typedef Data::const_iterator const_ra_iterator;
typedef const_ra_iterator ra_iterator;
typedef Data::const_reverse_iterator const_reverse_ra_iterator;
typedef const_reverse_ra_iterator reverse_ra_iterator;
const_iterator begin() const {return const_iterator(this, 2);}
const_iterator end() const {return const_iterator(this, size());}
const_iterator jump(size_type p) {return const_iterator(this,0).jump(p);}
const_reverse_iterator rbegin() const {return ++const_reverse_iterator(this, size());}
const_reverse_iterator rend() const {return const_reverse_iterator(this, 0);}
const_reverse_iterator rjump(size_type p) {return const_reverse_iterator(this,0).jump(p);}
const_ra_iterator ra_begin() const {return data.begin();}
const_ra_iterator ra_end() const {return data.end();}
const_reverse_ra_iterator r_ra_begin() const {return data.rbegin();}
const_reverse_ra_iterator r_ra_end() const {return data.rend();}
};
}
|
