Range-view Operation on list

The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive. This half-open range mirrors the typical for-loop:

for (int i=fromIndex; i<toIndex; i++) {
    ...
}

As the term view implies, the returned List is backed by the List on which subList was called, so changes in the former List are reflected in the latter.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List. For example, the following idiom removes a range of elements from a list:

list.subList(fromIndex, toIndex).clear();

Similar idioms may be constructed to search for an element in a range:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Note that the above idioms return the index of the found element in the subList, not the index in the backing List.

Any polymorphic algorithm that operates on a List (like the replace and shuffle examples, above) works with the List returned by subList.

Here's a polymorphic algorithm whose implementation uses subList to deal a hand from a deck. That is to say, it returns a new List (the "hand") containing the specified number of elements taken from the end of the specified List (the "deck"). The elements returned in the hand are removed from the deck.

public static List dealHand(List deck, int n) {
    int deckSize = deck.size();
    List handView = deck.subList(deckSize-n, deckSize);
    List hand = new ArrayList(handView);
    handView.clear();
    return hand;
}

 

The literal-minded might say that this program deals from the bottom of the deck, but I prefer to think that the computer is holding the deck upside down. At any rate, for many common List implementations, like ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

Here's a program using the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command line arguments: the number of hands to deal and the number of cards in each hand.

 

import java.util.*;

class Deal {
    public static void main(String args[]) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);

       // Make a normal 52-card deck
        String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8","9","10","jack","queen","king"};
        List deck = new ArrayList();
        for (int i=0; i<suit.length; i++)
            for (int j=0; j<rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);

        Collections.shuffle(deck);

        for (int i=0; i<numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

Let's run the program:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts]

While the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only as a transient object, to perform one or a sequence of range operations on the backing List. The longer you use the subList object, the greater the probability that you'll compromise it by modifying the backing List directly (or through another subList object).

 

Positional Access and Search Operations on Lists

The basic positional access operations (get, set, add and remove) behave just like their longer-named counterparts in Vector (elementAt, setElementAt, insertElementAt and removeElementAt) with one noteworthy exception. The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void). The search operations indexOf and lastIndexOf behave exactly like the identically named operations in Vector.

The addAll operation inserts all of the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator. This call is the positional access analogue of Collection's addAll operation.

Here's a little function to swap two indexed values in a List.

private static void swap(List a, int i, int j) {
    Object tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

Of course there's one big difference. This is a polymorphic algorithm: it swaps two elements in any List, regardless of its implementation type. "Big deal," you say, "What's it good for?" Funny you should ask. Take a look at this:

public static void shuffle(List list, Random rnd) {
    for (int i=list.size(); i>1; i--)
        swap(list, i-1, rnd.nextInt(i));
}

This algorithm (which is included in the JDK's Collectionsclass) randomly permutes the specified List using the specified source of randomness. It's a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactly list.size()-1 iterations). The following short program uses this algorithm to print the words in its argument list in random order:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = new ArrayList();
        for (int i=0; i<args.length; i++)
            l.add(args[i]);
        Collections.shuffle(l, new Random());
        System.out.println(l);
    }
}

In fact, we can make this program even shorter and faster. The Arraysclass has a static factory method called asList that allows an array to be viewed as a List. This method does not copy the array; changes in the List write through to the array, and vice-versa. The resulting List is not a general-purpose List implementation, in that it doesn't implement the (optional) add and remove operations: arrays are not resizable. Taking advantage of Arrays.asList and calling an alternate form of shuffle that uses a default source of randomness, you get the following tiny program, whose behavior is identical to the previous program:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = Arrays.asList(args);
        Collections.shuffle(l);
        System.out.println(l);
    }
}

Collection Operations on Lists–Simple and Bulk

Create the lists

List list1 = new ArrayList(); 
List list2 = new ArrayList(); 

Add the elements

// Add elements to the lists ...
list1.add("Hanuman");

Bulk Add
Copy all the elements from list2 to list1 (list1 += list2). list1 becomes the union of list1 and list2

list1.addAll(list2); 

Bulk Remove
Remove all the elements in list1 from list2 (list1 -= list2). list1 becomes the asymmetric difference of list1 and list2

list1.removeAll(list2); 

Intersection of Lists
Get the intersection of list1 and list2. list1 becomes the intersection of list1 and list2

list1.retainAll(list2); 

Remove all elements from a list

list1.clear(); 

Truncate the list

int newSize = 2;
list1.subList(newSize, list1.size()).clear(); 

Operations on SortedSet

The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:

• The Iterator returned by the iterator operation traverses the sorted set in order.
• The array returned by toArray contains the sorted set's elements in order.

Although the interface doesn't guarantee it, the toString method of the JDK's SortedSet implementations returns a string containing all the elements of the sorted set, in order.

Range-view Operations on SortedSet

The Range-view operations are somewhat analogous to those provided by the List interface, but there is one big difference. Range-views of a sorted set remain valid even if the backing sorted set is modified directly. This is feasible because the endpoints of a range view of a sorted set are absolute points in the element-space, rather than specific elements in the backing collection (as is the case for lists). A range-view of a sorted set is really just a window onto whatever portion of the set lies in the designated part of the element-space. Changes to the range-view write back to the backing sorted set and vice-versa. Thus, it's OK to use range-views on sorted sets for long periods of time (unlike range-views on lists). Sorted sets provide three range-view operations. The first, subSet takes two endpoints (like subList). Rather than indices, the endpoints are objects. They must be comparable to the elements in the sorted set (using the set's Comparator or the natural ordering of its elements, whichever the set uses to order itself). Like subList the range is half-open, including its low endpoint but excluding the high one.
Thus, the following one-liner tells you how many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:

int count = dictionary.subSet("doorbell", "pickl

See also post -Operations on SortedSet

Operations on SortedSet

The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:

• The Iterator returned by the iterator operation traverses the sorted set in order.
• The array returned by toArray contains the sorted set's elements in order.

Although the interface doesn't guarantee it, the toString method of the JDK's SortedSet implementations returns a string containing all the elements of the sorted set, in order.

See also post - RangeView operations on SortedSet

Operation between the two sets in java

// Create the sets
Set set1 = new HashSet();
Set set2 = new HashSet();

// Add elements to the sets ... // Copy all the elements from set2 to set1 (set1 += // set2)
// set1 becomes the union of set1 and set2
set1.addAll(set2);

// Remove all the elements in set1 from set2 (set1 -= set2) // set1 becomes the
// asymmetric difference of set1 and set2
set1.removeAll(set2);

// Get the intersection of set1 and set2
// set1 becomes the intersection of set1 and set2
set1.retainAll(set2);

// Remove all elements from a set
set1.clear();

Operations on a set

Create the set

Set set = new HashSet();

 

Add elements to the set

set.add("a");
set.add("b"); 
set.add("c"); 

Remove elements from the set

set.remove("c"); 

Get number of elements in set

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

Adding an element that already exists in the set has no effect
 

set.add("a"); 
size = set.size(); // 2

Determining if an element is in the set

boolean b = set.contains("a"); // true
b = set.contains("c"); // false //

Iterating over the elements in the set

Iterator it = set.iterator();
while (it.hasNext()) {
  // Get element
  Object element = it.next();
}

Create an array containing the elements in the set (in this case a String array)

String[] array = (String[])set.toArray(new String[set.size()]);

 

See also Operations on 2 Sets in java

 

Operating on Lists

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

• Collection Operations on Lists -  Simple and Bulk
• Positional Access and Search Operations on List
• Iterating over the List
• Range view operations on lists