boost/graph/detail/permutation.hpp
// (C) Copyright Jeremy Siek 2001.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_PERMUTATION_HPP
#define BOOST_PERMUTATION_HPP
#include <vector>
#include <memory>
#include <functional>
#include <algorithm>
#include <boost/graph/detail/shadow_iterator.hpp>
namespace boost
{
template < class Iter1, class Iter2 >
void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)
{
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
typedef std::ptrdiff_t D :
#else
typedef typename std::iterator_traits< Iter1 >::difference_type D;
#endif
D n
= 0;
while (permuter != last)
{
std::swap(result[n], result[*permuter]);
++n;
++permuter;
}
}
template < class InIter, class RandIterP, class RandIterR >
void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)
{
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
typedef std::ptrdiff_t i = 0;
#else
typename std::iterator_traits< RandIterP >::difference_type i = 0;
#endif
for (; first != last; ++first, ++i)
result[p[i]] = *first;
}
namespace detail
{
template < class RandIter, class RandIterPerm, class D, class T >
void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)
{
D i = 0, pi, n = last - first, cycle_start;
T tmp;
std::vector< int > visited(n, false);
while (i != n)
{ // continue until all elements have been processed
cycle_start = i;
tmp = first[i];
do
{ // walk around a cycle
pi = p[i];
visited[pi] = true;
std::swap(tmp, first[pi]);
i = pi;
} while (i != cycle_start);
// find the next cycle
for (i = 0; i < n; ++i)
if (visited[i] == false)
break;
}
}
} // namespace detail
template < class RandIter, class RandIterPerm >
void permute(RandIter first, RandIter last, RandIterPerm p)
{
detail::permute_helper(first, last, p, last - first, *first);
}
// Knuth 1.3.3, Vol. 1 p 176
// modified for zero-based arrays
// time complexity?
//
// WARNING: T must be a signed integer!
template < class PermIter > void invert_permutation(PermIter X, PermIter Xend)
{
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
typedef std::ptrdiff_t T :
#else
typedef typename std::iterator_traits< PermIter >::value_type T;
#endif
T n
= Xend - X;
T m = n;
T j = -1;
while (m > 0)
{
T i = X[m - 1] + 1;
if (i > 0)
{
do
{
X[m - 1] = j - 1;
j = -m;
m = i;
i = X[m - 1] + 1;
} while (i > 0);
i = j;
}
X[m - 1] = -i - 1;
--m;
}
}
// Takes a "normal" permutation array (and its inverse), and turns it
// into a BLAS-style permutation array (which can be thought of as a
// serialized permutation).
template < class Iter1, class Iter2, class Iter3 >
inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)
{
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
typedef std::ptrdiff_t P1;
typedef std::ptrdiff_t P2;
typedef std::ptrdiff_t D;
#else
typedef typename std::iterator_traits< Iter1 >::value_type P1;
typedef typename std::iterator_traits< Iter2 >::value_type P2;
typedef typename std::iterator_traits< Iter1 >::difference_type D;
#endif
D n = q_end - q;
for (D i = 0; i < n; ++i)
{
P1 qi = q[i];
P2 qii = q_inv[i];
*p++ = qii;
std::swap(q[i], q[qii]);
std::swap(q_inv[i], q_inv[qi]);
}
}
// Not used anymore, leaving it here for future reference.
template < typename Iter, typename Compare >
void merge_sort(Iter first, Iter last, Compare cmp)
{
if (first + 1 < last)
{
Iter mid = first + (last - first) / 2;
merge_sort(first, mid, cmp);
merge_sort(mid, last, cmp);
std::inplace_merge(first, mid, last, cmp);
}
}
// time: N log N + 3N + ?
// space: 2N
template < class Iter, class IterP, class Cmp, class Alloc >
inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
{
typedef typename std::iterator_traits< IterP >::value_type P;
typedef typename std::iterator_traits< IterP >::difference_type D;
D n = last - first;
std::vector< P, Alloc > q(n);
for (D i = 0; i < n; ++i)
q[i] = i;
std::sort(make_shadow_iter(first, q.begin()),
make_shadow_iter(last, q.end()), shadow_cmp< Cmp >(cmp));
invert_permutation(q.begin(), q.end());
std::copy(q.begin(), q.end(), p);
}
template < class Iter, class IterP, class Cmp >
inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)
{
typedef typename std::iterator_traits< IterP >::value_type P;
sortp(first, last, p, cmp, std::allocator< P >());
}
template < class Iter, class IterP >
inline void sortp(Iter first, Iter last, IterP p)
{
typedef typename std::iterator_traits< Iter >::value_type T;
typedef typename std::iterator_traits< IterP >::value_type P;
sortp(first, last, p, std::less< T >(), std::allocator< P >());
}
template < class Iter, class IterP, class Cmp, class Alloc >
inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
{
typedef typename std::iterator_traits< IterP >::value_type P;
typedef typename std::iterator_traits< IterP >::difference_type D;
D n = last - first;
std::vector< P, Alloc > q(n), q_inv(n);
for (D i = 0; i < n; ++i)
q_inv[i] = i;
std::sort(make_shadow_iter(first, q_inv.begin()),
make_shadow_iter(last, q_inv.end()), shadow_cmp< Cmp >(cmp));
std::copy(q_inv, q_inv.end(), q.begin());
invert_permutation(q.begin(), q.end());
serialize_permutation(q.begin(), q.end(), q_inv.end(), p);
}
} // namespace boost
#endif // BOOST_PERMUTATION_HPP