/***************************************************************************

 *

 * alg_test.h - common definitions for algorithms tests

 *

 * $Id: alg_test.h 349021 2005-11-25 20:32:27Z sebor $

 *

 ***************************************************************************

 *

 * Copyright (c) 1994-2005 Quovadx,  Inc., acting through its  Rogue Wave

 * Software division. Licensed under the Apache License, Version 2.0 (the

 * "License");  you may  not use this file except  in compliance with the

 * License.    You    may   obtain   a   copy   of    the   License    at

 * http://www.apache.org/licenses/LICENSE-2.0.    Unless   required    by

 * applicable law  or agreed to  in writing,  software  distributed under

 * the License is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR

 * CONDITIONS OF  ANY KIND, either  express or implied.  See  the License

 * for the specific language governing permissions  and limitations under

 * the License.

 * 

 **************************************************************************/

#ifndef _RWSTD_ALG_TEST_H_INCLUDED

#define _RWSTD_ALG_TEST_H_INCLUDED

#include <iterator>

#include <cassert>   // for assert()

#include <testdefs.h>

#include "rw/_defs.h"

// defining macro for var

#define n_total_op_assign_ (*Getn_total_op_assign_())

#define n_total_op_eq_ (*Getn_total_op_eq_())

#define gen_   (* Get_gen_())     

// objects of class X maintain a count of their instances in existence,

// the number of defaut and copy ctor calls, assignment operators, and

// the number of calls to operator==() and operator<()

struct _TEST_EXPORT X

{

    const int id_;        // a unique non-zero id of the object

    int       origin_;    // id of the original object that this

                          // is a (perhaps indirect) copy of (id_

                          // when this is the original)

    int       src_id_;    // id of the object that this is a direct

                          // copy of (id_ when this the original)

    int       val_;       // object's value

    // number of times the object has been copied into another object,

    // regardless of whether the operation threw an exception or not

    _RWSTD_SIZE_T n_copy_ctor_;

    // number of times the object's assignment operator has been invoked,

    // regardless of whether the operation threw an exception or not

    _RWSTD_SIZE_T n_op_assign_;

    // number of times the object's operator== was invoked

    // regardless of whether the operation threw an exception

    _RWSTD_SIZE_T n_op_eq_;

    // number of times the object's operator< was invoked

    // regardless of whether the operation threw an exception

    _RWSTD_SIZE_T n_op_lt_;

    static _RWSTD_SIZE_T count_;   // number of objects in existence (>= 0)

    static int id_gen_;            // generates a unique non-zero id

    _TEST_EXPORT   static int (*_gen_)();          // extern "C++" int (*)()

 _TEST_EXPORT     static _RWSTD_SIZE_T n_total_def_ctor_;    // number of default ctor calls

  _TEST_EXPORT    static _RWSTD_SIZE_T n_total_copy_ctor_;   // ... copy ctors ...

  _TEST_EXPORT    static _RWSTD_SIZE_T n_total_dtor_;        // ... dtors ...

//new chnage decl of member var

 _TEST_EXPORT     static _RWSTD_SIZE_T _n_total_op_assign_;   // ... assignment operators ...

 _TEST_EXPORT     static _RWSTD_SIZE_T _n_total_op_eq_;       // ... equality operators ...

  _TEST_EXPORT    static _RWSTD_SIZE_T n_total_op_lt_;       // ... operators <= ...

    // classes thrown from the respective functions

    struct Exception { int id_; };

    struct DefCtor: Exception { };

    struct CopyCtor: Exception { };

    struct Dtor: Exception { };

    struct OpAssign: Exception { };

    struct OpEq: Exception { };

    struct OpLt: Exception { };

    // throw object's `id' wrapped in the appropriate struct when the

    // corresponding n_total_xxx_ counter reaches the value pointed to

    // by the respective pointer below

    static _RWSTD_SIZE_T* def_ctor_throw_ptr_;

    static _RWSTD_SIZE_T* copy_ctor_throw_ptr_;

    static _RWSTD_SIZE_T* dtor_throw_ptr_;

