sl@0: /***************************************************************************
sl@0: *
sl@0: * alg_test.h - common definitions for algorithms tests
sl@0: *
sl@0: * $Id: alg_test.h 349021 2005-11-25 20:32:27Z sebor $
sl@0: *
sl@0: ***************************************************************************
sl@0: *
sl@0: * Copyright (c) 1994-2005 Quovadx, Inc., acting through its Rogue Wave
sl@0: * Software division. Licensed under the Apache License, Version 2.0 (the
sl@0: * "License"); you may not use this file except in compliance with the
sl@0: * License. You may obtain a copy of the License at
sl@0: * http://www.apache.org/licenses/LICENSE-2.0. Unless required by
sl@0: * applicable law or agreed to in writing, software distributed under
sl@0: * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
sl@0: * CONDITIONS OF ANY KIND, either express or implied. See the License
sl@0: * for the specific language governing permissions and limitations under
sl@0: * the License.
sl@0: *
sl@0: **************************************************************************/
sl@0:
sl@0: #ifndef _RWSTD_ALG_TEST_H_INCLUDED
sl@0: #define _RWSTD_ALG_TEST_H_INCLUDED
sl@0:
sl@0: #include <iterator>
sl@0:
sl@0: #include <cassert> // for assert()
sl@0:
sl@0: #include <testdefs.h>
sl@0: #include "rw/_defs.h"
sl@0:
sl@0:
sl@0: // defining macro for var
sl@0: #define n_total_op_assign_ (*Getn_total_op_assign_())
sl@0: #define n_total_op_eq_ (*Getn_total_op_eq_())
sl@0: #define gen_ (* Get_gen_())
sl@0: // objects of class X maintain a count of their instances in existence,
sl@0: // the number of defaut and copy ctor calls, assignment operators, and
sl@0: // the number of calls to operator==() and operator<()
sl@0: struct _TEST_EXPORT X
sl@0: {
sl@0: const int id_; // a unique non-zero id of the object
sl@0: int origin_; // id of the original object that this
sl@0: // is a (perhaps indirect) copy of (id_
sl@0: // when this is the original)
sl@0: int src_id_; // id of the object that this is a direct
sl@0: // copy of (id_ when this the original)
sl@0: int val_; // object's value
sl@0:
sl@0: // number of times the object has been copied into another object,
sl@0: // regardless of whether the operation threw an exception or not
sl@0: _RWSTD_SIZE_T n_copy_ctor_;
sl@0:
sl@0: // number of times the object's assignment operator has been invoked,
sl@0: // regardless of whether the operation threw an exception or not
sl@0: _RWSTD_SIZE_T n_op_assign_;
sl@0:
sl@0: // number of times the object's operator== was invoked
sl@0: // regardless of whether the operation threw an exception
sl@0: _RWSTD_SIZE_T n_op_eq_;
sl@0:
sl@0: // number of times the object's operator< was invoked
sl@0: // regardless of whether the operation threw an exception
sl@0: _RWSTD_SIZE_T n_op_lt_;
sl@0:
sl@0: static _RWSTD_SIZE_T count_; // number of objects in existence (>= 0)
sl@0: static int id_gen_; // generates a unique non-zero id
sl@0: _TEST_EXPORT static int (*_gen_)(); // extern "C++" int (*)()
sl@0:
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T n_total_def_ctor_; // number of default ctor calls
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T n_total_copy_ctor_; // ... copy ctors ...
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T n_total_dtor_; // ... dtors ...
sl@0: //new chnage decl of member var
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T _n_total_op_assign_; // ... assignment operators ...
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T _n_total_op_eq_; // ... equality operators ...
sl@0: _TEST_EXPORT static _RWSTD_SIZE_T n_total_op_lt_; // ... operators <= ...
sl@0:
sl@0: // classes thrown from the respective functions
sl@0: struct Exception { int id_; };
sl@0: struct DefCtor: Exception { };
sl@0: struct CopyCtor: Exception { };
sl@0: struct Dtor: Exception { };
sl@0: struct OpAssign: Exception { };
sl@0: struct OpEq: Exception { };
sl@0: struct OpLt: Exception { };
sl@0:
sl@0: // throw object's `id' wrapped in the appropriate struct when the
sl@0: // corresponding n_total_xxx_ counter reaches the value pointed to
sl@0: // by the respective pointer below
sl@0: static _RWSTD_SIZE_T* def_ctor_throw_ptr_;
sl@0: static _RWSTD_SIZE_T* copy_ctor_throw_ptr_;
sl@0: static _RWSTD_SIZE_T* dtor_throw_ptr_;
sl@0: static _RWSTD_SIZE_T* op_assign_throw_ptr_;
sl@0: static _RWSTD_SIZE_T* op_eq_throw_ptr_;
sl@0: static _RWSTD_SIZE_T* op_lt_throw_ptr_;
sl@0:
sl@0: // objects to which the pointers above initally point
sl@0: static _RWSTD_SIZE_T def_ctor_throw_count_;
sl@0: static _RWSTD_SIZE_T copy_ctor_throw_count_;
sl@0: static _RWSTD_SIZE_T dtor_throw_count_;
sl@0: static _RWSTD_SIZE_T op_assign_throw_count_;
sl@0: static _RWSTD_SIZE_T op_eq_throw_count_;
sl@0: static _RWSTD_SIZE_T op_lt_throw_count_;
sl@0:
sl@0: _TEST_EXPORT X ();
sl@0:
sl@0: _TEST_EXPORT X (const X&);
sl@0:
sl@0: _TEST_EXPORT ~X ();
sl@0:
sl@0: _TEST_EXPORT X& operator= (const X&);
sl@0:
sl@0: _TEST_EXPORT bool operator== (const X&) const;
sl@0: _TEST_EXPORT bool operator< (const X&) const;
sl@0:
sl@0: // the following operators are not declared or defined in order
sl@0: // to detect any unwarranted assumptions made in algorithms
sl@0: // bool operator!= (const X &rhs) const;
sl@0: // bool operator> (const X &rhs) const;
sl@0: // bool operator>= (const X &rhs) const;
sl@0: // bool operator<= (const X &rhs) const;
sl@0: // X operator- () const;
sl@0: // X operator+ () const;
sl@0:
sl@0: _TEST_EXPORT bool
sl@0: is_count (_RWSTD_SIZE_T copy_ctor,
sl@0: _RWSTD_SIZE_T op_assign,
sl@0: _RWSTD_SIZE_T op_eq,
sl@0: _RWSTD_SIZE_T op_lt) const;
sl@0:
sl@0: _TEST_EXPORT static bool
sl@0: is_total (_RWSTD_SIZE_T count,
sl@0: _RWSTD_SIZE_T n_def_ctor,
sl@0: _RWSTD_SIZE_T n_copy_ctor,
sl@0: _RWSTD_SIZE_T n_op_assign,
sl@0: _RWSTD_SIZE_T n_op_eq,
sl@0: _RWSTD_SIZE_T n_op_lt);
sl@0:
sl@0: _TEST_EXPORT static void reset_totals ();
sl@0:
sl@0: // construct an array of objects of type X each initialized
sl@0: // from the corresponding element of the character array
sl@0: static X* from_char (const char*, _RWSTD_SIZE_T = ~0UL);
sl@0:
sl@0: // returns -1 when less, 0 when same, or +1 when the array
sl@0: // of X objects is greater than the character string
sl@0: static int compare (const X*, const char*, _RWSTD_SIZE_T = ~0UL);
sl@0: static int compare (const char*, const X*, _RWSTD_SIZE_T = ~0UL);
sl@0:
sl@0: // returns -1 when less, 0 when same, or +1 when the first
sl@0: // array of X objects is greater than the second array
sl@0: static int compare (const X*, const X*, _RWSTD_SIZE_T);
sl@0: };
sl@0:
sl@0:
sl@0: struct _TEST_EXPORT UnaryPredicate
sl@0: {
sl@0: // total number of times operator() was invoked
sl@0: static _RWSTD_SIZE_T n_total_op_fcall_;
sl@0:
sl@0: UnaryPredicate ();
sl@0:
sl@0: UnaryPredicate (const UnaryPredicate&);
sl@0:
sl@0: UnaryPredicate& operator= (const UnaryPredicate&);
sl@0:
sl@0: virtual ~UnaryPredicate ();
sl@0:
sl@0: virtual bool operator()(const X&) const;
sl@0: };
sl@0:
sl@0:
sl@0: struct _TEST_EXPORT BinaryPredicate
sl@0: {
sl@0: // total number of times operator() was invoked
sl@0: static _RWSTD_SIZE_T n_total_op_fcall_;
sl@0:
sl@0: bool ignore_case_;
sl@0:
sl@0: BinaryPredicate (bool = false);
sl@0:
sl@0: BinaryPredicate (const BinaryPredicate&);
sl@0:
sl@0: BinaryPredicate& operator= (const BinaryPredicate&);
sl@0:
sl@0: virtual ~BinaryPredicate ();
sl@0:
sl@0: virtual bool operator()(const X&, const X&) const;
sl@0: };
sl@0:
sl@0:
sl@0: class _TEST_EXPORT tempstr;
sl@0:
sl@0: // converts a sequence of objects of type X to a tempstr object
sl@0: // in the format "[%p0, %p1): { x0, >x1<, ..., xN - 1 } where N
sl@0: // is defined as: N = (X*)p1 - (X*)p0
sl@0: // the last argument, if non-negative, indicates the index of the
sl@0: // element enclosed in between the '>' and '<' characters
sl@0: _TEST_EXPORT void to_string (tempstr*, const X*, const X*, int = -1);
sl@0:
sl@0:
sl@0: // generate a unique sequential number starting from 0
sl@0: _TEST_EXPORT int gen_seq ();
sl@0:
sl@0: // generate numbers in the sequence 0, 0, 1, 1, 2, 2, 3, 3, etc...
sl@0: _TEST_EXPORT int gen_seq_2lists ();
sl@0:
sl@0: // generate a sequence of subsequences (i.e., 0, 1, 2, 3, 4, 0, 1, 2, etc...)
sl@0: _TEST_EXPORT int gen_subseq ();
sl@0:
sl@0: // wrapper around a (possibly) extern "C" int rand()
sl@0: // extern "C++"
sl@0: _TEST_EXPORT int gen_rnd ();
sl@0:
sl@0:
sl@0: // computes an integral log2
sl@0: inline unsigned ilog2 (unsigned long n)
sl@0: {
sl@0: unsigned result = 0;
sl@0: while (n >>= 1)
sl@0: ++result;
sl@0: return result;
sl@0: }
sl@0:
sl@0:
sl@0: // computes an integral log10
sl@0: inline unsigned ilog10 (unsigned long n)
sl@0: {
sl@0: unsigned result = 0;
sl@0: while (n /= 10)
sl@0: ++result;
sl@0: return result;
sl@0: }
sl@0:
sl@0:
sl@0: // returns true iff a sequence of (not necessarily unique) values
sl@0: // is sorted in an ascending order
sl@0: template <class InputIterator>
sl@0: inline bool is_sorted_lt (InputIterator first, InputIterator last)
sl@0: {
sl@0: if (first == last)
sl@0: return true;
sl@0:
sl@0: for (InputIterator prev (first); ++first != last; prev = first) {
sl@0: if (*first < *prev)
sl@0: return false;
sl@0: }
sl@0:
sl@0: return true;
sl@0: }
sl@0:
sl@0:
sl@0: // returns true iff a sequence of (not necessarily unique) values
sl@0: // is sorted in a descending order
sl@0: template <class InputIterator>
sl@0: inline bool is_sorted_gt (InputIterator first, InputIterator last)
sl@0: {
sl@0: if (first == last)
sl@0: return true;
sl@0:
sl@0: for (InputIterator prev (first); ++first != last; prev = first) {
sl@0: if (*prev < *first)
sl@0: return false;
sl@0: }
sl@0:
sl@0: return true;
sl@0: }
sl@0:
sl@0:
sl@0: // type used to exercise that algorithms do not apply operators
sl@0: // to function objects the latter are not required to define
sl@0: struct conv_to_bool {
sl@0:
sl@0: static conv_to_bool make (bool val) {
sl@0: conv_to_bool tmp;
sl@0: tmp.val_ = val;
sl@0: return tmp;
sl@0: }
sl@0:
sl@0: operator bool () const {
sl@0: return val_;
sl@0: }
sl@0:
sl@0: public:
sl@0: bool operator!() const
sl@0: {
sl@0: return val_ != 0;
sl@0: } // not defined
sl@0:
sl@0: bool val_;
sl@0: };
sl@0:
sl@0: // not defined
sl@0: void operator&& (const conv_to_bool&, bool);
sl@0: void operator&& (bool, const conv_to_bool&);
sl@0: void operator|| (const conv_to_bool&, bool);
sl@0: void operator|| (bool, const conv_to_bool&);
sl@0:
sl@0: // element-type prototypes to exercise container requirements
sl@0:
sl@0:
sl@0: // meets requirements listed at 25, p7
sl@0: template <class T>
sl@0: struct predicate {
sl@0: conv_to_bool operator() (const T &a) const {
sl@0: _RWSTD_UNUSED (a);
sl@0: return conv_to_bool::make (true);
sl@0: }
sl@0: };
sl@0:
sl@0:
sl@0: // meets requirements listed at 25, p8
sl@0: template <class T>
sl@0: struct binary_predicate {
sl@0: conv_to_bool operator() (const T &a, const T &b) const {
sl@0: _RWSTD_UNUSED (a);
sl@0: _RWSTD_UNUSED (b);
sl@0: return conv_to_bool::make (true);
sl@0: }
sl@0: };
sl@0:
sl@0:
sl@0: // meets requirements listed at 25.2.3, p2
sl@0: template <class T>
sl@0: struct func {
sl@0: typedef T argument_type;
sl@0: typedef argument_type& reference;
sl@0:
sl@0: reference operator() (const argument_type&) const {
sl@0: return _RWSTD_REINTERPRET_CAST (reference,
sl@0: _RWSTD_CONST_CAST (func*, this)->dummy);
sl@0: }
sl@0:
sl@0: private:
sl@0: char dummy;
sl@0: };
sl@0:
sl@0:
sl@0: // meets requirements listed at 25.2.3, p2
sl@0: template <class T>
sl@0: struct binary_func {
sl@0: typedef T argument_type;
sl@0: typedef argument_type& reference;
sl@0:
sl@0: reference operator() (const argument_type&,
sl@0: const argument_type&) const {
sl@0: return _RWSTD_REINTERPRET_CAST (reference,
sl@0: _RWSTD_CONST_CAST (binary_func*, this)->dummy);
sl@0: }
sl@0:
sl@0: private:
sl@0: char dummy;
sl@0: };
sl@0:
sl@0:
sl@0: // a base-class to extend the requirements classes from
sl@0:
sl@0: enum { no_ctor = 0, def_ctor = 1, cpy_ctor = 2 };
sl@0:
sl@0: template <int c = no_ctor>
sl@0: struct base;
sl@0:
sl@0:
sl@0: template<>
sl@0: struct base<no_ctor>
sl@0: {
sl@0: private:
sl@0: // struct s added to prevent gcc warning: base<no_ctor> has a private
sl@0: // constructor and no friends
sl@0: struct s { };
sl@0: friend struct s;
sl@0:
sl@0: base ();
sl@0: base (const base&);
sl@0: void operator= (base&);
sl@0: };
sl@0:
sl@0:
sl@0: template<>
sl@0: struct base<def_ctor>
sl@0: {
sl@0: base () : unused (0) { }
sl@0:
sl@0: private:
sl@0:
sl@0: void operator= (base&);
sl@0: base (const base&);
sl@0:
sl@0: // unused member prevents bogus HP aCC warnings (see Onyx #23561)
sl@0: int unused;
sl@0: };
sl@0:
sl@0:
sl@0: template<>
sl@0: struct base<cpy_ctor>
sl@0: {
sl@0: // explicitly specifying redundant template parameters to work
sl@0: // around a SunPro 5.2 bug (see Onyx #24260)
sl@0: base (const base<cpy_ctor> &rhs): unused (rhs.unused) { }
sl@0:
sl@0: private:
sl@0:
sl@0: base ();
sl@0: void operator= (base&);
sl@0:
sl@0: // unused member prevents bogus HP aCC warnings (see Onyx #23561)
sl@0: int unused;
sl@0: };
sl@0:
sl@0:
sl@0: template<>
sl@0: struct base<(def_ctor | cpy_ctor)>
sl@0: {
sl@0: base (): unused (0) { }
sl@0:
sl@0: // explicitly specifying redundant template parameters to work
sl@0: // around a SunPro 5.2 bug (see Onyx #24260)
sl@0: base (const base<(def_ctor | cpy_ctor)> &rhs): unused (rhs.unused) { }
sl@0:
sl@0: private:
sl@0:
sl@0: void operator= (base&);
sl@0:
sl@0: // unused member prevents bogus HP aCC warnings (see Onyx #23561)
sl@0: int unused;
sl@0: };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: struct eq_comp: T { };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline bool operator== (const eq_comp<T>&, const eq_comp<T>&)
sl@0: {
sl@0: return true;
sl@0: }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: struct lt_comp: T { };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline bool operator< (const lt_comp<T>&, const lt_comp<T>&)
sl@0: {
sl@0: return true;
sl@0: }
sl@0:
sl@0:
sl@0: // assignment
sl@0:
sl@0: template <class T>
sl@0: struct assign : T
sl@0: {
sl@0: assign& operator= (const assign& rhs) {
sl@0: unused = rhs.unused;
sl@0: return *this;
sl@0: }
sl@0: private:
sl@0: // unused member prevents bogus HP aCC warnings (see Onyx #23561)
sl@0: int unused;
sl@0: };
sl@0:
sl@0:
sl@0: // conversion structs
sl@0:
sl@0: // struct split into 2 to eliminate the following g++ 2.95.2 warning:
sl@0: // warning: choosing `convert<T>::operator U&()' over
sl@0: // `convert<T>::operator const U&() const'
sl@0:
sl@0: template <class T, class U>
sl@0: struct cvt : T
sl@0: {
sl@0: operator U& () {
sl@0: return _RWSTD_REINTERPRET_CAST (U&, *this);
sl@0: }
sl@0: };
sl@0:
sl@0:
sl@0: template <class T, class U>
sl@0: struct const_cvt : T
sl@0: {
sl@0: operator const U& () const {
sl@0: return _RWSTD_REINTERPRET_CAST (const U&, *this);
sl@0: }
sl@0: };
sl@0:
sl@0:
sl@0: #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
sl@0:
sl@0: struct DummyBase { };
sl@0:
sl@0: # define ITER_BASE(ign1, ign2, ign3, ign4, ign5) DummyBase
sl@0: #else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)
sl@0: // when partial specialization isn't supported
sl@0: # define ITER_BASE(Cat, T, Dist, Ptr, Ref) \
sl@0: std::iterator<Cat, T, Dist, Ptr, Ref >
sl@0: #endif // _RWSTD_NO_CLASS_PARTIAL_SPEC
sl@0:
sl@0:
sl@0: // satisfies the requirements in 24.1.1 [lib.input.iterators]
sl@0: template <class T>
sl@0: struct InputIter: ITER_BASE (std::input_iterator_tag, T, int, T*, T&)
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef value_type* pointer;
sl@0: typedef value_type& reference;
sl@0: typedef int difference_type;
sl@0: typedef std::input_iterator_tag iterator_category;
sl@0:
sl@0: // body shared by all copies of the same InputIter specialization
sl@0: // to detect algorithms that pass through the same interator more
sl@0: // than once (disallowed by 24.1.1, p3)
sl@0: struct Shared {
sl@0: const value_type *cur_;
sl@0: const value_type *beg_;
sl@0: const value_type *end_;
sl@0: int ref_;
sl@0:
sl@0: Shared (const value_type *cur,
sl@0: const value_type *beg,
sl@0: const value_type *end)
sl@0: : cur_ (cur), beg_ (beg), end_ (end), ref_ (1) { }
sl@0:
sl@0: ~Shared () {
sl@0: cur_ = beg_ = end_ = 0;
sl@0: ref_ = -1;
sl@0: }
sl@0:
sl@0: private:
sl@0: Shared (const Shared&); // not defined
sl@0: void operator= (const Shared&); // not defined
sl@0:
sl@0: };
sl@0:
sl@0: // InputIterators are not default constructible
sl@0: InputIter (const value_type *cur,
sl@0: const value_type *beg,
sl@0: const value_type *end)
sl@0: : ptr_ (new Shared (cur, beg, end)), cur_ (cur) { }
sl@0:
sl@0: InputIter (const InputIter &rhs)
sl@0: : ptr_ (rhs.ptr_), cur_ (rhs.cur_) {
sl@0: assert (0 != ptr_);
sl@0: ++ptr_->ref_;
sl@0: }
sl@0:
sl@0: ~InputIter () {
sl@0: assert (0 != ptr_);
sl@0:
sl@0: if (0 == --ptr_->ref_) // decrement the reference count
sl@0: delete ptr_;
sl@0: ptr_ = 0;
sl@0: cur_ = 0;
sl@0: }
sl@0:
sl@0: InputIter& operator= (const InputIter &rhs) {
sl@0: assert (rhs == rhs); // assert `rhs' is valid
sl@0:
sl@0: assert (0 != ptr_);
sl@0: if (0 == --ptr_->ref_)
sl@0: delete ptr_;
sl@0:
sl@0: ptr_ = rhs.ptr_;
sl@0:
sl@0: assert (0 != ptr_);
sl@0: ++ptr_->ref_;
sl@0:
sl@0: cur_ = rhs.cur_;
sl@0:
sl@0: return *this;
sl@0: }
sl@0:
sl@0: bool operator== (const InputIter &rhs) const {
sl@0: // assert that both arguments are in the domain of operator==()
sl@0: // i.e., that no copy of *this or `rhs' has been incremented
sl@0: // and that no copy passed through this value of the iterator
sl@0:
sl@0: assert (0 != ptr_);
sl@0: assert (cur_ == ptr_->cur_);
sl@0:
sl@0: assert (0 != rhs.ptr_);
sl@0: assert (rhs.cur_ == rhs.ptr_->cur_);
sl@0:
sl@0: return cur_ == rhs.cur_;
sl@0: }
sl@0:
sl@0: bool operator!= (const InputIter &rhs) const {
sl@0: return !(*this == rhs);
sl@0: }
sl@0:
sl@0: // returning const-reference rather than a value in order
sl@0: // not to impose the CopyConstructible requirement on T
sl@0: // and to disallow constructs like *InputIter<T>() = T()
sl@0: const value_type& operator* () const {
sl@0: assert (*this == *this); // assert *this is valid
sl@0: assert (cur_ < ptr_->end_); // assert *this is dereferenceable
sl@0: return *cur_;
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW(const value_type* operator-> () const);
sl@0:
sl@0: InputIter& operator++ () {
sl@0: assert (*this == *this); // assert *this is valid
sl@0: assert (cur_ < ptr_->end_); // assert *this is not past the end
sl@0:
sl@0: ptr_->cur_ = ++cur_;
sl@0:
sl@0: return *this;
sl@0: }
sl@0:
sl@0: InputIter operator++ (int) {
sl@0: return ++*this;
sl@0: }
sl@0:
sl@0: // private:
sl@0: Shared *ptr_;
sl@0: const value_type *cur_; // past-the-end
sl@0: };
sl@0:
sl@0:
sl@0: // satisfies the requirements in 24.1.2 [lib.output.iterators]
sl@0: template <class T>
sl@0: struct OutputIter: ITER_BASE (std::output_iterator_tag, T, int, T*, T&)
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef value_type* pointer;
sl@0: typedef value_type& reference;
sl@0: typedef int difference_type;
sl@0: typedef std::output_iterator_tag iterator_category;
sl@0:
sl@0: // body shared by all copies of the same OutputIter specialization
sl@0: // to detect algorithms that pass through the same interator more
sl@0: // than once (disallowed by 24.1.2, p2)
sl@0: struct Shared {
sl@0: pointer cur_;
sl@0: pointer assign_;
sl@0: const value_type *begin_;
sl@0: const value_type *end_;
sl@0: int ref_;
sl@0:
sl@0: Shared (pointer cur, const value_type *end)
sl@0: : cur_ (cur), assign_ (cur), begin_ (cur), end_ (end), ref_ (1) { }
sl@0:
sl@0: ~Shared () {
sl@0: begin_ = end_ = cur_ = assign_ = 0;
sl@0: ref_ = -1;
sl@0: }
sl@0:
sl@0: private:
sl@0: Shared (const Shared&); // not defined
sl@0: void operator= (const Shared&); // not defined
sl@0:
sl@0: };
sl@0:
sl@0: // class whose objects are returned from OutputIter::operator*
sl@0: // to detect multiple assignments (disallowed by 24.1.2, p2)
sl@0: class Proxy {
sl@0: friend struct OutputIter;
sl@0:
sl@0: Shared* const ptr_;
sl@0:
sl@0: Proxy (Shared *ptr): ptr_ (ptr) { }
sl@0:
sl@0: public:
sl@0: void operator= (const value_type &rhs) {
sl@0: assert (0 != ptr_);
sl@0:
sl@0: // verify that the iterator is in the valid range
sl@0: assert (ptr_->cur_ >= ptr_->begin_ && ptr_->cur_ <= ptr_->end_);
sl@0:
sl@0: // verify that the assignment point is the same as the current
sl@0: // position `cur' within the sequence or immediately before it
sl@0: // (in order to allow the expression: *it++ = val)
sl@0: assert ( ptr_->assign_ == ptr_->cur_
sl@0: || ptr_->assign_ + 1 == ptr_->cur_);
sl@0:
sl@0: // assign and increment the assignment point
sl@0: *ptr_->assign_++ = rhs;
sl@0: }
sl@0: };
sl@0:
sl@0: // OutputIterators are not default constructible
sl@0: OutputIter (pointer cur,
sl@0: const value_type *,
sl@0: const value_type *end)
sl@0: : ptr_ (new Shared (cur, end)), cur_ (cur) { }
sl@0:
sl@0: OutputIter (const OutputIter &rhs)
sl@0: : ptr_ (rhs.ptr_), cur_ (rhs.cur_) {
sl@0: ++ptr_->ref_; // increment the reference count
sl@0: }
sl@0:
sl@0: ~OutputIter () {
sl@0: if (0 == --ptr_->ref_) // decrement the reference count
sl@0: delete ptr_;
sl@0: ptr_ = 0;
sl@0: cur_ = 0;
sl@0: }
sl@0:
sl@0: OutputIter& operator= (const OutputIter &rhs) {
sl@0: if (0 == --ptr_->ref_)
sl@0: delete ptr_;
sl@0:
sl@0: ptr_ = rhs.ptr_;
sl@0: ++ptr_->ref_;
sl@0:
sl@0: cur_ = rhs.cur_;
sl@0:
sl@0: return *this;
sl@0: }
sl@0:
sl@0: void operator= (const value_type &rhs) const {
sl@0: **this = rhs;
sl@0: }
sl@0:
sl@0: // return a proxy in order to detect multiple assignments
sl@0: // through the iterator (disallowed by 24.1.2, p2))
sl@0: Proxy operator* () const {
sl@0: assert (0 != ptr_);
sl@0: assert (ptr_->assign_ && ptr_->assign_ != ptr_->end_);
sl@0:
sl@0: return Proxy (ptr_);
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
sl@0:
sl@0: OutputIter& operator++ () {
sl@0: assert (cur_ == ptr_->cur_);
sl@0: assert (ptr_->cur_ >= ptr_->begin_ && ptr_->cur_ < ptr_->end_);
sl@0: cur_ = ++ptr_->cur_;
sl@0: return *this;
sl@0: }
sl@0:
sl@0: // returning a const value rather than a modifiable value
sl@0: // in order to verify the requirement in row 5 of Table 73
sl@0: const OutputIter operator++ (int) {
sl@0: OutputIter tmp (*this);
sl@0: return ++*this, tmp;
sl@0: }
sl@0:
sl@0: // private:
sl@0: Shared *ptr_;
sl@0: pointer cur_;
sl@0: };
sl@0:
sl@0:
sl@0: // satisfies the requirements in 24.1.3 [lib.forward.iterators]
sl@0: template <class T>
sl@0: struct FwdIter: ITER_BASE (std::forward_iterator_tag, T, int, T*, T&)
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef value_type* pointer;
sl@0: typedef value_type& reference;
sl@0: typedef int difference_type;
sl@0: typedef std::forward_iterator_tag iterator_category;
sl@0:
sl@0: FwdIter (): cur_ (0), end_ (0) { }
sl@0:
sl@0: FwdIter (pointer cur,
sl@0: const value_type *,
sl@0: const value_type *end)
sl@0: : cur_ (cur), end_ (end) { }
sl@0:
sl@0: FwdIter (const FwdIter &rhs)
sl@0: : cur_ (rhs.cur_), end_ (rhs.end_) { }
sl@0:
sl@0: ~FwdIter () {
sl@0: end_ = cur_ = 0;
sl@0: }
sl@0:
sl@0: FwdIter& operator= (const FwdIter &rhs) {
sl@0: cur_ = rhs.cur_;
sl@0: end_ = rhs.end_;
sl@0: return *this;
sl@0: }
sl@0:
sl@0: bool operator== (const FwdIter &rhs) const {
sl@0: assert (cur_ != 0);
sl@0: return cur_ == rhs.cur_;
sl@0: }
sl@0:
sl@0: bool operator!= (const FwdIter &rhs) const {
sl@0: return !(*this == rhs);
sl@0: }
sl@0:
sl@0: reference operator* () const {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return *cur_;
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
sl@0:
sl@0: FwdIter& operator++ () {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return ++cur_, *this;
sl@0: }
sl@0:
sl@0: FwdIter operator++ (int) {
sl@0: FwdIter tmp (*this);
sl@0: return ++*this, tmp;
sl@0: }
sl@0:
sl@0: // private:
sl@0: pointer cur_; // pointer to current element
sl@0: const value_type *end_; // past-the-end
sl@0: };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: struct ConstFwdIter: FwdIter<T>
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef FwdIter<value_type> Base;
sl@0:
sl@0: ConstFwdIter (): Base () { }
sl@0:
sl@0: ConstFwdIter (const value_type *cur,
sl@0: const value_type *begin,
sl@0: const value_type *end)
sl@0: : Base (_RWSTD_CONST_CAST (value_type*, cur), begin, end) { }
sl@0:
sl@0: const value_type& operator* () const {
sl@0: return Base::operator* ();
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (const value_type* operator-> () const);
sl@0: };
sl@0:
sl@0:
sl@0: // satisfies the requirements in 24.1.4 [lib.bidirectional.iterators]
sl@0: template <class T>
sl@0: struct BidirIter: ITER_BASE (std::bidirectional_iterator_tag, T, int, T*, T&)
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef value_type* pointer;
sl@0: typedef value_type& reference;
sl@0: typedef int difference_type;
sl@0: typedef std::bidirectional_iterator_tag iterator_category;
sl@0:
sl@0: BidirIter (): cur_ (0), begin_ (0), end_ (0) { }
sl@0:
sl@0: BidirIter (pointer cur,
sl@0: const value_type *begin,
sl@0: const value_type *end)
sl@0: : cur_ (cur), begin_ (begin), end_ (end) { }
sl@0:
sl@0: BidirIter (const BidirIter &rhs)
sl@0: : cur_ (rhs.cur_), begin_ (rhs.begin_), end_ (rhs.end_) { }
sl@0:
sl@0: ~BidirIter () {
sl@0: begin_ = end_ = cur_ = 0;
sl@0: }
sl@0:
sl@0: BidirIter& operator= (const BidirIter &rhs) {
sl@0: cur_ = rhs.cur_;
sl@0: end_ = rhs.end_;
sl@0: return *this;
sl@0: }
sl@0:
sl@0: bool operator== (const BidirIter &rhs) const {
sl@0: assert (cur_ != 0 && rhs.cur_ != 0);
sl@0: return cur_ == rhs.cur_;
sl@0: }
sl@0:
sl@0: bool operator!= (const BidirIter &rhs) const {
sl@0: return !(*this == rhs);
sl@0: }
sl@0:
sl@0: reference operator* () const {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return *cur_;
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
sl@0:
sl@0: BidirIter& operator++ () {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return ++cur_, *this;
sl@0: }
sl@0:
sl@0: BidirIter operator++ (int) {
sl@0: BidirIter tmp (*this);
sl@0: return ++*this, tmp;
sl@0: }
sl@0:
sl@0: BidirIter& operator-- () {
sl@0: assert (cur_ != 0 && cur_ != begin_);
sl@0: return --cur_, *this;
sl@0: }
sl@0:
sl@0: BidirIter operator-- (int) {
sl@0: BidirIter tmp (*this);
sl@0: return --*this, tmp;
sl@0: }
sl@0:
sl@0: // private:
sl@0: pointer cur_; // pointer to current element
sl@0: const value_type *begin_; // first in range
sl@0: const value_type *end_; // past-the-end
sl@0: };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: struct ConstBidirIter: BidirIter<T>
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef BidirIter<value_type> Base;
sl@0:
sl@0: ConstBidirIter (): Base () { }
sl@0:
sl@0: ConstBidirIter (const value_type *cur,
sl@0: const value_type *begin,
sl@0: const value_type *end)
sl@0: : Base (_RWSTD_CONST_CAST (value_type*, cur), begin, end) { }
sl@0:
sl@0: const value_type& operator* () const {
sl@0: return Base::operator* ();
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (const value_type* operator-> () const);
sl@0: };
sl@0:
sl@0:
sl@0: // satisfies the requirements in 24.1.5 [lib.random.access.iterators]
sl@0: template <class T>
sl@0: struct RandomAccessIter
sl@0: : ITER_BASE (std::random_access_iterator_tag, T, int, T*, T&)
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef value_type* pointer;
sl@0: typedef value_type& reference;
sl@0: typedef int difference_type;
sl@0: typedef std::random_access_iterator_tag iterator_category;
sl@0:
sl@0: RandomAccessIter (): cur_ (0), begin_ (0), end_ (0) { }
sl@0:
sl@0: RandomAccessIter (pointer cur,
sl@0: const value_type *begin,
sl@0: const value_type *end)
sl@0: : cur_ (cur), begin_ (begin), end_ (end) { }
sl@0:
sl@0: RandomAccessIter (const RandomAccessIter &rhs)
sl@0: : cur_ (rhs.cur_), begin_ (rhs.begin_), end_ (rhs.end_) { }
sl@0:
sl@0: ~RandomAccessIter () {
sl@0: begin_ = end_ = cur_ = 0;
sl@0: }
sl@0:
sl@0: RandomAccessIter& operator= (const RandomAccessIter &rhs) {
sl@0: cur_ = rhs.cur_;
sl@0: begin_ = rhs.begin_;
sl@0: end_ = rhs.end_;
sl@0: return *this;
sl@0: }
sl@0:
sl@0: reference operator* () const {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return *cur_;
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
sl@0:
sl@0: RandomAccessIter& operator++ () {
sl@0: assert (cur_ != 0 && cur_ != end_);
sl@0: return ++cur_, *this;
sl@0: }
sl@0:
sl@0: RandomAccessIter operator++ (int) {
sl@0: RandomAccessIter tmp (*this);
sl@0: return ++*this, tmp;
sl@0: }
sl@0:
sl@0: RandomAccessIter& operator-- () {
sl@0: assert (cur_ != 0 && cur_ != begin_);
sl@0: return --cur_, *this;
sl@0: }
sl@0:
sl@0: RandomAccessIter operator-- (int) {
sl@0: RandomAccessIter tmp (*this);
sl@0: return --*this, tmp;
sl@0: }
sl@0:
sl@0: RandomAccessIter& operator+= (difference_type n) {
sl@0: assert ( cur_ != 0
sl@0: && (!end_ || cur_ + n <= end_)
sl@0: && (!begin_ || cur_ + n >= begin_));
sl@0: return cur_ += n, *this;
sl@0: }
sl@0: RandomAccessIter& operator-= (difference_type n) {
sl@0: return *this += -n;
sl@0: }
sl@0:
sl@0: RandomAccessIter operator+ (difference_type n) const {
sl@0: return RandomAccessIter (*this) += n;
sl@0: }
sl@0:
sl@0: RandomAccessIter operator- (difference_type n) const {
sl@0: return RandomAccessIter (*this) -= n;
sl@0: }
sl@0:
sl@0: difference_type operator- (const RandomAccessIter &rhs) const {
sl@0: assert (cur_ != 0 && rhs.cur_ != 0);
sl@0: return cur_ - rhs.cur_;
sl@0: }
sl@0:
sl@0: bool operator== (const RandomAccessIter &rhs) const {
sl@0: assert (cur_ != 0 && rhs.cur_ != 0);
sl@0: return cur_ == rhs.cur_;
sl@0: }
sl@0:
sl@0: bool operator!= (const RandomAccessIter &rhs) const {
sl@0: return !(*this == rhs);
sl@0: }
sl@0:
sl@0: bool operator< (const RandomAccessIter &rhs) const {
sl@0: assert (cur_ != 0 && rhs.cur_ != 0);
sl@0: return cur_ < rhs.cur_;
sl@0: };
sl@0:
sl@0: bool operator> (const RandomAccessIter &rhs) const {
sl@0: return rhs < *this;
sl@0: }
sl@0:
sl@0: bool operator<= (const RandomAccessIter &rhs) const {
sl@0: return !(rhs < *this);
sl@0: }
sl@0:
sl@0: bool operator>= (const RandomAccessIter &rhs) const {
sl@0: return !(*this < rhs);
sl@0: }
sl@0:
sl@0: reference operator[] (difference_type inx) const {
sl@0: assert ( cur_ != 0
sl@0: && (!end_ || cur_ + inx < end_)
sl@0: && !(begin_ || cur_ + inx >= begin_));
sl@0: return cur_ [inx];
sl@0: }
sl@0:
sl@0: // private:
sl@0: pointer cur_; // pointer to current element
sl@0: const value_type *begin_; // first in range
sl@0: const value_type *end_; // past-the-end
sl@0: };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: struct ConstRandomAccessIter: RandomAccessIter<T>
sl@0: {
sl@0: typedef T value_type;
sl@0: typedef RandomAccessIter<value_type> Base;
sl@0: typedef typename Base::difference_type difference_type;
sl@0:
sl@0: ConstRandomAccessIter (): Base () { }
sl@0:
sl@0: ConstRandomAccessIter (const value_type *cur,
sl@0: const value_type *begin,
sl@0: const value_type *end)
sl@0: : Base (_RWSTD_CONST_CAST (value_type*, cur), begin, end) { }
sl@0:
sl@0: const value_type& operator* () const {
sl@0: return Base::operator* ();
sl@0: }
sl@0:
sl@0: _RWSTD_OPERATOR_ARROW (const value_type* operator-> () const);
sl@0:
sl@0: const value_type& operator[] (difference_type inx) const {
sl@0: return Base::operator[] (inx);
sl@0: }
sl@0: };
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline T*
sl@0: make_iter (T *cur, const T*, const T*, T*)
sl@0: {
sl@0: return cur;
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline T*
sl@0: copy_iter (T *ptr, const T*)
sl@0: {
sl@0: return ptr;
sl@0: }
sl@0:
sl@0: // dummy function argument provided to help broken compilers (PR #29835)
sl@0:
sl@0: template <class T>
sl@0: inline InputIter<T>
sl@0: make_iter (const T *cur, const T *begin, const T *end, const InputIter<T>&)
sl@0: {
sl@0: return InputIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline InputIter<T>
sl@0: copy_iter (const InputIter<T> &it, const T*)
sl@0: {
sl@0: return InputIter<T>(it.cur_, it.ptr_->beg_, it.ptr_->end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (InputIter<T>, const T*)
sl@0: { return "InputIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline OutputIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, const OutputIter<T>&)
sl@0: {
sl@0: return OutputIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline OutputIter<T>
sl@0: copy_iter (const OutputIter<T> &it, const T*)
sl@0: {
sl@0: return OutputIter<T>(it.cur_, 0, it.ptr_->end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (OutputIter<T>, const T*)
sl@0: { return "OutputIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline FwdIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, FwdIter<T>)
sl@0: {
sl@0: return FwdIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline FwdIter<T>
sl@0: copy_iter (const FwdIter<T> &it, const T*)
sl@0: {
sl@0: return FwdIter<T>(it.cur_, 0, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (FwdIter<T>, const T*)
sl@0: { return "ForwardIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline ConstFwdIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, ConstFwdIter<T>)
sl@0: {
sl@0: return ConstFwdIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline ConstFwdIter<T>
sl@0: copy_iter (const ConstFwdIter<T> &it, const T*)
sl@0: {
sl@0: return ConstFwdIter<T>(it.cur_, 0, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (ConstFwdIter<T>, const T*)
sl@0: { return "ConstForwardIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline BidirIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, BidirIter<T>)
sl@0: {
sl@0: return BidirIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline BidirIter<T>
sl@0: copy_iter (const BidirIter<T> &it, const T*)
sl@0: {
sl@0: return BidirIter<T>(it.cur_, it.begin_, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (BidirIter<T>, const T*)
sl@0: { return "BidirectionalIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline ConstBidirIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, ConstBidirIter<T>)
sl@0: {
sl@0: return ConstBidirIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline ConstBidirIter<T>
sl@0: copy_iter (const ConstBidirIter<T> &it, const T*)
sl@0: {
sl@0: return ConstBidirIter<T>(it.cur_, it.begin_, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (ConstBidirIter<T>, const T*)
sl@0: { return "ConstBidirectionalIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline RandomAccessIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, RandomAccessIter<T>)
sl@0: {
sl@0: return RandomAccessIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline RandomAccessIter<T>
sl@0: copy_iter (const RandomAccessIter<T> &it, const T*)
sl@0: {
sl@0: return RandomAccessIter<T>(it.cur_, it.begin_, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (RandomAccessIter<T>, const T*)
sl@0: { return "RandomAccessIterator"; }
sl@0:
sl@0:
sl@0: template <class T>
sl@0: inline ConstRandomAccessIter<T>
sl@0: make_iter (T *cur, const T *begin, const T *end, ConstRandomAccessIter<T>)
sl@0: {
sl@0: return ConstRandomAccessIter<T>(cur, begin, end);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline ConstRandomAccessIter<T>
sl@0: copy_iter (const ConstRandomAccessIter<T> &it, const T*)
sl@0: {
sl@0: return ConstRandomAccessIter<T>(it.cur_, it.begin_, it.end_);
sl@0: }
sl@0:
sl@0: template <class T>
sl@0: inline const char* type_name (ConstRandomAccessIter<T>, const T*)
sl@0: { return "ConstRandomAccessIterator"; }
sl@0:
sl@0: typedef int (*fptr_gen_)();
sl@0:
sl@0: //exporting fun for exporting global var
sl@0: _TEST_EXPORT _RWSTD_SIZE_T* Getn_total_op_assign_();
sl@0: _TEST_EXPORT _RWSTD_SIZE_T* Getn_total_op_eq_();
sl@0: _TEST_EXPORT fptr_gen_* Get_gen_();
sl@0: #endif // _RWSTD_ALG_TEST_H_INCLUDED