Java for C# Programmers 11: Algorithms

Algorithms

In Java, there are many algorithms available as static methods of the Collections class. I’m giving here examples for the most important ones.

    import java.util.Collections;    
    List numbers = new ArrayList();
    numbers.add(1);
    numbers.add(5);
    numbers.add(4);                 // 1 5 4
    Collections.sort(numbers);      // 1 4 5
    Collections.reverse(numbers);   // 5 4 1
    Collections.shuffle(numbers);   // 4 1 5
    Collections.swap(numbers, 0, 2);   // 5 1 4
    Collections.fill(numbers, 7);      // 7 7 7

    List num2 = new ArrayList();
    Collections.addAll(num2,  2, 6, 5);    // 2 6 5

    Collections.copy(numbers, num2);    // numbers is 2 6 5
    Collections.sort(num2);     // 2 5 6
    num2.add(7);            // 2 5 6 7
    Collections.rotate(num2, 1);     // 7 2 5 6 
    Collections.rotate(num2, -1);    // 2 5 6 7      
    int pos = Collections.binarySearch(num2, 5);    // pos is 1

    pos = Collections.binarySearch(num2, 3);    
        // -> pos is -2. pos is (-(insertion_point) - 1), if the 
        // element is not contained in the collection. 
        // Therefore you can add an element to a collection
        // with a line like the following. 
    num2.add(-pos-1, 3);        //  2 3 5 6 7

    pos = Collections.binarySearch(num2, -8);   // pos is -1
    num2.add(-pos-1, -8);           //  -8 2 3 5 6 7

    Collections.shuffle(num2);      // 2 3 -8 5 7 6
    int n = Collections.min(num2);  // -8 
    int m = Collections.max(num2);  // 7 
    boolean b = num2.contains(3);   // true 

    b = num2.contains(4);           // false
    b = num2.containsAll(numbers);      // true;    
    numbers.add(11);        
    b = num2.containsAll(numbers);      // false;   

    b = Collections.disjoint(num2, numbers); // false
    numbers.clear();        // numbers is empty
    Collections.addAll(numbers, 11, 9, 1);  // 11 9 1
    b = Collections.disjoint(num2, numbers);    // true

    numbers.add(11);                            // 11 9 1 11 
    n = Collections.frequency(numbers, 11);     // 2

    Collections.copy(numbers, num2);    
      // -> IndexOutOfBoundsException: Source does not fit in dest 

UnsupportedOperationException

Gotcha: In Java, it may be that a collection has the Collection interface but does not really implement it. This is true especially for unmodifiable collections. In these cases, it is common practice that all methods that are not really implemented throw UnsupportedOperationException.

Converting Arrays to Lists And Vice Versa

As arrays and Iterables do not have a common base, you sometimes will need to convert an array to an Iterable and vice versa.

Array to Iterable

To use an array in a function, where a List or an Iterable is required, you can create a fixed-size List from the array. Such a fixed-size List is no real List, it is just a wrapper around the array and has a List interface.

Gotcha: This interface is not implemented out. Only reading functions are implemented. All the others throw UnsupportedOperationException.

void a(Iterable list)
{
    for(int i: ll)
        System.out.printf(" %d", i);
}

Integer[] h4 = {4, 5, 11, 46};
a(h4);      // Compile error: The method a(Iterable)
            // is not applicable for the arguments (Integer[])  

List ll = Arrays.asList(h4);
a(ll);      // ok,   4 5 11 46

ll.add(4711) // **GOTCHA** throws UnsupportedOperationException 

Probably it is safer to use only the Iterable interface with
the asList function:

Iterable l2 = Arrays.asList(h4);
a(l2);       // ok,   4 5 11 46

l2.add(4711) // Compile error: The method add(int) is 
             // undefined for the type Iterable    

If you need a List with variable size, use the following construct. This will copy the array into a List and not only create a wrapper.

List ll = new ArrayList(Arrays.asList(h4));
ll.add(4711); // ok
a(ll);     // 4 5 11 46 4711

List to Array

ToArray Method

Sometimes, you may need an array but you have a List. Imagine you must use this function:

static void b(Integer[] ll)
{
    for (int i : ll)
        System.out.printf("%d ", i);
}

And you have a List.

List h5 = new ArrayList();
h5.add(89);
h5.add(76);

Then you can create an array of Integer like this.

Integer[] h6 = new Integer[h5.size()];
h5.toArray(h6);

b(h6);  // 89 76

Manual Method

If you have got a function which needs an int[] array like this

    static void a(int[] ll)
    {
        for (int i : ll)
            System.out.printf("%d ", i);
    }

And you have a List like above, then you can of course create an array of int like this:

    int[] h7 = new int[ts.size()];
    for (int i = 0; i < ts.size(); ++i)
        h7[i] = ts.get(i);

    a(h7);    // 89 76