Collections Algorithms

The collections framework provides several high-performance algorithms for manipulating collection elements. These algorithms are implemented as static methods of class Collections (Fig. 19.7). Algorithms sort, binarySearch, reverse, shuffle, fill and copy operate on Lists. Algorithms min, max, addAll, frequency and disjoint operate on Collections.

Figure 19.7. Collections algorithms.

Algorithm	Description
sort	Sorts the elements of a List.
binarySearch	Locates an object in a List.
reverse	Reverses the elements of a List.
shuffle	Randomly orders a List's elements.
fill	Sets every List element to refer to a specified object.
copy	Copies references from one List into another.
min	Returns the smallest element in a Collection.
max	Returns the largest element in a Collection.
addAll	Appends all elements in an array to a collection.
frequency	Calculates how many elements in the collection are equal to the specified element.
disjoint	Determines whether two collections have no elements in common.

Software Engineering Observation 19.4

The collections framework algorithms are polymorphic. That is, each algorithm can operate on objects that implement specific interfaces, regardless of the underlying implementations.

 

19.6.1. Algorithm sort

Algorithm sort sorts the elements of a List, which must implement the Comparable interface. The order is determined by the natural order of the elements' type as implemented by its class's compareTo method. Method compareTo is declared in interface Comparable and is sometimes called the natural comparison method. The sort call may specify as a second argument a Comparator object that determines an alternative ordering of the elements.

Sorting in Ascending Order

Figure 19.8 uses algorithm sort to order the elements of a List in ascending order (line 20). Recall that List is a generic type and accepts one type argument that specifies the list element typeline 15 declares list as a List of String. Note that lines 18 and 23 each use an implicit call to the list's toString method to output the list contents in the format shown on the second and fourth lines of the output.

Figure 19.8. Collections method sort.

