Monday, September 27, 2010

Cloning

Cloning

Why clone?

Sometimes you need to make a copy of an object. Most of the time the fact that Java uses references to objects is a great advantage because you don't have to worry about making copies of objects, but sometimes you need a copy.

  • Protect against changes. You need a copy to hand to someone you don't trust to leave the object unchanged.
  • In place of new. The standard way to make new objects is to use the new operator, which calls a class constructor. A different way to think about creating multiple objects of a "class" is to create on prototype and create new objects by copying this prototype, typically by calling on a factory method to create new objects. This is useful if different kinds of objects are distinguished by different parameter values.

    For example, you might want several kinds of arrowheads - filled, empty, diamonds, barbed, etc. With a little planning, code can be written to draw all of these types, differing only in parameter values (isFilled, pointAngle, barbAngle). Different types of graphical objects can simply be created once, and cloned to make a new objects of that "class".

The clone() method - and why you might want to override it

The Object class defines a clone() method that makes a shallow copy of an object.

Protected not public. Even if a shallow copy was sufficient, and it's often not, a user can't get to it because it's protected and not public, so only subclasses can see it, but no users! You can make it available by overriding it in your class and making it public -- you can always make an overridden method more visible that it was in the parent class.

Deep vs. Shallow Copies in java

Deep vs. Shallow Copies

Assignment and copies

Assignment. The assignment operator (=) makes a copy of the "value". For a primitive type (int, double, etc) this simply copies the numeric value, but the assignment of a object copies only the reference (address in memory) of the object.

Sharing immutable objects

One object may have many references to it. If an object is immutable, ie can't be changed, it can safely be shared, and there is no reason to have more than one copy of it. The most common example of this is the String class. All string objects are immutable. This is very useful and is fast because there is no need to copy the contents of the string, but only the reference to it (typically 32 bits). If you need a mutable string, then you can use StringBuilder.

No way to tell if something is immutable

The careful reader of Java keywords may have noticed that there is a const keyword. Mysteriously, this keyword has no use. The intent was to use it to declare things to be unchangeable, but it turned out to be too hard to make this work in an absolutely safe manner. There is no way to know if objects of a class are immutable, except by reading the documentation.

The final keyword allows only one assignment to a variable, but doesn't protect the fields of the object that variable references.

Keywords in java

Reserved words are words that can't be used as identifiers. Many of them are keywords that have a special purpose in Java.

abstractbooleanbreakbytecasecatch
charclassconstcontinuedefaultdo
doubleelseextendsfinalfinallyfloat
forgotoifimplementsimportinstanceof
intinterfacelongnativenewnull
packageprivateprotectedpublicreturnshort
staticstrictfpsuperswitchsynchronizedthis
throwthrowstransienttryvoidvolatile
whileassertenum


A literal in Java technology denotes a constant value. So for example 0 is an integer literal, and
It is important to note the following
  1. const and goto are not currently in use.
  2. null, true, and false are reserved literals but can be considered as reserved words for the purpose of exam.
  3. It is important to understand that Java language is case-sensitive. So even though super is a keyword, Super is not.
  4. All the Java technology keywords are in lower case.
  5. strictfp is a new keyword added in Java 1.2. assert is added in Java 1.4 and enum in Java 5.0

Sunday, September 26, 2010

Invoking Methods

  Suppose you are writing a debugger which allows the user to select and then invoke methods during a debugging session. Since you don't know at compile time which methods the user will invoke, you cannot hardcode the method name in your source code. Instead, you must follow these steps:
  1. Create a Class object that corresponds to the object whose method you want to invoke. See Retrieving Class Objects for more information.
  2. Create a Method object by invoking getMethod upon the Class object. The getMethod method has two arguments: a String containing the method name, and an array of Class objects. Each element in the array corresponds to a parameter of the method you want to invoke. For more information on retrieving Method objects, see Obtaining Method Information
  3. Invoke the method by calling invoke. The invoke method has two arguments: an array of argument values to be passed to the invoked method, and an object whose class declares or inherits the method.
The sample program that follows shows you how to invoke a method dynamically. The program retrieves the Method object for the String.concat method and then uses invoke to concatenate two String objects.
import java.lang.reflect.*;

class SampleInvoke {

public static void main(String[] args) {
String firstWord = "Hello ";
String secondWord = "everybody.";
String bothWords = append(firstWord, secondWord);
System.out.println(bothWords);
}

public static String append(String firstWord, String secondWord) {
String result = null;
Class c = String.class;
Class[] parameterTypes = new Class[] {String.class};
Method concatMethod;
Object[] arguments = new Object[] {secondWord};
try {
 concatMethod = c.getMethod("concat", parameterTypes);
 result = (String) concatMethod.invoke(firstWord, arguments);
} catch (NoSuchMethodException e) {
System.out.println(e);
} catch (IllegalAccessException e) {
System.out.println(e);
} catch (InvocationTargetException e) {
System.out.println(e);
}
return result;
}
}
The output of the preceding program is:
Hello everybody.


Summary of Classes

The following table summarizes the classes that comprise the reflection API. The Class and Object classes are in the java.lang package. The other classes are contained in the java.lang.reflect package.
ClassDescription
ArrayProvides static methods to dynamically create and access arrays.
ClassRepresents, or reflects, classes and interfaces.
ConstructorProvides information about, and access to, a constructor for a class.
Allows you to instantiate a class dynamically.
FieldProvides information about, and dynamic access to, a field of a class
or an interface.
MethodProvides information about, and access to, a single method on a class
or interface. Allows you to invoke the method dynamically.
ModifierProvides static methods and constants that allow you to get
information about the access modifiers of a class and its members.
ObjectProvides the getClass method.
So on the class basis:
For each of these three types of class components -- constructors, fields, and methods -- see here for more--http://www.ibm.com/developerworks/library/j-dyn0603/

