Collections

ActiveNET™

Collection write-up

Enterprise Solution Provider

1. Collection (i) a. -AbstractCollection (c) i. --AbstractList (c) 1. ---Vector (c) a. ----Stack (c) 2. ---ArrayList (c) 3. ---AbstractSequentialList (c) a. ----LinkedList (c) ii. --AbstractSet (c) 1. ---HashSet (c) a. ----LinkedHashSet (c) 2. ---TreeSet (c) b. -List (i) i. --AbstractList c. -Set (i) i. --AbstractSet (c) ii. --SortedSet (i) 1. ---TreeSet (c) iii. --LinkedHashSet (c) 2. Map (i) (Not a sub class of Collection interface) a. --SortedMap (i) i. ---TreeMap (c) b. --AbstractMap (c) i. ---IdentityHashMap (c) ii. ---TreeMap (c) iii. ---HashMap (c) iv. ---TreeMap (c) v. ---WeakHashMap c. --Attributes (c) d. --HashMap (c) i. ---LinkedHashMap (c) ii. ---PrinterStateReasons (c)

www.activenetindia.com

1

ActiveNET™

Collection write-up

Enterprise Solution Provider

e. f. g. h.

--Hashtable (c) --IdentityHashMap --RenderingHints --WeakHashMap

3. Serializable a. -Attribute i. --PrintServiceAttribute 1. ---PrinterStateReasons 4. Comparator a. Collator 5. Iterator a. ListIterator

6. Observer 7. RandomAccess a. ArrayList b. Vector 8. BitSet 9. Calendar a. GregorianCalendar 10. Collections binarySearch(List, Object), copy(List, List), enumeration(Collection), fill(List, Object), max(Collection), ,on(Collection), replaceAll (List, Object old, Object new), reverseOrder(), rotate(List, int distance), sort(List), synchronizedCollection(Collection), synchronizedList(List), synchronizedSet(Set), synchronizedMap(Map), unmodifiableCollection(Collection), unmodifiableList(List), unmodifiableSet(Set), unmodifiableMap(Map) 11. Currency 12. Date 13. Dictionary a. Hashtable i. Properties 14. EventObject 15. ResourceBundle a. ListResourceBundle b. PropertyResourceBundle 16. Locale 17. PropertyPermission 18. Random 19. TimeZone a. SimpleTimeZone 20. Enumeration a. StringTokenizer 21. Timer 22. TimerTask

www.activenetindia.com

2

ActiveNET™

Collection write-up

Enterprise Solution Provider

The primary advantages of a collections framework are that it: • •

• • • •

Reduces programming effort by providing useful data structures and algorithms so you don't have to write them yourself. Increases performance by providing high-performance implementations of useful data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be easily tuned by switching implementations. Provides interoperability between unrelated APIs by establishing a common language to pass collections back and forth. Reduces the effort required to learn APIs by eliminating the need to learn multiple ad hoc collection APIs. Reduces the effort required to design and implement APIs by eliminating the need to produce ad hoc collections APIs. Fosters software reuse by providing a standard interface for collections and algorithms to manipulate them.

The collections framework consists of: 1. Collection Interfaces - Represent different types of collections, such as sets, lists and maps. These interfaces form the basis of the framework. 2. General-purpose Implementations - Primary implementations of the collection interfaces. 3. Legacy Implementations - The collection classes from earlier releases, Vector and Hashtable, have been retrofitted to implement the collection interfaces. 4. Wrapper Implementations - Add functionality, such as synchronization, to other implementations.

www.activenetindia.com

3

ActiveNET™

Collection write-up

Enterprise Solution Provider

5. Convenience Implementations - High-performance "mini-implementations" of the collection interfaces. 6. Abstract Implementations - Partial implementations of the collection interfaces to facilitate custom implementations. 7. Algorithms - Static methods that perform useful functions on collections, such as sorting a list. 8. Infrastructure - Interfaces that provide essential support for the collection interfaces. 9. Array Utilities - Utility functions for arrays of primitives and reference objects. Not, strictly speaking, a part of the Collections Framework, this functionality is being added to the Java platform at the same time and relies on some of the same infrastructure. Collection Interfaces: •

•

•

