%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  galois_field_iterator.tex       LiDIA documentation
%%
%%  This file contains the documentation of the
%%  class galois_field_iterator
%%
%%  Copyright   (c) 2004   by the LiDIA-Group
%%
%%  Author:  Christoph Ludwig
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NAME

\CLASS{galois_field_iterator} \dotfill iterator over galois fields


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ABSTRACT

\code{galois_field_iterator} allows you to enumerate all
elements of a galois field.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DESCRIPTION

There are cases where it's cheaper to simply enumerate the elements
of a field rather than to search for a generator of the multiplicative group
and then to iterate through all powers of this
generator. \code{galois_field_iterator} is intended as the tool of choice
for such cases.

\code{galois_field_iterator} imposes a somewhat arbitrary ordering on the
elements of a \code{galois_field}. (It's the lexicographic ordering on
the polynomials representing the field elements.) Variables of type
\code{galois_field_iterator} essentially behave as if they were pointers into
an sorted array of all field elements. This imagined array -- or \emph{range}
in the terminology of the ISO C++ standard -- of all field elements is
accessible through the member functions \code{begin()} and \code{end()} of
\code{galois_field}.

\code{galois_field_iterator} is a model of the \emph{bidirectional iterator
  concept} and defines the typedefs \code{value_type},
\code{iterator_category}, \code{pointer}, and \code{reference}.

Recall that the range $[\code{iter1}, \code{iter2})$ defined by the iterators
\code{iter1}, \code{iter2} ends \emph{before} \code{iter2}. In general, it is
therefore an error to dereference \code{iter2}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CONS

\begin{fcode}{ct}{galois_field_iterator}{}
  constructs an iterator over the empty ``dummy'' field
  \code{galois_field()}. 
\end{fcode}

\begin{fcode}{ct}{galois_field_iterator}{galois_field const& $K$}
  constructs an iterator pointing to the ``first'' element in $K$. I.\,e., the
  constructed iterator points to $0$ unless $K$ is the empty ``dummy'' field.
\end{fcode}

\begin{fcode}{ct}{galois_field_iterator}{gf_element const& $x$}
  constructs an iterator over the field \code{$x$.get_field()} pointing to
  $x$. The postcondition is \code{*galois_field_iterator($x$) == $x$}.  
\end{fcode}

\begin{fcode}{ct}{galois_field_iterator}{galois_field_iterator const& iter}
  the usual copy constructor.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ACCS

Let \code{iter} be an instance of type \code{galois_field_iterator}.

\begin{cfcode}{galois_field const&}{iter.get_field}{}
  returns the field over which \code{iter} iterates.
\end{cfcode}

\begin{cfcode}{gf_element const&}{iter.operator*}{}
  returns the element \code{iter} points to. If \code{iter} is defined over
  the empty ``dummy'' field (\code{iter.get_field() == galois_field()}) or
  \code{iter} points past the last element of the corresponding field then a
  \code{precondition_error} is raised.
\end{cfcode}

\begin{cfcode}{gf_element const*}{iter.operator->}{}
  returns the address of the element \code{iter} points to.
  If \code{iter} is defined over the empty ``dummy'' field
  (\code{iter.get_field() == galois_field()}) or \code{iter} points past the
  last element of the corresponding field then a \code{precondition_error} is
  raised. 
\end{cfcode}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ASGN

Let \code{iter} be an instance of type \code{galois_field_iterator}.
The operator \code{=} is overloaded. The following functions are also
implemented: 

\begin{fcode}{void}{iter.move_past_the_end}{}
  assigns the iterator pointing one past the last element of the corresponding
  field. This function requires only constant time.
\end{fcode}

\begin{fcode}{void}{swap}{galois_field_iterator& lhs,
    galois_field_iterator& rhs}
  replaces the value of lhs by rhs and vice versa.
\end{fcode}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\COMP

The operators \code{==} and \code{!=} are overloaded. Two iterators
\code{iter1} and \code{iter2} compare equal if and only if at least
one of the following conditions holds:
\begin{itemize}
\item both iterators belong to the empty ``dummy'' field
\item the iterators belong to the same field and both point past the last
  element. 
\item the iterators belong to the same field and both point to the same
  element. 
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\BASIC

Let \code{iter} be an instance of type \code{galois_field_iterator}.

\begin{fcode}{galois_field_iterator&}{iter.operator++}{}
  \code{++iter} makes \code{iter} point to the next element in
  the corresponding field and returns a reference to \code{iter}.

  The preincrement operator fails if \code{iter} belongs to the empty
  ``dummy'' field or if it points past the last element of its field.
\end{fcode}

\begin{fcode}{galois_field_iterator}{iter.operator++}{int}
  \code{iter++} makes \code{iter} point to the next element in
  the corresponding field and returns the original value of \code{iter}.

  The postincrement operator fails if \code{iter} belongs to the empty
  ``dummy'' field or if it points past the last element of its field.
\end{fcode}

\begin{fcode}{galois_field_iterator}{iter.operator-{}-}{}
  \code{-{}-iter} makes \code{iter} point to the previous element in
  the corresponding field and returns a reference to \code{iter}.

  The predecrement operator fails if \code{iter} belongs to the empty
  ``dummy'' field or if it points to the first element of its field, i.\,e.\
  if \code{*iter == gf_element(iter.get_field())}.
\end{fcode}

\begin{fcode}{galois_field_iterator}{iter.operator-{}-}{int}
  \code{iter-{}-} makes \code{iter} point to the previous element in
  the corresponding field and returns the original value of \code{iter}.

  The postdecrement operator fails if \code{iter} belongs to the empty
  ``dummy'' field or if it points to the first element of its field, i.\,e.\
  if \code{*iter == gf_element(iter.get_field())}.
\end{fcode}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SEEALSO

\SEE{galois_field}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\EXAMPLES

\begin{quote}
\begin{verbatim}
#include <iostream>

#include "LiDIA/galois_field.h"
#include "LiDIA/gf_element.h"
#include "LiDIA/galois_field_iterator.h"

using namespace std;
using namespace LiDIA;

int main() {
  galois_field gf(5, 2);

  cout << "All elements of galois_field(5, 2):\n ";
  galois_field_iterator end_iter = gf.end();
  for(galois_field_iterator iter = gf.begin(); iter != end_iter; ++iter) {
    cout << " " << *iter;
  }
  cout << endl;
}
\end{verbatim}
\end{quote}
produces the following output:
\begin{quote}
\begin{verbatim}
  All elements of galois_field(5, 2):
  (0) (1) (2) (3) (4) (x) (x+ 1) (x+ 2) (x+ 3) (x+ 4) (2 * x) 
  (2 * x+ 1) (2 * x+ 2) (2 * x+ 3) (2 * x+ 4) (3 * x) (3 * x+ 1)
  (3 * x+ 2) (3 * x+ 3) (3 * x+ 4) (4 * x) (4 * x+ 1) (4 * x+ 2)
  (4 * x+ 3) (4 * x+ 4)
\end{verbatim}
\end{quote}

A further example can be found in the file
\url{src/finite_fields/gfpn/galois_field_iterator_appl.cc}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AUTHOR

Christoph Ludwig

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