The Java Class File Format

Introduction

Compiled binary executables for different platforms usually differ not only in the instruction set, libraries, and APIs at which they are aimed, but also by the file format which is used to represent the program code. For instance, Windows uses the COFF file format, while Linux uses the ELF file format. Because Java aims at binary compatibility, it needs a universal file format for its programs - the Class File format.
The class file consists of some data of fixed length and lots of data of variable length and quantity, often nested inside other data of variable length. Therefore it is generally necessary to parse the whole file to read any one piece of data, because you will not know where that data is until you have worked your way through all the data before it. The JVM would just read the class file once and either store the data from the class file temporarily in a more easily accessed (but larger) format, or just remember where everything is in the class file. For this reason, a surprisingly large amount of the code of any JVM will be concerned with the interpretation, mapping, and possibly caching of this class file format.
Please note that this document is just an overview. The actual Class File format description is in the 'Java Virtual Machine Specification' which can be found online here, or in printed form here.

The Start

The Class file starts with the following bytes:
Length (number of bytes)Example
magic40xCAFEBABE
minor_version20x0003
major_version20x002D
The 'magic' bytes are always set to 0xCAFEBABE and are simply a way for the JVM to check that it has loaded a class file rather than some other set of bytes.
The version bytes identify the version of the Class File format which this file conforms to. Obviously a JVM would have trouble reading a class file format which was defined after that JVM was written. Each new version of the JVM specification generally says what range of Class File versions it should be able to process.

Constant Pool

This major_version is followed by the constant_pool_count (2 bytes), and the constant_pool table.
The constant_pool table consists of several entries which can be of various types, and therefore of variable length. There are constant_pool_count - 1 entries, and each entries is referred to by its 1-indexed position in the table. Therefore, the first item is referred to as Constant Pool item 1. An index into the Constant Pool table can be store in 2 bytes.
Each entry can be one of the following, and is identified by the tag byte at the start of the entry.
TagContents
CONSTANT_Class7The name of a class 
CONSTANT_Fieldref 9The name and type of a Field, and the class of which it is a member.
CONSTANT_Methodref 10The name and type of a Method, and the class of which it is a member.
CONSTANT_InterfaceMethodref 11The name and type of a Interface Method, and the Interface of which it is a member.
CONSTANT_String8The index of a CONSTANT_Utf8 entry.
CONSTANT_Integer34 bytes representing a Java integer.
CONSTANT_Float 44 bytes representing a Java float.
CONSTANT_Long58 bytes representing a Java long.
CONSTANT_Double68 bytes representing a Java double.
CONSTANT_NameAndType12The Name and Type entry for a field, method, or interface.
CONSTANT_Utf812 bytes for the length, then a string in Utf8 (Unicode) format.
Note that the primitive types, such as CONSTANT_Integer, are stored in big-endian format, with the most significant bits first. This is the most obvious and intuitive way of storing values, but some processors (in particular, Intel x86 processors) use values in little-endian format, so the JVM may need to manipulate these bytes to get the data into the correct form.
Many of these entries refer to other entries, but they generally end up referring to one or more Utf8 entries.
For instance, here is are the levels of containment for a CONSTANT_Fieldref entry:
CONSTANT_Fieldref
    index to a CONSTANT_Class entry
        index to a CONSTANT_Utf8 entry
    index to a CONSTANT_NameAndType entry
        index to a CONSTANT_Utf8 entry (name)
        index to a CONSTANT_Utf8 entry (type descriptor)
Note that simple text names are used to identify entities such as classes, fields, and methods. This greatly simplifies the task of linking them together both externally and internally.

The Middle Bit

access_flags (2 bytes)

This shows provide information about the class, by ORing the following flags together:
  • ACC_PUBLIC
  • ACC_FINAL
  • ACC_SUPER
  • ACC_INTERFACE
  • ACC_ABSTRACT

this_class

These 2 bytes are an index to a CONSTANT_Class entry in the constant_pool, which should provide the name of this class.

super_class

Like this_class, but provides the name of the class's parent class. Remember that Java only has single-inheritance, so there can not be more than one immediate base class.

Interfaces

2 bytes for the interfaces_count, and then a table of CONSTANT_InterfaceRef indexes, showing which interfaces this class 'implements' or 'extends'..

Fields

After the interfaces table, there are 2 bytes for the fields_count, followed by a table of field_info tables.
Each field_info table contains the following information:
Length (number of bytes)Description
access_flags2e.g. ACC_PUBLIC, ACC_PRIVATE, etc
name_index2Index of a CONSTANT_Utf8
descriptor_index2Index of a CONSTANT_Utf8 (see type descriptors)
attributes_count2
attributesvariese.g. Constant Value. (see attributes)

Methods

 After the fields table, there are 2 bytes for the methods_count, followed by a table of method_info tables. This has the same entries as the field_info table, with the following differences:
  • The access_flags are slightly different.
  • The descriptor has a slightly different format (see type descriptors)
  • A different set attributes are included in the attributes table - most importantly the 'code' attribute which contains the Java bytecode for the method. (see attributes)

Type Descriptors

Field and Method types are represented, in a special notation, by a string. This notation is described below.

Primitive Types

Primitive types are represented by one of the following characters:
byteB
charC
doubleD
floatF
intI
longJ
shortS
booleanZ
For instance, an integer field would have a descriptor of "I".

Classes

Classes are indicated by an 'L', followed by the path to the class name, then a semi-colon to mark the end of the class name.
For instance, a String field would have a descriptor of "Ljava/lang/String;"

