My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
Paid Surveys
|
updatable collections in java
Posted Date: 20 May 2008 Resource Type: Articles/Knowledge Sharing Category: Education
|
Posted By: mohit Member Level: Gold
Rating:  Points: 1
|
|
|
UpdatableCollections
Updatable collections are `normal' mutable collections. They:
Allow insertion, removal, and/or replacement of elements in accordance with their element semantics. Some such operations (like clear, take) are common to all updatable classes.
Maintain a `version number' that changes upon each successful modification.
Produce elements() enumerations that contain consistency checks, invalidating the enumeration if the base collection has been changed during the course of a traversal.
UpdatableSets
Updatable collections maintaining Set semantics. They support an `include' operation that adds an element if not present, plus a version that includes all elements from a supplied Eunumeration.
UpdatableBags
Updatable collections with an add(v) operation, that adds an occurrence of v to the collection, and addIfAbsent that only conditionally adds the element.
UpdatableSeqs
Seqs with standard indexed update operations (insertAt, replaceAt, removeAt). They also support method insertElementsAt(int index, Enumeration e) that adds all elements of e, in order, at position index. UpdatableSeqs also support special (often more efficient) methods operating on the front and back of the sequence,
UpdatableMaps
Maps with update operations, principally putAt(key, element) and removeAt(key).
SortableCollections
A `mixin' for collections that support a sort operation that accepts a Comparator. The difference between Sorted and Sortable is that (Element- or Key-) SortedCollections are always in sorted order, while Sortable ones may be sorted (via sort(Comparator cmp)), but may then be altered in ways so they are no longer sorted.
Generally, implementations are written at the point in the interface hierarchy that they most naturally support. They mainly use classic data structure implementation techniques, with an emphasize safety and correctness, but with enough efficiency that you will not usually have to build your own special-case data structures.
Currently, there are no `wrapped' implementation types that allow one implementation to serve as another kind of collection. You can always build these yourself. For example, it's possible to have an RBTree serve as the underlying implementation for a Set by making, say, an RBSet class holding a reference to an RBTree, and forwarding include as addIfAbsent, and so on. Similarly, there are not any Seq-like classes (like Stack or Queue) that ONLY support operations on the front or back, since you can just use UpdatableSeqs for such purposes merely by not using those other operations; or if you like, making a special class holding an UpdatableSeq and forwarding it only selected messages.
The reason there are so many different implementation types it that, in the collections business, it's not the case that one size fits all. Different Implementations have different time/space tradeoffs, and different operations they are particularly good and bad at. The basic strategy for building a collection package is to force all of these implementations to share common interfaces, so that only the person doing the initial construction of a collection object that will be passed around and used polymorphically has to care about these issues. If you do not care, just use the ones handed out by DefaultImplementations, which makes pretty reasonable choices. If you do care, be sure to look over the time complexities listed in the documentation for each implementation class.
Forcing implementations to share common interfaces is a standard OO trick, but sometimes leads to classes providing methods that they'd almost rather not support. For example LinkedLists support indexed access of the elements of the list. This is pretty slow. You'd only use a LinkedList if you only rarely need to access by index.
All current implementations are subclasses of UpdatableImpl a convenient abstract class that provides default implementations of many UpdatableCollection operations.
Also, all current UpdatableCollection classes implement constructive operations (excluding, adding, etc) by cloning full copies, which is not very fast.
Current implementations include:
HashedSets implement UpdatableSet
Standard implementation of hash tables of single elements.
RBTrees implement UpdatableBag, ElementSortedCollection
Implementation of red-black trees, a form of balanced sorted binary search tree.
LinkedLists implement UpdatableSeq, SortableCollection
Standard implementation of linked lists.
CircularLists implement UpdatableSeq
Standard implementation of double-linked circluar lists.
Dynarrays implement UpdatableSeq, SortableCollection
Buffered array that dynamically resizes when necessary.
LinkedBuffers implement UpdatableBag
An expandable list of array-based buffers.
HashedMaps implement Map
Hash Table of keyed elements,
LLMaps implement Map
LinkedLists of (key, element) pairs supporting Map operations.
RBMaps implement Map, KeySortedCollection
Red-Black trees of keyed elements
These implementation classes contain only methods described in their interfaces, plus, in most cases, a few special `tuning' methods that let you override default properties of the underlying data structures. These include:
Hash tables: methods to determine and set the number of buckets and the loadFactorThreshold.
Linked buffers: methods to determine and set the chunkSize for buffers.
Dynarrays: methods to determine and set the capacity of the underlying arrays
Red-black trees: methods to reset the elementComparator or keyComparator used for ordering.
Many of the implementation classes themselves rely on yet lower-level classes of basic data structures. These classes are also made public in this package, so that you can use them as the building-blocks of other Collection implementations. They currently include:
Cell
A simple box holding an Object
LLCell
Cells with next-pointers. Each cell knows how to do basic linked list operations like insert another LLCell after itself.
LLPair
An extension of LLCell in which each node has a key
CLCell
A cell with next- and prev- pointers, and operations so that objects maintain themselves in proper circular list order.
RBCell
A cell with red-black-tree pointers and color, and methods to add new RBCells, properly rebalancing the tree it is in upon insertion. And so on
RBPair
RBCells with keys.
|
Responses
|
| Author: Abdul Sathar 20 May 2008 | Member Level: Gold Points : 2 | useful and informative article.
| | Author: mohit 20 May 2008 | Member Level: Gold Points : 2 | thanks abdul
| | Author: Vidya 21 May 2008 | Member Level: Diamond Points : 2 | Good article
| | Author: Shyni 31 May 2008 | Member Level: Gold Points : 2 | This is great Information, Thanks for your effort to share it with everyone.
|
|
|