    static _RWSTD_SIZE_T* op_assign_throw_ptr_;

    static _RWSTD_SIZE_T* op_eq_throw_ptr_;

    static _RWSTD_SIZE_T* op_lt_throw_ptr_;

    // objects to which the pointers above initally point

    static _RWSTD_SIZE_T def_ctor_throw_count_;

    static _RWSTD_SIZE_T copy_ctor_throw_count_;

    static _RWSTD_SIZE_T dtor_throw_count_;

    static _RWSTD_SIZE_T op_assign_throw_count_;

    static _RWSTD_SIZE_T op_eq_throw_count_;

    static _RWSTD_SIZE_T op_lt_throw_count_;

 _TEST_EXPORT   X ();

 _TEST_EXPORT   X (const X&);

 _TEST_EXPORT   ~X ();

_TEST_EXPORT    X& operator= (const X&);

 _TEST_EXPORT   bool operator== (const X&) const;

 _TEST_EXPORT   bool operator< (const X&) const;

    // the following operators are not declared or defined in order

    // to detect any unwarranted assumptions made in algorithms

    //    bool operator!= (const X &rhs) const;

    //    bool operator> (const X &rhs) const;

    //    bool operator>= (const X &rhs) const;

    //    bool operator<= (const X &rhs) const;

    //    X operator- () const;

    //    X operator+ () const;

 _TEST_EXPORT  bool

    is_count (_RWSTD_SIZE_T copy_ctor,

              _RWSTD_SIZE_T op_assign,

              _RWSTD_SIZE_T op_eq,

              _RWSTD_SIZE_T op_lt) const;

_TEST_EXPORT    static bool

    is_total (_RWSTD_SIZE_T count,

              _RWSTD_SIZE_T n_def_ctor,

              _RWSTD_SIZE_T n_copy_ctor,

              _RWSTD_SIZE_T n_op_assign,

              _RWSTD_SIZE_T n_op_eq,

              _RWSTD_SIZE_T n_op_lt);

_TEST_EXPORT    static void reset_totals ();										

    // construct an array of objects of type X each initialized

    // from the corresponding element of the character array

    static X* from_char (const char*, _RWSTD_SIZE_T = ~0UL);

    // returns -1 when less, 0 when same, or +1 when the array

    // of X objects is greater than the character string

    static int compare (const X*, const char*, _RWSTD_SIZE_T = ~0UL);

    static int compare (const char*, const X*, _RWSTD_SIZE_T = ~0UL);

    // returns -1 when less, 0 when same, or +1 when the first

    // array of X objects is greater than the second array

    static int compare (const X*, const X*, _RWSTD_SIZE_T);

};

struct _TEST_EXPORT UnaryPredicate

{

    // total number of times operator() was invoked

    static _RWSTD_SIZE_T n_total_op_fcall_;

    UnaryPredicate ();

    UnaryPredicate (const UnaryPredicate&);

    UnaryPredicate& operator= (const UnaryPredicate&);

    virtual ~UnaryPredicate ();

    virtual bool operator()(const X&) const;

};

struct _TEST_EXPORT BinaryPredicate

{

    // total number of times operator() was invoked

    static _RWSTD_SIZE_T n_total_op_fcall_;

    bool ignore_case_;

    BinaryPredicate (bool = false);

    BinaryPredicate (const BinaryPredicate&);

    BinaryPredicate& operator= (const BinaryPredicate&);

    virtual ~BinaryPredicate ();

    virtual bool operator()(const X&, const X&) const;

};

class _TEST_EXPORT tempstr;

// converts a sequence of objects of type X to a tempstr object

// in the format "[%p0, %p1): { x0, >x1<, ..., xN - 1 } where N

// is defined as: N = (X*)p1 - (X*)p0

// the last argument, if non-negative, indicates the index of the

// element enclosed in between the '>' and '<' characters

_TEST_EXPORT void to_string (tempstr*, const X*, const X*, int = -1);

// generate a unique sequential number starting from 0