Arrays

Arrays are indicated with a '[' character.
For instance an array of Integers would have a descriptor of "[I".
Multi-dimensional arrays simply have extra '[' characters. For instance, "[[I".

Field Descriptors

A field has just one type, described in a string in the above notation. e.g. "I", or "Ljava/lang/String".

Method Descriptors

Because methods involve several types - the arguments and the return type - their type descriptor notation is slightly different. The argument types are at the start of the string inside brackets, concatenated together. Note that the type descriptors are concatenated without any separator character. The return type is after the closing bracket.
For instance, "int someMethod(long lValue, boolean bRefresh);" would have a descriptor of "(JZ)I". 

Attributes

Both the field_info table and the method_info table include a list of attributes. Each attribute starts with the index of a CONSTANT_Utf8 (2 bytes) and then the length of the following data (4 bytes). The structure of the following data depends on the particular attribute type. This allows new or custom attributes to be included in the class file without disrupting the existing structure, and without requiring recognition in the JVM specification. Any unrecognised attribute types will simply be ignored.
Attributes can contain sub-attributes. For instance, the code attribute can contain a LineNumberTable attribut
Here are some possible attributes:
CodeDetails, including bytecode, of a method's code.
ConstantValueUsed by 'final' fields
ExceptionsExceptions thrown by a method.
InnerClassesA class's inner classes.
LineNumberTableDebugging information
LocalVariableTableDebugging information.
SourceFileSource file name.
SyntheticShows that the field or method was generated by the compiler.

Code attribute

The Code attribute is used by the method_info table. It is where you will find the actual bytecodes (opcodes an operands) of the method's classes.
The attributes has the following structure:
Length (number of bytes)Description
max_stack2Size of stack required by the method's code.
max_locals2Number of local variables required by the method's code.
code_length2
codecode_lengthThe method's executable bytecodes
exception_table_length2
exception_tablevariesThe exceptions which the method can throw.
attributes_count2
attributesvariese.g. LineNumberTable
Each exception table entry has the following structure, each describing one exception catch:
Length (number of bytes)Description
start_pc2Offset of start of try/catch range.
end_pc2Offset of end of try/catch range.
handler_pc2Offset of start of exception handler code.
catch_type2Type of exception handled.
These entries for the Code attribute will probably only make sense to you if you are familiar with the rest of the JVM specification.
source: http://www.murrayc.com/learning/java/java_classfileformat.shtml

Run-Time Type Information and Casts

Rectangle r = new Rectangle (new Point (0,0), 5, 10);
Square s = new Square (new Point (0,0), 15);
 
 
Lets say that square extends rectangle.

Clearly, the assignment
r = s;
is valid because Square is derived from Rectangle.
That is, since a Square is a Rectangle, we may assign s to r.

On the other hand, the assignment
s = r; // Wrong.
is not valid because a Rectangle instance is not necessarily a Square. Consider now the following declarations:
Rectangle r = new Square (new Point (0,0), 20);
Square s;
The assignment s=r is still invalid because r is a Rectangle, and a Rectangle is not necessarily a Square, despite the fact that in this case it actually is!

In order to do the assignment, it is necessary to convert the type of r from a Rectangle to a Square. This is done in Java using a cast operator :
s = (Square) r;
The Java virtual machine checks at run-time that r actually does refer to a Square and if it does not, the operation throws a ClassCastException

To determine the type of the object to which r refers, we must make use of run-time type information  . In Java every class supports the method getClass which returns an instance of java.lang.Class that represents the class of the object.
Thus, we can determine the class of an object like this:
if (r.getClass() == Square.class)
s = (Square) r;
This code does not throw an exception because the cast operation is only attempted when r actually is a Square.
Enhanced by Zemanta

Interfaces in java

Interfaces in java are the pure abstract classes in which functions are given...which are to be implemented by all the class implementing those interface.

Note that in java interface naming is like Iterable, etc...i.e ending with able many times.

Multiple Inheritance in Java

In Java a class can be derived from only one base class. That is, the following declaration is not allowed:
class C extends A, B // Wrong;
{
}
Nevertheless, it is possible for a class to extend a base class and to implement one or more interfaces:
class C extends A 
implements D, E
{
}
 
The derived class c inherits the members of A and it implements all the methods defined in the interfaces D and E.

Inheritance among interfaces in java

Non-static or Member inner class

If a static member class is analogous to a class field or class method, a member class is analogous to an instance field or instance method.

By default, an inner class is non-static:
This fragment defines the class A which contains a non-static inner class B.

A non-static inner class can be instantiated only inside a non-static method of the outer class. This is because every instance of a non-static inner class must be associated with an instance of the outer class. In a sense, every instance of a non-static inner class exists ``inside'' an instance of the outer class. A single instance of the outer class may have associated with it more than one instance of the inner class.
Because an instance of a non-static inner class has an associated instance of the outer class, the methods of the inner class can access directly any of the members (fields or methods) of the outer class instance. For example, the f method defined above can access both x and y directly.
public class A
{
  int y;

  public class B
  {
   int x;
   void f () {}
  }
}
The Java keyword this  can be used in a non-static method to refer to the current object instance. Thus in the method f, this refers to an instance of the inner B class. Every non-static inner class is associated with an instance of A.this.

Use: An Enumeration Implemented as a Member Class
public class LinkedStack {
  // Our static member interface; body omitted here... 
  public static interface Linkable { ... }

  // The head of the list
  private Linkable head;  

  // Method bodies omitted here
  public void push(Linkable node) { ... }
  public Linkable pop() { ... }

  // This method returns an Enumeration object for this LinkedStack
public java.util.Enumeration enumerate() { return new Enumerator(); }

