org.apache.lucene.util

## Class MSBRadixSorter

- java.lang.Object
- - org.apache.lucene.util.Sorter
  - - org.apache.lucene.util.MSBRadixSorter

- Direct Known Subclasses:
    StableMSBRadixSorter

      public abstract class MSBRadixSorter
      extends Sorter

  Radix sorter for variable-length strings. This class sorts based on the most significant byte first and falls back to `IntroSorter` when the size of the buckets to sort becomes small. It is NOT stable. Worst-case memory usage is about `2.3 KB`.
  NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected static int` | `HISTOGRAM_SIZE`
    `protected int` | `maxLength`

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `protected` | `MSBRadixSorter(int maxLength)` Sole constructor.

  - ### Method Summary

    All Methods Instance Methods Abstract Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected abstract int` | `byteAt(int i, int k)` Return the k-th byte of the entry at index `i`, or `-1` if its length is less than or equal to `k`.
    `protected int` | `compare(int i, int j)` Compare entries found in slots `i` and `j`.
    `protected int` | `getBucket(int i, int k)` Return a number for the k-th character between 0 and `HISTOGRAM_SIZE`.
    `protected Sorter` | `getFallbackSorter(int k)` Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal.
    `protected void` | `reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k)` Reorder based on start/end offsets for each bucket.
    `void` | `sort(int from, int to)` Sort the slice which starts at `from` (inclusive) and ends at `to` (exclusive).
    `protected void` | `sort(int from, int to, int k, int l)`

    - ### Methods inherited from class org.apache.lucene.util.Sorter

      `comparePivot, setPivot, swap`

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### HISTOGRAM_SIZE

          protected static final int HISTOGRAM_SIZE

      See Also:
        Constant Field Values

    - #### maxLength

          protected final int maxLength

  - ### Constructor Detail

    - #### MSBRadixSorter

          protected MSBRadixSorter(int maxLength)

      Sole constructor.
      Parameters:
        `maxLength` - the maximum length of keys, pass `Integer.MAX_VALUE` if unknown.

  - ### Method Detail

    - #### byteAt

          protected abstract int byteAt(int i,
                                        int k)

      Return the k-th byte of the entry at index `i`, or `-1` if its length is less than or equal to `k`. This may only be called with a value of `i` between `0` included and `maxLength` excluded.

    - #### getFallbackSorter

          protected Sorter getFallbackSorter(int k)

      Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal.

    - #### compare

          protected final int compare(int i,
                                      int j)

      Description copied from class: `Sorter`
      Compare entries found in slots `i` and `j`. The contract for the returned value is the same as `Comparator.compare(Object, Object)`.
      Specified by:
        `compare` in class `Sorter`

    - #### sort

          public void sort(int from,
                           int to)

      Description copied from class: `Sorter`
      Sort the slice which starts at `from` (inclusive) and ends at `to` (exclusive).
      Specified by:
        `sort` in class `Sorter`

    - #### sort

          protected void sort(int from,
                              int to,
                              int k,
                              int l)

    - #### getBucket

          protected int getBucket(int i,
                                  int k)

      Return a number for the k-th character between 0 and `HISTOGRAM_SIZE`.

    - #### reorder

          protected void reorder(int from,
                                 int to,
                                 int[] startOffsets,
                                 int[] endOffsets,
                                 int k)

      Reorder based on start/end offsets for each bucket. When this method returns, startOffsets and endOffsets are equal.
      Parameters:
        `startOffsets` - start offsets per bucket
        `endOffsets` - end offsets per bucket

Copyright © 2000-2021 Apache Software Foundation. All Rights Reserved.