_TEST_EXPORT int gen_seq ();

// generate numbers in the sequence 0, 0, 1, 1, 2, 2, 3, 3, etc... 

_TEST_EXPORT int gen_seq_2lists ();

// generate a sequence of subsequences (i.e., 0, 1, 2, 3, 4, 0, 1, 2, etc...)

_TEST_EXPORT int gen_subseq ();

// wrapper around a (possibly) extern "C" int rand()

// extern "C++" 

_TEST_EXPORT  int gen_rnd ();

// computes an integral log2

inline unsigned ilog2 (unsigned long n)

{

    unsigned result = 0;

    while (n >>= 1)

        ++result;

    return result;

}

// computes an integral log10

inline unsigned ilog10 (unsigned long n)

{

    unsigned result = 0;

    while (n /= 10)

        ++result;

    return result;

}

// returns true iff a sequence of (not necessarily unique) values

// is sorted in an ascending order

template <class InputIterator>

inline bool is_sorted_lt (InputIterator first, InputIterator last)

{

    if (first == last)

        return true;

    for (InputIterator prev (first); ++first != last; prev = first) {

        if (*first < *prev)

            return false;

    }

    return true;

}

// returns true iff a sequence of (not necessarily unique) values

// is sorted in a descending order

template <class InputIterator>

inline bool is_sorted_gt (InputIterator first, InputIterator last)

{

    if (first == last)

        return true;

    for (InputIterator prev (first); ++first != last; prev = first) {

        if (*prev < *first)

            return false;

    }

    return true;

}

// type used to exercise that algorithms do not apply operators

// to function objects the latter are not required to define

struct conv_to_bool {

    static conv_to_bool make (bool val) {

        conv_to_bool tmp;

        tmp.val_ = val;

        return tmp;

    }

    operator bool () const {

        return val_;

    }

public:

    bool operator!() const

    	{

    	return val_ != 0;

    	}                  // not defined

    bool val_;

};

// not defined

void operator&& (const conv_to_bool&, bool);

void operator&& (bool, const conv_to_bool&);

void operator|| (const conv_to_bool&, bool);

void operator|| (bool, const conv_to_bool&);

// element-type prototypes to exercise container requirements

// meets requirements listed at 25, p7

template <class T>

struct predicate {

    conv_to_bool operator() (const T &a) const {

        _RWSTD_UNUSED (a);

        return conv_to_bool::make (true);

    }

};

// meets requirements listed at 25, p8

template <class T>

struct binary_predicate {

    conv_to_bool operator() (const T &a, const T &b) const {

        _RWSTD_UNUSED (a);

        _RWSTD_UNUSED (b);

        return conv_to_bool::make (true);

    }

};

// meets requirements listed at 25.2.3, p2

template <class T>

struct func {

    typedef T              argument_type;

    typedef argument_type& reference;

    reference operator() (const argument_type&) const {

        return _RWSTD_REINTERPRET_CAST (reference,

                   _RWSTD_CONST_CAST (func*, this)->dummy);

    }

private:

    char dummy;

};

// meets requirements listed at 25.2.3, p2

template <class T>

struct binary_func {

    typedef T              argument_type;

    typedef argument_type& reference;

    reference operator() (const argument_type&, 

                          const argument_type&) const {

        return _RWSTD_REINTERPRET_CAST (reference,

                   _RWSTD_CONST_CAST (binary_func*, this)->dummy);

    }

private:

    char dummy;

};

// a base-class to extend the requirements classes from

enum { no_ctor = 0, def_ctor = 1, cpy_ctor = 2 };

template <int c = no_ctor>

struct base;

template<>

struct base<no_ctor>

{

private:

    // struct s added to prevent gcc warning: base<no_ctor> has a private

    // constructor and no friends

    struct s { };

    friend struct s;

    base ();

    base (const base&);

    void operator= (base&);

};

template<>

struct base<def_ctor>

{

    base () : unused (0) { }

private:

    void operator= (base&);

    base (const base&);

    // unused member prevents bogus HP aCC warnings (see Onyx #23561)

