allow sorting through an adaptor

[giecrilj@…]

The following code does not compile because the transform adaptor offers a proxy reference that cannot be modified:

#include <iostream>
#include <boost/array.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/bind.hpp>
#include <boost/range/algorithm/sort.hpp>

struct underlying { int m_; }; 

int main (int, char *[]) { 
  enum LocalParam { BASE = 073, VALUE = 030 }; 
  typedef ::boost ::array < underlying, +BASE - 01 > mycont; mycont v;
  for 
    (::boost ::range_iterator < mycont >:: type p ((::boost ::begin (v))); 
p < ::boost ::end (v); ++p) 
    p -> m_ = p == ::boost ::begin (v)? +VALUE: p [-01] .m_ * VALUE % BASE;
  ::boost ::copy 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1)), 
       ::std ::ostream_iterator 
< int, ::std ::istream ::char_type > 
       (::std:: cout, " ")); ::std ::cout << '\n';
  ::boost ::sort 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1)));   
::boost ::copy 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1)), 
       ::std ::ostream_iterator 
< int, ::std ::istream ::char_type > 
       (::std:: cout, " ")); 
  return (::std ::cout << '\n') .flush ()? +EXIT_SUCCESS: +EXIT_FAILURE; }

This is a deficiency because, when you have relational data packaged in a container, you often wish to create various indices based on various aspects of the data. This is currently unsupported by Boost, except for Multi-Index, but Multi-Index does not allow you to create a detached index; instead, it insists on maintaining all indices dynamically all the time, which is not always necessary and it brings a performance penalty compared to sorting static data.

I have implemented the missing adaptor and called it shufflebase; when applied to an adaptor, it allows the sort algorithm to rearrange the original container based on the ordering of the adaptor.

Here is the adaptor code; note that it does not carry any algorithm, only type juggling and general logistics:

#include <boost/range/iterator_range.hpp>       /* boost:: iterator_range */

#ifndef BOOST_RANGE_ADAPTOR_SHUFFLEBASE_DEFINED
#if 1
namespace boost {
  /*
the following declarations are used in namespace adaptors;
they are here to keep the namespace in one piece */

#if 2
  namespace traits { template < class P_I > struct shufflebase; }
#endif    /* &boost.traits */

  template < class P_I > class shufflebase_iterator;

#if 2
namespace adaptors {
  /* a forward declaration for operator | */
  template < class P_R > struct shufflebase_range;

#if 3
  namespace detail
{ struct /* tag enabler for operator | */ shufflebase_forwarder {};
template < class P_R >
inline struct shufflebase_range < P_R const >
/* applies the shufflebase adaptor to a range */
operator | (P_R const &p_r, struct detail:: shufflebase_forwarder );
}
#endif    /* &boost.adaptors.detail */

#if 3
  namespace /* static */ {
    detail :: shufflebase_forwarder const
/* the formal parameter for operator | */
(&shufflebase) ((detail ::shufflebase_forwarder ())); }
#endif    /* &boost.adaptors.static */

#if 3
  namespace traits { template < class P_T > struct shufflebase_range; }
#endif    /* &boost.adaptors.traits & */

#if 3
  template < class P_R >
  /* applies shufflebase_iterator to the range */
struct shufflebase_range     
:public traits ::shufflebase_range < P_R > ::base {
public:
    inline shufflebase_range (P_R &p_r);
private: typedef traits ::shufflebase_range < P_R > traits;
private: typedef typename traits ::base base;
public: typedef typename traits ::iterator iterator; };
#endif    /* #boost.adaptors.shufflebase_range */

#if 3
  namespace traits {

#if 4
    template < class P_R >
/* typedefs for shufflebase_range proper */ struct shufflebase_range
{ typedef  
::boost :: shufflebase_iterator
< typename ::boost ::range_iterator < P_R > ::type > iterator;
typedef struct ::boost ::iterator_range < iterator > base; };
#endif    /* #boost.adaptors.traits.shufflebase_range */

 }
#endif    /* &boost.adaptors.traits */

}
#endif    /* &boost.adaptors */

#if 2
  template < class P_I >
/*
Behaves transparently when applied to an adapted iterator
except that assignments are possible and apply to the underlying base */
  class shufflebase_iterator  
    :public /* iterator faciade */ traits:: shufflebase < P_I >:: base_type
  {
public:
/* constructs from an adapted iterator */
inline shufflebase_iterator (P_I const &);
  public:
/* inherited */ typedef typename shufflebase_iterator ::reference reference;
  public: /* returns a proxy reference */
    inline
reference
/* safety net: exclude application of default operator = to temporary */ const
operator* () const;
  public:
/* inherited */ typedef typename shufflebase_iterator ::value_type value_type;
  public: /* assigns the value to the base element, bypassing the adaptor */
    inline void assign (value_type const &p_v) const;
  public:
/* bookkeeping */
typedef typename traits:: shufflebase < P_I >:: base_type inherited; };
#endif    /* #boost.shufflebase_iterator */

#if 2
  namespace detail { template < class P_I > class shufflebase_reference;

#if 3
    template < class P_I >
    /*
Stores a value of an iterator.  

This class plays a double duty:
it stores the base value for assigning to a reference
and it caches the adapted value for comparisons.  
This causes some memory overhead
that I believe is unavoidable
without knowing the details of the managed adaptor.  
Moreover, caching the adapted value may speed things up a bit.  

This class is necessary
because the sorting algorithm puts some values aside for later use.  */

