Skip to content

Commit

Permalink
Started to clean up new sort algorithms, made things compile for sort…
Browse files Browse the repository at this point in the history 
…_by_key
  • Loading branch information
@hkaiser @biddisco
hkaiser authored and biddisco committed Jun 10, 2016
1 parent 70688b9 commit 36ee856
Show file tree
Hide file tree
Showing 18 changed files with 1,161 additions and 1,039 deletions.
768 changes: 398 additions & 370 deletions hpx/parallel/algorithms/sort/algorithm/blk_ind.hpp
View file

Large diffs are not rendered by default.

157 changes: 81 additions & 76 deletions hpx/parallel/algorithms/sort/algorithm/heap_sort.hpp
View file
Expand Up @@ -2,10 +2,10 @@
/// @file heap_sort.hpp
/// @brief Insertion Sort algorithm
///
/// @author Copyright (c) 2010 Francisco Jose Tapia (fjtapia@gmail.com )\n
/// @author Copyright (c) 2010 Francisco Jose Tapia (fjtapia@gmail.com)\n
/// Distributed under the Boost Software License, Version 1.0.\n
/// ( See accompanyingfile LICENSE_1_0.txt or copy at
/// http://www.boost.org/LICENSE_1_0.txt )
/// (See accompanyingfile LICENSE_1_0.txt or copy at
/// http://www.boost.org/LICENSE_1_0.txt)
/// @version 0.1
///
/// @remarks
Expand All @@ -31,8 +31,7 @@ HPX_INLINE_NAMESPACE(v2) { namespace boostsort
{
namespace algorithm
{
using std::iterator_traits ;
using namespace tools ;
using namespace tools;
//
//------------------------------------------------------------------------------
// function : sort3
Expand All @@ -48,57 +47,61 @@ using namespace tools ;
//-----------------------------------------------------------------------------
template <class value_t>
inline bool sort3 (value_t &R0, value_t &R1, value_t &R2,
bool &B0 ,bool &B1, bool &B2 )
bool &B0 ,bool &B1, bool &B2)
{ //----------------------------- begin-------------------------------
B0 = B1 = B2 = false ;
int value = 0 ;
if ( R0 < R1) value +=4 ;
if ( R1 < R2) value += 2;
if ( R0 < R2) value += 1 ;
B0 = B1 = B2 = false;
int value = 0;
if (R0 < R1) value += 4;
if (R1 < R2) value += 2;
if (R0 < R2) value += 1;

switch ( value )
{ case 0: break ;
case 2: std::swap ( R1 , R2);
B1 = B2 = true ;
break ;
case 3: if ( not ( R0 > R1))
{ std::swap ( R0 , R2);
B0 = B2 = true ;
switch (value)
{
case 0: break;
case 2: std::swap (R1 , R2);
B1 = B2 = true;
break;
case 3: if (!(R0 > R1))
{
std::swap (R0 , R2);
B0 = B2 = true;
}
else
{ auto Aux = std::move ( R2 );
R2 = std::move(R1 );
R1 = std::move ( R0 );
R0 = std::move ( Aux );
B0 = B1 = B2 = true ;
};
{
auto Aux = std::move (R2);
R2 = std::move(R1);
R1 = std::move (R0);
R0 = std::move (Aux);
B0 = B1 = B2 = true;
}
break;
case 4: std::swap (R0 , R1);
B0 = B1 = true;
break;
case 4: std::swap ( R0 , R1);
B0 = B1 = true ;
break ;

case 5: if ( R1 > R2)
{ auto Aux = std::move ( R0);
case 5: if (R1 > R2)
{
auto Aux = std::move (R0);
R0 = std::move(R1);
R1 = std::move( R2);
R2 = std::move ( Aux);
B0 = B1 = B2 = true ;
R1 = std::move(R2);
R2 = std::move (Aux);
B0 = B1 = B2 = true;
}
else
{ std::swap ( R0 , R2);
B0 = B2 = true ;
};
break ;
{
std::swap (R0 , R2);
B0 = B2 = true;
}
break;

case 7: std::swap ( R0 , R2);
B0 = B2 = true ;
break ;
case 7: std::swap (R0 , R2);
B0 = B2 = true;
break;
default: abort();

}

return ( B0 or B1 or B2);
};
return (B0 || B1 || B2);
}
//
//-----------------------------------------------------------------------------
// function : make_heap
Expand All @@ -109,22 +112,24 @@ inline bool sort3 (value_t &R0, value_t &R1, value_t &R2,
/// @remarks This algorithm is O(NLogN)
//-----------------------------------------------------------------------------
template < class iter_t,
class Compare = std::less < typename iterator_traits<iter_t>::value_type >
class Compare = std::less < typename std::iterator_traits<iter_t>::value_type >
>
void make_heap ( iter_t first , size_t N , Compare comp = Compare())
void make_heap (iter_t first , size_t N , Compare comp = Compare())
{ //-------------------- begin -----------------------------
size_t pos_father , pos_son ;
iter_t iter_father = first , iter_son = first ;
bool SW = false ;
size_t pos_father , pos_son;
iter_t iter_father = first , iter_son = first;
bool SW = false;

for ( size_t i = 1 ; i < N ; ++i)
{ pos_father = i ;
iter_father = first + i ;
SW = false ;
for (size_t i = 1; i < N; ++i)
{
pos_father = i;
iter_father = first + i;
SW = false;
do
{ iter_son = iter_father ;
pos_son = pos_father ;
pos_father = ( pos_son - 1 )>>1 ;
{
iter_son = iter_father;
pos_son = pos_father;
pos_father = (pos_son - 1)>>1;
iter_father = first + pos_father;
if ((SW = comp(*iter_father, *iter_son)))
std::iter_swap (iter_father, iter_son);
Expand All @@ -141,23 +146,23 @@ void make_heap ( iter_t first , size_t N , Compare comp = Compare())
/// @remarks This algorithm is O(NLogN)
//-----------------------------------------------------------------------------
template < class iter_t,
class Compare =std::less <typename iterator_traits<iter_t>::value_type>
class Compare =std::less <typename std::iterator_traits<iter_t>::value_type>
>
void heap_sort ( iter_t first , iter_t last , Compare comp= Compare() )
void heap_sort (iter_t first , iter_t last , Compare comp= Compare())
{ //--------------------------- begin -----------------------------
assert ( (last - first) >= 0 );
size_t N = last - first ;
if ( N < 2 ) return ;
assert ((last - first) >= 0);
size_t N = last - first;
if (N < 2) return;
//-----------------------------------------------------------------------
// Creating the initial heap
//-----------------------------------------------------------------------
make_heap ( first , N ,comp);
make_heap (first , N ,comp);

//-----------------------------------------------------------------------
// Sort the heap
//-----------------------------------------------------------------------
size_t pos_father , pos_son ;
iter_t iter_father = first , iter_son = first ;
size_t pos_father , pos_son;
iter_t iter_father = first , iter_son = first;

bool SW = false;
for (size_t i = 1; i < N; ++i)
Expand Down Expand Up @@ -200,24 +205,24 @@ void heap_sort ( iter_t first , iter_t last , Compare comp= Compare() )
/// @remarks This algorithm is O(NLogN)
//-----------------------------------------------------------------------------
template < class iter_t,
typename compare = std::less<typename iterator_traits<iter_t>::value_type>
typename compare = std::less<typename std::iterator_traits<iter_t>::value_type>
>
void indirect_heap_sort ( iter_t first, iter_t last ,
compare comp = compare() )
void indirect_heap_sort (iter_t first, iter_t last ,
compare comp = compare())
{ //------------------------------- begin--------------------------
typedef less_ptr_no_null <iter_t, compare> compare_ptr ;
typedef less_ptr_no_null <iter_t, compare> compare_ptr;

std::vector<iter_t> VP ;
create_index ( first , last , VP);
heap_sort ( VP.begin() , VP.end(), compare_ptr(comp) );
sort_index ( first , VP) ;
};
std::vector<iter_t> VP;
create_index (first , last , VP);
heap_sort (VP.begin() , VP.end(), compare_ptr(comp));
sort_index (first , VP);
}
//
//****************************************************************************
};// End namespace algorithm
};};// End HPX_INLINE_NAMESPACE(v2)
};// End namespace parallel
};// End namespace hpx
}// End namespace algorithm
}}// End HPX_INLINE_NAMESPACE(v2)
}// End namespace parallel
}// End namespace hpx
//****************************************************************************
//
#endif
37 changes: 19 additions & 18 deletions hpx/parallel/algorithms/sort/algorithm/indirect.hpp
View file
Expand Up @@ -21,12 +21,11 @@