Collections that do not support any modification operations (such as add, remove and clear) are referred to as unmodifiable. Collections that are not unmodifiable are referred to modifiable. Collections that additionally guarantee that no change in the Collection object will ever be visible are referred to as immutable. Collections that are not immutable are referred to as mutable. Lists that guarantee that their size remains constant even though the elements may change are referred to as fixed-size. Lists that are not fixed-size are referred to as variable-size.

Collection Implementation

Implementations Hash Table Resizable Array Balanced Tree Linked List Set

HashSet

Interfaces List

TreeSet ArrayList

Map HashMap

LinkedList TreeMap

The general-purpose implementations support all of the optional operations in the collection interfaces, and have no restrictions on the elements they may contain. They are unsynchronized, but the Collections class contains static factories called synchronization wrappers that may be used to add synchronization to any unsynchronized collection. All of the new implementations have fail-fast iterators, which detect illegal concurrent modification, and fail quickly and cleanly (rather than behaving erratically). The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide skeletal implementations of the core collection interfaces, to minimize the effort required to implement them. The API documentation

www.activenetindia.com

4

ActiveNET™

Collection write-up

Enterprise Solution Provider

for these classes describes precisely how each method is implemented so the implementer knows which methods should be overridden, given the performance of the "basic operations" of a specific implementation. Annotated outline of Collection Framework •

•

Collection Interfaces - The primary means by which collections are manipulated. o Collection - A group of objects. No assumptions are made about the order of the collection (if any), or whether it may contain duplicate elements. o Set - The familiar set abstraction. No duplicate elements permitted. May or may not be ordered. Extends the Collection interface. o List - Ordered collection, also known as a sequence. Duplicates are generally permitted. Allows positional access. Extends the Collection interface. o Map - A mapping from keys to values. Each key can map to at most one value. o SortedSet - A set whose elements are automatically sorted, either in their natural ordering (see the Comparable interface), or by a Comparator object provided when a SortedSet instance is created. Extends the Set interface. o SortedMap - A map whose mappings are automatically sorted by key, either in the keys' natural ordering or by a comparator provided when a SortedMap instance is created. Extends the Map interface. General-Purpose Implementations - The primary implementations of the collection interfaces. o HashSet - Hash table implementation of the Set interface. The best allaround implementation of the Set interface. It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. o TreeSet Red-black tree implementation of the SortedSet interface. This class implements the Set interface, backed by a TreeMap instance. This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator provided at set creation time, depending on which constructor is used. o ArrayList - Resizable-array implementation of the List interface. Implements all optional list operations, and permit all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.) o LinkedList - Doubly-linked list implementation of the List interface. May provide better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list. Useful for queues and double-ended queues (deques).

www.activenetindia.com

5

ActiveNET™

Collection write-up

Enterprise Solution Provider

HashMap - Hash table implementation of the Map interface. (Essentially an unsynchronized Hashtable that supports null keys and values.) The best all-around implementation of the Map interface. o TreeMap Red-black tree implementation of the SortedMap interface. Wrapper Implementations - Functionality-enhancing implementations for use with other implementations. Accessed soley through static factory methods. o Collections.unmodifiableInterface - Return an unmodifiable view of a specified collection that throws an UnsupportedOperationException if the user attempts to modify it. o Collections.synchronizedInterface - Return a synchronized collection that is backed by the specified (typically unsynchronized) collection. As long as all accesses to the backing collection are through the returned collection, thread-safety is guaranteed. Convenience Implementations - High-performance "mini-implementations" of the collection interfaces. o Arrays.asList - Allows an array to be viewed as a list. o EMPTY_SET, EMPTY_LIST and EMPTY_MAP - constants representing the empty set and list (immutable). o singleton, singletonList, and singletonMap - returns an immutable "singleton" set, list, or map, containing only the specified object (or keyvalue mapping). o nCopies - Returns an immutable list consisting of n copies of a specified object. Legacy Implementations - Older collection classes have been retrofitted to implement the collection interfaces. o Vector - Synchronized resizable-array implementation of the List interface with additional "legacy methods." o Hashtable - Synchronized hash table implementation of the Map interface that does not allow null keys or values, with additional "legacy methods." Special Purpose Implementation o WeakHashMap - an implementation of the Map interface that stores only weak references to its keys. Storing only weak references allows keyvalue pairs to be garbage-collected when the key is no longer referenced outside of the WeakHashMap. This class provides the easiest way to harness the power of weak references. It is useful for implementing "registry-like" data structures, where the utility of an entry vanishes when its key is no longer reachable by any thread. Abstract Implementations - Partial implementations of the collection interfaces to facilitate custom implementations. o AbstractCollection - Skeletal implementation of a collection that is neither a set nor a list (such as a "bag" or multiset). o AbstractSet - Skeletal implementation of a set. o AbstractList - Skeletal implementation of a list backed by a randomaccess data store (such as an array). o AbstractSequentialList - Skeletal implementation of a list backed by a sequential-access data store (such as a linked list). o

