Using Arrays.binarySearch to compare a String to an Object

Question

I'm working on an implentation of a Suffix Array to be used for speeding up phrase searches.

I have an array of "Suffix"-objects, this is the Suffix Array. Each Suffix-object has two values, document and position.

I have a Comparator that sorts this array based on a lookup in a dictionary of strings using the two values document and position. (For example, one suffix object with document=1, position=5 points to "fish" and another object points to "cake". "Cake" will be sorted in front of "fish". This works just fine, and the suffix array is sorted as expected in lexographical order

Now, however, I want to do a binary search lookup in this suffix array, and the input this time is a string. How can I use Arrays.binarySearch() with the Comparator I made to compare a String key (the phrase I'm searching for) to search the suffix array? It would be trivial to compare the String with the Suffix object if the binarySearch() method would let me somehow do it in the Comparator...

Could you possibly include code samples for what you are trying to accomplish? — Zack
– Zack, Commented Feb 26, 2013 at 19:10
@moose: No. The man with the hat is "Heisenberg" from the popular TV series Breaking Bad. I don't know what KIT is and I haven't posted anything to anywhere regarding this problem. — ponycat
– ponycat, Commented Feb 26, 2013 at 19:48
@ponycat: Ah, I didn't know that this was a wide-spread image. KIT is Karlsruhe Institute of Technology, a university. We have an exam here in three days where you have to know how to create suffix trees / arrays, so I thought you might also be a student from here. — Martin Thoma
– Martin Thoma, Commented Feb 26, 2013 at 20:48

Bernhard Barker · Accepted Answer · 2013-02-26 20:17:11Z

1

Not sure if I completely understand, but here are my thoughts:

Modify your compareTo method in your class as follows:

class Suffix implements Comparable<Object>
{
   /* ... */

   int getDocumentId() { /* ... */ }
   int getPosition() { /* ... */ }

   @Override
   public int compareTo(Object o)
   {
      if (o.getClass() == String.class)
      {
         /* Derived from compare code comment */
         String key = dictionary.getDocument(getDocumentId()).getData();
         String suffix = (getPosition() == 0) ? key : key.substring(getPosition());

         suffix.compareTo((String)o);
      }
      else
      {
         /* same as original comparison */
      }
   }
}

Then you can do:

Arrays.binarySearch(yourArray, yourString);

edited Feb 26, 2013 at 20:17

answered Feb 26, 2013 at 19:45

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ponycat Over a year ago

The problem is that the string it points to is not saved in my object. There is a separate "storage" that I access using the ints document and position, and from that storage I can derive the string.

ponycat Over a year ago

Thank you very much for your time and help! While your solution doesn't fit very snugly with my implementation (mostly due to my terrible explanation of the real problem) it has helped point me in the right direction for another solution. Thanks again!

Collectives™ on Stack Overflow

Using Arrays.binarySearch to compare a String to an Object

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related