SuffixArray.java

net.minecraft.client.searchtree.SuffixArray

信息

• 全限定名：net.minecraft.client.searchtree.SuffixArray
• 类型：public class
• 包：net.minecraft.client.searchtree
• 源码路径：src/main/java/net/minecraft/client/searchtree/SuffixArray.java
• 起始行号：L21
• 职责：

  TODO

字段/常量

• DEBUG_COMPARISONS

  • 类型: boolean
  • 修饰符: private static final
  • 源码定位: L22
  • 说明:

    TODO

• DEBUG_ARRAY

  • 类型: boolean
  • 修饰符: private static final
  • 源码定位: L23
  • 说明:

    TODO

• LOGGER

  • 类型: Logger
  • 修饰符: private static final
  • 源码定位: L24
  • 说明:

    TODO

• END_OF_TEXT_MARKER

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L25
  • 说明:

    TODO

• END_OF_DATA

  • 类型: int
  • 修饰符: private static final
  • 源码定位: L26
  • 说明:

    TODO

• list

  • 类型: List<T>
  • 修饰符: protected final
  • 源码定位: L27
  • 说明:

    TODO

• chars

  • 类型: IntList
  • 修饰符: private final
  • 源码定位: L28
  • 说明:

    TODO

• wordStarts

  • 类型: IntList
  • 修饰符: private final
  • 源码定位: L29
  • 说明:

    TODO

• suffixToT

  • 类型: IntList
  • 修饰符: private
  • 源码定位: L30
  • 说明:

    TODO

• offsets

  • 类型: IntList
  • 修饰符: private
  • 源码定位: L31
  • 说明:

    TODO

• maxStringLength

  • 类型: int
  • 修饰符: private
  • 源码定位: L32
  • 说明:

    TODO

内部类/嵌套类型

• 无

构造器

• 无

方法

下面的方法块按源码顺序生成。

public void add(T t, String text) @ L34

• 方法名：add
• 源码定位：L34
• 返回类型：void
• 修饰符：public

参数:

• t: T
• text: String

说明:

TODO

public void generate() @ L51

• 方法名：generate
• 源码定位：L51
• 返回类型：void
• 修饰符：public

参数:

• 无

说明:

TODO

private void print() @ L111

• 方法名：print
• 源码定位：L111
• 返回类型：void
• 修饰符：private

参数:

• 无

说明:

TODO

private String getString(int i) @ L119

• 方法名：getString
• 源码定位：L119
• 返回类型：String
• 修饰符：private

参数:

• i: int

说明:

TODO

private int compare(String text, int index) @ L140

• 方法名：compare
• 源码定位：L140
• 返回类型：int
• 修饰符：private

参数:

• text: String
• index: int

说明:

TODO

public List<T> search(String text) @ L164

• 方法名：search
• 源码定位：L164
• 返回类型：List
• 修饰符：public

参数:

• text: String

说明:

TODO

代码

@OnlyIn(Dist.CLIENT)
public class SuffixArray<T> {
    private static final boolean DEBUG_COMPARISONS = Boolean.parseBoolean(System.getProperty("SuffixArray.printComparisons", "false"));
    private static final boolean DEBUG_ARRAY = Boolean.parseBoolean(System.getProperty("SuffixArray.printArray", "false"));
    private static final Logger LOGGER = LogUtils.getLogger();
    private static final int END_OF_TEXT_MARKER = -1;
    private static final int END_OF_DATA = -2;
    protected final List<T> list = Lists.newArrayList();
    private final IntList chars = new IntArrayList();
    private final IntList wordStarts = new IntArrayList();
    private IntList suffixToT = new IntArrayList();
    private IntList offsets = new IntArrayList();
    private int maxStringLength;
 
    public void add(T t, String text) {
        this.maxStringLength = Math.max(this.maxStringLength, text.length());
        int index = this.list.size();
        this.list.add(t);
        this.wordStarts.add(this.chars.size());
 
        for (int i = 0; i < text.length(); i++) {
            this.suffixToT.add(index);
            this.offsets.add(i);
            this.chars.add(text.charAt(i));
        }
 
        this.suffixToT.add(index);
        this.offsets.add(text.length());
        this.chars.add(-1);
    }
 
