indextable.h File Reference

#include <cassert>
#include <vector>
#include <typedefs.h>

Include dependency graph for indextable.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	comparepairfirst< T, U, Compare >
Functions
template<class Compare , class T >
void	sortIndexTable (vector< uint > &out, Compare c, vector< T > const &v)
	Sort a vector without altering the original vector. An array of indexes are sorted.
template<class IterOut , class Compare , class IterIn >
void	sortIndexTable (IterOut out, Compare c, IterIn first, IterIn last)
	Indexed containers.
template<typename T >
void	vectorshuffle (vector< T > &v1, vector< uint > &index)
	Randomly shuffles vector v1 with the index preserved.

---

Function Documentation

template<class IterOut , class Compare , class IterIn >

void sortIndexTable	(	IterOut	out,
		Compare	c,
		IterIn	first,
		IterIn	last
	)			[inline]

Indexed containers.

I modified the code from an online C++ coding review. Herb Sutter http://www.gotw.ca/gotw/073.htm

Changes: added a general Compare template parameter. Modified the variables order to my workspaces convention which has the output variables at the start of the function signature. Renamed the class variables and added an explicit vector interface which although in the example adds one more line of code I believe makes the function interface more clear. Chelton Evans 2007-02-06.

Example

  uintc aimax=10;
  int ai[10]={15,12,13,14,18,11,10,17,16,19};
  vector<int> aidxtbl(aimax);
  sortIndexTable(aidxtbl.begin(),less<int>(),ai,ai+aimax);

Definition at line 90 of file indextable.h.

{
  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
	)			[inline]

Sort a vector without altering the original vector. An array of indexes are sorted.

Example

  int ai[10]={15,12,13,14,18,11,10,17,16,19};
  uintc aimax=10;
  vector<int> ai2(ai,ai+aimax);  // data
  vector<uint> aidxtbl2; // index array
  sortIndexTable(aidxtbl2,greater<int>(),ai2);

Definition at line 114 of file indextable.h.

Referenced by indextabletest01().

{
  out.resize(v.size());
  sortIndexTable(out.begin(),c,v.begin(),v.end());
}

template<typename T >

void vectorshuffle	(	vector< T > &	v1,
		vector< uint > &	index
	)			[inline]

Randomly shuffles vector v1 with the index preserved.

ie the original element at the i'th index can be found at v1[index[i]].

Definition at line 127 of file indextable.h.

Referenced by quickhull2Drandomized< PT, D >::quickhull2Drandomized().

{
  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] ];
}