•

•

•

•

•

www.activenetindia.com

6

ActiveNET™

Collection write-up

Enterprise Solution Provider

AbstractMap - Skeletal implementation of a map. Algorithms o sort(List) - Sorts a list using a merge sort algorithm, which provides average-case performance comparable to a high-quality quicksort, guaranteed O(n*log n) performance (unlike quicksort), and stability (unlike quicksort). (A stable sort is one that does not reorder equal elements.) o binarySearch(List, Object) - Searches for an element in an ordered list using the binary search algorithm. o reverse(List) - Reverses the order of the elements in the a list. o shuffle(List) - Randomly permutes the elements in a list. o fill(List, Object) - Overwrites every element in a list with the specified value. o copy(List dest, List src) - Copies the source list into the destination list. o min(Collection) - Returns the minimum element in a collection. o max(Collection) - Returns the maximum element in a collection. Infrastructure o Iterators - Similar to the familiar Enumeration interface, but more powerful, and with improved method names. Iterator - In addition to the functionality of the Enumeration interface, allows the user to remove elements from the backing collection with well defined, useful semantics. ListIterator - Iterator for use with lists. In addition to the functionality of the Iterator interface, supports bi-directional iteration, element replacement, element insertion and index retrieval. o Ordering Comparable - Imparts a natural ordering to classes that implement it. The natural ordering may be used to sort a list or maintain order in a sorted set or map. Many classes have been retrofitted to implement this interface. Comparator - Represents an order relation, which may be used to sort a list or maintain order in a sorted set or map. Can override a type's natural ordering, or order objects of a type that does not implement the Comparable interface. o Runtime Exceptions UnsupportedOperationException - Thrown by collections if an unsupported optional operation is called. ConcurrentModificationException - Thrown by iterators and list iterators if the backing collection is modified unexpectedly while the iteration is in progress. Also thrown by sublist views of lists if the backing list is modified unexpectedly. Array Utilities o Arrays - Contains static methods to sort, search, compare and fill arrays of primitives and Objects. o

•

•

•

www.activenetindia.com

7

ActiveNET™

Collection write-up

Enterprise Solution Provider

With the announcement of the Collections API at JavaOne, Josh Bloch, senior staff engineer at Sun Microsystems, introduced a clean, simple, and elegant approach that extends the Java libraries to cover collections of individual objects (sets and lists), as well as collections of object pairs (maps). Although vectors and hashtables worked reasonably well for such aggregations, the new API provides major improvements. First we'll take a look at the interfaces that define the Collections API and the standard Java classes that implement them. We'll see how the API simplifies coding and promotes code reuse. Then we'll discuss some of other advantages this API has over its predecessor APIs. We'll finish with a short discussion of sorting and synchronization. The Interface Definitions The major interfaces in this API are Collection, Set, List, and Map. The following is a short description of each of these interfaces: • • • •

A Set is a collection of objects that is guaranteed not to have any duplicates. A List is a collection of objects in which the order of the elements is preserved. A Collection is a more generic interface for a group of objects that are in no special order and which may include duplicates. A Map contains pairs of objects that are associated with each other

One of the advantages of the Set interface is that it makes it easy to do set-oriented operations. As a result, you can easily construct the union, intersection, or difference between two sets. And, since both the List and Set interfaces derive from Collection, any operation that works on a Collection argument will work equally well on a List or a Set. The Collection interface therefore provides the highest degree of code reuse. When you write a method that takes a Collection as an argument, you can reuse it for a widest possible variety of aggregate data structures. More on Map The key/value pairs in a Map each consist of a "key" object, which is used as an index, and the data value it indexes in the same way that, say, your bank account number is used to look up the value of your bank account. The Map interface is a generalization of the Hashtable class. The Dictionary super class is also a generalization of Hashtable, but because Map is an interface rather than an abstract class like Dictionary, it will find many more uses than Dictionary. The Dictionary class didn't define much in the way of reusable behavior, so there was never much reason to extend it to make a new class. And since Java is a single-inheritance language, that meant you could never extend an existing class and also define it as a "dictionary." So your methods probably always defined Hashtable arguments, rather than Dictionary arguments, because Hashtable was the only "dictionary" you ever used. But Map is an interface. Any class that implements that interface can be treated as a "map," so methods that work on Map arguments also will work for those classes. Therefore, with the new API it becomes worthwhile to write methods that take Map arguments rather than Hashtable arguments. That translates to more reusable code and more code reuse, because future Map objects will work with older methods.