  // Here is the implementation of the Enumeration interface,
  // defined as a member class. 
  protected class Enumerator implements java.util.Enumeration {
    Linkable current;
    // The constructor uses the private head 
    //field of the containing class
   public Enumerator() { current = head; }
   public boolean hasMoreElements() {  return (current != null); }
   public Object nextElement() {
     if (current == null) throw new java.util.NoSuchElementException();
     Object value = current;
     current = current.getNext();
     return value;
   }
  }
}



Restrictions on Member Classes

There are three important restrictions on member classes:
  • A member class cannot have the same name as any containing class or package. This is an important rule, and one not shared by fields and methods.
  • Member classes cannot contain any static fields, methods, or classes (with the exception of constant fields declared both static and final). staticfields, methods, and classes are top-level constructs not associated with any particular object, while every member class is associated with an instance of its enclosing class. Defining a static top-level member within a non-top-level member class simply promotes confusion and bad programming style, so you are required to define all static members within a top-level or static member class or interface.
  • Interfaces cannot be defined as member classes. An interface cannot be instantiated, so there is no object to associate with an instance of the enclosing class. If you declare an interface as a member of a class, the interface is implicitly static, making it a static member class.

New Syntax for Member Classes

The most important feature of a member class is that it can access the instance fields and methods in its containing object. We saw this in theLinkedStack.Enumerator() constructor of above link list example:
public Enumerator() { current = head; }
In this example, head is a field of the LinkedStack class, and we assign it to the current field of the Enumerator class. The current code works, but what if we want to make these references explicit? We could try code like this:
public Enumerator() { this.current = this.head; }
This code does not compile, however. this.current is fine; it is an explicit reference to the current field in the newly created Enumerator object. It is thethis.head expression that causes the problem; it refers to a field named head in the Enumerator object. Since there is no such field, the compiler generates an error. To solve this problem, Java defines a special syntax for explicitly referring to the containing instance of the this object. Thus, if we want to be explicit in our constructor, we can use the following syntax:
public Enumerator() { this.current = LinkedStack.this.head; }
The general syntax is classname.this, where classname is the name of a containing class. Note that member classes can themselves contain member classes, nested to any depth. Since no member class can have the same name as any containing class, however, the use of the enclosing class name prepended to this is a perfectly general way to refer to any containing instance. This syntax is needed only when referring to a member of a containing class that is hidden by a member of the same name in the member class.

Accessing superclass members of the containing class

When a class shadows or overrides a member of its superclass, you can use the keyword super to refer to the hidden member. This super syntax can be extended to work with member classes as well. On the rare occasion when you need to refer to a shadowed field f or an overridden method m of a superclass of a containing class C, use the following expressions:
C.super.f
C.super.m()

This syntax was not implemented by Java 1.1 compilers, but it works correctly as of Java 1.2.

Specifying the containing instance

As we've seen, every instance of a member class is associated with an instance of its containing class. Look again at our definition of the enumerate() method in :
public Enumeration enumerate() { return new Enumerator(); }

When a member class constructor is invoked like this, the new instance of the member class is automatically associated with the this object. This is what you would expect to happen and exactly what you want to occur in most cases. Occasionally, however, you may want to specify the containing instance explicitly when instantiating a member class. You can do this by preceding the new operator with a reference to the containing instance. Thus, the enumerate() method shown above is shorthand for the following:
public Enumeration enumerate() { return this.new Enumerator(); }

Let's pretend we didn't define an enumerate() method for LinkedStack. In this case, the code to obtain an Enumerator object for a given LinkedStackobject might look like this:
LinkedStack stack = new LinkedStack();    // Create an empty stack
Enumeration e = stack.new Enumerator();   // Create an Enumeration for it
The containing instance implicitly specifies the name of the containing class; it is a syntax error to explicitly specify that containing class:
Enumeration e = stack.new LinkedStack.Enumerator();  // Syntax error

There is one other special piece of Java syntax that specifies an enclosing instance for a member class explicitly. Before we consider it, however, let me point out that you should rarely, if ever, need to use this syntax. It is one of the pathological cases that snuck into the language along with all the elegant features of inner classes.
As strange as it may seem, it is possible for a top-level class to extend a member class. This means that the subclass does not have a containing instance, but its superclass does. When the subclass constructor invokes the superclass constructor, it must specify the containing instance. It does this by prepending the containing instance and a period to the super keyword. If we had not declared our Enumerator class to be a protected member of LinkedStack, we could subclass it. Although it is not clear why we would want to do so, we could write code like the following:
// A top-level class that extends a member class
class SpecialEnumerator extends LinkedStack.Enumerator {
  // The constructor must explicitly specify a containing instance
  // when invoking the superclass constructor. 
  public SpecialEnumerator(LinkedStack s) { s.super(); }
    // Rest of class omitted... 
}

Scope Versus Inheritance for Member Classes

