/usr/include/blasr/algorithms/sorting/MultikeyQuicksort.hpp is in libblasr-dev 0~20151014+gitbe5d1bf-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #ifndef _BLASR_MULTIKEY_QUICKSORT_HPP_
#define _BLASR_MULTIKEY_QUICKSORT_HPP_
/*
* This is an implementation of MultiKey Quicksort, or ssort1 from
* Bentley and Sedgewick, Fast Algorithms for Sorting and Searching
* Strings, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms
* (SODA), pages 360-369, January 1997.
*
* The implementation here sorts lists of indices into an array of
* substrings rather than the substrings themselves (for use in suffix
* array generation). Furthermore, it is made to be sse-alizeable to
* speed up sorts on modern architectures.
*/
#include <limits.h>
#include <vector>
#include <algorithm>
#include "NucConversion.hpp"
#include "FASTASequence.hpp"
#include "Types.h"
typedef unsigned int UInt;
void UIntSwap(unsigned int &a, unsigned int &b);
void VecSwap( UInt i, UInt j, UInt n, UInt index[]);
unsigned char ComputeMedianValue(unsigned char text[], UInt index[], int length,
UInt low, UInt high, int offset, UInt maxPossible, UInt *freq );
UInt FindFirstOf(unsigned char text[], UInt index[], UInt length,
UInt low, UInt high, int offset, Nucleotide nuc);
void SwapIndices(UInt &a, UInt &b);
void TransformSequenceForSorting(unsigned char text[], UInt textLength, int bound);
void TransformBackSequence(Nucleotide text[], UInt textLength);
/*
* depth: the current depth of how much is sorted.
* bound: how far to sort.
*/
void MediankeyBoundedQuicksort(unsigned char text[], UInt index[], UInt length,
UInt low, UInt high, int depth, int bound, UInt maxChar= 0, UInt *freq=NULL);
#endif // _BLASR_MULTIKEY_QUICKSORT_HPP_
|