java - 插入排序的数据结构，可以获得子集的长度

Question

我正在寻找 Java 中按插入排序的数据结构，它可以快速查找和删除特定元素并计算在该元素之后添加的元素数。

LinkedHashSet 理论上满足此要求，但接口(interface)没有提供任何方法，例如创建从指定元素开始的 Iterator。我总是不得不遍历整个集合。

感谢任何建议。

编辑: 好吧，我对(不是真的)LinkedHashSet 的简单实现完全是我目前唯一的用例如下，以防万一有人感兴趣。这可以更改为包括实际迭代元素的可能性，而不仅仅是能够计算元素的数量。可能也需要一些重构......

public class DoublyLinkedHashSet<T> {
private final Map<T, Entry> map;
private Entry youngestEntry;

public DoublyLinkedHashSet() {
    this.map = new HashMap<T, Entry>();
}

public int size() {
    return map.size();
}

public boolean contains(final T element) {
    return map.containsKey(element);
}

public void add(final T element) {
    final Entry newEntry = new Entry();
    final Entry entryForElement = map.put(element, newEntry);
    boolean entryWasNotAlreadyInSet = entryForElement == null;
    if (entryWasNotAlreadyInSet) {
        newEntry.previousEntry = youngestEntry;
        if (youngestEntry != null) {
            youngestEntry.hasNext = true;
            youngestEntry.nextEntry = newEntry;
        }
    }
    youngestEntry = newEntry;
}

public void remove(final T element) {
    removeEntry(element);
}

public int removeAndGetAmountOfEntriesAfter(final T element) {
    Entry startEntry = removeEntry(element);

    if (startEntry == null) {
        return 0;
    }

    return countAllNextEntries(startEntry);
}

private int countAllNextEntries(final Entry startEntry) {
    int amount = 0;
    Entry currentEntry = startEntry;
    while (currentEntry.hasNext) {
        amount++;
        currentEntry = currentEntry.nextEntry;
    }
    return amount;
}

private Entry removeEntry(final T element) {
    final Entry removedEntry = map.remove(element);

    if (removedEntry == null) {
        return null;
    }

    if (hasPreviousAndNextEntry(removedEntry)) {
        final Entry previousEntry = removedEntry.previousEntry;
        final Entry nextEntry = removedEntry.previousEntry;
        connect(previousEntry, nextEntry);
    } else if (isEndOfList(removedEntry)) {
        final Entry previousEntry = removedEntry.previousEntry;
        resetEndTo(previousEntry);
    } else if (isHead(removedEntry)) {
        final Entry nextEntry = removedEntry.nextEntry;
        resetHeadTo(nextEntry);
    }

    return removedEntry;
}

private boolean hasPreviousAndNextEntry(final Entry entry) {
    return entry.hasPrevious && entry.hasNext;
}

private void connect(final Entry previousEntry, final Entry nextEntry) {
    previousEntry.nextEntry = nextEntry;
}

private boolean isHead(final Entry entry) {
    return !entry.hasPrevious && entry.hasNext;
}

private void resetHeadTo(final Entry entry) {
    entry.previousEntry = null;
    entry.hasPrevious = false;
}

private boolean isEndOfList(final Entry removedEntry) {
    return removedEntry.hasPrevious && !removedEntry.hasNext;
}

private void resetEndTo(final Entry entry) {
    entry.nextEntry = null;
    entry.hasNext = false;
    youngestEntry = entry;
}

private static final class Entry {
    private boolean hasNext;
    private boolean hasPrevious;
    private Entry nextEntry;
    private Entry previousEntry;
}
}

Answer 1

您应该能够使用 SortedSet .它提供了一个 tailSet应该做你需要的方法。

您可以通过向对象添加序列号并按其排序来按插入顺序对它们进行排序。