    int unused;

};

template<>

struct base<cpy_ctor>

{

    // explicitly specifying redundant template parameters to work

    // around a SunPro 5.2 bug (see Onyx #24260)

    base (const base<cpy_ctor> &rhs): unused (rhs.unused) { }

private:

    base ();

    void operator= (base&);

    // unused member prevents bogus HP aCC warnings (see Onyx #23561)

    int unused;

};

template<>

struct base<(def_ctor | cpy_ctor)>

{

    base (): unused (0) { }

    // explicitly specifying redundant template parameters to work

    // around a SunPro 5.2 bug (see Onyx #24260)

    base (const base<(def_ctor | cpy_ctor)> &rhs): unused (rhs.unused) { }

private:

    void operator= (base&);

    // unused member prevents bogus HP aCC warnings (see Onyx #23561)

    int unused;

};

template <class T>

struct eq_comp: T { };

template <class T>

inline bool operator== (const eq_comp<T>&, const eq_comp<T>&)

{

    return true;

}

template <class T>

struct lt_comp: T { };

template <class T>

inline bool operator< (const lt_comp<T>&, const lt_comp<T>&)

{

    return true;

}

// assignment

template <class T>

struct assign : T

{

    assign& operator= (const assign& rhs) {

        unused = rhs.unused;

        return *this;

    }

private:

    // unused member prevents bogus HP aCC warnings (see Onyx #23561)

    int unused;

};

// conversion structs

// struct split into 2 to eliminate the following g++ 2.95.2 warning:

// warning: choosing `convert<T>::operator U&()' over 

//                   `convert<T>::operator const U&() const'

template <class T, class U>

struct cvt : T 

{

    operator U& () {

        return _RWSTD_REINTERPRET_CAST (U&, *this);

    }

};

template <class T, class U>

struct const_cvt : T

{

    operator const U& () const {

        return _RWSTD_REINTERPRET_CAST (const U&, *this);

    }

};

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

struct DummyBase { };

#  define ITER_BASE(ign1, ign2, ign3, ign4, ign5) DummyBase

#else   // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

   // when partial specialization isn't supported 

#  define ITER_BASE(Cat, T, Dist, Ptr, Ref) \

          std::iterator<Cat, T, Dist, Ptr, Ref >

#endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC

// satisfies the requirements in 24.1.1 [lib.input.iterators]

template <class T>

struct InputIter: ITER_BASE (std::input_iterator_tag, T, int, T*, T&)

{

    typedef T                       value_type;

    typedef value_type*             pointer;

    typedef value_type&             reference;

    typedef int                     difference_type;

    typedef std::input_iterator_tag iterator_category;

    // body shared by all copies of the same InputIter specialization

    // to detect algorithms that pass through the same interator more

    // than once (disallowed by 24.1.1, p3)

    struct Shared {

        const value_type *cur_;

        const value_type *beg_;

        const value_type *end_;

        int               ref_;

        Shared (const value_type *cur,

                const value_type *beg,

                const value_type *end)

            : cur_ (cur), beg_ (beg), end_ (end), ref_ (1) { }

        ~Shared () {

            cur_ = beg_ = end_ = 0;

            ref_ = -1;

        }

    private:

        Shared (const Shared&);           // not defined

        void operator= (const Shared&);   // not defined

    };

    // InputIterators are not default constructible

    InputIter (const value_type *cur,

               const value_type *beg,

               const value_type *end)

        : ptr_ (new Shared (cur, beg, end)), cur_ (cur) { }

    InputIter (const InputIter &rhs)

        : ptr_ (rhs.ptr_), cur_ (rhs.cur_) {

        assert (0 != ptr_);

        ++ptr_->ref_;

    }

    ~InputIter () {

        assert (0 != ptr_);

        if (0 == --ptr_->ref_)   // decrement the reference count

            delete ptr_;

        ptr_ = 0;

        cur_ = 0;

    }