We've just noted that a top-level class can extend a member class. With the introduction of member classes, there are two separate hierarchies that must be considered for any class. The first is the classhierarchy, from superclass to subclass, that defines the fields and methods a member class inherits. The second is the containmenthierarchy, from containing class to contained class, that defines a set of fields and methods that are in the scope of (and are therefore accessible to) the member class.
The two hierarchies are entirely distinct from each other; it is important that you do not confuse them. This should not be a problem if you refrain from creating naming conflicts, where a field or method in a superclass has the same name as a field or method in a containing class. If such a naming conflict does arise, however, the inherited field or method takes precedence over the field or method of the same name in the containing class. This behavior is logical: when a class inherits a field or method, that field or method effectively becomes part of that class. Therefore, inherited fields and methods are in the scope of the class that inherits them and take precedence over fields and methods by the same name in enclosing scopes.
Because this can be quite confusing, Java does not leave it to chance that you get it right. Whenever there is a naming conflict between an inherited field or method and a field or method in a containing class, Java requires that you explicitly specify which one you mean. For example, if a member class B inherits a field namedx and is contained within a class A that also defines a field named x, you must use this.x to specify the inherited field and A.this.x to specify the field in the containing class. Any attempt to use the field x without an explicit specification of the desired instance causes a compilation error.
A good way to prevent confusion between the class hierarchy and the containment hierarchy is to avoid deep containment hierarchies. If a class is nested more than two levels deep, it is probably going to cause more confusion than it is worth. Furthermore, if a class has a deep class hierarchy (i.e., it has many superclass ancestors), consider defining it as a top-level class, rather than as a member class.


Static Inner Classes

Consider the following Java code fragment:
public class A
{
int y;

public static class B
{
int x;

void f () {}
}
}
This fragment defines the class A which contains an static inner class B. A static inner class behaves like any ``outer'' class. It may contain methods and fields, and it may be instantiated like this:
A.B object = new A.B ();
This statement creates an new instance of the inner class B.
Given such an instance, we can invoke the f method in the usual way:
object.f();
 
Note:
It is not necessarily the case that an instance of the outer class A exists even when we have created an instance of the inner class. Similarly, instantiating the outer class A does not create any instances of the inner class B.
The methods of a static inner class may access all the members (fields or methods) of the inner class but they can access only static members (fields or methods) of the outer class. Thus, f can access the field x, but it cannot access the field y.

Inner classes in java

In Java it is possible to define one class inside another. A class defined inside another one is called an inner class . Java provides two kinds of inner classes--static and non-static.

Inserting an Element into a Sorted Array

// Create anarray with an ordered list of items
String[] sortedArray = new String[]{"ant", "bat", "cat", "dog"};

// Search for a non-existent item and then insert it
int index = Arrays.binarySearch(sortedArray, "cow");
if (index < 0) { // Compute the insert index
    int insertIndex = -index-1; // Insert the new item into sortedArray. The example here creates
   // a new larger array to hold the new item.
   String[] newSortedArray = new String[sortedArray.length+1];
   System.arraycopy(sortedArray, 0, newSortedArray, 0, insertIndex);
    System.arraycopy(sortedArray, insertIndex, newSortedArray, insertIndex+1, sortedArray.length-insertIndex);
  newSortedArray[insertIndex] = "cow"
  sortedArray = newSortedArray;
}

Finding an Element in a Sorted List in Java

 // Create a list with an ordered list of strings
List sortedList = new LinkedList();
sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"}));
// Search for the word "cat"
int index = Collections.binarySearch(sortedList, "cat"); // 2

// Search for a non-existent element
index = Collections.binarySearch(sortedList, "cow"); // -4
A negative return value indicates that the element is not in the list. However, the actual return value can be used to determine where that non-existent element should be inserted in the list if that were desired; see Inserting an Element into a Sorted List.

Inserting an Element into a Sorted List in java

Although binarySearch() is used to locate existent elements, it can also be used to determine the insert index for non-existent elements. Specifically, the insertion index is computed in the following way: insert-index = (-return-value)-1

// Create a list with an ordered list of items
List sortedList = new LinkedList();

sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"}));

// Search for the non-existent item
int index = Collections.binarySearch(sortedList, "cow"); // -4

// Add the non-existent item to the list
if (index < 0) { sortedList.add(-index-1, "cow"); }

Creating a Sorted Set

A sorted set is a set that maintains its items in a sorted order. Inserts and retrievals are more expensive in a sorted set but iterations over the set is always in order.

// Create the sorted set

SortedSet set = new TreeSet();

// Add elements to the set
set.add("b");
set.add("c");
set.add("a");

// Iterating over the elements in the set
Iterator it = set.iterator();
while (it.hasNext()) {
// Get element
Object element = it.next();
} // The elements are iterated in order: a, b, c

// Create an array containing the elements in a set (in this case a String array).
// The elements in the array are in order.
String[] array = (String[])set.toArray(new String[set.size()]);

Finding an Element in a Sorted Array

// Create an array with an ordered list of strings
String[] sortedArray = new String[]{"ant", "bat", "cat", "dog"};

// Search for the word "cat"
 int index = Arrays.binarySearch(sortedArray, "cat"); // 2

// Search for a non-existent element
index = Arrays.binarySearch(sortedArray, "cow"); // -4

Creating a Type-Specific Map [5.0]

Generics can be used to create a map that will hold only objects of a certain type. This example creates a map whose keys are Integer objects and values are String objects.

Map<Integer, String> map = new HashMap<Integer, String>(); 
map.put(1, "first"); 
map.put(2, "second"); 
// map.put(1, 2); <- Syntax error 
 
 
 
A map declared to hold objects of a type T can also hold objects that extend from T. In this example, a map is created to hold Number objects as keys. Both Integer and Float are subclasses of Number.

Map<Number, String> numMap = new HashMap<Number, String>(); 
numMap.put(.5, "half"); 
numMap.put(1, "first"); 
 
 
Note that although null is not a subclass of any type, if the collection supports null values, it can be added to the type-specific collection.

map.put(null, null); 
 
 
 
A value retrieved from a type-specific collection does not need to be casted. In this example, a URL value is retrieved and used without an explicit cast.

Map<String, URL> urlMap = new HashMap<String, URL>(); 
try { 
            urlMap.put("java", new URL("http://java.com")); 
} catch (MalformedURLException e) { } 
String s = urlMap.get("java").getHost();

Creating a Map That Retains Order-of-Insertion

