Class Bzip2DivSufSort


  • final class Bzip2DivSufSort
    extends java.lang.Object
    DivSufSort suffix array generator.
    Based on libdivsufsort 1.2.3 patched to support Bzip2.
    This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX" comments within the class). Documentation within the class is largely absent.
    • Constructor Summary

      Constructors 
      Constructor Description
      Bzip2DivSufSort​(byte[] block, int[] bwtBlock, int blockLength)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private static int BUCKET_B​(int c0, int c1)  
      private static int BUCKET_BSTAR​(int c0, int c1)  
      int bwt()
      Performs a Burrows Wheeler Transform on the input array.
      private int constructBWT​(int[] bucketA, int[] bucketB)  
      private static int getIDX​(int a)  
      private void lsIntroSort​(int isa, int isaD, int isaN, int first, int last)  
      private void lsSort​(int isa, int n, int depth)  
      private void lsUpdateGroup​(int isa, int first, int last)  
      private int sortTypeBstar​(int[] bucketA, int[] bucketB)  
      private static void ssBlockSwap​(int[] array1, int first1, int[] array2, int first2, int size)  
      private int ssCompare​(int p1, int p2, int depth)  
      private int ssCompareLast​(int pa, int p1, int p2, int depth, int size)  
      private void ssFixdown​(int td, int pa, int sa, int i, int size)  
      private void ssHeapSort​(int td, int pa, int sa, int size)  
      private void ssInsertionSort​(int pa, int first, int last, int depth)  
      private static int ssLog​(int n)  
      private int ssMedian3​(int td, int pa, int v1, int v2, int v3)  
      private int ssMedian5​(int td, int pa, int v1, int v2, int v3, int v4, int v5)  
      private void ssMerge​(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth)  
      private void ssMergeBackward​(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)  
      private void ssMergeCheckEqual​(int pa, int depth, int a)  
      private void ssMergeForward​(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)  
      private void ssMultiKeyIntroSort​(int pa, int first, int last, int depth)  
      private int ssPivot​(int td, int pa, int first, int last)  
      private int ssSubstringPartition​(int pa, int first, int last, int depth)  
      private void subStringSort​(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size)  
      private static void swapElements​(int[] array1, int idx1, int[] array2, int idx2)  
      private void trCopy​(int isa, int isaN, int first, int a, int b, int last, int depth)  
      private void trFixdown​(int isa, int isaD, int isaN, int sa, int i, int size)  
      private int trGetC​(int isa, int isaD, int isaN, int p)  
      private void trHeapSort​(int isa, int isaD, int isaN, int sa, int size)  
      private void trInsertionSort​(int isa, int isaD, int isaN, int first, int last)  
      private void trIntroSort​(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size)  
      private static int trLog​(int n)  
      private int trMedian3​(int isa, int isaD, int isaN, int v1, int v2, int v3)  
      private int trMedian5​(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5)  
      private Bzip2DivSufSort.PartitionResult trPartition​(int isa, int isaD, int isaN, int first, int last, int v)  
      private int trPivot​(int isa, int isaD, int isaN, int first, int last)  
      private void trSort​(int isa, int n, int depth)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • INSERTIONSORT_THRESHOLD

        private static final int INSERTIONSORT_THRESHOLD
        See Also:
        Constant Field Values
      • LOG_2_TABLE

        private static final int[] LOG_2_TABLE
      • SA

        private final int[] SA
      • T

        private final byte[] T
      • n

        private final int n
    • Constructor Detail

      • Bzip2DivSufSort

        Bzip2DivSufSort​(byte[] block,
                        int[] bwtBlock,
                        int blockLength)
        Parameters:
        block - The input array
        bwtBlock - The output array
        blockLength - The length of the input data
    • Method Detail

      • swapElements

        private static void swapElements​(int[] array1,
                                         int idx1,
                                         int[] array2,
                                         int idx2)
      • ssCompare

        private int ssCompare​(int p1,
                              int p2,
                              int depth)
      • ssCompareLast

        private int ssCompareLast​(int pa,
                                  int p1,
                                  int p2,
                                  int depth,
                                  int size)
      • ssInsertionSort

        private void ssInsertionSort​(int pa,
                                     int first,
                                     int last,
                                     int depth)
      • ssFixdown

        private void ssFixdown​(int td,
                               int pa,
                               int sa,
                               int i,
                               int size)
      • ssHeapSort

        private void ssHeapSort​(int td,
                                int pa,
                                int sa,
                                int size)
      • ssMedian3

        private int ssMedian3​(int td,
                              int pa,
                              int v1,
                              int v2,
                              int v3)
      • ssMedian5

        private int ssMedian5​(int td,
                              int pa,
                              int v1,
                              int v2,
                              int v3,
                              int v4,
                              int v5)
      • ssPivot

        private int ssPivot​(int td,
                            int pa,
                            int first,
                            int last)
      • ssLog

        private static int ssLog​(int n)
      • ssSubstringPartition

        private int ssSubstringPartition​(int pa,
                                         int first,
                                         int last,
                                         int depth)
      • ssMultiKeyIntroSort

        private void ssMultiKeyIntroSort​(int pa,
                                         int first,
                                         int last,
                                         int depth)
      • ssBlockSwap

        private static void ssBlockSwap​(int[] array1,
                                        int first1,
                                        int[] array2,
                                        int first2,
                                        int size)
      • ssMergeForward

        private void ssMergeForward​(int pa,
                                    int[] buf,
                                    int bufoffset,
                                    int first,
                                    int middle,
                                    int last,
                                    int depth)
      • ssMergeBackward

        private void ssMergeBackward​(int pa,
                                     int[] buf,
                                     int bufoffset,
                                     int first,
                                     int middle,
                                     int last,
                                     int depth)
      • getIDX

        private static int getIDX​(int a)
      • ssMergeCheckEqual

        private void ssMergeCheckEqual​(int pa,
                                       int depth,
                                       int a)
      • ssMerge

        private void ssMerge​(int pa,
                             int first,
                             int middle,
                             int last,
                             int[] buf,
                             int bufoffset,
                             int bufsize,
                             int depth)
      • subStringSort

        private void subStringSort​(int pa,
                                   int first,
                                   int last,
                                   int[] buf,
                                   int bufoffset,
                                   int bufsize,
                                   int depth,
                                   boolean lastsuffix,
                                   int size)
      • trGetC

        private int trGetC​(int isa,
                           int isaD,
                           int isaN,
                           int p)
      • trFixdown

        private void trFixdown​(int isa,
                               int isaD,
                               int isaN,
                               int sa,
                               int i,
                               int size)
      • trHeapSort

        private void trHeapSort​(int isa,
                                int isaD,
                                int isaN,
                                int sa,
                                int size)
      • trInsertionSort

        private void trInsertionSort​(int isa,
                                     int isaD,
                                     int isaN,
                                     int first,
                                     int last)
      • trLog

        private static int trLog​(int n)
      • trMedian3

        private int trMedian3​(int isa,
                              int isaD,
                              int isaN,
                              int v1,
                              int v2,
                              int v3)
      • trMedian5

        private int trMedian5​(int isa,
                              int isaD,
                              int isaN,
                              int v1,
                              int v2,
                              int v3,
                              int v4,
                              int v5)
      • trPivot

        private int trPivot​(int isa,
                            int isaD,
                            int isaN,
                            int first,
                            int last)
      • lsUpdateGroup

        private void lsUpdateGroup​(int isa,
                                   int first,
                                   int last)
      • lsIntroSort

        private void lsIntroSort​(int isa,
                                 int isaD,
                                 int isaN,
                                 int first,
                                 int last)
      • lsSort

        private void lsSort​(int isa,
                            int n,
                            int depth)
      • trCopy

        private void trCopy​(int isa,
                            int isaN,
                            int first,
                            int a,
                            int b,
                            int last,
                            int depth)
      • trIntroSort

        private void trIntroSort​(int isa,
                                 int isaD,
                                 int isaN,
                                 int first,
                                 int last,
                                 Bzip2DivSufSort.TRBudget budget,
                                 int size)
      • trSort

        private void trSort​(int isa,
                            int n,
                            int depth)
      • BUCKET_B

        private static int BUCKET_B​(int c0,
                                    int c1)
      • BUCKET_BSTAR

        private static int BUCKET_BSTAR​(int c0,
                                        int c1)
      • sortTypeBstar

        private int sortTypeBstar​(int[] bucketA,
                                  int[] bucketB)
      • constructBWT

        private int constructBWT​(int[] bucketA,
                                 int[] bucketB)
      • bwt

        public int bwt()
        Performs a Burrows Wheeler Transform on the input array.
        Returns:
        the index of the first character of the input array within the output array