www.activenetindia.com

8

ActiveNET™

Collection write-up

Enterprise Solution Provider

Another feature of a Map is that it has multiple views, where each view is a Collection. You can view the set of keys in the table, the set of key/value pairs the table contains, or the collection of values in the table. The neat thing about these views is that they are not copies of the underlying data in the table, but are instead full-fledged views of it. So changes to any of the views are immediately reflected in the underlying table, and vice versa. Each of the views also is a Collection (a Set of keys, a Set of pairs, or a Collection of values), so operations work on any of the views of a Map -- which in turn affects the underlying Map. The Class Definitions In addition to the interfaces, the java.util class library now includes multiple implementations based on hashtables, arrays, balanced trees ("b-trees"), and linked-list data structures. There is HashSet and HashMap, ArrayList and LinkedList, as well as TreeSet and TreeMap. You choose the interface that gives you the functionality you need, then you choose the implementation for the performance you need. You define variables and parameters using the interfaces, which lets you change implementations at the drop of a hat. For example, instead of coding: Hashtable t = new Hashtable(); You would now write: Map m = new HashMap(); All of the code that uses m is now working with a Map, so you can easily change m to use a TreeMap or any other class that implements the Map interface. For the same reason, you define variables and arguments using the Set and List interfaces. But for maximum generality, you define them using the Collection interface rather than Set or List whenever you can. That allows your code to work with the widest possible variety of collection classes. Additional Improvements In addition to the sheer elegance of the design, the Collections API provides a number of improvements that remove many small thorns from the developer's side: • • •

• • •

Null elements can be inserted into any of the structures. One method, size(), gives the number of elements in any of the collections. You can construct a Sublist view of a list which, as discussed above, is a full-fledged view. Changing one view changes the other. But when you write a method that takes a List as an argument, you don't have to write a second version of the method that takes two arguments to specify a range of items. Instead, you pass it a sublist. That reduces API proliferation. Instead of using getElementAt(), you use the shorter and simpler get(). The new API includes an Iterator interface that replaces enumerations. You use getNext() instead of nextElement(), and hasNext() instead of hasMoreElements(). It's a good API -consistent, regular... and short. The Iterator implementations let you add and remove items while looping, which prevents you from falling into the infinite loops and index-beyond-bounds exceptions that invariably

www.activenetindia.com

9

ActiveNET™

Collection write-up

Enterprise Solution Provider plague you when you enumerate a Vector.

