Java Rumblings

Saturday, 25 September 2010

Sorting a List

// Create a list
String[] strArray = new String[] {"z", "a", "C"};
List list = Arrays.asList(strArray);

// Sort
Collections.sort(list); // C, a, z

// Case-insensitive sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER); // a, C, z

// Reverse-order sort
Collections.sort(list, Collections.reverseOrder()); // z, a, C

// Case-insensitive reverse-order sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
Collections.reverse(list); // z, C, a

Operating on Lists

There are various type of operations that can be performed on lists:

ArrayList example 2

// Create the list
List list = new LinkedList(); // Doubly-linked list
list = new ArrayList(); // List implemented as growable array
// Append an element to the list

list.add("a");

// Insert an element at the head of the list

list.add(0, "b");

// Get the number of elements in the list

int size = list.size(); // 2

// Retrieving the element at the end of the list

Object element = list.get(list.size()-1); // a

// Retrieving the element at the head of the

list element = list.get(0); // b

// Remove the first occurrence of an element boolean
b = list.remove("b"); // true
b = list.remove("b"); // false // Remove the element at a particular index element = list.remove(0); // a

Collection introduction (Index)

1. Some methods of collecting

Arrays
BigInteger

2. What are collections?

3. Introduction to collections
In Java 1.2, an entirely new set of interfaces and classes was added to the Java libraries to support more sophisticated collections handling. Earlier there were vectors and hashtable and stack...later came Collections, lists, sets and map. Java 5 introduces queue.

4. Interface in Collections
describes the core collection interfaces, which are the heart and soul of the Java Collections Framework. You'll learn general guidelines for effective use of these interfaces, including when to use which interface. You'll also learn idioms for each interface that will help you get the most out of the interfaces.
Some interfaces in this framework:

Interface for object ordering:

Comparable
Comparator

5. Implementations in Collections
describes the JDK's general-purpose collection implementations and tells you when to use which implementation. You'll also learn about the wrapper implementations, which add functionality to general-purpose implementations. Some implementations in java collections:

Vectors implements RandomAccess //synchronized equivalent of ArrayList
AbstractCollection implements Collection, Iterable
AbstractList implements List
ArrayList implements RandomAccess
AbstractSequentialList
LinkedList implements Deque
Stack //adds peek,push and pop()
AbstractSet implements Set
HashSet
LinkedHashSet
TreeSet implements SortedSet
EnumSet // Bitset implementation for Enum class.
AbstractQueue implements Queue
PriorityQueue
ArrayDeque implements Queue Deque

Besides these classes , there is Collections(note plural) or java.util.Collections which has static methods to deal with collections.

6. Algorithms describes the polymorphic algorithms provided by the JDK to operate on collections. With any luck you'll never have to write your own sort routine again!

7. Custom Implementations tells you why you might want to write your own collection implementation (instead of using one of the general-purpose implementations provided by the JDK), and how you'd go about it. It's easy with the JDK's abstract collection.

8. Interoperability tells you how the collections framework interoperates with older APIs that predate the addition of Collections to Java. Also, it tells you how to design new APIs so that they'll interoperate seamlessly with other new APIs.

9. Class or Interface : When using collections?

10. Performance of various collections

Examples

Thursday, 23 September 2010

blocking queue has the following characteristics:

methods to add an item to the queue, waiting for space to become available in the queue if necessary;
corresponding methods that take an item from the queue, waiting for an item to put in the queue if it is empty;
optional time limits and interruptibility on the latter calls;
efficient thread-safety: blocking queues are specifically designed to have their put() method called from one thread and the take() method from another— in particular, items posted to the queue will be published correctly to any other thread taking the item from the queue again; significantly, the implementations generally achieve this without locking the entire queue, making them highly concurrent components;
integration with Java thread pools: a flavour of blocking queue can be passed into the constructor of ThreadPoolExecutor to customise the behaviour of the thread pool.

These features make BlockingQueues useful for cases such as the following:

a server, where incoming connections are placed on a queue, and a pool of threads picks them up as those threads become free;
in a variety of parallel processes, where we want to manage or limit resource usage at different stages of the process.

Queues in Java 5: the Queue interface

Java 5 adds queues to the Collections framework. A queue is in some ways a sub-construct of a list, usually implemented as a linked list, with the following characteristics:

