0

I'm making a book index where I have an inner class called Entry which holds a String (the word itself) and an Integer TreeSet to hold all the line numbers the word appears on.

I have a ListIndex class (which holds the Entry class) where I create an ArrayList of type Entry. When I add a word to the list, I need to check whether the word is already in the list by using binarySearch(). However, I can't use Collections.binarySearch(myList, word) because the ArrayList is of type Entry.

My Entry class implements Comparable but I still don't understand how I can fix this. Any help will be appreciated!

user11610667
  • 23
  • 5
  • Can you show simple example? – Giga Kokaia May 05 '20 at 20:11
  • Your Question is not clear. Are you trying to check that an `Entry` object exists (regardless of line numbers)? Or are you trying to see if an `Entry` object exists AND has at least one entry in its `TreeSet` of line numbers? Are you just looking for a entry for a word, or are you trying to insert a line number into the `TreeSet`. You need to more thoroughly think through your scenario. – Basil Bourque May 05 '20 at 20:15
  • Does `Entry` consist of anything more than `String` and a `TreeSet`? If not, you would be better off using a `Map`. – Basil Bourque May 05 '20 at 20:18

2 Answers2

0

Use bogus Entry object as criterion

Assuming your implementation on Entry for the compareTo method required by the Comparable interface merely defers to its contained String object’s compareTo method and ignores the state of the TreeSet of line numbers…

Just instantiate a bogus Entry object with your target string. Use that Entry object just for Collections.binarySearch, then discard.

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.

To send the target object to garbage collection faster, reassign target = null ; after the binary search.

Use Map instead of Entry class

If your Entry class is nothing more than a String and a TreeSet, then I suggest you skip defining that class at all. Use Map instead. The key is a String for the index entry word(s), and the value is a TreeSet.

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

To search for an entry, use Map::containsKey and pass the index entry word(s).

Multimap behavior

You can then use Java 8 computeIfAbsent method to get convenient multimap behavior for easy access to the set of line numbers. Demonstrated on this Answer.

Or use a 3rd-party multimap implementation. For example, the Google Guava library

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
  • Thank you so much! – user11610667 May 05 '20 at 22:32
  • @user11610667 You are welcome. Please take a moment to edit your Question, to make it more clear. See my Comments on the Question. Thousands of people may be reading your Question over the years ahead, so make it most helpful. – Basil Bourque May 06 '20 at 00:17
0

You should implement Comparable interface in Entry like this 

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
0xh3xa
  • 4,801
  • 2
  • 14
  • 28