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