4. Arrays

Introduction

// ----------------------------------------------------------------------------------
String[] simple = new String[] { "this", "that", "the", "other" };
String[][] nested = new String[][] { { "this" }, { "that" }, { "the", "other" } };
assert simple.length == 4;
assert nested.length == 3;
assert nested[2].length == 2;

// Mixed types (Java 1.4+)
Object[] mixed = new Object[] { "a", new Integer(1) };

// Mixed types (Java 1.5+) with auto boxing
Object[] mixed5 = new Object[] { "a", 1 };
// ----------------------------------------------------------------------------------

Specifying a List In Your Program

// ----------------------------------------------------------------------------------
String[] a = new String[] { "quick", "brown", "fox" };
assert a.length == 3;

a = "Why are you teasing me?".split(" ");
assert Arrays.equals(a, new String[] { "Why", "are", "you", "teasing", "me?" });

// Convert an array to a fixed-size list
List list = Arrays.asList(a);
assert list.size() == 5;

// Make that list variable and insert something at the top
List variableList = new ArrayList(list);
variableList.add(0, "First");
assert variableList.get(0).equals("First");
// ----------------------------------------------------------------------------------

Printing a List with Commas

/**
 * Join the elements of collection using the provided separator.
 */
public static String join( Collection col, String sep ) {
    StringBuffer sb = new StringBuffer();
    Iterator li = col.iterator();
    if ( li.hasNext() ) {
        sb.append( li.next() );
        while ( li.hasNext() ) {
            sb.append( sep );
            sb.append( li.next() );
        }
    }
    return sb.toString();
}

/**
 * Join the elements of enumeration using the provided separator
 * (provides interoperatbility for legacy APIs that return enumerations).
 */
public static String join( Enumeration e, String sep ) {
    return join( Collections.list( e ), sep );
}

/**
 * Join the elements of array using the provided separator.
 */
public static String join( Object[] col, String sep ) {
    StringBuffer sb = new StringBuffer();
    if ( col.length >= 1 ) {
        sb.append( col[0] );
    }
    for ( int i = 1; i < col.length; i++ ) {
        sb.append( sep );
        sb.append( col[i] );
    }
    return sb.toString();
}

// @@INCOMPLETE@@

Changing Array Size

// ----------------------------------------------------------------------------------
// In Java, we can't change the size of an array, but we can do it
// for Collection types (like List).

// Wrap the array with an ArrayList (because the list returns by
// Arrays.asList is fixed-size)
String[] people = new String[] { "Crosby", "Stills", "Nash" };
List list = new ArrayList(Arrays.asList(people));
assert list.size() == 3;

list.add("Young");
assert list.size() == 4;
// ----------------------------------------------------------------------------------

Doing Something with Every Element in a List

// ----------------------------------------------------------------------------------
String[] people = new String[] { "Crosby", "Stills", "Nash", "Young" };

// For loop
for (int i = 0; i < people.length; i++) {
  String person = people[i];
  // ...
}

// Enhanced For loop (Java 1.5+)
for (String person : people) {
  // ...
}

// Closure Style (using apache commons-collections 1.0+)
List list = Arrays.asList(people);
CollectionUtils.forAllDo(list, new Closure() {
  public void execute(Object person) {
    // ...
  }
});
// ----------------------------------------------------------------------------------

Iterating Over an Array by Reference

Extracting Unique Elements from a List

/**
 * Keep only first element (contains-wise, hence equals-wise) of
 * supplied collection.
 */
public static Collection uniq( Collection col ) {
    try {
        Collection ret = (Collection)col.getClass().newInstance();
        Iterator li = col.iterator();
        while ( li.hasNext() ) {
            Object elem = li.next();
            if ( ! ret.contains( elem ) ) {
                ret.add( elem );
            }
        }
        return ret;

    } catch ( InstantiationException ie ) {
        System.err.println( "can't create new object for class: "
                            + col.getClass() + ": " + ie );
        return null;

    } catch ( IllegalAccessException iae ) {
        System.err.println( "can't create new object for class: "
                            + col.getClass() + ": " + iae );
        return null;
    }
}