    InputIter& operator= (const InputIter &rhs) {

        assert (rhs == rhs);   // assert `rhs' is valid

        assert (0 != ptr_);

        if (0 == --ptr_->ref_)

            delete ptr_;

        ptr_ = rhs.ptr_;

        assert (0 != ptr_);

        ++ptr_->ref_;

        cur_ = rhs.cur_;

        return *this;

    }

    bool operator== (const InputIter &rhs) const {

        // assert that both arguments are in the domain of operator==()

        // i.e., that no copy of *this or `rhs' has been incremented

        // and that no copy passed through this value of the iterator

        assert (0 != ptr_);

        assert (cur_ == ptr_->cur_);

        assert (0 != rhs.ptr_);

        assert (rhs.cur_ == rhs.ptr_->cur_);

        return cur_ == rhs.cur_;

    }

    bool operator!= (const InputIter &rhs) const {

        return !(*this == rhs);

    }

    // returning const-reference rather than a value in order

    // not to impose the CopyConstructible requirement on T

    // and to disallow constructs like *InputIter<T>() = T()

    const value_type& operator* () const {

        assert (*this == *this);      // assert *this is valid

        assert (cur_ < ptr_->end_);   // assert *this is dereferenceable

        return *cur_;

    }

    _RWSTD_OPERATOR_ARROW(const value_type* operator-> () const);

    InputIter& operator++ () {

        assert (*this == *this);      // assert *this is valid

        assert (cur_ < ptr_->end_);   // assert *this is not past the end

        ptr_->cur_ = ++cur_;

        return *this;

    }

    InputIter operator++ (int) {

        return ++*this;

    }

// private:

    Shared           *ptr_;

    const value_type *cur_;   // past-the-end

};

// satisfies the requirements in 24.1.2 [lib.output.iterators]

template <class T>

struct OutputIter: ITER_BASE (std::output_iterator_tag, T, int, T*, T&)

{

    typedef T                        value_type;

    typedef value_type*              pointer;

    typedef value_type&              reference;

    typedef int                      difference_type;

    typedef std::output_iterator_tag iterator_category;

    // body shared by all copies of the same OutputIter specialization

    // to detect algorithms that pass through the same interator more

    // than once (disallowed by 24.1.2, p2)

    struct Shared {

        pointer           cur_;

        pointer           assign_;

        const value_type *begin_;

        const value_type *end_;

        int               ref_;

        Shared (pointer cur, const value_type *end)

            : cur_ (cur), assign_ (cur), begin_ (cur), end_ (end), ref_ (1) { }

        ~Shared () {

            begin_ = end_ = cur_ = assign_ = 0;

            ref_ = -1;

        }

    private:

        Shared (const Shared&);           // not defined

        void operator= (const Shared&);   // not defined

    };

    // class whose objects are returned from OutputIter::operator*

    // to detect multiple assignments (disallowed by 24.1.2, p2)

    class Proxy {

        friend struct OutputIter;

        Shared* const ptr_;

        Proxy (Shared *ptr): ptr_ (ptr) { }

    public:

        void operator= (const value_type &rhs) {

            assert (0 != ptr_);

            // verify that the iterator is in the valid range

            assert (ptr_->cur_ >= ptr_->begin_ && ptr_->cur_ <= ptr_->end_);

            // verify that the assignment point is the same as the current

            // position `cur' within the sequence or immediately before it

            // (in order to allow the expression: *it++ = val)

            assert (   ptr_->assign_ == ptr_->cur_

                    || ptr_->assign_ + 1 == ptr_->cur_);

            // assign and increment the assignment point

            *ptr_->assign_++ = rhs;

        }

    };

    // OutputIterators are not default constructible

    OutputIter (pointer           cur,

                const value_type *,

                const value_type *end)

        : ptr_ (new Shared (cur, end)), cur_ (cur) { }

    OutputIter (const OutputIter &rhs)

        : ptr_ (rhs.ptr_), cur_ (rhs.cur_) {

        ++ptr_->ref_;   // increment the reference count

    }

    ~OutputIter () {

        if (0 == --ptr_->ref_)   // decrement the reference count

            delete ptr_;

        ptr_ = 0;

        cur_ = 0;

    }

