Package com.marksayson.deletionchecker.format

Class PrefixIndex

java.lang.Object
com.marksayson.deletionchecker.format.PrefixIndex
public final class PrefixIndex extends Object
Adaptive, equal-count bucket index over a sorted identifier list.

The sorted identifiers are sliced into buckets of a target size K; each bucket records its first entry index and its first identifier as a separator. A lookup first finds the candidate bucket with a floor search over the small, cache-resident separator array, then binary searches only that bucket's entry range. All comparisons are unsigned byte-wise (UnsignedBytes), matching the order the dataset is sorted in.

The index is built in the exact shape it is serialized: a startIndex table and a separatorOffset table of bucketCount + 1 entries each, plus one contiguous separatorData block. An empty identifier list yields a single bucket with an empty separator, so build, serialization, and search stay uniform — the zero-identifier short-circuit is then only an optimization, not a correctness requirement.

Callers must pass identifiers already sorted by unsigned bytes and deduplicated; this class does not verify either.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEFAULT_BUCKET_SIZE
    The generator's launch default for the bucket target size K.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    bucketCount()
    Returns the number of buckets, always at least 1.
    int
    bucketEnd(int bucket)
    Returns the entry index just past the last entry of the given bucket.
    int
    bucketStart(int bucket)
    Returns the first entry index of the given bucket.
    static PrefixIndex
    build(List<byte[]> sortedIdentifiers)
    Builds an index over sortedIdentifiers using DEFAULT_BUCKET_SIZE.
    static PrefixIndex
    build(List<byte[]> sortedIdentifiers, int bucketSize)
    Builds an index over sortedIdentifiers with the given bucket target size.
    int
    identifierCount()
    Returns the number of identifiers indexed.
    int
    selectBucket(byte[] query)
    Selects the candidate bucket for query: the greatest bucket index whose separator is <= query by unsigned byte order, or 0 when query precedes every separator.
    byte[]
    separatorData()
    Returns a copy of the contiguous separatorData block: every bucket's separator bytes stored back to back in bucket order.
    int[]
    separatorOffset()
    Returns a copy of the separatorOffset table: bucketCount + 1 byte offsets into separatorData(), one per separator plus a trailing total length.
    int[]
    startIndex()
    Returns a copy of the startIndex table: bucketCount + 1 entries, the last equal to identifierCount().

    Methods inherited from class java.lang.Object

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

  • Field Details

    • DEFAULT_BUCKET_SIZE

      public static final int DEFAULT_BUCKET_SIZE
      The generator's launch default for the bucket target size K. The runtime reads the actual K of a dataset from its file header, never from this constant.
      See Also:

  • Method Details

    • build

      public static PrefixIndex build(List<byte[]> sortedIdentifiers)
      Builds an index over sortedIdentifiers using DEFAULT_BUCKET_SIZE.
      Parameters:
      sortedIdentifiers - the identifiers, already sorted by unsigned bytes and deduplicated
      Returns:
      the index

    • build

      public static PrefixIndex build(List<byte[]> sortedIdentifiers, int bucketSize)
      Builds an index over sortedIdentifiers with the given bucket target size.
      Parameters:
      sortedIdentifiers - the identifiers, already sorted by unsigned bytes and deduplicated
      bucketSize - the target number of entries per bucket (K); must be at least 1
      Returns:
      the index
      Throws:
      IllegalArgumentException - if bucketSize is less than 1

    • identifierCount

      public int identifierCount()
      Returns the number of identifiers indexed.
      Returns:
      the identifier count

    • bucketCount

      public int bucketCount()
      Returns the number of buckets, always at least 1.
      Returns:
      the bucket count

    • selectBucket

      public int selectBucket(byte[] query)
      Selects the candidate bucket for query: the greatest bucket index whose separator is <= query by unsigned byte order, or 0 when query precedes every separator. This is a floor search, not an exact match.
      Parameters:
      query - the lookup key, UTF-8 encoded
      Returns:
      a bucket index in [0, bucketCount)

    • bucketStart

      public int bucketStart(int bucket)
      Returns the first entry index of the given bucket.
      Parameters:
      bucket - a bucket index in [0, bucketCount)
      Returns:
      the entry index where bucket begins

    • bucketEnd

      public int bucketEnd(int bucket)
      Returns the entry index just past the last entry of the given bucket.
      Parameters:
      bucket - a bucket index in [0, bucketCount)
      Returns:
      the entry index where bucket ends, exclusive

    • startIndex

      public int[] startIndex()
      Returns a copy of the startIndex table: bucketCount + 1 entries, the last equal to identifierCount().
      Returns:
      the start-index table

    • separatorOffset

      public int[] separatorOffset()
      Returns a copy of the separatorOffset table: bucketCount + 1 byte offsets into separatorData(), one per separator plus a trailing total length.
      Returns:
      the separator-offset table

    • separatorData

      public byte[] separatorData()
      Returns a copy of the contiguous separatorData block: every bucket's separator bytes stored back to back in bucket order.
      Returns:
      the separator-data block