Although they are not actually deprecated, the Enumeration interface, arrays, Vector class, and Dictionary class now are obsolete. (Deprecation would be impossible. There is too much code that uses them and too many changes would be required to that code to use the new APIs.) But now you have the best of all possible worlds. Old code still runs. Future code can be more elegant. And there is no problem whatsoever in translating a Collection into one of the older data structures, or vice versa. The new data structures can be converted to the old data types when they are sent to existing methods, and older data structures that are passed back can be converted to the new data types. So new code and old code can work fine together. Sorting As part of the changes to JDK 1.2, all of the sortable data structures in the standard class library now implement the Comparable interface. The list of sortable classes includes String, Date, File, URL, the numeric "wrapper" classes (like Integer and Float), and the numeric classes in the math package (like BigDecimal). The Collection class defines a sort method that works on any collection of Comparable objects, so you get sorting of all the standard data types. But you can also vary the sort order. Instead of calling the single-argument sort(Collection) method in the Collection class, you can call the dual argument sort(Collection, Comparator) method, where the Comparator object is any object that implements the Comparator interface. That Comparator interface consists of a single compareTo method which you define to get the sort-order you want. For example, if you want odd numbers to sort before even numbers, you define a method that returns -1 (less than) if the first object is odd and the second even, +1 (greater than) if the reverse is true, or zero if they are equal. The Collection implements the Comparator interface to predefine several common variations on the normal sorting order, including reverse-order sorts and case-insensitive String sorts. Synchronization The standard implementations of the Collections API interfaces (HashMap, TreeMap and the like) are defined with no built-in synchronization mechanisms. That way, single-thread applications do not pay the performance cost of unnecessary synchronization, and multithreaded applications that are already using synchronization do not incur the performance penalty that results from multiple synchronization. For simple multithreading applications, an application can use the synchronized "wrapper" classes. For example, instead of creating a object using HashMap(), the app could use SynchronizedHashMap(). That implementation "wraps" a HashMap inside of an object which is synchronized. Developers of multithreading will note that the wrapper classes provide relatively "unsophisticated" synchronization. It allows only one thread at a time to access the HashMap, even though multiple threads could be allowed to do so (if they were using different keys). The "wrapper" implementation also requires an extra method call. To achieve maximum parallelism or maximum performance, therefore, you would subclass one of the existing implementations and add synchronization mechanisms within them. Whether you use the simple synchronized wrappers or provide your own more sophisticated synchronization mechanisms, the bottom line is that now you can choose when to incur the cost of synchronization, instead of having it foisted off on you. To developers obsessed with

www.activenetindia.com

10

ActiveNET™

Collection write-up

Enterprise Solution Provider performance, that will come as great news.

Conclusion The new API provides a powerful and elegant alternative to the often-confusing mixture of APIs used for arrays, Vectors, and Hashtables. It redefines the essence of "good programming practice" in Java, because it means that most every method needs to use the new interfaces and implementation classes instead of the older data structures. Now if the String class would only add a size() method to replace itslength() method! Sigh. But heck, it's down to a pretty minor quibble now, instead of a major annoyance. The new acronym to remember is SLaCS -- String Length and Collection Size. That's better than the old one. You don't even want to know what that one was.

www.activenetindia.com

11

ActiveNET™

Collection write-up

Enterprise Solution Provider

Java Collections API Design FAQ This document answers frequently asked questions concerning the design of the Java collections framework. It is derived from the large volume of traffic on the collectionscomments alias. It serves as a design rationale for the collections framework.

Core Interfaces - General Questions

Why don't you support immutability directly in the core collection interfaces so that you can do away with optional operations (and UnsupportedOperationException)? 2. Won't programmers have to surround any code that calls optional operations with a try-catch clause in case they throw an UnsupportedOperationException? 3. Why isn't there a core interface for "bags" (AKA multisets)? 4. Why don't you provide for "gating functions" that facilitate the implementation of type-safe collections? 5. Why didn't you use "Beans-style names" for consistency?

Collection Interface 1. Why doesn't Collection extend Cloneable and Serializable? 2. Why don't you provide an "apply" method in Collection to apply a given method ("upcall") to all the elements of the Collection? 3. Why didn't you provide a "Predicate" interface, and related methods (e.g., a method to find the first element in the Collection satisfying the predicate)? 4. Why don't you provide a form of the addAll method that takes an Enumeration (or an Iterator)? 5. Why don't the concrete implementations in the JDK have Enumeration (or Iterator) constructors? 6. Why don't you provide an Iterator.add method?

List Interface 1. Why don't you rename the List interface to Sequence; doesn't "list" generally suggest "linked list"? Also, doesn't it conflict with java.awt.List? 2. Why don't you rename List's set method to replace, to avoid confusion with Set.

Map Interface 1. Why doesn't Map extend Collection?

Iterator Interface 1. Why doesn't Iterator extend Enumeration? 2. Why don't you provide an Iterator.peek method that allows you to look at

www.activenetindia.com

12

ActiveNET™

Collection write-up

Enterprise Solution Provider

the next element in an iteration without advancing the iterator?

Miscellaneous 1. Why did you write a new collections framework instead of adopting JGL (a preexisting collections package from ObjectSpace, Inc.) into the JDK? 2. Why don't you eliminate all of the methods and classes that return "views" (Collections backed by other collection-like objects). This would greatly reduce aliasing. 3. Why don't you provide for "observable" collections that send out Events when they're modified?