    OutputIter& operator= (const OutputIter &rhs) {

        if (0 == --ptr_->ref_)

            delete ptr_;

        ptr_ = rhs.ptr_;

        ++ptr_->ref_;

        cur_ = rhs.cur_;

        return *this;

    }

    void operator= (const value_type &rhs) const {

        **this = rhs;

    }

    // return a proxy in order to detect multiple assignments

    // through the iterator (disallowed by 24.1.2, p2))

    Proxy operator* () const {

        assert (0 != ptr_);

        assert (ptr_->assign_ && ptr_->assign_ != ptr_->end_);

        return Proxy (ptr_);

    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);

    OutputIter& operator++ () {

        assert (cur_ == ptr_->cur_);

        assert (ptr_->cur_ >= ptr_->begin_ && ptr_->cur_ < ptr_->end_);

        cur_ = ++ptr_->cur_;

        return *this;

    }

    // returning a const value rather than a modifiable value

    // in order to verify the requirement in row 5 of Table 73

    const OutputIter operator++ (int) {

        OutputIter tmp (*this);

        return ++*this, tmp;

    }

// private:

    Shared  *ptr_;

    pointer  cur_;

};

// satisfies the requirements in 24.1.3 [lib.forward.iterators]

template <class T>

struct FwdIter: ITER_BASE (std::forward_iterator_tag, T, int, T*, T&)

{

    typedef T                         value_type;

    typedef value_type*               pointer;

    typedef value_type&               reference;

    typedef int                       difference_type;

    typedef std::forward_iterator_tag iterator_category;

    FwdIter (): cur_ (0), end_ (0) { }

    FwdIter (pointer           cur,

             const value_type *,

             const value_type *end)

        : cur_ (cur), end_ (end) { }

    FwdIter (const FwdIter &rhs)

        : cur_ (rhs.cur_), end_ (rhs.end_) { }

    ~FwdIter () {

        end_ = cur_ = 0;

    }

    FwdIter& operator= (const FwdIter &rhs) {

        cur_ = rhs.cur_;

        end_ = rhs.end_;

        return *this;

    }

    bool operator== (const FwdIter &rhs) const {

        assert (cur_ != 0);

        return cur_ == rhs.cur_;

    }

    bool operator!= (const FwdIter &rhs) const {

        return !(*this == rhs);

    }

    reference operator* () const {

        assert (cur_ != 0 && cur_ != end_);

        return *cur_;

    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);

    FwdIter& operator++ () {

        assert (cur_ != 0 && cur_ != end_);

        return ++cur_, *this;

    }

    FwdIter operator++ (int) {

        FwdIter tmp (*this);

        return ++*this, tmp;

    }

// private:

    pointer           cur_;   // pointer to current element

    const value_type *end_;   // past-the-end

};

template <class T>

struct ConstFwdIter: FwdIter<T>

{

    typedef T                   value_type;

    typedef FwdIter<value_type> Base;

    ConstFwdIter (): Base () { }

    ConstFwdIter (const value_type *cur,

                  const value_type *begin,

                  const value_type *end)

        : Base (_RWSTD_CONST_CAST (value_type*, cur), begin, end) { }

    const value_type& operator* () const {

        return Base::operator* ();

    }

    _RWSTD_OPERATOR_ARROW (const value_type* operator-> () const);

};

// satisfies the requirements in 24.1.4 [lib.bidirectional.iterators]

template <class T>

struct BidirIter: ITER_BASE (std::bidirectional_iterator_tag, T, int, T*, T&)

{

    typedef T                               value_type;

    typedef value_type*                     pointer;

    typedef value_type&                     reference;

    typedef int                             difference_type;

    typedef std::bidirectional_iterator_tag iterator_category;

    BidirIter (): cur_ (0), begin_ (0), end_ (0) { }

    BidirIter (pointer           cur,

               const value_type *begin,

               const value_type *end)

        : cur_ (cur), begin_ (begin), end_ (end) { }

