1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  galois_field_iterator.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the
6%%  class galois_field_iterator
7%%
8%%  Copyright   (c) 2004   by the LiDIA-Group
9%%
10%%  Author:  Christoph Ludwig
11%%
12
13%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
14
15\NAME
16
17\CLASS{galois_field_iterator} \dotfill iterator over galois fields
18
19
20%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
21
22\ABSTRACT
23
24\code{galois_field_iterator} allows you to enumerate all
25elements of a galois field.
26
27
28%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
29
30\DESCRIPTION
31
32There are cases where it's cheaper to simply enumerate the elements
33of a field rather than to search for a generator of the multiplicative group
34and then to iterate through all powers of this
35generator. \code{galois_field_iterator} is intended as the tool of choice
36for such cases.
37
38\code{galois_field_iterator} imposes a somewhat arbitrary ordering on the
39elements of a \code{galois_field}. (It's the lexicographic ordering on
40the polynomials representing the field elements.) Variables of type
41\code{galois_field_iterator} essentially behave as if they were pointers into
42an sorted array of all field elements. This imagined array -- or \emph{range}
43in the terminology of the ISO C++ standard -- of all field elements is
44accessible through the member functions \code{begin()} and \code{end()} of
45\code{galois_field}.
46
47\code{galois_field_iterator} is a model of the \emph{bidirectional iterator
48  concept} and defines the typedefs \code{value_type},
49\code{iterator_category}, \code{pointer}, and \code{reference}.
50
51Recall that the range $[\code{iter1}, \code{iter2})$ defined by the iterators
52\code{iter1}, \code{iter2} ends \emph{before} \code{iter2}. In general, it is
53therefore an error to dereference \code{iter2}.
54
55%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
56
57\CONS
58
59\begin{fcode}{ct}{galois_field_iterator}{}
60  constructs an iterator over the empty ``dummy'' field
61  \code{galois_field()}.
62\end{fcode}
63
64\begin{fcode}{ct}{galois_field_iterator}{galois_field const& $K$}
65  constructs an iterator pointing to the ``first'' element in $K$. I.\,e., the
66  constructed iterator points to $0$ unless $K$ is the empty ``dummy'' field.
67\end{fcode}
68
69\begin{fcode}{ct}{galois_field_iterator}{gf_element const& $x$}
70  constructs an iterator over the field \code{$x$.get_field()} pointing to
71  $x$. The postcondition is \code{*galois_field_iterator($x$) == $x$}.
72\end{fcode}
73
74\begin{fcode}{ct}{galois_field_iterator}{galois_field_iterator const& iter}
75  the usual copy constructor.
76\end{fcode}
77
78
79%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
80
81\ACCS
82
83Let \code{iter} be an instance of type \code{galois_field_iterator}.
84
85\begin{cfcode}{galois_field const&}{iter.get_field}{}
86  returns the field over which \code{iter} iterates.
87\end{cfcode}
88
89\begin{cfcode}{gf_element const&}{iter.operator*}{}
90  returns the element \code{iter} points to. If \code{iter} is defined over
91  the empty ``dummy'' field (\code{iter.get_field() == galois_field()}) or
92  \code{iter} points past the last element of the corresponding field then a
93  \code{precondition_error} is raised.
94\end{cfcode}
95
96\begin{cfcode}{gf_element const*}{iter.operator->}{}
97  returns the address of the element \code{iter} points to.
98  If \code{iter} is defined over the empty ``dummy'' field
99  (\code{iter.get_field() == galois_field()}) or \code{iter} points past the
100  last element of the corresponding field then a \code{precondition_error} is
101  raised.
102\end{cfcode}
103
104%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
105
106\ASGN
107
108Let \code{iter} be an instance of type \code{galois_field_iterator}.
109The operator \code{=} is overloaded. The following functions are also
110implemented:
111
112\begin{fcode}{void}{iter.move_past_the_end}{}
113  assigns the iterator pointing one past the last element of the corresponding
114  field. This function requires only constant time.
115\end{fcode}
116
117\begin{fcode}{void}{swap}{galois_field_iterator& lhs,
118    galois_field_iterator& rhs}
119  replaces the value of lhs by rhs and vice versa.
120\end{fcode}
121
122%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
123
124\COMP
125
126The operators \code{==} and \code{!=} are overloaded. Two iterators
127\code{iter1} and \code{iter2} compare equal if and only if at least
128one of the following conditions holds:
129\begin{itemize}
130\item both iterators belong to the empty ``dummy'' field
131\item the iterators belong to the same field and both point past the last
132  element.
133\item the iterators belong to the same field and both point to the same
134  element.
135\end{itemize}
136
137%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
138
139\BASIC
140
141Let \code{iter} be an instance of type \code{galois_field_iterator}.
142
143\begin{fcode}{galois_field_iterator&}{iter.operator++}{}
144  \code{++iter} makes \code{iter} point to the next element in
145  the corresponding field and returns a reference to \code{iter}.
146
147  The preincrement operator fails if \code{iter} belongs to the empty
148  ``dummy'' field or if it points past the last element of its field.
149\end{fcode}
150
151\begin{fcode}{galois_field_iterator}{iter.operator++}{int}
152  \code{iter++} makes \code{iter} point to the next element in
153  the corresponding field and returns the original value of \code{iter}.
154
155  The postincrement operator fails if \code{iter} belongs to the empty
156  ``dummy'' field or if it points past the last element of its field.
157\end{fcode}
158
159\begin{fcode}{galois_field_iterator}{iter.operator-{}-}{}
160  \code{-{}-iter} makes \code{iter} point to the previous element in
161  the corresponding field and returns a reference to \code{iter}.
162
163  The predecrement operator fails if \code{iter} belongs to the empty
164  ``dummy'' field or if it points to the first element of its field, i.\,e.\
165  if \code{*iter == gf_element(iter.get_field())}.
166\end{fcode}
167
168\begin{fcode}{galois_field_iterator}{iter.operator-{}-}{int}
169  \code{iter-{}-} makes \code{iter} point to the previous element in
170  the corresponding field and returns the original value of \code{iter}.
171
172  The postdecrement operator fails if \code{iter} belongs to the empty
173  ``dummy'' field or if it points to the first element of its field, i.\,e.\
174  if \code{*iter == gf_element(iter.get_field())}.
175\end{fcode}
176
177%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
178
179\SEEALSO
180
181\SEE{galois_field}
182
183
184%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
185
186\EXAMPLES
187
188\begin{quote}
189\begin{verbatim}
190#include <iostream>
191
192#include "LiDIA/galois_field.h"
193#include "LiDIA/gf_element.h"
194#include "LiDIA/galois_field_iterator.h"
195
196using namespace std;
197using namespace LiDIA;
198
199int main() {
200  galois_field gf(5, 2);
201
202  cout << "All elements of galois_field(5, 2):\n ";
203  galois_field_iterator end_iter = gf.end();
204  for(galois_field_iterator iter = gf.begin(); iter != end_iter; ++iter) {
205    cout << " " << *iter;
206  }
207  cout << endl;
208}
209\end{verbatim}
210\end{quote}
211produces the following output:
212\begin{quote}
213\begin{verbatim}
214  All elements of galois_field(5, 2):
215  (0) (1) (2) (3) (4) (x) (x+ 1) (x+ 2) (x+ 3) (x+ 4) (2 * x)
216  (2 * x+ 1) (2 * x+ 2) (2 * x+ 3) (2 * x+ 4) (3 * x) (3 * x+ 1)
217  (3 * x+ 2) (3 * x+ 3) (3 * x+ 4) (4 * x) (4 * x+ 1) (4 * x+ 2)
218  (4 * x+ 3) (4 * x+ 4)
219\end{verbatim}
220\end{quote}
221
222A further example can be found in the file
223\url{src/finite_fields/gfpn/galois_field_iterator_appl.cc}.
224%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
225
226\AUTHOR
227
228Christoph Ludwig
229
230%%% Local Variables:
231%%% mode: latex
232%%% TeX-master: t
233%%% End:
234