Core Interfaces - General Questions 1. Why don't you support immutability directly in the core collection interfaces so that you can do away with optional operations (and UnsupportedOperationException)? This is the most controversial design decision in the whole API. Clearly, static (compile time) type checking is highly desirable, and is the norm in Java. We would have supported it if we believed it were feasible. Unfortunately, attempts to achieve this goal cause an explosion in the size of the interface hierarchy, and do not succeed in eliminating the need for runtime exceptions (though they reduce it substantially). Doug Lea, who wrote a popular Java collections package that did reflect mutability distinctions in its interface hierarchy, no longer believes it is a viable approach, based on user experience with his collections package. In his words (from personal correspondence) "Much as it pains me to say it, strong static typing does not work for collection interfaces in Java." To illustrate the problem in gory detail, suppose you want to add the notion of modifiability to the Hierarchy. You need four new interfaces: ModifiableCollection, ModifiableSet, ModifiableList, and ModifiableMap. What was previously a simple hierarchy is now a messy heterarchy. Also, you need a new Iterator interface for use with unmodifiable Collections, that does not contain the remove operation. Now can you do away with UnsupportedOperationException? Unfortunately not. Consider arrays. They implement most of the List operations, but not remove and add. They are "fixed-size" Lists. If you want to capture this notion in the hierarchy, you have to add two new interfaces: VariableSizeList and VariableSizeMap. You don't have to add VariableSizeCollection and VariableSizeSet, because they'd be identical to ModifiableCollection and

www.activenetindia.com

13

ActiveNET™

Collection write-up

Enterprise Solution Provider

ModifiableSet, but you might choose to add them anyway for consistency's sake. Also, you need a new variety of ListIterator that doesn't support the add and remove operations, to go along with unmodifiable List. Now we're up to ten or twelve interfaces, plus two new Iterator interfaces, instead of our original four. Are we done? No. Consider logs (such as error logs, audit logs and journals for recoverable data objects). They are natural append-only sequences, that support all of the List operations except for remove and set (replace). They require a new core interface, and a new iterator. And what about immutable Collections, as opposed to unmodifiable ones? (i.e., Collections that cannot be changed by the client AND will never change for any other reason). Many argue that this is the most important distinction of all, because it allows multiple threads to access a collection concurrently without the need for synchronization. Adding this support to the type hierarchy requires four more interfaces. Now we're up to twenty or so interfaces and five iterators, and it's almost certain that there are still collections arising in practice that don't fit cleanly into any of the interfaces. For example, the collection-views returned by Map are natural delete-only collections. Also, there are collections that will reject certain elements on the basis of their value, so we still haven't done away with runtime exceptions. When all was said and done, we felt that it was a sound engineering compromise to sidestep the whole issue by providing a very small set of core interfaces that can throw a runtime exception. 2. Won't programmers have to surround any code that calls optional operations with a try-catch clause in case they throw an UnsupportedOperationException? It was never our intention that programs should catch these exceptions: that's why they're unchecked (runtime) exceptions. They should only arise as a result of programming errors, in which case, your program will halt due to the uncaught exception. 3. Why isn't there a core interface for "bags" (AKA multisets)? The Collection interface provides this functionality. We are not providing any public implementations of this interface, as we think that it wouldn't be used frequently enough to "pull its weight." We occasionally return such Collections, which are implemented easily atop AbstractCollection (for example, the Collection returned by Map.values). 4. Why don't you provide for "gating functions" that facilitate the

www.activenetindia.com

14

ActiveNET™

Collection write-up

Enterprise Solution Provider

implementation of type-safe collections? We are extremely sympathetic to the desire for type-safe collections. Rather than adding a "band-aid" to the framework that enforces type-safety in an ad hoc fashion, the framework has been designed to mesh with all of the parameterizedtypes proposals currently being discussed. In the event that parameterized types are added to the language, the entire collections framework will support compiletime type-safe usage, with no need for explicit casts. Unfortunately, this won't happen in the the 1.2 release. In the meantime, people who desire runtime type safety can implement their own gating functions in "wrapper" collections surrounding JDK collections. 5. Why didn't you use "Beans-style names" for consistency? While the names of the new collections methods do not adhere to the "Beans naming conventions", we believe that they are reasonable, consistent and appropriate to their purpose. It should be remembered that the Beans naming conventions do not apply to the JDK as a whole; the AWT did adopt these conventions, but that decision was somewhat controversial. We suspect that the collections APIs will be used quite pervasively, often with multiple method calls on a single line of code, so it is important that the names be short. Consider, for example, the Iterator methods. Currently, a loop over a collection looks like this: for (Iterator i = c.iterator(); i.hasNext(); ) System.out.println(i.next());