    BidirIter (const BidirIter &rhs)

        : cur_ (rhs.cur_), begin_ (rhs.begin_), end_ (rhs.end_) { }

    ~BidirIter () {

        begin_ = end_ = cur_ = 0;

    }

    BidirIter& operator= (const BidirIter &rhs) { 

        cur_ = rhs.cur_;

        end_ = rhs.end_;

        return *this; 

    }

    bool operator== (const BidirIter &rhs) const {

        assert (cur_ != 0 && rhs.cur_ != 0);

        return cur_ == rhs.cur_;

    }

    bool operator!= (const BidirIter &rhs) const {

        return !(*this == rhs);

    }

    reference operator* () const {

        assert (cur_ != 0 && cur_ != end_);

        return *cur_;

    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);

    BidirIter& operator++ () {

        assert (cur_ != 0 && cur_ != end_);

        return ++cur_, *this;

    }

    BidirIter operator++ (int) {

        BidirIter tmp (*this);

        return ++*this, tmp;

    }

    BidirIter& operator-- () {

        assert (cur_ != 0 && cur_ != begin_);

        return --cur_, *this;

    }

    BidirIter operator-- (int) {

        BidirIter tmp (*this);

        return --*this, tmp;

    }

// private:

    pointer           cur_;     // pointer to current element

    const value_type *begin_;   // first in range

    const value_type *end_;     // past-the-end

};

template <class T>

struct ConstBidirIter: BidirIter<T>

{

    typedef T                     value_type;

    typedef BidirIter<value_type> Base;

    ConstBidirIter (): Base () { }

    ConstBidirIter (const value_type *cur,

                    const value_type *begin,

                    const value_type *end)

        : Base (_RWSTD_CONST_CAST (value_type*, cur), begin, end) { }

    const value_type& operator* () const {

        return Base::operator* ();

    }

    _RWSTD_OPERATOR_ARROW (const value_type* operator-> () const);

};

// satisfies the requirements in 24.1.5 [lib.random.access.iterators]

template <class T>

struct RandomAccessIter

    : ITER_BASE (std::random_access_iterator_tag, T, int, T*, T&)

{

    typedef T                               value_type;

    typedef value_type*                     pointer;

    typedef value_type&                     reference;

    typedef int                             difference_type;

    typedef std::random_access_iterator_tag iterator_category;

    RandomAccessIter (): cur_ (0), begin_ (0), end_ (0) { }

    RandomAccessIter (pointer           cur,

                      const value_type *begin,

                      const value_type *end)

        : cur_ (cur), begin_ (begin), end_ (end) { }

    RandomAccessIter (const RandomAccessIter &rhs)

        : cur_ (rhs.cur_), begin_ (rhs.begin_), end_ (rhs.end_) { }

    ~RandomAccessIter () {

        begin_ = end_ = cur_ = 0;

    }

    RandomAccessIter& operator= (const RandomAccessIter &rhs) {

        cur_   = rhs.cur_;

        begin_ = rhs.begin_;

        end_   = rhs.end_;

        return *this; 

    }

    reference operator* () const {

        assert (cur_ != 0 && cur_ != end_);

        return *cur_;

    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);

    RandomAccessIter& operator++ () {

        assert (cur_ != 0 && cur_ != end_);

        return ++cur_, *this;

    }

    RandomAccessIter operator++ (int) {

        RandomAccessIter tmp (*this);

        return ++*this, tmp;

    }

    RandomAccessIter& operator-- () {

        assert (cur_ != 0 && cur_ != begin_);

        return --cur_, *this;

    }

    RandomAccessIter operator-- (int) {

        RandomAccessIter tmp (*this);

        return --*this, tmp;

    }

    RandomAccessIter& operator+= (difference_type n) {

        assert (   cur_ != 0

                && (!end_ || cur_ + n <= end_)

                && (!begin_ || cur_ + n >= begin_));

        return cur_ += n, *this;

    }

    RandomAccessIter& operator-= (difference_type n) {

        return *this += -n;

    }