Map map = new LinkedHashMap();

// Add some elements 
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");
map.put("2", "value4");

// List the entries 
for (Iterator it=map.keySet().iterator(); it.hasNext(); )
{
   Object key = it.next();
  Object value = map.get(key); 
} // [1=value1, 2=value4, 3=value3]

Creating a Hash Map in java

This example shows how to create hash map and perform some operations on it.
// Create a hash table 
Map map = new HashMap(); // hash table
//Map map = new TreeMap(); // you can do sorted
//map as well



// Add key/value pairs to the map
map.put("a", new Integer(1));
map.put("b", new Integer(2));
map.put("c", new Integer(3));


// Get number of entries in map
int size = map.size(); // 2

// Adding an entry whose key exists in the map causes

// the new value to replace the old value
Object oldValue = map.put("a", new Integer(9)); // 1


// Remove an entry from the map and return the value of the removed entry
oldValue = map.remove("c"); // 3


// Iterate over the keys in the map
Iterator it = map.keySet().iterator();
while (it.hasNext()) {
// Get key
Object key = it.next();
} // Iterate over the values in the map
it = map.values().iterator();
while (it.hasNext()) {
// Get value
Object value = it.next();
}


Weak hashmap - Automatically Removing an Unreferenced Element from a Hash Table

When a key is added to a map, the map will prevent the key from being garbage-collected. However, a weak map will automatically remove a key if the key is not being referenced by any other object. An example where this type of map might be useful is a registry where a registrant is automatically removed after it is garbage-collected.

// Create the weak map 
Map weakMap = new WeakHashMap(); 
 
// Add a key to the weak map 
weakMap.put(keyObject, valueObject); 
 