Everything fits neatly on one line, even if the Collection name is a long expression. If we named the methods "getIterator", "hasNextElement" and "getNextElement", this would no longer be the case. Thus, we adopted the "traditional" JDK style rather than the Beans style.

Collection Interface 1. Why doesn't Collection extend Cloneable and Serializable? Many Collection implementations (including all of the ones provided by the JDK) will have a public clone method, but it would be mistake to require it of all Collections. For example, what does it mean to clone a Collection that's backed by a terabyte SQL database? Should the method call cause the company to requisition a new disk farm? Similar arguments hold for serializable.

www.activenetindia.com

15

ActiveNET™

Collection write-up

Enterprise Solution Provider

If the client doesn't know the actual type of a Collection, it's much more flexible and less error prone to have the client decide what type of Collection is desired, create an empty Collection of this type, and use the addAll method to copy the elements of the original collection into the new one. 2. Why don't you provide an "apply" method in Collection to apply a given method ("upcall") to all the elements of the Collection? This is what is referred to as an "Internal Iterator" in the "Design Patterns" book (Gamma et al.). We considered providing it, but decided not to as it seems somewhat redundant to support internal and external iterators, and Java already has a precedent for external iterators (with Enumerations). The "throw weight" of this functionality is increased by the fact that it requires a public interface to describe upcalls. 3. Why didn't you provide a "Predicate" interface, and related methods (e.g., a method to find the first element in the Collection satisfying the predicate)? It's easy to implement this functionality atop Iterators, and the resulting code may actually look cleaner as the user can inline the predicate. Thus, it's not clear whether this facility pulls its weight. It could be added to the Collections class at a later date (implemented atop Iterator), if it's deemed useful. 4. Why don't you provide a form of the addAll method that takes an Enumeration (or an Iterator)? Because we don't believe in using Enumerations (or Iterators) as "poor man's collections." This was occasionally done in prior releases, but now that we have the Collection interface, it is the preferred way to pass around abstract collections of objects. 5. Why don't the concrete implementations in the JDK have Enumeration (or Iterator) constructors? Again, this is an instance of an Enumeration serving as a "poor man's collection" and we're trying to discourage that. Note however, that we strongly suggest that all concrete implementations should have constructors that take a Collection (and create a new Collection with the same elements). 6. Why don't you provide an Iterator.add method? The semantics are unclear, given that the contract for Iterator makes no guarantees about the order of iteration. Note, however, that ListIterator does provide an add operation, as it does guarantee the order of the iteration.

www.activenetindia.com

16

ActiveNET™

Collection write-up

Enterprise Solution Provider

List Interface 1. Why don't you rename the List interface to Sequence; doesn't "list" generally suggest "linked list"? Also, doesn't it conflict with java.awt.List? People were evenly divided as to whether List suggests linked lists. Given the implementation naming convention, , there was a strong desire to keep the core interface names short. Also, several existing names (AbstractSequentialList, LinkedList) would have been decidedly worse if we changed List to Sequence. The naming conflict can be dealt with by the following incantation: import java.util.*; import java.awt.*; import java.util.List;

// Dictates interpretation of "List"

2. Why don't you rename List's set method to replace, to avoid confusion with Set. It was decided that the "set/get" naming convention was strongly enough enshrined in the language that we'd stick with it.

Map Interface 1. Why doesn't Map extend Collection? This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa). If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs", but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to. Collection could be made to extend Map, but this raises the question: what are the keys? There's no really satisfactory answer, and forcing one leads to an unnatural interface. Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values). While it is, in principle, possible to view a List as a Map mapping indices to elements, this has the nasty property that deleting an element from the List

www.activenetindia.com

17

ActiveNET™

Collection write-up

Enterprise Solution Provider

changes the Key associated with every element before the deleted element. That's why we don't have a map view operation on Lists.

Iterator Interface 1. Why doesn't Iterator extend Enumeration? We view the method names for Enumeration as unfortunate. They're very long, and very frequently used. Given that we were adding a method and creating a whole new framework, we felt that it would be foolish not to take advantage of the opportunity to improve the names. Of course we could support the new and old names in Iterator, but it doesn't seem worthwhile. 2. Why don't you provide an Iterator.peek method that allows you to look at the next element in an iteration without advancing the iterator? It can be implemented atop the current Iterators (a similar pattern to java.io.PushbackInputStream). We believe that its use would be rare enough that it isn't worth including in the interface that everyone has to implement.

