-
Notifications
You must be signed in to change notification settings - Fork 0
/
FibonacciIterator.hh
185 lines (167 loc) · 7.39 KB
/
FibonacciIterator.hh
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/******************************************************************************
* File: FibonacciIterator.hh
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An STL-style iterator for iterating across the Fibonacci numbers. This
* iterator stores two Fibonacci numbers, F(n) and F(n+1), and can move around
* the entries of the Fibonacci sequence one at a time by using the two
* values to produce either the next value in the sequence or the preivous
* value in the sequence. For example, given F(n) and F(n+1) we can produce
* an iterator for F(n+1), F(n+2) by using the fact that
*
* (F(n+1), F(n+2)) = (F(n+1), F(n) + F(n+1))
*
* Similarly, we can get an iterator to (F(n-1), F(n)) by noting that
*
* (F(n-1), F(n)) = (F(n+1) - F(n), F(n))
*
* At each point, the iterator acts as though it is iterating over the first
* value in the tuple, so the iterator (F(3), F(4)) looks like an iterator over
* the value F(3) = 2.
*
* The implementation of a Fibonacci iterator provided in this header file
* allows the type of the numbers used by the iterator to be customized along
* with the binary addition and subtraction operators used. This means that
* the implementation can be customized so that it computes Fibonacci numbers
* with a custom integer type, or to allow for computation of Fibonacci numbers
* in a group other than the integers. For example, if the addition and
* subtraction operators are implemented as multiplication and division, then
* the Fibonacci iterator will visit Fibonacci powers of a number, which can be
* used to take logarithms efficiently.
*/
#ifndef FibonacciIterator_Included
#define FibonacciIterator_Included
#include <functional> // For std::plus, std::minus
#include <iterator> // For std::bidirectional_iterator_tag, std::iterator
/**
* An iterator class capable of navigating across the Fibonacci sequence using
* a user-specified integer type.
*/
template <typename Integer, typename Plus = std::plus<Integer>,
typename Minus = std::minus<Integer> >
class FibonacciIterator: public std::iterator<std::bidirectional_iterator_tag,
const Integer> {
public:
/**
* Constructor: FibonacciIterator(Integer zero = Integer(0),
* Integer one = Integer(1),
* Plus p = Plus(), Minus m = Minus())
* Usage: FibonacciIterator<int> itr;
* --------------------------------------------------------------------------
* Constructs a new Fibonacci iterator traversing the Fibonacci sequence
* whose first two terms are zero and one and that uses the specified plus
* and minus function objects to navigate the sequence.
*/
explicit FibonacciIterator(Integer zero = Integer(0),
Integer one = Integer(1),
Plus p = Plus(), Minus m = Minus());
/**
* operator* () const;
* operator-> () const;
* Usage: cout << *itr << endl;
* --------------------------------------------------------------------------
* Dereferences and returns the current integer in the sequence. You should
* not modify the values returned as they are not guaranteed to be valid
* after the iterator advances. Moreover, you should not hold pointers or
* references to these values, as the memory will be recycled after the
* iterator is incremented or decremented.
*/
const Integer& operator* () const;
const Integer* operator-> () const;
/**
* operator++ ();
* operator++ (int);
* operator-- ();
* operator-- (int);
* Usage: ++itr; --itr; itr++; itr--;
* --------------------------------------------------------------------------
* Moves the iterator one step forward or backward in the Fibonacci sequence.
* If integer overflow occurs, the results depend on the type of the integer
* being used as a counter. If the iterator is backed up while at 0, the
* results are mathematically well-defined but depend on the underlying type
* of the integer for correctness.
*/
FibonacciIterator& operator++ ();
const FibonacciIterator operator++ (int);
FibonacciIterator& operator-- ();
const FibonacciIterator operator-- (int);
private:
/* The current and next Fibonacci values in the sequence. */
Integer curr, next;
/* The plus and minus operators. */
Plus plus;
Minus minus;
};
/* Comparison functions for FibonacciIterator. */
template <typename Integer, typename Plus, typename Minus>
bool operator== (const FibonacciIterator<Integer, Plus, Minus>& lhs,
const FibonacciIterator<Integer, Plus, Minus>& rhs);
template <typename Integer, typename Plus, typename Minus>
bool operator!= (const FibonacciIterator<Integer, Plus, Minus>& lhs,
const FibonacciIterator<Integer, Plus, Minus>& rhs);
/* * * * * Implementation Below This Point * * * * */
/* Constructor sets up the internal fields based on the parameters. */
template <typename Integer, typename Plus, typename Minus>
FibonacciIterator<Integer, Plus, Minus>::FibonacciIterator(Integer zero,
Integer one,
Plus plus,
Minus minus)
: curr(zero), next(one), plus(plus), minus(minus) {
// Handled in initializer list.
}
/* Dereferencing to a value just returns the current value in the sequence. */
template <typename Integer, typename Plus, typename Minus>
const Integer& FibonacciIterator<Integer, Plus, Minus>::operator* () const {
return curr;
}
template <typename Integer, typename Plus, typename Minus>
const Integer* FibonacciIterator<Integer, Plus, Minus>::operator-> () const {
return &**this;
}
/* Incrementing the Fibonacci iterator walks forward one step in the Fibonacci
* series.
*/
template <typename Integer, typename Plus, typename Minus>
FibonacciIterator<Integer, Plus, Minus>&
FibonacciIterator<Integer, Plus, Minus>::operator++ () {
Integer newNext = plus(curr, next);
curr = next;
next = newNext;
return *this;
}
template <typename Integer, typename Plus, typename Minus>
const FibonacciIterator<Integer, Plus, Minus>
FibonacciIterator<Integer, Plus, Minus>::operator++ (int) {
FibonacciIterator result = *this;
++ *this;
return result;
}
/* Decrementing the Fibonacci iterator backs it up one step in the sequence. */
template <typename Integer, typename Plus, typename Minus>
FibonacciIterator<Integer, Plus, Minus>&
FibonacciIterator<Integer, Plus, Minus>::operator-- () {
Integer prev = minus(next, curr);
next = curr;
curr = prev;
return *this;
}
template <typename Integer, typename Plus, typename Minus>
const FibonacciIterator<Integer, Plus, Minus>
FibonacciIterator<Integer, Plus, Minus>::operator-- (int) {
FibonacciIterator result = *this;
-- *this;
return result;
}
/* Equality comparisons just check if the two values are equal. */
template <typename Integer, typename Plus, typename Minus>
bool operator== (const FibonacciIterator<Integer, Plus, Minus>& lhs,
const FibonacciIterator<Integer, Plus, Minus>& rhs) {
return lhs.curr == rhs.curr && lhs.next == rhs.next;
}
/* Disequality implemented in terms of equality. */
template <typename Integer, typename Plus, typename Minus>
bool operator!= (const FibonacciIterator<Integer, Plus, Minus>& lhs,
const FibonacciIterator<Integer, Plus, Minus>& rhs) {
return !(lhs == rhs);
}
#endif