// Get all keys that are still being referenced 
Iterator it = weakMap.keySet().iterator(); 
while (it.hasNext()) { // Get key 
    Object key = it.next(); 
 
The weak map does not automatically release the value if it is no longer used. To enable automatically release of the value, the value must be wrapped in a WeakReference object:

WeakReference weakValue = new WeakReference(valueObject); 
weakMap.put(keyObject, weakValue); 
// Get all keys that are still being referenced and check whether 
// or not the value has been garbage-collected 
it = weakMap.keySet().iterator(); 
while (it.hasNext()) {
// Get key 
Object key = it.next(); 
weakValue = (WeakReference)weakMap.get(key);
if (weakValue == null) 
{ // Value has been garbage-collected 
} else { 
// Get value 
valueObject = weakValue.get(); 
}
}
 

Operation between the two sets in java

// Create the sets
Set set1 = new HashSet();
Set set2 = new HashSet();

// Add elements to the sets ... // Copy all the elements from set2 to set1 (set1 += // set2)
// set1 becomes the union of set1 and set2
set1.addAll(set2);

// Remove all the elements in set1 from set2 (set1 -= set2) // set1 becomes the
// asymmetric difference of set1 and set2
set1.removeAll(set2);

// Get the intersection of set1 and set2
// set1 becomes the intersection of set1 and set2
set1.retainAll(set2);

// Remove all elements from a set
set1.clear();

LinkedHashSet - Creating a Set That Retains Order-of-Insertion

To retain the order of insertion, LinkedHashSet is used.
Example:

Set set = new LinkedHashSet(); 
// Add some elements
set.add("1"); set.add("2"); set.add("3"); set.add("2");

// List the elements
for (Iterator it=set.iterator(); it.hasNext(); )
{
Object o = it.next();
} // [1, 2, 3]

Operations on a set

Create the set

Set set = new HashSet();

 
Add elements to the set

set.add("a");
set.add("b");
set.add("c");



Remove elements from the set

set.remove("c"); 


Get number of elements in set

int size = set.size(); // 2


Adding an element that already exists in the set has no effect
 

set.add("a"); 
size = set.size(); // 2


Determining if an element is in the set

boolean b = set.contains("a"); // true
b = set.contains("c"); // false //


Iterating over the elements in the set

Iterator it = set.iterator();
while (it.hasNext()) {
// Get element
Object element = it.next();
}


Create an array containing the elements in the set (in this case a String array)

String[] array = (String[])set.toArray(new String[set.size()]);

 


 

Sorting a List

// Create a list
String[] strArray = new String[] {"z", "a", "C"};
List list = Arrays.asList(strArray);

// Sort
Collections.sort(list); // C, a, z

// Case-insensitive sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER); // a, C, z

// Reverse-order sort
Collections.sort(list, Collections.reverseOrder()); // z, a, C

// Case-insensitive reverse-order sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
Collections.reverse(list); // z, C, a

Operating on Lists

There are various type of operations that can be performed on lists:

ArrayList example 2

// Create the list
List list = new LinkedList(); // Doubly-linked list
list = new ArrayList(); // List implemented as growable array
// Append an element to the list
list.add("a"); 
// Insert an element at the head of the list
list.add(0, "b"); 
// Get the number of elements in the list
int size = list.size(); // 2 
// Retrieving the element at the end of the list
Object element = list.get(list.size()-1); // a
// Retrieving the element at the head of the
list element = list.get(0); // b
// Remove the first occurrence of an element boolean
b = list.remove("b"); // true
b = list.remove("b"); // false // Remove the element at a particular index element = list.remove(0); // a

Saturday, September 25, 2010

Collection introduction (Index)

1. Some methods of collecting

2. What are collections?


3. Introduction to collections
In Java 1.2, an entirely new set of interfaces and classes was added to the Java libraries to support more sophisticated collections handling. Earlier there were vectors and hashtable and stack...later came Collections, lists, sets and map. Java 5 introduces queue.

4. Interface in Collections
describes the core collection interfaces, which are the heart and soul of the Java Collections Framework. You'll learn general guidelines for effective use of these interfaces, including when to use which interface. You'll also learn idioms for each interface that will help you get the most out of the interfaces.
Some interfaces in this framework:

Interface for object ordering:

5. Implementations in Collections
describes the JDK's general-purpose collection implementations and tells you when to use which implementation. You'll also learn about the wrapper implementations, which add functionality to general-purpose implementations. Some implementations in java collections:
  • Vectors implements RandomAccess //synchronized equivalent of ArrayList
  • AbstractCollection implements Collection, Iterable
  • AbstractList implements List 
  • ArrayList implements RandomAccess 
  • AbstractSequentialList 
  • LinkedList implements Deque 
  • Stack //adds peek,push and pop()
  • AbstractSet implements Set 
  • HashSet 
  • LinkedHashSet
  • TreeSet implements SortedSet
  • EnumSet // Bitset implementation for Enum class. 
  • AbstractQueue implements Queue
  • PriorityQueue
  • ArrayDeque implements Queue Deque

Besides these classes , there is Collections(note plural) or java.util.Collections which has static methods to deal with collections.

6. Algorithms describes the polymorphic algorithms provided by the JDK to operate on collections. With any luck you'll never have to write your own sort routine again!

7. Custom Implementations tells you why you might want to write your own collection implementation (instead of using one of the general-purpose implementations provided by the JDK), and how you'd go about it. It's easy with the JDK's abstract collection.

8. Interoperability tells you how the collections framework interoperates with older APIs that predate the addition of Collections to Java. Also, it tells you how to design new APIs so that they'll interoperate seamlessly with other new APIs. 

9. Class or Interface : When using collections? 

10. Performance of various collections


Examples


Friday, September 24, 2010

blocking queue has the following characteristics:
  • methods to add an item to the queue, waiting for space to become available in the queue if necessary;
  • corresponding methods that take an item from the queue, waiting for an item to put in the queue if it is empty;
  • optional time limits and interruptibility on the latter calls;
  • efficient thread-safety: blocking queues are specifically designed to have their put() method called from one thread and the take() method from another— in particular, items posted to the queue will be published correctly to any other thread taking the item from the queue again; significantly, the implementations generally achieve this without locking the entire queue, making them highly concurrent components;
  • integration with Java thread pools: a flavour of blocking queue can be passed into the constructor of ThreadPoolExecutor to customise the behaviour of the thread pool.
These features make BlockingQueues useful for cases such as the following:
  • a server, where incoming connections are placed on a queue, and a pool of threads picks them up as those threads become free;
  • in a variety of parallel processes, where we want to manage or limit resource usage at different stages of the process.

Queues in Java 5: the Queue interface

Java 5 adds queues to the Collections framework. A queue is in some ways a sub-construct of a list, usually implemented as a linked list, with the following characteristics:
  • unlike a normal list, it is not random access: that is, you can't get or set the element at an arbitrary position in the list;
  • get and set operations always take place at the ends of the queue (generally, one "takes from the head" and "puts on the tail").
In a standard queue, the next item to be taken is the one at the head of the queue, i.e. the one that has been there the longest. When items are added to the queue, they are added to the tail. The item at the tail can only be accessed once all the items placed before it have been removed in order.

Why use a queue?

So you may well be thinking: why use a queue if it has these restrictions? Can't you just use a boring old ArrayList or LinkedList1? It turns out there are at least three main reasons:
  • in some cases, a queue is "conceptually what we want";
  • eliminating random access allows optimisations for concurrency;
  • Java's efficient BlockingQueue implementations can take some of the work out of the most typical use of queues.
Places where we "conceptually" want a queue are where we are dealing with a so-called producer-consumer pattern. That is, one thread "produces" a list of jobs for another thread to pick up. Of course, we could use an ordinary (synchronized) LinkedList if this was purely our motivation. However, it turns out that restricting access to the head and tail of the queue allows for further optimisation for concurrent access.

Queues with thread pools

One place, then, in which queues are useful is for the work queue of a thread pool. Java provides the ThreadPoolExecutor class; when constructing this class, you can pass in the queue that you want the thread pool to use. Or, you can construct your thread pool with one of the utility methods in the Executors class, in which case a default BlockingQueue will be used.

Queue implementations firstly share a new Queue interface, which has several methods for accessing the head and tail of the queue. Recall that items are always placed on the end or "tail" of the list, and always read from the beginning or "head" of the list.
OperationThrows exception
if not possible
Returns value
if not possible
Add item to tailadd()offer()
Remove item from headremove()poll()
"Peek" item at headelement()peek()
Methods specified by the Java Queue interface

Types of Queues

Java provides Queue implementations depending on a few key criteria:
  • thread-safety: if you don't require the queue to be accessed concurrently from multiple threads, then a plain LinkedList can be used as a Queue; the advantage of the other implementations is that they offer efficient thread-safety;
  • blocking or non-blocking: various blocking implementations add extra methods to put and remove items from the queue, blocking until the operation is possible, with an optional time limit;
  • bound or non-bound: sometimes it is useful to put an upper limit on the number of items that can fit in the queue, e.g. to prevent a thread pool from queueing up too many jobs when the machine is busy;
  • other special operations: Java provides an implementation that orders by priority, and another that applies a delay to queued items.
As of Java 6, the various queue classes are as follows:
Queue implementations as of Java 6
Blocking?Other criteriaBoundNon-bound
BlockingNoneArrayBlockingQueueLinkedBlockingQueue
Priority-based PriorityBlockingQueue
Delayed DelayQueue
Non-blockingThread-safe ConcurrentLinkedQueue
Non thread-safe LinkedList
Non thread-safe, priority-based PriorityQueue
One further type of queue not included above is the SynchronousQueue, which is effectively a zero-length queue (so that a thread adding an item to the queue will block until another thread removes the item).

Blocking queues

In general, the most interesting queue implementations are the various blocking queues, which allow efficient concurrent access and are useful for coordinating objects between threads, particularly in the so-called producer-consumer pattern. In Java, all blocking queue implementations implement the BlockingQueue interface, which we look at next.

Thursday, September 23, 2010

ListIterator interface

ListIterator methods

ListIterator is implemented only by the classes that implement the List interface (ArrayList, LinkedList, and Vector). ListIterator provides the following.
ResultMethod Description
Forward iteration
b = it.hasNext() true if there is a next element in the collection.
obj = it.next() Returns the next object.
Backward iteration
b = it.hasPrevious() true if there is a previous element.
obj = it.previous() Returns the previous element.
Getting the index of an element
i = it.nextIndex() Returns index of element that would be returned by subsequent call to next().
i = it.previousIndex() Returns index of element that would be returned by subsequent call to previous().
Optional modification methods. UnsupportedOperationException thrown if unsupported.
it.add(obj) Inserts obj in collection before the next element to be returned by next() and after an element that would be returned by previous().
it.set() Replaces the most recent element that was returned by next or previous().
it.remove() Removes the most recent element that was returned by next() or previous().

So its of form:
public interface ListIterator extends Iterator {
boolean hasNext();
Object next();

boolean hasPrevious();
Object previous();

int nextIndex();
int previousIndex();

void remove(); // Optional
void set(Object o); // Optional
void add(Object o); // Optional
}

The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) are intended to do exactly the same thing in both interfaces. The hasPrevious and previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backwards whereas next moves it forwards.