// @@INCOMPLETE@@

Finding Elements in One Array but Not Another

// ----------------------------------------------------------------------------------
String[] a = new String[] { "1", "1", "2", "2", "3", "3", "3", "4", "5" };
String[] b = new String[] { "1", "2", "4" };

// using apache commons-collections 3.2+
List diff = ListUtils.removeAll(Arrays.asList(a), Arrays.asList(b));
assert Arrays.equals(diff.toArray(), new String[] { "3", "3", "3", "5" });
// ----------------------------------------------------------------------------------

Computing Union, Intersection, or Difference of Unique Lists

// ----------------------------------------------------------------------------------
String[] a = new String[] { "1", "3", "5", "6", "7", "8" };
String[] b = new String[] { "2", "3", "5", "7", "9" };

// using apache commons-collections 1.0+

List intersection = ListUtils.intersection(Arrays.asList(a), 
Arrays.asList(b));
assert Arrays.equals(intersection.toArray(), new String[] { "3", "5", "7" });

List union = ListUtils.union(Arrays.asList(a), Arrays.asList(b));
Set unionUnique = new TreeSet(union);
assert Arrays.equals(unionUnique.toArray(),
                     new String[] { "1", "2", "3", "5", "6", "7", "8", "9" });

List diff = ListUtils.subtract(Arrays.asList(a), Arrays.asList(b));
assert Arrays.equals(diff.toArray(), new String[] { "1", "6", "8" });
// ----------------------------------------------------------------------------------

Appending One Array to Another

// ----------------------------------------------------------------------------------
String[] a = new String[] { "Time", "Flies" };
String[] b = new String[] { "An", "Arrow" };

// Append to existing list
List members = new ArrayList(Arrays.asList(a));
members.addAll(Arrays.asList(b));
assert Arrays.equals(members.toArray(),
                     new String[] { "Time", "Flies", "An", "Arrow" });

// Append and create a new list (using apache commons-collections 1.0+)
List union = ListUtils.union(Arrays.asList(a), Arrays.asList(b));
assert Arrays.equals(union.toArray(),
                     new String[] { "Time", "Flies", "An", "Arrow" });
// ----------------------------------------------------------------------------------

Reversing an Array

// ----------------------------------------------------------------------------------
String[] items = new String[] { "the", "quick", "brown", "fox" };

// Reverse the array itself (using apache commons-collections 1.0+)
String[] copy = (String[]) items.clone();
CollectionUtils.reverseArray(copy);
assert Arrays.equals(copy, new String[] { "fox", "brown", "quick", "the" });

// Iterate backward (using apache commons-collections 3.2+)
ReverseListIterator iter = new ReverseListIterator(Arrays.asList(items));
StringBuffer firstLetters = new StringBuffer();
while (iter.hasNext()) {
    firstLetters.append(iter.next().toString().charAt(0));
}
assert firstLetters.toString().equals("fbqt");
// ----------------------------------------------------------------------------------

Processing Multiple Elements of an Array

Finding the First List Element That Passes a Test

// ----------------------------------------------------------------------------------
String[] names = new String[] { "bill", "jack", "charles", "jim", "mike" };

// using apache commons-collections 1.0+

Predicate jFinder = new Predicate() {
    public boolean evaluate(Object name) {
        return name.toString().charAt(0) == 'j';
    }
};

// Find the first name that starts with 'j'
String firstJ = (String) CollectionUtils.find(Arrays.asList(names), jFinder);
assert firstJ.equals("jack");
// ----------------------------------------------------------------------------------

Finding All Elements in an Array Matching Certain Criteria