unlike a normal list, it is not random access: that is, you can't get or set the element at an arbitrary position in the list;
get and set operations always take place at the ends of the queue (generally, one "takes from the head" and "puts on the tail").

In a standard queue, the next item to be taken is the one at the head of the queue, i.e. the one that has been there the longest. When items are added to the queue, they are added to the tail. The item at the tail can only be accessed once all the items placed before it have been removed in order.

Why use a queue?

So you may well be thinking: why use a queue if it has these restrictions? Can't you just use a boring old ArrayList or LinkedList¹? It turns out there are at least three main reasons:

in some cases, a queue is "conceptually what we want";
eliminating random access allows optimisations for concurrency;
Java's efficient BlockingQueue implementations can take some of the work out of the most typical use of queues.

Places where we "conceptually" want a queue are where we are dealing with a so-called producer-consumer pattern. That is, one thread "produces" a list of jobs for another thread to pick up. Of course, we could use an ordinary (synchronized) LinkedList if this was purely our motivation. However, it turns out that restricting access to the head and tail of the queue allows for further optimisation for concurrent access.

Queues with thread pools

One place, then, in which queues are useful is for the work queue of a thread pool. Java provides the ThreadPoolExecutor class; when constructing this class, you can pass in the queue that you want the thread pool to use. Or, you can construct your thread pool with one of the utility methods in the Executors class, in which case a default BlockingQueue will be used.

Queue implementations firstly share a new Queue interface, which has several methods for accessing the head and tail of the queue. Recall that items are always placed on the end or "tail" of the list, and always read from the beginning or "head" of the list.

Methods specified by the Java `Queue` interface
Operation	Throws exception if not possible	Returns value if not possible
Add item to tail	`add()`	`offer()`
Remove item from head	`remove()`	`poll()`
"Peek" item at head	`element()`	`peek()`

Types of Queues

Java provides Queue implementations depending on a few key criteria:

thread-safety: if you don't require the queue to be accessed concurrently from multiple threads, then a plain LinkedList can be used as a Queue; the advantage of the other implementations is that they offer efficient thread-safety;
blocking or non-blocking: various blocking implementations add extra methods to put and remove items from the queue, blocking until the operation is possible, with an optional time limit;
bound or non-bound: sometimes it is useful to put an upper limit on the number of items that can fit in the queue, e.g. to prevent a thread pool from queueing up too many jobs when the machine is busy;
other special operations: Java provides an implementation that orders by priority, and another that applies a delay to queued items.

As of Java 6, the various queue classes are as follows:

Queue implementations as of Java 6
Blocking?	Other criteria	Bound	Non-bound
Blocking	None	`ArrayBlockingQueue`	`LinkedBlockingQueue`
	Priority-based		`PriorityBlockingQueue`
	Delayed		`DelayQueue`
Non-blocking	Thread-safe		`ConcurrentLinkedQueue`
	Non thread-safe		`LinkedList`
	Non thread-safe, priority-based		`PriorityQueue`

One further type of queue not included above is the SynchronousQueue, which is effectively a zero-length queue (so that a thread adding an item to the queue will block until another thread removes the item).

Blocking queues

In general, the most interesting queue implementations are the various blocking queues, which allow efficient concurrent access and are useful for coordinating objects between threads, particularly in the so-called producer-consumer pattern. In Java, all blocking queue implementations implement the BlockingQueue interface, which we look at next.

ListIterator interface

ListIterator methods

ListIterator is implemented only by the classes that implement the List interface (ArrayList, LinkedList, and Vector). ListIterator provides the following.

Result	Method	Description
Forward iteration
`b =`	`it.hasNext()`	`true` if there is a next element in the collection.
`obj =`	`it.next()`	Returns the next object.
Backward iteration
`b =`	`it.hasPrevious()`	`true` if there is a previous element.
`obj =`	`it.previous()`	Returns the previous element.
Getting the index of an element
`i =`	`it.nextIndex()`	Returns index of element that would be returned by subsequent call to next().
`i =`	`it.previousIndex()`	Returns index of element that would be returned by subsequent call to previous().
Optional modification methods. UnsupportedOperationException thrown if unsupported.
	`it.add(obj)`	Inserts obj in collection before the next element to be returned by `next()` and after an element that would be returned by `previous()`.
	`it.set()`	Replaces the most recent element that was returned by `next` or `previous()`.
	`it.remove()`	Removes the most recent element that was returned by `next()` or `previous()`.