namespace hpx {
namespace parallel {
HPX_INLINE_NAMESPACE(v2) { namespace boostsort {
namespace algorithm {
namespace hpx {
namespace parallel{
HPX_INLINE_NAMESPACE(v2) { namespace boostsort {
namespace algorithm {

using std::iterator_traits ;
//
//##########################################################################
// ##
Expand All @@ -42,7 +41,7 @@ using std::iterator_traits ;
//---------------------------------------------------------------------------
template < class iter_t ,
class comp_t
=std::less<typename iterator_traits<iter_t>::value_type> >
=std::less<typename std::iterator_traits<iter_t>::value_type> >
struct less_ptr_no_null
{ //----------------------------- Variables -----------------------
comp_t comp ;
Expand All @@ -51,7 +50,7 @@ struct less_ptr_no_null
inline bool operator ()( iter_t T1, iter_t T2 ) const
{ //-------------------- begin ------------------------------
return comp(*T1 ,*T2);
};
}
};
//
//-----------------------------------------------------------------------------
Expand All @@ -70,7 +69,7 @@ void create_index (iter_t first, iter_t last, std::vector<iter_t> &VP )
VP.clear() ;
VP.reserve ( N1);
for ( ; first != last ; ++first) VP.push_back( first);
};
}
//
//-----------------------------------------------------------------------------
// function : sort_index
Expand All @@ -81,12 +80,14 @@ void create_index (iter_t first, iter_t last, std::vector<iter_t> &VP )
//-----------------------------------------------------------------------------
template <class iter_t>
void sort_index (iter_t first, std::vector<iter_t> &VP )
{ //-------------------------- begin -------------------------------------
typedef typename iterator_traits<iter_t>::value_type value_t ;
{
//-------------------------- begin -------------------------------------
typedef typename std::iterator_traits<iter_t>::value_type value_t ;
size_t Ax = 0 , Bx =0 , Pos =0 , N = VP.size();
iter_t itA, itB ;
while ( Pos < N )
{ while ( Pos < N and (size_t (VP[Pos]-first)) == Pos ) ++Pos;
{
while ( Pos < N and (size_t (VP[Pos]-first)) == Pos ) ++Pos;
if ( Pos == N ) return ;
Ax = Bx = Pos ;
itA = first + Ax ;
Expand All @@ -97,18 +98,18 @@ void sort_index (iter_t first, std::vector<iter_t> &VP )
*itA = std::move ( *itB);
itA = itB ;
Ax = Bx ;
};
}
*itA = std::move ( Aux ) ;
VP[Ax] = itA ;
++Pos ;
};
};
}
}
//
//****************************************************************************
};// End namespace algorithm
};// End namespace parallel
};};// End HPX_INLINE_NAMESPACE(v2)
};// End namespace boost
}// End namespace algorithm
}// End namespace parallel
}}// End HPX_INLINE_NAMESPACE(v2)
}// End namespace boost
//****************************************************************************
//
#endif
40 changes: 21 additions & 19 deletions hpx/parallel/algorithms/sort/algorithm/insertion_sort.hpp
View file
Expand Up @@ -22,12 +22,10 @@
#include <utility> // std::swap