    public void generate() {
        int charCount = this.chars.size();
        int[] positions = new int[charCount];
        int[] lefts = new int[charCount];
        int[] rights = new int[charCount];
        int[] reverse = new int[charCount];
        IntComparator comparator = (a, b) -> lefts[a] == lefts[b] ? Integer.compare(rights[a], rights[b]) : Integer.compare(lefts[a], lefts[b]);
        Swapper swapper = (a, b) -> {
            if (a != b) {
                int tmp = lefts[a];
                lefts[a] = lefts[b];
                lefts[b] = tmp;
                tmp = rights[a];
                rights[a] = rights[b];
                rights[b] = tmp;
                tmp = reverse[a];
                reverse[a] = reverse[b];
                reverse[b] = tmp;
            }
        };
 
        for (int i = 0; i < charCount; i++) {
            positions[i] = this.chars.getInt(i);
        }
 
        int count = 1;
 
        for (int max = Math.min(charCount, this.maxStringLength); count * 2 < max; count *= 2) {
            for (int i = 0; i < charCount; reverse[i] = i++) {
                lefts[i] = positions[i];
                rights[i] = i + count < charCount ? positions[i + count] : -2;
            }
 
            Arrays.quickSort(0, charCount, comparator, swapper);
 
            for (int i = 0; i < charCount; i++) {
                if (i > 0 && lefts[i] == lefts[i - 1] && rights[i] == rights[i - 1]) {
                    positions[reverse[i]] = positions[reverse[i - 1]];
                } else {
                    positions[reverse[i]] = i;
                }
            }
        }
 
        IntList oldSuffixToT = this.suffixToT;
        IntList oldOffsets = this.offsets;
        this.suffixToT = new IntArrayList(oldSuffixToT.size());
        this.offsets = new IntArrayList(oldOffsets.size());
 
        for (int ix = 0; ix < charCount; ix++) {
            int index = reverse[ix];
            this.suffixToT.add(oldSuffixToT.getInt(index));
            this.offsets.add(oldOffsets.getInt(index));
        }
 
        if (DEBUG_ARRAY) {
            this.print();
        }
    }
 
    private void print() {
        for (int i = 0; i < this.suffixToT.size(); i++) {
            LOGGER.debug("{} {}", i, this.getString(i));
        }
 
        LOGGER.debug("");
    }
 
    private String getString(int i) {
        int start = this.offsets.getInt(i);
        int offset = this.wordStarts.getInt(this.suffixToT.getInt(i));
        StringBuilder builder = new StringBuilder();
 
        for (int j = 0; offset + j < this.chars.size(); j++) {
            if (j == start) {
                builder.append('^');
            }
 
            int p = this.chars.getInt(offset + j);
            if (p == -1) {
                break;
            }
 
            builder.append((char)p);
        }
 
        return builder.toString();
    }
 
    private int compare(String text, int index) {
        int start = this.wordStarts.getInt(this.suffixToT.getInt(index));
        int offset = this.offsets.getInt(index);
 
        for (int i = 0; i < text.length(); i++) {
            int p = this.chars.getInt(start + offset + i);
            if (p == -1) {
                return 1;
            }
 
            char c = text.charAt(i);
            char c2 = (char)p;
            if (c < c2) {
                return -1;
            }
 
            if (c > c2) {
                return 1;
            }
        }
 
        return 0;
    }
 
    public List<T> search(String text) {
        int suffixCount = this.suffixToT.size();
        int low = 0;
        int high = suffixCount;
 
        while (low < high) {
            int mid = low + (high - low) / 2;
            int c = this.compare(text, mid);
            if (DEBUG_COMPARISONS) {
                LOGGER.debug("comparing lower \"{}\" with {} \"{}\": {}", text, mid, this.getString(mid), c);
            }
 
            if (c > 0) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
 
        if (low >= 0 && low < suffixCount) {
            int lowerBound = low;
            high = suffixCount;
 
            while (low < high) {
                int midx = low + (high - low) / 2;
                int cx = this.compare(text, midx);
                if (DEBUG_COMPARISONS) {
                    LOGGER.debug("comparing upper \"{}\" with {} \"{}\": {}", text, midx, this.getString(midx), cx);
                }
 
                if (cx >= 0) {
                    low = midx + 1;
                } else {
                    high = midx;
                }
            }
 
            int upperBound = low;
            IntSet matches = new IntOpenHashSet();
 
            for (int i = lowerBound; i < upperBound; i++) {
                matches.add(this.suffixToT.getInt(i));
            }
 
            int[] ints = matches.toIntArray();
            java.util.Arrays.sort(ints);
            Set<T> result = Sets.newLinkedHashSet();
 
            for (int t : ints) {
                result.add(this.list.get(t));
            }
 
            return Lists.newArrayList(result);
        } else {
            return Collections.emptyList();
        }
    }
}

引用的其他类

• LoggedChatMessage
  • 引用位置: 方法调用
  • 关联成员: System.getProperty()