So its of form:

public interface ListIterator extends Iterator {
    boolean hasNext();
    Object next();

    boolean hasPrevious();
    Object previous();

    int nextIndex();
    int previousIndex();

    void remove();          // Optional
    void set(Object o);     // Optional
    void add(Object o);     // Optional
}

The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) are intended to do exactly the same thing in both interfaces. The hasPrevious and previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backwards whereas next moves it forwards.

Here's the standard idiom for iterating backwards through a list:

for (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) {
    Foo f = (Foo) i.previous();
    ...
}

Note the argument to listIterator in the above idiom. The List interface has two forms of the listIterator method. The form with no arguments returns a ListIterator positioned at the beginning of the list, and the form with an int argument returns a ListIterator positioned at the specified index. The index refers to the element that would be returned by an initial call to next. If the index value of n is used, then the initial call to next would return null, since it would point just past the end of the list. An initial call to previous would return the element whose index was index-1.

In a list of length n, there are n+1 valid values for index, from 0 to n, inclusive.

Intuitively speaking, the cursor is always between two elements, the one that would be returned by a call to previous and the one that would be returned by a call to next. The n+1 valid index values correspond to the n+1 "gaps" between elements, from the gap before the first element to the gap after the last one. The diagram below shows the five possible cursor positions in a list containing four elements.

Element(0)   Element(1)   Element(2)   Element(3)   
         ^            ^            ^            ^            ^
  Index: 0            1            2            3            4

Calls to next and previous can be intermixed, but you have to be a bit careful. The first call to previous after a sequence of calls to next returns the same element as the last call to next. Similarly, the first call to next after a sequence of calls to previous returns the same element as the last call to previous. This will become obvious if you stare at the foregoing text long enough. If it doesn't, go get yourself a steaming hot mug of Java, and try again.

nextIndex and previousIndex
It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used for one of two purposes: To report the position where something was found, or to record the position of the ListIterator so that another ListIterator with identical position can be created.
It should also come as no surprise that the number returned by nextIndex is always one greater than the number returned by previousIndex. This implies the behavior of the two boundary cases: a call to previousIndex when the cursor is before the initial element returns -1, and a call to nextIndex when the cursor is after the final element returns list.size()+1. To make all of this concrete, here's a possible implementation of List.indexOf:

public int indexOf(Object o) {
    for (ListIterator i = listIterator(); i.hasNext(); )
        if (o==null ? i.next()==null : o.equals(i.next()))
            return i.previousIndex();

    return -1; // Object not found
}

Note that the indexOf method returns i.previousIndex() though it is traversing the list in the forward direction. This is because i.nextIndex() would return the index of the element that we are about to examine, and we want to return the index of the element that we just examined. The Iterator interface provides the remove operation to remove from the Collection the last element returned by next. The ListIterator interface provides two additional operations to modify the list: set and add. The set method "overwrites" the last element returned by next or previous with the specified element. It is demonstrated by the following polymorphic algorithm to replace all occurrences of one specified value with another:

public static void replace(List l, Object val, Object newVal) {
    for (ListIterator i = l.listIterator(); i.hasNext(); )
        if (val==null ? i.next()==null : val.equals(i.next()))
            i.set(newVal);
}

The only bit of trickiness in this example is the equality test between val and i.next. We have to special-case an val value of null in order to prevent a NullPointerException. The add method inserts a new element into the list, immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:

public static void replace(List l, Object val, List newVals) {
    for (ListIterator i = l.listIterator(); i.hasNext(); ) {
        if (val==null ? i.next()==null : val.equals(i.next())) {
            i.remove();
            for (Iterator j = newVals.iterator(); j.hasNext(); )
                i.add(j.next());
        }
    }
}

BAD BAD BAD

Q: What does this loop do? Note mixing of iterator with index.

ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist

int i = 0;
for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(alist.get(i++));
}

A: It throws an exception when it goes beyond the end.

After hasNext() returns true, the only way to advance the iterator is to call next(). But the element is retrived with get(), so the iterator is never advanced. hasNext() will continue to always be true (ie, there is a first element), and eventually the get() will request something beyond the end of the ArrayList. Use either the iterator scheme.

for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(it.next());
}

Or the indexing scheme, but don't mix them.

for (int i=0; i < alist.size(); i++) {
    System.out.println(alist.get(i));
}

Pages