    class shufflebase_value
    {
public: /* bookkeeping */ typedef P_I base_type;
public: /* construct from a reference */
  inline
  shufflebase_value (class shufflebase_reference < base_type > const &p_r);
    public: /* the adapted value type */
typedef typename ::std ::iterator_traits < base_type > ::value_type adapted;
    public: /* compares as adapted */
      inline operator adapted const &() const;
    private: /* the adapted value */ adapted m_adapted;
public: /* the base value type */
  typedef typename traits ::shufflebase < base_type > ::base_value base_value;
    private: /* the base value */ base_value m_base;
    public:
/*
returns the base value for assignment
(the adapter is meant to affect the base container, remember? */
inline base_value const &base () const; };
#endif    /* #boost.detail.shufflebase_value */

#if 3
    template < class P_I >

    /*
A proxy class serving as reference type for shufflebase_iterator.  

Implicitly converts to the adapted reference for comparisons.  
Assignment affects the base object instead.
    */

    class shufflebase_reference
    {
public: /* bookkeeping */ typedef P_I base_type;
public: /* the adapted reference type */ typedef
typename ::std ::iterator_traits < base_type > ::reference reference;
    public: /* compares as adapted */
      inline operator reference const () const;   
    public:
/* the adapted value type */
typedef class shufflebase_value < base_type > value_type;
    public: /* assigned value goes to base */
inline
    shufflebase_reference const
&operator= (value_type const &p_v) const;
public: /* constructor */ inline
      shufflebase_reference (shufflebase_iterator < base_type > const &);
    private:
/* the proxied iterator */
shufflebase_iterator < base_type > const &m_ref;
    public: /* extract the base value for assigning to a value object */
inline
typename
::std ::iterator_traits < typename base_type:: base_type > ::value_type const
&base () const;
    private:
/* references are not assignable */
void operator = (shufflebase_reference const &); };
#endif    /* #boost.detail.shufflebase_reference */

  }
#endif    /* &boost.detail */

#if 2
namespace traits {

#if 3
  template < class P_I >
/* contains typedefs for shufflebase_iterator */ struct shufflebase
  {
/* bookkeeping */ typedef P_I iterator;

/* the base type for shufflebase_iterator */
typedef ::boost ::iterator_adaptor
  <
    class shufflebase_iterator < iterator >, iterator,  
  class detail:: shufflebase_value < iterator >,
::boost:: use_default,
class detail:: shufflebase_reference < iterator >
  > base_type;

    /* the base value */ typedef
  typename
  ::std ::iterator_traits < typename iterator ::base_type >:: value_type
  base_value;     
/*
The proper place to define base_value would be class shufflebase_value;
however, this type is shared by other auxiliary classes;
they depend on each other, causing the compiler to fail.  */ };
#endif /* #boost.traits.shufflebase */

}
#endif    /* &boost.traits */

}
#endif /* &boost */

#define BOOST_RANGE_ADAPTOR_SHUFFLEBASE_DEFINED
#endif

#ifndef BOOST_RANGE_ADAPTOR_SHUFFLEBASE_IMPLEMENTED

