//============================================================================
// Contents:
//
//  This header contains class definitions for pseudo-random bit sequence
//  and pseudo-random number classes. The code is a fully functional and
//  tested exploratory prototype illustrating the adoption and application
//  of the STL model to generated sequences.
//
// Author:
//
//  Kevlin Henney (kevlin@acm.org), May 1995
//
// Use:
//
//  This header file is standalone, ie. there is no associated translation
//  unit with this header. Straight header file inclusion is all that is
//  required to bring these classes into your program and build environment.
//
//  Templates are not used in the current implementation and care has been
//  taken to ensure that the code will compile and run with C++ compilers
//  conforming to at least the Cfront version 2.1 definition of the language.
//
//  Copyright for the code remains with the original author, Kevlin Henney.
//  This code may be used and distributed freely, subject to the following
//  constraints: any modification must acknowledge original authorship and
//  copyright; except for distribution, no charge may be made for this code.
//
// Guidelines:
//
//  Member function categories (sub-interfaces) are all introduced with an
//  access specifier followed by a comment containing the category name.
//  Friendship is specified within categories as a strong suggestion that the
//  only visibility being granted is to the members contained in that category
//  (an idea inspired by an actual language level feature in Eiffel). There
//  are some additional comments that indicate intended usage or behaviour
//  and hence future direction for language features that are not widespread,
//  eg. use of bool and explicit.
//
//  The iterator model and the container model, of which a subset is used
//  to define iteratables, is defined by the STL and is now incorporated into
//  the draft C++ standard. An implementation and definition of the STL
//  is available from ftp://butler.hpl.hp.com/stl.
//
// Notes:
//
//  The member implementations given here are all lightweight and are
//  fully inlined. Note that random_number::iterator::operator++() contains
//  a loop which some implementations may not inline (possibly issuing a
//  warning). However, it did not seem worthwhile adding an out-of-line
//  function -- and hence a translation unit -- just for this.
//
//  Templates are not used in this implementation. It is expected that the
//  final one will, specialising on bool for the bit sequence. However, this
//  trial implementation has the advantage that it compiles and runs on more
//  existing compilers.
//============================================================================

#ifndef RANDOM_H
#define RANDOM_H

extern "C"
{
#include <limits.h>
#include <stddef.h>
}

//----------------------------------------------------------------------------
// Description:
//
//  The random_bits class provides iterators over a random bit/bool sequence
//  from a given seed. The class qualifies as an unbound traversable patterned
//  on the STL model, with the iterators satisfying the requirements for
//  input iterators.
//
// Usage:
//
//  A random bit sequence is characterised by its seed, which is provided
//  at construction. The characteristic sequence this 'indexes' is
//  accessed through an iterator, of which many may exist concurrently for
//  a given random sequence object, obtained using random_bits::begin(). The
//  operations on the iterator are pointer-like and fairly self evident.
//
//  A default created sequence or one with a seed of 0 has zero length, ie.
//  begin() == end(), otherwise the sequence is periodic (large period) and
//  unbounded, ie. begin() != end() always holds true.
//
// Implementation:
//
//  The implementation is based on the linear feedback shift register
//  described by Bruce Schneier in "Pseudo-random_numbers sequence generator
//  for 32-bit CPUs", DDJ February 1992.
//
//  Linear feedback shift registers are stationary when their registers
//  are set to zero. This is used as a convenient indicator of the
//  sequence's notional end.
//
//  The template version of a random sequence class specialises this
//  implementation on the bool type.
//----------------------------------------------------------------------------

class random_bits
{

public: // parameterising types

    typedef int /* bool */ value_type;
    typedef unsigned long  seed_type;

public: // reference types (for compatibility, otherwise unused)

    typedef value_type       &reference;
    typedef const value_type &const_reference;
    typedef value_type       *pointer;
    typedef const value_type *const_pointer;

public: // iterator types

    class iterator
    {
    public: // construction and destruction

        iterator()
          : shift_register(0) {}

        iterator(const iterator &that)
          : shift_register(that.shift_register) {}

        ~iterator() {}

    public: // assignment

        iterator &operator=(const iterator &rhs)
        {
            shift_register = rhs.shift_register;
            return *this;
        }

        iterator &operator++()
        {
            shift_register =
                ((shift_register >> 31 ^
                  shift_register >>  6 ^
                  shift_register >>  4 ^
                  shift_register >>  2 ^
                  shift_register >>  1 ^
                  shift_register) & 1) << 31 |
                shift_register >> 1;
            return *this;
        }

        iterator operator++(int)
        {
            iterator original = *this;
            ++*this;
            return original;
        }

    public: // query

        value_type operator*() const
        {
            return shift_register & 1;
        }

        int /* bool */ operator==(const iterator &rhs) const
        {
            return shift_register == rhs.shift_register;
        }

        int /* bool */ operator!=(const iterator &rhs) const
        {
            return shift_register != rhs.shift_register;
        }

    private: // construction

        friend class random_bits;

        iterator(seed_type acorn)
          : shift_register(acorn) { ++*this; } // warm up

    private: // state

        seed_type  shift_register;

    };

    typedef iterator const_iterator;

public: // construction and destruction

    random_bits() {}

    random_bits(const random_bits &that)
      : start(that.start) {}

    /* explicit */ random_bits(seed_type acorn)
      : start(acorn) {}

