indextable.h

Go to the documentation of this file.

#ifndef INDEXTABLE_H
#define INDEXTABLE_H

#include <cassert>
#include <vector>

using namespace std;

#include <typedefs.h>

template< class Compare, class T >
void sortIndexTable
(
  vector<uint> & out,
  Compare c,
  vector<T> const & v
);


template< class IterOut, class Compare, class IterIn >
void sortIndexTable
( 
  IterOut out,
  Compare c,
  IterIn first, 
  IterIn last 
);

template< typename T >
void vectorshuffle
(
  vector<T> & v1,
  vector<uint> & index
);

//---------------------------------------------------------
// Implementation


template< class T, class U, class Compare >
struct comparepairfirst
{
  bool operator()
  (
    pair<T,U> const & a,
    pair<T,U> const & b 
  ) const
    { return Compare()(*a.first,*b.first); }
};

template< class IterOut, class Compare, class IterIn >
void sortIndexTable
( 
  IterOut out,
  Compare c,
  IterIn first, 
  IterIn last 
)
{
  vector<pair<IterIn,int> > s(last-first);
  uintc imax(s.size());
  for (uint i=0; i<imax; ++i)
    s[i]=make_pair(first+i,i);
  sort
  (
    s.begin(),
    s.end(),
    comparepairfirst<IterIn,int,Compare>()
  );
  for (uint i=0; i<imax; ++i,++out)
    *out=s[i].second;
}


template< class Compare, class T >
void sortIndexTable
(
  vector<uint> & out,
  Compare c,
  vector<T> const & v
)
{
  out.resize(v.size());
  sortIndexTable(out.begin(),c,v.begin(),v.end());
}


template< typename T >
void vectorshuffle
(
  vector<T> & v1,
  vector<uint> & index
)
{
  uintc n(v1.size());
  index.resize(n);
  for (uint i=0; i<n; ++i)
    index[i]=i;
  random_shuffle(index.begin(),index.end());

  vector<T> v2(v1.begin(),v1.end());
  for (uint i=0; i<n; ++i)
    v1[i] = v2[ index[i] ];
}



 
#endif