#if 1
namespace boost {

#if 2
  namespace adaptors {

#if 3
    namespace detail {

#if 4
      template <class P_R >
      inline struct shufflebase_range < P_R const >
      operator | (P_R const &p_r, shufflebase_forwarder)
{  return shufflebase_range < P_R const > (p_r); }
#endif    /* !boost.adaptors.shufflebase_range.operator| */

}
#endif    /* &boost.adaptors.detail */

#if 3
    template < class P_R >
    inline shufflebase_range < P_R > ::shufflebase_range (P_R &p_r)  
:base (iterator (::boost ::begin (p_r)), iterator (::boost ::end (p_r))) {}
#endif    /* !boost.adaptors.shufflebase_range.shufflebase_range */
}
#endif    /* &boost.adaptors */

#if 2
  template < class P_I >
  inline typename shufflebase_iterator < P_I > ::reference const
  shufflebase_iterator < P_I > ::operator * () const { return *this; }
#endif    /* !boost.shufflebase_iterator.operator * */

#if 2
  namespace detail {

#if 3
    template < class P_I >
    inline shufflebase_reference < P_I > ::operator reference const () const
{ return *this -> m_ref. base (); }
#endif    /* !boost.detail.shufflebase_reference::reference */

#if 3
    template < class P_I >
    inline shufflebase_reference < P_I > const
    &shufflebase_reference < P_I > ::operator = (value_type const &p_v) const
{ this -> m_ref .assign (p_v); return *this; }
#endif    /* !boost.detail.shufflebase_reference::operator = */

#if 3
    template < class P_I >
    inline shufflebase_reference < P_I > ::shufflebase_reference
    (shufflebase_iterator < P_I > const &p_ref) :m_ref (p_ref) {}
#endif    /* !boost.detail.shufflebase_reference.shufflebase_reference */

#if 3
    template < class P_I >
inline shufflebase_value < P_I > ::shufflebase_value
    (class shufflebase_reference < P_I > const &p_r)      
:m_adapted (p_r), m_base (p_r. base ()) {}
#endif    /* !boost.detail.shufflebase_value.shufflebase_value */

#if 3
template < class P_I >
inline shufflebase_value < P_I >:: operator adapted const & () const
{ return this -> m_adapted; }
#endif    /* !boost.detail.shufflebase_value.adapted & */

#if 3
template < class P_I >
inline
typename ::std ::iterator_traits < typename P_I ::base_type > ::value_type
const
&shufflebase_reference < P_I > :: base () const
{ return *this -> m_ref .base () .base (); }
#endif    /* !boost.detail.shufflebase_reference.base */

#if 3
template < class P_I >
typename shufflebase_value < P_I > ::base_value const
&shufflebase_value < P_I > ::base () const { return this -> m_base; }
#endif    /* !boost.detail.shufflebase_value.base */

}
#endif    /* &boost.detail */

#if 2
template < class P_I >
inline shufflebase_iterator < P_I >:: shufflebase_iterator (P_I const &p_i)
:inherited (p_i) { }
#endif    /* !boost.shufflebase_iterator. */

#if 2
template < class P_I >
inline void shufflebase_iterator < P_I > ::assign (value_type const &p_v) const
{ *this -> base (). base () = p_v. base (); }
#endif    /* !boost.shufflebase_iterator.assign */

}
#endif    /* &boost */

#define BOOST_RANGE_ADAPTOR_SHUFFLEBASE_IMPLEMENTED
#endif

Having this, the following code becomes valid:

#include <iostream>
#include <boost/array.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/bind.hpp>
#include <boost/range/algorithm/sort.hpp>

struct underlying { int m_; }; 

int main (int, char *[]) { 
  enum LocalParam { BASE = 073, VALUE = 030 }; 
  typedef ::boost ::array < underlying, +BASE - 01 > mycont; mycont v;
  for 
    (::boost ::range_iterator < mycont >:: type p ((::boost ::begin (v))); 
p < ::boost ::end (v); ++p) 
    p -> m_ = p == ::boost ::begin (v)? +VALUE: p [-01] .m_ * VALUE % BASE;
  ::boost ::copy 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1)), 
       ::std ::ostream_iterator 
< int, ::std ::istream ::char_type > 
       (::std:: cout, " ")); ::std ::cout << '\n';
  ::boost ::sort 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1))
| ::boost ::adaptors ::shufflebase);   
::boost ::copy 
      (v 
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1)), 
       ::std ::ostream_iterator 
< int, ::std ::istream ::char_type > 
       (::std:: cout, " ")); 
  return (::std ::cout << '\n') .flush ()? +EXIT_SUCCESS: +EXIT_FAILURE; }

and it produces the following output:

24 45 18 19 43 29 47 7 50 20 8 15 6 26 34 49 55 22 56 46 42 5 2 48 31 36 38 27 58 35 14 41 40 16 30 12 52 9 39 51 44 53 33 25 10 4 37 3 13 17 54 57 11 28 23 21 32 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

[ne01026@…]

an implementation of make_index using shufflebase indexes an arbitrary transformed range