Как я могу вызвать binarySearch () в моем классе Entry?

Question

Я делаю указатель книги, где у меня есть внутренний класс Entry, который содержит String (само слово) и Integer TreeSet для хранения всех номеров строк, на которых появляется слово.

У меня есть класс ListIndex (который содержит класс Entry), в котором я создаю ArrayList типа Entry. Когда я добавляю слово в список, мне нужно проверить, есть ли оно уже в списке, с помощью binarySearch (). Однако я не могу использовать Collections.binarySearch (myList, word), потому что ArrayList имеет тип Entry.

Мой класс Entry реализует Comparable, но я все еще не понимаю, как я могу это исправить. Любая помощь будет оценена по достоинству!

Answer 1

Вы должны реализовать интерфейс Comparable в Entry вот так

static class Entry implements Comparable {

        String text;
        TreeSet<Integer> set;

        public Entry(String text, TreeSet<Integer> set) {
            this.text = text;
            this.set = set;
        }

        @Override
        public String toString() {
            return text;
        }

        @Override
        public int compareTo(Object obj) {
            if (obj instanceof String)
                return text.compareTo((String) obj);
            else {
                Entry otherEntry = (Entry) obj;
                return text.compareTo(otherEntry.text);
            }
        }
    }

    public static void main(String[] args) {
        List<Entry> entries = new ArrayList<>();
        entries.add(new Entry("bbbb", new TreeSet<>()));
        entries.add(new Entry("aaaa", new TreeSet<>()));
        entries.add(new Entry("cccc", new TreeSet<>()));
        entries.add(new Entry("hhhh", new TreeSet<>()));
        entries.add(new Entry("dddd", new TreeSet<>()));

        Collections.sort(entries);
        int index = Collections.binarySearch(entries, "cccc", (e1, e2) -> e1.compareTo(e2));
        System.out.println(index);
    }

, output

2

Answer 2

Использовать фиктивный Entry объект в качестве критерия

Предполагая, что ваша реализация Entry для метода compareTo, требуемого интерфейсом Comparable, просто подчиняется содержащемуся в нем String методу compareTo объекта и игнорирует состояние TreeSet номеров строк…

Просто создайте фиктивный объект Entry с вашей целевой строкой. Используйте этот объект Entry только для Collections.binarySearch, затем отбросьте.

Entry target = new Entry( "Widget" , new TreeSet<Integer>() ) ;
int index = Collections.binarySearch( myList , target ) ;  // Assuming the `compareTo` method compares only the `String` member field while ignoring the `TreeSet` member field.
if( entry < 0 ) { … no entry yet exists … }
else  // Else, entry found to exist.
{ 
    Entry entry = myList.get( index ) ;
    …
}
…
// As `target` goes out of scope, the object becomes a candidate for garbage collection, to be deleted from memory eventually.

Чтобы быстрее отправить объект target в сборку мусора, переназначьте target = null ; после двоичного поиска .

Используйте Map вместо Entry class

Если ваш Entry класс - это не что иное, как String и TreeSet, то я предлагаю вам пропустить определение этого класс вообще. Вместо этого используйте Map. Ключ - String для слова (слов) записи указателя, а значение - TreeSet.

Map< String , TreeSet< Integer > > entries = new TreeMap<>() ;

Для поиска записи используйте Map::containsKey и передать слово (слова) записи указателя.

Поведение Multimap

Затем вы можете использовать метод Java 8 computeIfAbsent, чтобы получить удобное поведение multimap для легкого доступа к набору номера строк. Продемонстрировано на этом ответе .

Или используйте стороннюю реализацию с несколькими картами. Например, Google Guava библиотека