Sorting positions in Java

I don't know how to put the question forth but i think an example might go a long way in clearing up the question....so here it is:

Say i have an array of strings: "Bob" "Alan" "Conrad" "Alice" "Alex".

After sorting alphabetically the array will become:"Alan" "Alex" "Alice" "Bob" "Conrad".

So we know in 开发者_如何学运维this case that the sorted element starting from "B" will be positioned after position number 3.

Now my question is,is there an inbuilt function in java/android which will let me know after the sorting where one group ends and the other starts (At which position the string transitions from "A" to "B")?

EDIT: Or maybe even two different functions used in conjunction

I'm not familiar with any inbuilt function that would do this. I doubt that there is one; partly because this seems like a relatively unusual request, and partly because it really needs a functional argument in the second step. Guava (and other libraries) provide a Predicate interface that would do the trick, but there's nothing like that in the standard library.

That said, you can do this quite simply with two steps:

1. Sort the collection. (This can't reasonably be avoided; you have to inspect every element and know their relative ordering anyway, so you can't do any better than the O(n) behaviour that sorting will impose).
2. Walk through the sorted collection, testing every element against a predicate until you find the first one that matches/doesn't match.

For the latter step if you have something like a binary tree, and your test lends itself to a Comparator-like interface, you can iterate through the tree more quickly. But in the general case of a true/false check you can't make such assumptions, so you'd just need to walk through. (In the fully general case with an unsorted collection you'll be performing the operation in linear time anyway so this isn't a big deal).

It would be straightforward to package this up as a library operation of your own, though (assuming that you have a definition of Function1 or Transformer or similar from some library):

public <T> int indexOfPartition(Collection<T> coll, Function1<T, Boolean> pred, Comparator<T> cmp) {
    final Collection<T> sorted = Collections.sort(coll, cmp);
    final Iterator<T> iter = sorted.iterator();        
    int idx = 0;
    // Walk through the collection until we find an element that is "false"
    // under the predicate (i.e. not in the first partition).
    while (iter.hasNext() && pred(iter.next()) {
        idx++;
    }

    // TODO think about what you want when the collection is empty and/or when
    // the partition never changes (e.g. list of entirely strings starting
    // with "A")
    return idx;
}

You could dress this up with overloads to pass in default comparators and predicates, etc.

And in fact if you want the predicate to be dynamic, then instead of a Function1<T, Boolean> you could pass in a Function1<T, ?> which maps inputs to an arbitrary output object - then walk the string until the output object is different. In your example, you could pass a function to map Strings to their first character, depending on what you want is "when B starts" or "when the initial letter changes from the first element's".

I think your definition of group is a bit strange... there cannot be a built in function to find such a thing because it can be defined in many different way.

I think that after sorting yo may use regular expression to find your "group transition". give a look to here

If your list is pre-sorted, look into Collections.binarySearch. If you search for an item that you know would be positioned between two existing groups, such as "B", it will spit out the negative number corresponding to the list position that item would be found at.

You should keep the data sorted in your list. Then look at how the NavigableSet#headSet or tailSet is implemented and leverage that to write your own utility functions over the sorted list.

You can use java.util.Arrays.sort to sort your array, but you'll have to loop yourself and find the first element starting with B to know its position.

If Guava is an option, you might use its Iterables.indexOf method (although it would need a collection of Strings, and not an array).