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

Collections

Collections in Java involve several inconsistencies which seem quite odd for a C# developer. To understand some of the oddities of Java collections, you should keep in mind that Java is an old framework and at some points in its evolution, some new paradigms have been introduced and some old paradigms have been changed.

Before Java 5, you had collections that had Object as contained type. Later Java versions have generic collections and generic collection-interfaces. I’ll talk only about the generics here, but am leaving away the mostly.

Collection Interfaces

Modern Java collection handling is based completely on generic interfaces. The basic interface for collections is Collection.

From Collection derived interfaces are

List, Set, Queue, Deque, SortedSet, NavigableSet and the thread-safe interfaces concurrent.BlockingQueue, concurrent.BlockingDeque, concurrent.TransferQueue.

The following table shows the interfaces and the implementations available in Java SE 7. The names are mostly self-explanatory but where needed, some explanations are given under the table.

• ArrayList and Vector are nearly the same, the main difference is that Vector is synchronized and ArrayList is not.
• Stack extends Vector and so is synchronized, too.
• LinkedHashSet is implemented as a hash table with an added linked list. The linked list orders its elements in the order the elements have been added to the LinkedHashSet.

Map Interface

The Map interface is equivalent to C#’s IDictionary. Map is the base interface of these extended interfaces: SortedMap, NavigableMap, concurrent.ConcurrentMap and concurrent.ConcurrentNavigableMap.

Gotcha: Strange, but true: a Map is not a Collection in Java.

HashMap, Hashtable, TreeMap, WeakHashMap, Properties and LinkedHashMap are the most important implementations of the Map interface.

• The difference between Hashtable and HashMap is: Hashtable is synchronized, HashMap is not.
• A TreeMap is implemented as tree. It is ordered by key.
• LinkedHashMap keeps a linked list which is ordered by the order of insertion of elements into the list.
• A WeakHashMap stores keys as weak references. The C# analogon to a WeakHashMap is a Dictionary>.
  Gotcha: The WeakHashMap automatically removes an entry if the entry’s key is garbage collected. Of course, a Dictionary> does not remove entries automatically.
• Properties can be used for ini-files.

Map Example

Map h = new HashMap();

h.put(20097, "Hamburg");
h.put(76307, "Karlsbad-Auerbach");
h.put(76307, "Karlsbad");

if (h.containsKey(20097))
    System.out.println(h.get(20097));     // Hamburg

System.out.println(h.get(22222));   //  null
System.out.println(h.get(76307));   //  Karlsbad

Set keys = h.keySet(); 
// -> { 20097, 76307 } in unpredictable order.

Collection values = h.values();  
// -> { "Hamburg", "Karlsbad" } in unpredictable order.

Set> entries = h.entrySet();  
// -> { {20097, "Hamburg"},  {76307, "Karlsbad"} }
//    in unpredictable order. 

Properties class

The Properties class is a Map that according to docs shall only contain String-String pairs. Nevertheless, and strange but true: it is derived from Hashtable, not from Hashtable.

The Properties class can be used to store ini-like files on disk. An example on how to use Properties to read and write data follows.

Properties p = new Properties();
p.setProperty("a", "A");
p.setProperty("b", "xy");

static void StoreProperties(String filename, Properties prop)
       throws IOException
{
    FileWriter fw = null;
    try
    {
        fw = new FileWriter(filename);
        prop.store(fw, "This is a comment.");
    }
    catch (Exception e)
    {
        e.printStackTrace();
    }
    finally
    {
        if (fw != null)
            fw.close();  // may throw
    }
}

static void ReadProperties(String filename, Properties prop) 
       throws IOException
{
    prop.clear();
    Reader fr = null;
    try
    {
        fr = new FileReader(filename);
        prop.load(fr);
    }
    catch  (Exception e)
    {
        e.printStackTrace();
    }
    finally
    {
        if( fr != null)
            fr.close();  // may throw
    }
}

Dictionary

From Java 1.0 on, there has been the abstract class Dictionary which of course denotes the same concept as the Map. So you will find this in legacy code frequently. Nowadays, Dictionary is deprecated.

IEnumerable, Equals, Indexers, …

equals, hashCode and compareTo

The Java methods equals, hashCode and compareTo are analog to C#’s Equals, GetHashCode and CompareTo. Like in C#, if you use any of the generic containers you must be aware that these methods must be implemented on your classes. Otherwise strange things will happen.

IEnumerable, IEnumerator / Iterable, Iterator

Iterable is the Java equivalent of C#’s IEnumerable and Iterator is the Java equivalent of IEnumerator. The following two code snippets show their usage.

// Java
TreeSet ts = ...;

Iterable t = ts;
for(java.util.Iterator it = t.iterator(); it.hasNext();)
        System.out.print(it.next() + " "); 

// C# 
List a = ...;

IEnumerable  t = a; 
for(IEnumerator en = t.GetEnumerator(); en.MoveNext();)
    Console.Write(en.Current + " ");

Some further Gotchas:

• Ordinary Java arrays do not implement IEnumerable. Nevertheless you can iterate over them by the extended for loop.
• Collections of primitive types are not allowed in Java. You need to use the corresponding wrapper class. Example: List = new LinkedList();
• Indexers do not exist in Java. Access to elements of array-like collections can be done by get(i) instead.