use std :: cmp :: Ordering ; # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork2 ; impl SortingNetwork2 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork2 } } impl SortingNetworkTrait for SortingNetwork2 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 2usize , "Expected slice of length {}" , 2usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork1 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 1usize ] = [ ( 0u8 , 1u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork2 { # [ inline ] fn order ( ) -> usize { 1usize } } impl :: std :: fmt :: Debug for SortingNetwork2 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 1usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork4 ; impl SortingNetwork4 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork4 } } impl SortingNetworkTrait for SortingNetwork4 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 4usize , "Expected slice of length {}" , 4usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork2 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 2usize ] = [ ( 0u8 , 1u8 , 2u8 ) , ( 1u8 , 1u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork4 { # [ inline ] fn order ( ) -> usize { 2usize } } impl :: std :: fmt :: Debug for SortingNetwork4 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 2usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork8 ; impl SortingNetwork8 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork8 } } impl SortingNetworkTrait for SortingNetwork8 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 8usize , "Expected slice of length {}" , 8usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork4 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 3usize ] = [ ( 0u8 , 1u8 , 4u8 ) , ( 2u8 , 1u8 , 2u8 ) , ( 1u8 , 3u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork8 { # [ inline ] fn order ( ) -> usize { 3usize } } impl :: std :: fmt :: Debug for SortingNetwork8 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 3usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork16 ; impl SortingNetwork16 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork16 } } impl SortingNetworkTrait for SortingNetwork16 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 16usize , "Expected slice of length {}" , 16usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork8 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 4usize ] = [ ( 0u8 , 1u8 , 8u8 ) , ( 4u8 , 1u8 , 4u8 ) , ( 2u8 , 3u8 , 2u8 ) , ( 1u8 , 7u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork16 { # [ inline ] fn order ( ) -> usize { 4usize } } impl :: std :: fmt :: Debug for SortingNetwork16 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 4usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork32 ; impl SortingNetwork32 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork32 } } impl SortingNetworkTrait for SortingNetwork32 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 32usize , "Expected slice of length {}" , 32usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork16 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 5usize ] = [ ( 0u8 , 1u8 , 16u8 ) , ( 8u8 , 1u8 , 8u8 ) , ( 4u8 , 3u8 , 4u8 ) , ( 2u8 , 7u8 , 2u8 ) , ( 1u8 , 15u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork32 { # [ inline ] fn order ( ) -> usize { 5usize } } impl :: std :: fmt :: Debug for SortingNetwork32 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 5usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork64 ; impl SortingNetwork64 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork64 } } impl SortingNetworkTrait for SortingNetwork64 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 64usize , "Expected slice of length {}" , 64usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork32 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 6usize ] = [ ( 0u8 , 1u8 , 32u8 ) , ( 16u8 , 1u8 , 16u8 ) , ( 8u8 , 3u8 , 8u8 ) , ( 4u8 , 7u8 , 4u8 ) , ( 2u8 , 15u8 , 2u8 ) , ( 1u8 , 31u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork64 { # [ inline ] fn order ( ) -> usize { 6usize } } impl :: std :: fmt :: Debug for SortingNetwork64 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 6usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork128 ; impl SortingNetwork128 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork128 } } impl SortingNetworkTrait for SortingNetwork128 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 128usize , "Expected slice of length {}" , 128usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork64 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 7usize ] = [ ( 0u8 , 1u8 , 64u8 ) , ( 32u8 , 1u8 , 32u8 ) , ( 16u8 , 3u8 , 16u8 ) , ( 8u8 , 7u8 , 8u8 ) , ( 4u8 , 15u8 , 4u8 ) , ( 2u8 , 31u8 , 2u8 ) , ( 1u8 , 63u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork128 { # [ inline ] fn order ( ) -> usize { 7usize } } impl :: std :: fmt :: Debug for SortingNetwork128 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 7usize , f ) } } # [ doc = r" Optimized sorting network for slices of specific length." ] # [ derive ( Clone , Copy ) ] pub struct SortingNetwork256 ; impl SortingNetwork256 { # [ doc = r" Creates a sorting network for slices of specific length." ] # [ inline ] pub fn new ( ) -> Self { SortingNetwork256 } } impl SortingNetworkTrait for SortingNetwork256 { fn sort_by < T , F > ( & self , slice : & mut [ T ] , compare : F ) where F : Fn ( & T , & T ) -> Ordering { let len = slice . len ( ) ; assert ! ( len == 256usize , "Expected slice of length {}" , 256usize ) ; { let ( lhs , rhs ) = slice . split_at_mut ( len / 2 ) ; let sub_sort = SortingNetwork128 :: new ( ) ; sub_sort . sort_by ( lhs , & compare ) ; sub_sort . sort_by ( rhs , & compare ) ; } let patterns : [ ( u8 , u8 , u8 ) ; 8usize ] = [ ( 0u8 , 1u8 , 128u8 ) , ( 64u8 , 1u8 , 64u8 ) , ( 32u8 , 3u8 , 32u8 ) , ( 16u8 , 7u8 , 16u8 ) , ( 8u8 , 15u8 , 8u8 ) , ( 4u8 , 31u8 , 4u8 ) , ( 2u8 , 63u8 , 2u8 ) , ( 1u8 , 127u8 , 1u8 ) ] ; for ( start , count , length ) in patterns . iter ( ) . cloned ( ) { let ( start , count , length ) = ( start as usize , count as usize , length as usize ) ; let gap = 2 * length ; for i in 0 .. ( count as usize ) { let offset = i * gap ; for j in 0 .. ( length as usize ) { let min = start + offset + j ; let max = min + length ; unsafe { swap_unchecked ( slice , min , max , & compare ) ; } } } println ! ( ) ; } } } impl FixedSizeSortingNetwork for SortingNetwork256 { # [ inline ] fn order ( ) -> usize { 8usize } } impl :: std :: fmt :: Debug for SortingNetwork256 { fn fmt ( & self , f : & mut :: std :: fmt :: Formatter ) -> :: std :: fmt :: Result { debug :: debug_fmt ( 8usize , f ) } } # [ cfg ( test ) ] mod sorting_network { use std :: prelude :: v1 :: * ; use super :: * ; fn shuffled ( length : usize ) -> Vec < usize > { let prime = 313373 ; let sorted : Vec < _ > = ( 0 .. length ) . collect ( ) ; ( 0 .. length ) . map ( | i | sorted [ ( i * prime ) % length ] ) . collect ( ) } mod length_2 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 2usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork2 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 2usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_4 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 4usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork4 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 4usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_8 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 8usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork8 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 8usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_16 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 16usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork16 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 16usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_32 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 32usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork32 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 32usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_64 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 64usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork64 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 64usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_128 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 128usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork128 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 128usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } mod length_256 { use super :: * ; # [ test ] fn fixed_size ( ) { let mut items = shuffled ( 256usize ) ; println ! ( "\ninput: {:?}\n" , items ) ; let sorter = SortingNetwork256 :: new ( ) ; sorter . sort ( & mut items [ .. ] ) ; let expected : Vec < _ > = ( 0 .. 256usize ) . collect ( ) ; assert_eq ! ( items , expected ) ; } } }