finding the highest indexes of an array in java

Question

So I am relatively new to java, and I have made a small application that takes in input from the user a (phone number, & a name). These values are saved under an array of objects(after asking for input..):

for(int i=0; i<users.length;i++){
users[i]= new id(name, phone);
}

what I am having trouble is the search function, this is what I have:

System.out.println("Enter users name: ");
nameIn =scan.next();
int [] simIndex = new int [100];

for(int z = 0; z<counter; z++){ //goes through all names
                //z tells us the name we are on
for(int o =0; o<nameIn.length() && o<users[z].name.length();o++){ //goes length of name
                    //o tells us the char we are at
char inputName = nameIn.charAt(o); //takes charAt increments
char indexName = users[z].name.charAt(o);
if(inputName == indexName){ //if inputed char and index char are the same
numSim++;
simIndex[z] =numSim; 

Everything works till this point. What I am trying to do is print out the highest values of SimIndex[] (those will be the most similiar to the input) So how do I find the highest values of an array and get their indexes?

Answer 1

As a few people already said you can sort your names by their similarity to the entered name. In order to do so you can keep the names in an array as you do now, but you will have to use a Comarator. This comparator will take two names and decide how similar they are. It will be used for sorting your array of names.

The trickier part is determining the similarity between two Strings. One way of computing this similarity is by using the Levenshtein distance. I've copied the "Iterative with two matrix rows" implementation of this algorithm from the wiki article and translated it into Java (see bottom of answer) and used that in my comparator:

// make sure that this is final so we can use it inside of the comparator
final String nameIn = scan.next();
Arrays.sort(names, 0, names.length, new Comparator<id>() {

  @Override
  public int compare(id o1, id o2) {
    String name1 = o1.name;
    String name2 = o2.name;

    // how different is name1 from nameIn?
    int name1Distance = levenshteinDistance(name1, nameIn);

    // how different is name2 from nameIn?
    int name2Distance = levenshteinDistance(name2, nameIn);

    // difference of the differences
    // if name1 and name2 are equally different from nameIn then this is 0
    // meaning that name1 and name2 are "equal"
    // if name1 is less different than name2 then this will be < 0
    // meaning that name1 is "less than" name2
    // if name1 is more different that name2 then this will be > 0
    // meaning that name1 is "more than" name2
    return name1Distance - name2Distance;
  }
});
// the names array is now sorted
// the first element in the array is least different from nameIn
// the last element in the array is most different from nameIn

if you want to just get an array of sorted indices rather than sorting the names array, you can do it in a very similar way :

// make sure that this is final so we can use it inside of the comparator
final String nameIn = scan.next();
// make a final reference to the names array so that it can be accessed in the comparator
final id[] namesFinal = names;
// this will be the array we will sort, it will hold the sorted indices of
// elements in the names array
final Integer[] sortedIndices = new Integer[names.length];

// initialize the sortedIndices array (index 0 is 0, index 1 is 1, etc)
for (int i = 0; i < sortedIndices.length; i++) {
    sortedIndices[i] = i;
}


Arrays.sort(sortedIndices, 0, names.length, new Comparator<Integer>() {

  @Override
  public int compare(Integer o1, Integer o2) {
    // get the names from the names array using o1 and o2 as indices
    String name1 = namesFinal[o1].name;
    String name2 = namesFinal[o2].name;

    // how different is name1 from nameIn?
    int name1Distance = levenshteinDistance(name1, nameIn);

    // how different is name2 from nameIn?
    int name2Distance = levenshteinDistance(name2, nameIn);

    // difference of the differences
    // if name1 and name2 are equally different from nameIn then this is 0
    // meaning that name1 and name2 are "equal"
    // if name1 is less different than name2 then this will be < 0
    // meaning that name1 is "less than" name2
    // if name1 is more different that name2 then this will be > 0
    // meaning that name1 is "more than" name2
    return name1Distance - name2Distance;
  }
});
// the sortedIndices array is now sorted
// the first element in the array is the index of the name that is least different from nameIn
// the last element in the array is the index of the name that is most different from nameIn

The Levenshtein distance method :

public static int levenshteinDistance(String s, String t) {
  // degenerate cases
  if (s == t) {
    return 0;
  }
  if (s.length() == 0) {
    return t.length();
  }
  if (t.length() == 0) {
    return s.length();
  }

  // create two work vectors of integer distances
  int[] v0 = new int[t.length() + 1];
  int[] v1 = new int[t.length() + 1];

  // initialize v0 (the previous row of distances)
  // this row is A[0][i]: edit distance for an empty s
  // the distance is just the number of characters to delete from t
  for (int i = 0; i < v0.length; i++) {
    v0[i] = i;
  }

  for (int i = 0; i < s.length(); i++) {
    // calculate v1 (current row distances) from the previous row v0

    // first element of v1 is A[i+1][0]
    // edit distance is delete (i+1) chars from s to match empty t
    v1[0] = i + 1;

    // use formula to fill in the rest of the row
    for (int j = 0; j < t.length(); j++) {
      int cost = (s.charAt(i) == t.charAt(j)) ? 0 : 1;
      v1[j + 1] = Math.min(v1[j] + 1, Math.min(v0[j + 1] + 1, v0[j] + cost));
    }

    // copy v1 (current row) to v0 (previous row) for next iteration
    for (int j = 0; j < v0.length; j++) {
      v0[j] = v1[j];
    }
  }

  return v1[t.length()];
}

Answer 2

With the guava library, you can use Ints#max. It takes an int[] as argument.

You will be better off using a TreeMap (instead of array) for this kind of an application.

Answer 3

If you put your values into an ArrayList, you can make use of Collections.sort

The Java Collections Trail is a worthwhile read. Understanding the basic collection types, when to use each, and the handy built-in features of collections will save you a lot of coding effort and heartache.