// ----------------------------------------------------------------------------------
String[] names = new String[] { "bill", "jack", "charles", "jim", "mike" };

// using apache commons-collections 1.0+

Predicate jFinder = new Predicate() {
  public boolean evaluate(Object name) {
    return name.toString().charAt(0) == 'j';
  }
};

// Find all names that starts with 'j'
Collection selected = CollectionUtils.select(Arrays.asList(names), jFinder);
assert Arrays.equals(selected.toArray(), new String[] { "jack", "jim" });
// ----------------------------------------------------------------------------------

Sorting an Array Numerically

// ----------------------------------------------------------------------------------
// Sort an array of primitives
int[] numbers = new int[] { 100, 3, 20 };
Arrays.sort(numbers);
assert Arrays.equals(numbers, new int[] { 3, 20, 100 });

// Sort an array of String alphabetically (default)
String[] names = new String[] { "100", "3", "20" };
Arrays.sort(names);
assert Arrays.equals(names, new String[] { "100", "20", "3" });

// Build a custom comparator to sort String numerically
Comparator custom = new Comparator() {
  public int compare(Object o1, Object o2) {
    return Integer.parseInt((String) o1) - Integer.parseInt((String) o2);
  }
};

// Sort an array of String with custom comparator
names = new String[] { "100", "3", "20" };
Arrays.sort(names, custom);
assert Arrays.equals(names, new String[] { "3", "20", "100" });

// Sorting a list of String with custom comparator
List list = Arrays.asList(new String[] { "100", "3", "20" });
Collections.sort(list, custom);
assert Arrays.equals(list.toArray(), new String[] { "3", "20", "100" });
// ----------------------------------------------------------------------------------

Sorting a List by Computable Field

// ----------------------------------------------------------------------------------
String[] names = new String[] { "bill", "jack", "charles", "jim", "mike" };

// Build a custom comparator to sort names by length and alphabetically
Comparator custom = new Comparator() {
    public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;
        
        int diff = s1.length() - s2.length();
        if (diff == 0) {
            diff = s1.compareTo(s2);
        }
        return diff;
    }
};

// Sorting list of String with custom comparator
List list = Arrays.asList(names);
Collections.sort(list, custom);
assert Arrays.equals(list.toArray(), new String[] { "jim", "bill", "jack", 
"mike", "charles" });
// ----------------------------------------------------------------------------------

Implementing a Circular List

// ----------------------------------------------------------------------------------
String[] a = new String[] { "1", "2", "3", "4", "5" };

// Using Collections.rotate
List list = Arrays.asList(a);
Collections.rotate(list, 2);
assert Arrays.equals(list.toArray(),
                     new String[] { "4", "5", "1", "2", "3" });

Collections.rotate(list, -2);
assert Arrays.equals(list.toArray(),
                     new String[] { "1", "2", "3", "4", "5" });

// Stack is based on Vector, which is synchronized.
// One could use ArrayStack from apache commons-collections 1.0+,
// which is NOT synchronized and therefore, faster if multi-threading
// is not an issue.
Stack circular = new Stack();
circular.addAll(Arrays.asList(a));

// At this point, 5 is the top of the stack

// Put the top item at the bottom...
circular.add(0, circular.pop());
assert Arrays.equals(circular.toArray(),
                     new String[] { "5", "1", "2", "3", "4" });

// ... and vice versa
circular.push(circular.remove(0));
assert Arrays.equals(circular.toArray(),
                     new String[] { "1", "2", "3", "4", "5" });
// ----------------------------------------------------------------------------------

Randomizing an Array

// ----------------------------------------------------------------------------------
String[] a = new String[] { "1", "2", "3", "4", "5" };

// One could also pass a subclass of Random as the second parameter to
// shuffle to use a custom ramdom strategy.
List list = Arrays.asList(a);
Collections.shuffle(list);
assert list.size() == 5;
// ----------------------------------------------------------------------------------

Program: words

Program: permute