Miscellaneous 1. Why did you write a new collections framework instead of adopting JGL (a preexisting collections package from ObjectSpace, Inc.) into the JDK? If you examine the goals for our Collections framework (in the Overview), you'll see that we are not really "playing in the same space" as JGL. Quoting from the "Design Goals" Section of the Java Collections Overview: "Our main design goal was to produce an API that was reasonably small, both in size, and (more importantly) in 'conceptual weight.'" JGL consists of approximately 130 classes and interfaces; its main goal was consistency with the C++ Standard Template Library (STL). This was not one of our goals. Java has traditionally stayed away from C++'s more complex features (e.g., multiple inheritance, operator overloading). Our entire framework, including all infrastructure, contains approximately 25 classes and interfaces. While this may cause some discomfort for some C++ programmers, we feel that it will be good for Java in the long run. As the Java libraries mature, they inevitably grow, but we are trying as hard as we can to keep them small and manageable, so that Java continues to be an easy, fun language to learn and to use.

www.activenetindia.com

18

ActiveNET™

Collection write-up

Enterprise Solution Provider

2. Why don't you eliminate all of the methods and classes that return "views" (Collections backed by other collection-like objects). This would greatly reduce aliasing. Given that we provide core collection interfaces behind which programmers can "hide" their own implementations, there will be aliased collections whether the JDK provides them or not. Eliminating all views from the JDK would greatly increase the cost of common operations like making a Collection out of an array, and would do away with many useful facilities (like synchronizing wrappers). One view that we see as being particularly useful is List.subList. The existence of this method means that people who write methods taking List on input do not have to write secondary forms taking an offset and a length (as they do for arrays). 3. Why don't you provide for "observable" collections that send out Events when they're modified? Primarily, resource constraints. If we're going to commit to such an API, it has to be something that works for everyone, that we can live with for the long haul. We may provide such a facility some day. In the meantime, it's not difficult to implement such a facility on top of the public APIs.

Important points on Collection API are: • • • • • • • • • • • • •

Collection is base interface in Collection API Set and List are the sub interfaces of Collection interface Map is one more interface available in Collection API Iterator is also one more interface available in Collection API Comparator used in implementing sorting algorithms in Collection API SortedSet and SortedMap interfaces to arrange Set and Map elements in order. Each base interface is having Abstract class available like AbstractLIst, AbstractSet and AbstractMap LinkedList follows FIFO sub class of Queue java.util package consists of 16 interfaces, 49 classes and 20 Exception classes TreeMap will maintain Map will be in ascending key order and sorted according to natural order. TreeSet This class implements the Set interface, backed by a TreeMap instance. This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements. SortedMap uses equals() to compare keys where as TreeMap uses Comparable interface function compateTo() for comparison. TreeSet and SortedSet are also same as above

www.activenetindia.com

19

ActiveNET™

Collection write-up

Enterprise Solution Provider

•

• • • • • • • • • •

WeakHashMap A hashtable-based Map implementation with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently than other Map implementations. Both null values and the null key are supported. This class has performance characteristics similar to those of the HashMap class, and has the same efficiency parameters of initial capacity and load factor. List interface contains one interface (ListIterator) List contains 4 sub classes (AbstractList, AbstractSequentialList, ArrayList and LinkedList) Set contains one interface SortedSet) Set contains 6 sub classes (AbstractSet, BitSet, EnumSet, HashSet, LinkedHashSet, and TreeSet) Map interface contains one interface (SortedMap) Map contains 7 sub classes (AbstractMap, EnumMap, HashMap, IdentityHashMap, LinkedHashMap, TreeMap and WeakHashMap) Queue sub classes are (AbstractQueue, PriorityQueue) Stack sub classing from Vector class. Uses LIFO order. Functions are empty(), peek(), push(E) same as v.addElement(Object), pop() and search(Object). Collections class functions are o checked functions [checkedCollection(Collection c, Class c)], o emptyXXX() (emptyList, emptyMap, emptySet), o synchronizedCollection o unmodifiableCollection

www.activenetindia.com

20