    ~random_bits() {}

public: // iteration

    iterator begin() const { return start; }

    iterator end() const { return iterator(); }

public: // assignment

    random_bits &operator=(const random_bits &rhs)
    {
        start = rhs.start;
        return *this;
    }

    random_bits &swap(random_bits &rhs)
    {
        if(*this != rhs)
        {
            iterator tmp = rhs.start;
            rhs.start    = start;
            start        = tmp;
        }
        return *this;
    }

public: // query

    int /* bool */ empty() const { return begin() == end(); }

    int /* bool */ operator==(const random_bits &rhs) const
    {
        return start == rhs.start;
    }

    int /* bool */ operator!=(const random_bits &rhs) const
    {
        return start != rhs.start;
    }

private: // state

    iterator start;

};

//----------------------------------------------------------------------------
// Description:
//
//  The random_number class provides iterators over a random sequence of
//  unsigned longs. The sequence length may be unbound or bound. The class
//  follows the STL model as much as is possible, with the iterators
//  satisfying the requirements for input iterators.
//
// Usage:
//
//  In addition to the usage notes provided above for random_bits, the
//  random_numbers class has a size query and a sized constructor. This
//  may be used to create a simple repeatable fixed length sequence of
//  numbers without requiring external counting on the part of an algorithm.
//
// Implementation:
//
//  The sequence of bits that represent the current random number are obtained
//  from an instance of random_bits, which is used for implementation.
//
//  A default template implementation will be similar, but should not require
//  the value_type to be a primitive, merely something that understands
//  bit operations. For this it is suggested that a significant_bits template
//  is used to hold a constant that indicates the number of significant bits
//  that should be collected. The default implementation for such would be
//  sizeof(value_type) * CHAR_BIT, but user defined numeric classes can
//  specialise significant_bits to return the appropriate value.
//----------------------------------------------------------------------------

class random_numbers
{

public: // parameterising types

    typedef unsigned long          value_type;
    typedef unsigned long          size_type;
    typedef random_bits::seed_type seed_type;

public: // reference types

    typedef value_type       &reference;
    typedef const value_type &const_reference;
    typedef value_type       *pointer;
    typedef const value_type *const_pointer;

public: // constants

    enum { infinite = -1 }; // treat as static const size_type

public: // iterator types

    class iterator
    {
    public: // construction and destruction

        iterator()
          : bit_iterator(), current(0), position(0) {}

        iterator(const iterator &that)
          : bit_iterator(that.bit_iterator),
            current(that.current),
            position(that.position) {}

        ~iterator() {}

    public: // assignment

        iterator &operator=(const iterator &rhs)
        {
            if(this != &rhs)
            {
                bit_iterator = rhs.bit_iterator;
                current      = rhs.current;
                position     = rhs.position;
            }
            return *this;
        }

        iterator &operator++()
        {
            current = 0;
            for(size_t bit = 0; bit < sizeof(value_type) * CHAR_BIT; ++bit)
                current = current << 1 | *bit_iterator++;
            ++position;
            return *this;
        }

        iterator operator++(int)
        {
            iterator original = *this;
            ++*this;
            return original;
        }

    public: // query

        const value_type &operator*() const
        {
            return current;
        }

        int /* bool */ operator==(const iterator &rhs) const
        {
            return  position == rhs.position &&
                    (bit_iterator == rhs.bit_iterator ||
                     bit_iterator == random_bits::iterator() ||
                     rhs.bit_iterator == random_bits::iterator());
        }

        int /* bool */ operator!=(const iterator &rhs) const
        {
            return !(*this == rhs);
        }

    private: // construction

        friend class random_numbers;

        iterator(const random_bits &source)
          : bit_iterator(source.begin()),
            current(0),
            position(-1)
        {
            ++*this; // warm up
        }

        iterator(size_type end_offset)
          : bit_iterator(),
            current(0),
            position(end_offset) {}

    private: // state

        random_bits::iterator bit_iterator;
        value_type            current;
        size_type             position;

    };

    typedef iterator const_iterator;

public: // construction and destruction

    random_numbers()
      : source(), length(0) {}

    random_numbers(const random_numbers &that)
      : source(that.source), length(that.length) {}

    random_numbers(seed_type acorn, size_type size = infinite)
      : source(acorn), length(acorn != 0 ? size : 0) {}

    ~random_numbers() {}

public: // iteration

    iterator begin() const { return iterator(source); }

    iterator end() const { return iterator(length); }

public: // assignment

    random_numbers &operator=(const random_numbers &rhs)
    {
        // not worth checking for self
        source = rhs.source;
        length = rhs.length;
        return *this;
    }

    random_numbers &swap(random_numbers &rhs)
    {
        if(*this != rhs)
        {
            random_numbers tmp = rhs;
            rhs                = *this;
            *this              = tmp;
        }
        return *this;
    }

public: // query

    int /* bool */ empty() const { return length == 0; }
    
    size_type size() const { return length; }

    size_type max_size() const { return infinite; }

    int /* bool */ operator==(const random_numbers &rhs) const
    {
        return source == rhs.source && length == rhs.length;
    }

    int /* bool */ operator!=(const random_numbers &rhs) const
    {
        return source != rhs.source || length != rhs.length;
    }

private: // state

    random_bits source;
    size_type   length;

};

//============================================================================

#endif /* RANDOM_H */