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.
|
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
|
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
|
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
|
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
|
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
|
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
|
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
|
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.