Here's the standard idiom for iterating backwards through a list:
for (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) {
Foo f = (Foo) i.previous();
...
}
Note the argument to listIterator in the above idiom. The List interface has two forms of the listIterator method. The form with no arguments returns a ListIterator positioned at the beginning of the list, and the form with an int argument returns a ListIterator positioned at the specified index. The index refers to the element that would be returned by an initial call to next. If the index value of n is used, then the initial call to next would return null, since it would point just past the end of the list. An initial call to previous would return the element whose index was index-1.

In a list of length n, there are n+1 valid values for index, from 0 to n, inclusive. 

Intuitively speaking, the cursor is always between two elements, the one that would be returned by a call to previous and the one that would be returned by a call to next. The n+1 valid index values correspond to the n+1 "gaps" between elements, from the gap before the first element to the gap after the last one. The diagram below shows the five possible cursor positions in a list containing four elements.
Element(0)   Element(1)   Element(2)   Element(3)   
^ ^ ^ ^ ^
Index: 0 1 2 3 4
Calls to next and previous can be intermixed, but you have to be a bit careful. The first call to previous after a sequence of calls to next returns the same element as the last call to next. Similarly, the first call to next after a sequence of calls to previous returns the same element as the last call to previous. This will become obvious if you stare at the foregoing text long enough. If it doesn't, go get yourself a steaming hot mug of Java, and try again.

nextIndex and previousIndex
It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used for one of two purposes: To report the position where something was found, or to record the position of the ListIterator so that another ListIterator with identical position can be created.
It should also come as no surprise that the number returned by nextIndex is always one greater than the number returned by previousIndex. This implies the behavior of the two boundary cases: a call to previousIndex when the cursor is before the initial element returns -1, and a call to nextIndex when the cursor is after the final element returns list.size()+1. To make all of this concrete, here's a possible implementation of List.indexOf:
public int indexOf(Object o) {
for (ListIterator i = listIterator(); i.hasNext(); )
if (o==null ? i.next()==null : o.equals(i.next()))
return i.previousIndex();

return -1; // Object not found
}
Note that the indexOf method returns i.previousIndex() though it is traversing the list in the forward direction. This is because i.nextIndex() would return the index of the element that we are about to examine, and we want to return the index of the element that we just examined. The Iterator interface provides the remove operation to remove from the Collection the last element returned by next. The ListIterator interface provides two additional operations to modify the list: set and add. The set method "overwrites" the last element returned by next or previous with the specified element. It is demonstrated by the following polymorphic algorithm to replace all occurrences of one specified value with another:
public static void replace(List l, Object val, Object newVal) {
for (ListIterator i = l.listIterator(); i.hasNext(); )
if (val==null ? i.next()==null : val.equals(i.next()))
i.set(newVal);
}
The only bit of trickiness in this example is the equality test between val and i.next. We have to special-case an val value of null in order to prevent a NullPointerException. The add method inserts a new element into the list, immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:
public static void replace(List l, Object val, List newVals) {
for (ListIterator i = l.listIterator(); i.hasNext(); ) {
if (val==null ? i.next()==null : val.equals(i.next())) {
i.remove();
for (Iterator j = newVals.iterator(); j.hasNext(); )
i.add(j.next());
}
}
}


BAD BAD BAD

Q: What does this loop do? Note mixing of iterator with index.
ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist

int i = 0;
for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
System.out.println(alist.get(i++));
}
A: It throws an exception when it goes beyond the end.
After hasNext() returns true, the only way to advance the iterator is to call next(). But the element is retrived with get(), so the iterator is never advanced. hasNext() will continue to always be true (ie, there is a first element), and eventually the get() will request something beyond the end of the ArrayList. Use either the iterator scheme.
for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
System.out.println(it.next());
}
Or the indexing scheme, but don't mix them.
for (int i=0; i < alist.size(); i++) {
System.out.println(alist.get(i));
}

Chitika