(This item is displayed on page 924 in the print version)

 1 // Fig. 19.8: Sort1.java
 2 // Using algorithm sort.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.Collections;
 6
 7 public class Sort1
 8 {
 9 private static final String suits[] =
10 { "Hearts", "Diamonds", "Clubs", "Spades" };
11
12 // display array elements
13 public void printElements()
14 {
15 List< String > list = Arrays.asList( suits ); // create List
16
17 // output list
18 System.out.printf( "Unsorted array elements:
%s
", list );
19
20 Collections.sort( list ); // sort ArrayList
21
22 // output list
23 System.out.printf( "Sorted array elements:
%s
", list );
24 } // end method printElements
25
26 public static void main( String args[] )
27 {
28 Sort1 sort1 = new Sort1();
29 sort1.printElements();
30 } // end main
31 } // end class Sort1

 

Unsorted array elements:
[Hearts, Diamonds, Clubs, Spades]
Sorted array elements:
[Clubs, Diamonds, Hearts, Spades]

 

Sorting in Descending Order

Figure 19.9 sorts the same list of strings used in Fig. 19.8 in descending order. The example introduces the Comparator interface, which is used for sorting a Collection's elements in a different order. Line 21 calls Collections's method sort to order the List in descending order. The static Collections method reverseOrder returns a Comparator object that orders the collection's elements in reverse order.

Figure 19.9. Collections method sort with a Comparator object.

(This item is displayed on pages 924 - 925 in the print version)

 1 // Fig. 19.9: Sort2.java
 2 // Using a Comparator object with algorithm sort.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.Collections;
 6
 7 public class Sort2
 8 {
 9 private static final String suits[] =
10 { "Hearts", "Diamonds", "Clubs", "Spades" };
11
12 // output List elements
13 public void printElements()
14 {
15 List list = Arrays.asList( suits ); // create List
16
17 // output List elements
18 System.out.printf( "Unsorted array elements:
%s
", list );
19
20 // sort in descending order using a comparator
21 Collections.sort( list, Collections.reverseOrder() );
22
23 // output List elements
24 System.out.printf( "Sorted list elements:
%s
", list );
25 } // end method printElements
26
27 public static void main( String args[] )
28 {
29 Sort2 sort2 = new Sort2();
30 sort2.printElements();
31 } // end main
32 } // end class Sort2

 

Unsorted array elements:
[Hearts, Diamonds, Clubs, Spades]
Sorted list elements:
[Spades, Hearts, Diamonds, Clubs]

 

Sorting with a Comparator

Figure 19.10 creates a custom Comparator class, named TimeComparator, that implements interface Comparator to compare two Time2 objects. Class Time2, declared in Fig. 8.5, represents times with hours, minutes and seconds.

Figure 19.10. Custom Comparator class that compares two Time2 objects.

(This item is displayed on page 926 in the print version)

 1 // Fig. 19.10: TimeComparator.java
 2 // Custom Comparator class that compares two Time2 objects.
 3 import java.util.Comparator;
 4
 5 public class TimeComparator implements Comparator< Time2 >
 6 {
 7 public int compare( Time2 tim1, Time2 time2 )
 8 {
 9 int hourCompare = time1.getHour() - time2.getHour(); // compare hour
10
11 // test the hour first
12 if ( hourCompare != 0 )
13 return hourCompare;
14
15 int minuteCompare =
16 time1.getMinute() - time2.getMinute(); // compare minute
17
18 // then test the minute
19 if ( minuteCompare != 0 )
20 return minuteCompare;
21
22 int secondCompare =
23 time1.getSecond() - time2.getSecond(); // compare second
24
25 return secondCompare; // return result of comparing seconds
26 } // end method compare
27 } // end class TimeComparator

Class TimeComparator implements interface Comparator, a generic type that takes one argument (in this case Time2). Method compare (lines 726) performs comparisons between Time2 objects. Line 9 compares the two hours of the Time2 objects. If the hours are different (line 12), then we return this value. If this value is positive, then the first hour is greater than the second and the first time is greater than the second. If this value is negative, then the first hour is less than the second and the first time is less than the second. If this value is zero, the hours are the same and we must test the minutes (and maybe the seconds) to determine which time is greater.

Figure 19.11 sorts a list using the custom Comparator class TimeComparator. Line 11 creates an ArrayList of Time2 objects. Recall that both ArrayList and List are generic types and accept a type argument that specifies the element type of the collection. Lines 1317 create five Time2 objects and add them to this list. Line 23 calls method sort, passing it an object of our TimeComparator class (Fig. 19.10).

Figure 19.11. Collections method sort with a custom Comparator object.

(This item is displayed on pages 926 - 927 in the print version)

 1 // Fig. 19.11: Sort3.java
 2 // Sort a list using the custom Comparator class TimeComparator.
 3 import java.util.List;
 4 import java.util.ArrayList;
 5 import java.util.Collections;
 6
 7 public class Sort3
 8 {
 9 public void printElements()
10 {
11 List< Time2 > list = new ArrayList< Time2 >(); // create List
12
13 list.add( new Time2( 6, 24, 34 ) );
14 list.add( new Time2( 18, 14, 58 ) );
15 list.add( new Time2( 6, 05, 34 ) );
16 list.add( new Time2( 12, 14, 58 ) );
17 list.add( new Time2( 6, 24, 22 ) );
18
19 // output List elements
20 System.out.printf( "Unsorted array elements:
%s
", list );
21
22 // sort in order using a comparator 
23 Collections.sort( list, new TimeComparator() );
24
25 // output List elements
26 System.out.printf( "Sorted list elements:
%s
", list );
27 } // end method printElements
28
29 public static void main( String args[] )
30 {
31 Sort3 sort3 = new Sort3();
32 sort3.printElements();
33 } // end main
34 } // end class Sort3

 

Unsorted array elements:
[6:24:34 AM, 6:14:58 PM, 6:05:34 AM, 12:14:58 PM, 6:24:22 AM]
Sorted list elements:
[6:05:34 AM, 6:24:22 AM, 6:24:34 AM, 12:14:58 PM, 6:14:58 PM]

 

19.6.2. Algorithm shuffle

Algorithm shuffle randomly orders a List's elements. In Chapter 7, we presented a card shuffling and dealing simulation that used a loop to shuffle a deck of cards. In Fig. 19.12, we use algorithm shuffle to shuffle a deck of Card objects that might be used in a card game simulator.

Figure 19.12. Card shuffling and dealing with Collections method shuffle.

(This item is displayed on pages 927 - 929 in the print version)

 1 // Fig. 19.12: DeckOfCards.java
 2 // Using algorithm shuffle.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.Collections;
 6
 7 // class to represent a Card in a deck of cards
 8 class Card
 9 {
10 public static enum Face { Ace, Deuce, Three, Four, Five, Six,
11 Seven, Eight, Nine, Ten, Jack, Queen, King };
12 public static enum Suit { Clubs, Diamonds, Hearts, Spades };
13
14 private final Face face; // face of card
15 private final Suit suit; // suit of card
16
17 // two-argument constructor
18 public Card( Face cardFace, Suit cardSuit )
19 {
20 face = cardFace; // initialize face of card
21 suit = cardSuit; // initialize suit of card
22 } // end two-argument Card constructor
23
24 // return face of the card
25 public Face getFace()
26 {
27 return face;
28 } // end method getFace
29
30 // return suit of Card
31 public Suit getSuit()
32 {
33 return suit;
34 } // end method getSuit
35
36 // return String representation of Card
37 public String toString()
38 {
39 return String.format( "%s of %s", face, suit );
40 } // end method toString
41 } // end class Card
42
43 // class DeckOfCards declaration
44 public class DeckOfCards
45 {
46 private List< Card > list; // declare List that will store Cards
47
48 // set up deck of Cards and shuffle
49 public DeckOfCards()
50 {
51 Card[] deck = new Card[ 52 ];
52 int count = 0; // number of cards
53
54 // populate deck with Card objects
55 for ( Card.Suit suit : Card.Suit.values() )
56 {
57 for ( Card.Face face : Card.Face.values() )
58 {
59 deck[ count ] = new Card( face, suit );
60 count++;
61 } // end for
62 } // end for
63
64 list = Arrays.asList( deck ); // get List 
65 Collections.shuffle( list ); // shuffle deck
66 } // end DeckOfCards constructor
67
68 // output deck
69 public void printCards()
70 {
71 // display 52 cards in two columns
72 for ( int i = 0; i < list.size(); i++ )
73 System.out.printf( "%-20s%s", list.get( i ),
74 ( ( i + 1 ) % 2 == 0 ) ? "
" : "	" );
75 } // end method printCards
76
77 public static void main( String args[] )
78 {
79 DeckOfCards cards = new DeckOfCards();
80 cards.printCards();
81 } // end main
82 } // end class DeckOfCards

 

King of Diamonds Jack of Spades
Four of Diamonds Six of Clubs
King of Hearts Nine of Diamonds
Three of Spades Four of Spades
Four of Hearts Seven of Spades
Five of Diamonds Eight of Hearts
Queen of Diamonds Five of Hearts
Seven of Diamonds Seven of Hearts
Nine of Hearts Three of Clubs
Ten of Spades Deuce of Hearts
Three of Hearts Ace of Spades
Six of Hearts Eight of Diamonds
Six of Diamonds Deuce of Clubs
Ace of Clubs Ten of Diamonds
Eight of Clubs Queen of Hearts
Jack of Clubs Ten of Clubs
Seven of Clubs Queen of Spades
Five of Clubs Six of Spades
Nine of Spades Nine of Clubs
King of Spades Ace of Diamonds
Ten of Hearts Ace of Hearts
Queen of Clubs Deuce of Spades
Three of Diamonds King of Clubs
Four of Clubs Jack of Diamonds
Eight of Spades Five of Spades
Jack of Hearts Deuce of Diamonds

 

Class Card (lines 841) represents a card in a deck of cards. Each Card has a face and a suit. Lines 1012 declare two enum typesFace and Suitwhich represent the face and the suit of the card, respectively. Method toString (lines 3740) returns a String containing the face and suit of the Card separated by the string " of ". When an enum constant is converted to a string, the constant's identifier is used as the string representation. Normally we would use all uppercase letters for enum constants. In this example, we chose to use capital letters for only the first letter of each enum constant because we want the card to be displayed with initial capital letters for the face and the suit (e.g., "Ace of Spades").

Lines 5562 populate the deck array with cards that have unique face and suit combinations. Both Face and Suit are public static enum types of class Card. To use these enum types outside of class Card, you must qualify each enum's type name with the name of the class in which it resides (i.e., Card) and a dot (.) separator. Hence, lines 55 and 57 use Card.Suit and Card.Face to declare the control variables of the for statements. Recall that method values of an enum type returns an array that contains all the constants of the enum type. Lines 5562 use enhanced for statements to construct 52 new Cards.

The shuffling occurs in line 65, which calls static method shuffle of class Collections to shuffle the elements of the array. Method shuffle requires a List argument, so we must obtain a List view of the array before we can shuffle it. Line 64 invokes static method asList of class Arrays to get a List view of the deck array.

Method printCards (lines 6975) displays the deck of cards in two columns. In each iteration of the loop, lines 7374 output a card left justified in a 20-character field followed by either a newline or an empty string based on the number of cards output so far. If the number of cards is even, a newline is output; otherwise, a tab is output.

19.6.3. Algorithms reverse, fill, copy, max and min

Class Collections provides algorithms for reversing, filling and copying Lists. Algorithm reverse reverses the order of the elements in a List, and algorithm fill overwrites elements in a List with a specified value. The fill operation is useful for reinitializing a List. Algorithm copy takes two argumentsa destination List and a source List. Each source List element is copied to the destination List. The destination List must be at least as long as the source List; otherwise, an IndexOutOfBoundsException occurs. If the destination List is longer, the elements not overwritten are unchanged.

Each of the algorithms we have seen so far operates on Lists. Algorithms min and max each operate on any Collection. Algorithm min returns the smallest element in a Collection, and algorithm max returns the largest element in a Collection. Both of these algorithms can be called with a Comparator object as a second argument to perform custom comparisons of objects, such as the TimeComparator in Fig. 19.11. Figure 19.13 demonstrates the use of algorithms reverse, fill, copy, min and max. Note that the generic type List is declared to store Characters.

Figure 19.13. Collections methods reverse, fill, copy, max and min.

(This item is displayed on pages 930 - 931 in the print version)

 1 // Fig. 19.13: Algorithms1.java
 2 // Using algorithms reverse, fill, copy, min and max.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.Collections;
 6
 7 public class Algorithms1
 8 {
 9 private Character[] letters = { 'P', 'C', 'M' };
10 private Character[] lettersCopy;
11 private List< Character > list;
12 private List< Character > copyList;
13
14 // create a List and manipulate it with methods from Collections
15 public Algorithms1()
16 {
17 list = Arrays.asList( letters ); // get List
18 lettersCopy = new Character[ 3 ];
19 copyList = Arrays.asList( lettersCopy ); // list view of lettersCopy
20
21 System.out.println( "Initial list: " );
22 output( list );
23
24 Collections.reverse( list ); // reverse order
25 System.out.println( "
After calling reverse: " );
26 output( list );
27
28 Collections.copy( copyList, list ); // copy List
29 System.out.println( "
After copying: " );
30 output( copyList );
31
32 Collections.fill( list, 'R' ); // fill list with Rs
33 System.out.println( "
After calling fill: " );
34 output( list );
35 } // end Algorithms1 constructor
36
37 // output List information
38 private void output( List< Character > listRef )
39 {
40 System.out.print( "The list is: " );
41
42 for ( Character element : listRef )
43 System.out.printf( "%s ", element );
44
45 System.out.printf( "
Max: %s", Collections.max( listRef ) );
46 System.out.printf( " Min: %s
", Collections.min( listRef ) );
47 } // end method output
48
49 public static void main( String args[] )
50 {
51 new Algorithms1();
52 } // end main
53 } // end class Algorithms1

 

Initial list:
The list is: P C M
Max: P Min: C

After calling reverse:
The list is: M C P
Max: P Min: C

After copying:
The list is: M C P
Max: P Min: C

After calling fill:
The list is: R R R
Max: R Min: R

 

Line 24 calls Collections method reverse to reverse the order of list. Method reverse takes one List argument. In this case, list is a List view of array letters. Array letters now has its elements in reverse order. Line 28 copies the elements of list into copyList, using Collections method copy. Changes to copyList do not change letters, because copyList is a separate List that is not a List view for letters. Method copy requires two List arguments. Line 32 calls Collections method fill to place the string "R" in each element of list. Because list is a List view of letters, this operation changes each element in letters to "R". Method fill requires a List for the first argument and an Object for the second argument. Lines 4546 call Collections methods max and min to find the largest and the smallest element of the collection, respectively. Recall that a List is a Collection, so lines 4546 can pass a List to methods max and min.

19.6.4. Algorithm binarySearch

In Section 16.2.2, we studied the high-speed binary-search algorithm. This algorithm is built into the Java collections framework as a static method of class Collections. The binarySearch algorithm locates an object in a List (i.e., a LinkedList, a Vector or an ArrayList). If the object is found, its index is returned. If the object is not found, binarySearch returns a negative value. Algorithm binarySearch determines this negative value by first calculating the insertion point and making its sign negative. Then, binarySearch subtracts 1 from the insertion point to obtain the return value, which guarantees that method binarySearch returns positive numbers (>=0) if and only if the object is found. If multiple elements in the list match the search key, there is no guarantee which one will be located first. Figure 19.14 uses the binarySearch algorithm to search for a series of strings in an ArrayList.

Figure 19.14. Collections method binarySearch.

(This item is displayed on pages 932 - 933 in the print version)

 1 // Fig. 19.14: BinarySearchTest.java
 2 // Using algorithm binarySearch.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.Collections;
 6 import java.util.ArrayList;
 7
 8 public class BinarySearchTest
 9 {
10 private static final String colors[] = { "red", "white",
11 "blue", "black", "yellow", "purple", "tan", "pink" };
12 private List< String > list; // ArrayList reference
13
14 // create, sort and output list
15 public BinarySearchTest()
16 {
17 list = new ArrayList< String >( Arrays.asList( colors ) );
18 Collections.sort( list ); // sort the ArrayList
19 System.out.printf( "Sorted ArrayList: %s
", list );
20 } // end BinarySearchTest constructor
21
22 // search list for various values
23 private void search()
24 {
25 printSearchResults( colors[ 3 ] ); // first item
26 printSearchResults( colors[ 0 ] ); // middle item
27 printSearchResults( colors[ 7 ] ); // last item
28 printSearchResults( "aqua" ); // below lowest
29 printSearchResults( "gray" ); // does not exist
30 printSearchResults( "teal" ); // does not exist
31 } // end method search
32
33 // perform searches and display search result
34 private void printSearchResults( String key )
35 {
36 int result = 0;
37
38 System.out.printf( "
Searching for: %s
", key );
39 result = Collections.binarySearch( list, key );
40
41 if ( result >= 0 )
42 System.out.printf( "Found at index %d
", result );
43 else
44 System.out.printf( "Not Found (%d)
",result );
45 } // end method printSearchResults
46
47 public static void main( String args[] )
48 {
49 BinarySearchTest binarySearchTest = new BinarySearchTest();
50 binarySearchTest.search();
51 } // end main
52 } // end class BinarySearchTest

 

Sorted ArrayList: [black, blue, pink, purple, red, tan, white, yellow]

Searching for: black
Found at index 0

Searching for: red
Found at index 4

Searching for: pink
Found at index 2

Searching for: aqua
Not Found (-1)

Searching for: gray
Not Found (-3)

Searching for: teal
Not Found (-7)

 

Recall that both List and ArrayList are generic types (lines 12 and 17). Collections method binarySearch expects the list's elements to be sorted in ascending order, so line 18 in the constructor sorts the list with Collections method sort. If the list's elements are not sorted, the result is undefined. Line 19 outputs the sorted list. Method search (lines 2331) is called from main to perform the searches. Each search calls method printSearchResults (lines 3445) to perform the search and output the results. Line 39 calls Collections method binarySearch to search list for the specified key. Method binarySearch takes a List as the first argument and an Object as the second argument. Lines 4144 output the results of the search. An overloaded version of binarySearch takes a Comparator object as its third argument, which specifies how binarySearch should compare elements.

19.6.5. Algorithms addAll, frequency and disjoint

Among others, J2SE 5.0 includes three new algorithms in class Collections, namely addAll, frequency and disjoint. Algorithm addAll takes two argumentsa Collection into which to insert the new element(s) and an array that provides elements to be inserted. Algorithm frequency takes two argumentsa Collection to be searched and an Object to be searched for in the collection. Method frequency returns the number of times that the second argument appears in the collection. Algorithm disjoint takes two Collections and returns true if they have no elements in common. Figure 19.15 demonstrates the use of algorithms addAll, frequency and disjoint.

Figure 19.15. Collections method addAll, frequency and disjoint.

(This item is displayed on pages 934 - 935 in the print version)

 1 // Fig. 19.15: Algorithms2.java
 2 // Using algorithms addAll, frequency and disjoint.
 3 import java.util.List;
 4 import java.util.Vector;
 5 import java.util.Arrays;
 6 import java.util.Collections;
 7
 8 public class Algorithms2
 9 {
10 private String[] colors = { "red", "white", "yellow", "blue" };
11 private List< String > list;
12 private Vector< String > vector = new Vector< String >();
13
14 // create List and Vector
15 // and manipulate them with methods from Collections
16 public Algorithms2()
17 {
18 // initialize list and vector
19 list = Arrays.asList( colors );
20 vector.add( "black" );
21 vector.add( "red" );
22 vector.add( "green" );
23
24 System.out.println( "Before addAll, vector contains: " );
25
26 // display elements in vector
27 for ( String s : vector )
28 System.out.printf( "%s ", s );
29
30 // add elements in colors to list 
31 Collections.addAll( vector, colors );
32
33 System.out.println( "

After addAll, vector contains: " );
34
35 // display elements in vector
36 for ( String s : vector )
37 System.out.printf( "%s ", s );
38
39 // get frequency of "red" 
40 int frequency = Collections.frequency( vector, "red" );
41 System.out.printf( 
42  "

Frequency of red in vector: %d
", frequency );
43
44 // check whether list and vector have elements in common
45 boolean disjoint = Collections.disjoint( list, vector );
46
47 System.out.printf( "
list and vector %s elements in common
",
48 ( disjoint ? "do not have" : "have" ) );
49 } // end Algorithms2 constructor
50
51 public static void main( String args[] )
52 {
53 new Algorithms2();
54 } // end main
55 } // end class Algorithms2

 

Before addAll, vector contains:
black red green

After addAll, vector contains:
black red green red white yellow blue

Frequency of red in vector: 2

list and vector have elements in common

 

Line 19 initializes list with elements in array colors, and lines 2022 add Strings "black", "red" and "green" to vector. Line 31 invokes method addAll to add elements in array colors to vector. Line 40 gets the frequency of String "red" in Collection vector using method frequency. Note that lines 4142 use the new printf method to print the frequency. Line 45 invokes method disjoint to test whether Collections list and vector have elements in common.