Sets
A Set is a Collection that contains unique elements (i.e., no duplicate elements). The collections framework contains several Set implementations, including HashSet and TreeSet. HashSet stores its elements in a hash table, and TReeSet stores its elements in a tree. The concept of hash tables is presented in Section 19.10. Figure 19.18 uses a HashSet to remove duplicate strings from a List. Recall that both List and Collection are generic types, so line 18 creates a List that contains String objects, and line 24 passes a Collection of Strings to method printNonDuplicates.
Figure 19.18. HashSet used to remove duplicate values from array of strings.
(This item is displayed on page 940 in the print version)
|
1 // Fig. 19.18: SetTest.java 2 // Using a HashSet to remove duplicates. 3 import java.util.List; 4 import java.util.Arrays; 5 import java.util.HashSet; 6 import java.util.Set; 7 import java.util.Collection; 8 9 public class SetTest 10 { 11 private static final String colors[] = { "red", "white", "blue", 12 "green", "gray", "orange", "tan", "white", "cyan", 13 "peach", "gray", "orange" }; 14 15 // create and output ArrayList 16 public SetTest() 17 { 18 List< String > list = Arrays.asList( colors ); 19 System.out.printf( "ArrayList: %s ", list ); 20 printNonDuplicates( list ); 21 } // end SetTest constructor 22 23 // create set from array to eliminate duplicates 24 private void printNonDuplicates( Collection< String > collection ) 25 { 26 // create a HashSet 27 Set< String > set = new HashSet< String >( collection ); 28 29 System.out.println( " Nonduplicates are: " ); 30 31 for ( String s : set ) 32 System.out.printf( "%s ", s ); 33 34 System.out.println(); 35 } // end method printNonDuplicates 36 37 public static void main( String args[] ) 38 { 39 new SetTest(); 40 } // end main 41 } // end class SetTest
|
Method printNonDuplicates (lines 2435), which is called from the constructor, takes a Collection argument. Line 27 constructs a HashSet from the Collection argument. Note that both Set and HashSet are generic types. By definition, Sets do not contain any duplicates, so when the HashSet is constructed, it removes any duplicates in the Collection. Lines 3132 output elements in the Set.
Sorted Sets
The collections framework also includes interface SortedSet (which extends Set) for sets that maintain their elements in sorted ordereither the elements' natural order (e.g., numbers are in ascending order) or an order specified by a Comparator. Class treeSet implements SortedSet. The program in Fig. 19.19 places strings into a treeSet. The strings are sorted as they are added to the treeSet. This example also demonstrates range-view methods, which enable a program to view a portion of a collection.
Figure 19.19. Using SortedSets and treeSets.
(This item is displayed on pages 941 - 942 in the print version)
|
1 // Fig. 19.19: SortedSetTest.java 2 // Using TreeSet and SortedSet. 3 import java.util.Arrays; 4 import java.util.SortedSet; 5 import java.util.TreeSet; 6 7 public class SortedSetTest 8 { 9 private static final String names[] = { "yellow", "green", 10 "black", "tan", "grey", "white", "orange", "red", "green" }; 11 12 // create a sorted set with TreeSet, then manipulate it 13 public SortedSetTest() 14 { 15 // create TreeSet 16 SortedSet< String > tree = 17 new TreeSet< String >( Arrays.asList( names ) ); 18 19 System.out.println( "sorted set: " ); 20 printSet( tree ); // output contents of tree 21 22 // get headSet based on "orange" 23 System.out.print( " headSet ("orange"): " ); 24 printSet( tree.headSet( "orange" ) ); 25 26 // get tailSet based upon "orange" 27 System.out.print( "tailSet ("orange"): " ); 28 printSet( tree.tailSet( "orange" ) ); 29 30 // get first and last elements 31 System.out.printf( "first: %s ", tree.first() ); 32 System.out.printf( "last : %s ", tree.last() ); 33 } // end SortedSetTest constructor 34 35 // output set 36 private void printSet( SortedSet< String > set ) 37 { 38 for ( String s : set ) 39 System.out.printf( "%s ", s ); 40 41 System.out.println(); 42 } // end method printSet 43 44 public static void main( String args[] ) 45 { 46 new SortedSetTest(); 47 } // end main 48 } // end class SortedSetTest
|
Lines 1617 of the constructor create a TReeSet of String that contains the elements of array names and assigns the SortedSet to the reference tree. Both SortedSet and TReeSet are generic types. Line 20 outputs the initial set of strings using method printSet (lines 3642), which we discuss momentarily. Line 24 calls treeSet method headSet to get a subset of the TReeSet in which every element is less than "orange". The view returned from headSet is then output with printSet. If any changes are made to the subset, they will also be made to the original treeSet because the subset returned by headSet is a view of the TReeSet.
Line 28 calls treeSet method tailSet to get a subset in which each element is greater than or equal to "orange". The view returned by tailSet is then output. Any changes made through the tailSet view are made to the original treeSet. Lines 3132 call SortedSet methods first and last to get the smallest and largest elements of the set, respectively.
Method printSet (lines 3642) accepts a SortedSet as an argument and prints it. Lines 3839 print each element of the SortedSet using the enhanced for statement.