namespace hpx {
namespace parallel {
HPX_INLINE_NAMESPACE(v2) { namespace boostsort {
namespace algorithm {

using std::iterator_traits;
namespace hpx {
namespace parallel {
HPX_INLINE_NAMESPACE(v2) { namespace boostsort {
namespace algorithm {

//-----------------------------------------------------------------------------
// function : insertion_sort
Expand All @@ -39,31 +37,35 @@ using std::iterator_traits;
//-----------------------------------------------------------------------------
template < class iter_t,
typename compare
= std::less <typename iterator_traits<iter_t>::value_type >
= std::less <typename std::iterator_traits<iter_t>::value_type >
>
inline void insertion_sort (iter_t first, iter_t last, compare comp=compare())
{ //------------------------- begin ----------------------
typedef typename iterator_traits<iter_t>::value_type value_t ;
{
//------------------------- begin ----------------------
typedef typename std::iterator_traits<iter_t>::value_type value_t ;

if ( (last-first) < 2 ) return ;
for ( iter_t Alfa = first +1 ;Alfa != last ; ++Alfa)
{ value_t Aux = std::move ( *Alfa);
{
value_t Aux = std::move ( *Alfa);
iter_t Beta = Alfa ;

while( Beta != first and comp ( Aux, *(Beta-1) ) )
{ *Beta = std::move ( *(Beta-1));
while( Beta != first && comp ( Aux, *(Beta-1) ) )
{
*Beta = std::move ( *(Beta-1));
--Beta ;
};
}

*Beta = std::move ( Aux );
};
};
}
}

//
//****************************************************************************
};// End namespace algorithm
};// End namespace parallel
};};// End HPX_INLINE_NAMESPACE(v2)
};// End namespace boost
}// End namespace algorithm
}// End namespace parallel
}}// End HPX_INLINE_NAMESPACE(v2)
}// End namespace boost
//****************************************************************************
//
#endif

0 comments on commit 36ee856

Please sign in to comment.