"Optional" Implementation on Interface Methods

Some interface definitions state that certain methods are optional. Iterator<E> is an example in Oracle Docs. The method remove() is said optional.

But Java language requires that every method in an interface is implemented by every implementation of that interface. There are no exceptions to this rule. It confused me for this point and I did some research. It turned out that the implementation is not really optional but it can be empty.

Take the remove() method of interface Iterator<E> as en example. The signature is

void remove();

To make this implementation optional, one can do one of following two. Either way, you are implementing the method.

void remove() {
    // empty
}

void remove() {
    throw new UnsupportedOperationException();
}

This is the real meaning of "optional" implementation. Of course, one can choose to actually implement the method like below.

void remove() {
    // do some thing here
    // validate state and remove element
}

Interface Implementation and Class Inheritance

Short note:
If superclass implements some interface and is extended by some subclass, by default the subclass implicitly implemented all methods declared in the interface. Programmers do not need to explicitly specify the implements as in superclass. However, it won't hurt if they do so.

Interface definition:

Superclass definition:

Subclass definition can be either of following two:
(Programmers do not have to override the methods, even explicitly using implements)

Inheritance and Override in Java

Some learning and testing code on Java class inheritance and member override.

Super class in pkg1:

Sub class in pkg2:

Main class for testing in pkg3:

Output:

in super private method1
in sub public method2
in super private method3
in super public method4
in super package-private method5
in sub private method1
in sub public method2
in sub public method3
in super public method4

Some points about inheritance and override in Java:

1. Only public or protected members can be overridden. In above test code, Line 21 in SubClass.java will break if commented out.
2. If moving SubClass and SuperClass to the same package, Line 21 in SubClass.java will work since default access scope is package-private.
3. private or package-private members cannot be overridden. Even they have definitions with same signature, they are different methods and overriding rules and resolution don't apply to them.
4. If calling in subclass, even with super, JVM will try to locate overriding members in subclass. Again, this happens only when the member is declared as public or protected.

How to Implement Singleton in Java

There are multiple solutions for this. Let me describe one by one.

Solution 1:

Solution 2:
Compared to Solution 1, this one is easier to change the singularity if things change.

Solution 3:
Compared to Solutions 1 and 2, this one is lazy instantiation and used double checked locking. Do not synchronize the method instead because for most cases if the instance is already initialized, threads want to return right away. Also, note the volatile in Line 2. This is used to avoid the out-of-order issue of double checked locking solution.

Solution 4:
This is a preferred solution as of Java v5.0.

Synchronized and Unsynchronized Types in Java

Types	Synchronized	Unsynchronized
Hashtable	Y	-
HashMap	-	Y
Vector	Y	-
ArrayList	-	Y
StringBuffer	Y	-
StringBuilder	-	Y

Hashtable & HashMap & HashSet

Hashtable

1. A table of records
2. Stores key-value pairs
3. Implements Map interface
4. Does not allow null key
5. Does not allow null values
6. Synchronized

HashMap

1. Stores key-value pairs
2. Implements Map interface
3. Allows null key (at most one)
4. Allows null values (arbitrary number)
5. Unsynchronized

HashSet

1. A collection of elements
2. Implements Set interface
3. Allows null element (at most one)
4. Unsynchronized

Access Modifiers in Java

Read some notes online, but just to summarize here for later convenient look-up.

There are four levels of accessibility in Java: public, protected, package, and private. From the blog in JavaPapers.com, I am also summarizing in a table below to show the differences.

Access Level	Same Class	Same Package	Subclasses	Other Packages
public	Y	Y	Y	Y
protected	Y	Y	Y	N
package	Y	Y	N	N
private	Y	N	N	N

Besides, below lists some notes about the access modifier usage and default level.

1. Classes can be qualified by public or no modifier only. When qualified without any modifier, by default the access level is package.
2. Interfaces can be qualified by public or no modifier only. When qualified without any modifier, by default the access level is also package.
3. Class methods and fields can be qualified by all, public, protected, private, or no modifier. When qualified without any modifier, by default the access level is package.
4. Interface methods and fields can be qualified by public or no modifier only. When qualified without any modifier, by default the access level is public.
5. Inheritance in Java can be public only and this is the default. Unlike C++, there is no protected or private inheritance.
6. The access specifier for an overriding method can allow more, but not less, access than the overridden method. For example, a protected instance method in the superclass can be made public, but not private, in the subclass.

References

JavaPapers.com

TutorialsPoint

Default access modifier of interface

Inheritance in Java?

Java Tutorial

Variable Length Argument List

Sometimes we need pass along an unknown number of arguments before actually calling the function, such as searching for the minimum of maximum of a list of numbers, or calculating their average. Most programming language are able to first construct an array or list and then pass the constructed object as a single argument. But we can also pass an undefined length of arguments, and this post just summarizes this approach. Different languages provide different ways to deal with this case, and here I am discussing C/C++, Java and Python.

In C/C++, we need the type va_list and macros va_start, va_arg, and va_end. All these are included in the header file <stdarg.h> or <cstdarg>. Below is an example.

In Java, however, we directly append an ellipse after the type name, and then we can give a variable name (which is actually is an array and can be iterated via enhanced for loop in Java).

In Python, programmers have more power than passing an array of arguments: it allows a dictionary of arguments, by which we actually passing both a set of identifier names and their corresponding values. This offers more options to use the variable length arguments.

In summary,

1. The variable length parameters are always placed at the end of parameter list of the function.
2. In C/C++, at least one parameter must be passed and declared in the list. There is no such requirement in Java or Python. Also, in C/C++, the comma or space is not required after the last given parameter.
3. In C/C++, the variable arguments are able to be converted to different types via va_arg, and also this conversion is required for each argument. However, Java will first construct an array of the same type for all the passed arguments. Of course, you can cast the elements if necessary.
4. In Python, the arguments in calling function may become a little bit complex. The general order is that non-keyword arguments should be placed before keyword arguments. Also, there may be explicitly defined or predefined tuple or dict that will be passed as variable arguments, and in general these are always placed after "in-place" arguments. Here is an example.

   def: foo(arg1, arg2, *nonkws, **kws):
       #### function body
   
   pre_Tuple = (pre_nonkw1, pre_nonkw2)
   pre_Dict = {'pre_kw1':pre_v1, 'pre_kw2':pre_v2}
   
   # call function foo()
   foo(val1, val2, nkw1, nkw2, kw1=v1, kw2=v2, *(expl_nkw1, expl_nkw2), **{'expl_kw1':expl_v1, 'expl_kw2':expl_v2})

   or

   foo(val1, val2, nkw1, nkw2, kw1=v1, kw2=v2, *pre_Tuple, **pre_Dict)

   
   The only possibility to reorder the argument list is

   foo(val1, val2, nkw1, nkw2, *(expl_nkw1, expl_nkw2), kw1=v1, kw2=v2, **{'expl_kw1':expl_v1, 'expl_kw2':expl_v2})

   or

   foo(val1, val2, nkw1, nkw2, *pre_Tuple, kw1=v1, kw2=v2, **pre_Dict)

   
   Explicitly defined tuple or dict cannot co-exist with predefined tuple or dict. Only one for each is possible.

Class and Struct

In C, there is no such special thing called class, and class is just an ordinary identifier. For example,

int class=2012;

The struct in C contains data members only, and all of them are visible in the same scope as struct itself.

In Java, there is no such thing called struct, but we can use class to implement struct. The class may contain member functions besides data fields, and programmer is able to declare the visibility for each member.

Interesting while kind of confusing, C++ has them both: class and struct. In many ways, C++ compilers treat them the same. Below are some short notes about class and struct in C++.

1. Both class and struct can have member data and member functions, and are able to specify their visibilities.
2. Both class and struct can inherit from and be inherited by another class or struct. To state more clearly, class can inherit from either class or a struct, and similarly, struct can inherit from either class or struct.
3. Both class and struct may contain pointers to the same class/struct type, but can't contain objects or references of the same class/struct type.
4. Both keywords class and struct can be omitted when declaring objects. While in C, the keywords struct, as well as union and enum, can not be omitted when declaring unless a typedef was used or anonymous variable is being declared.
5. C++ compilers don't distinguish the keywords class and struct in terms of type name. In other words, you may not define a class with name A and then define a struct with name A. The compilers will report "redefinition error". This is also true for struct, union and enum in C, although the keywords must be included for declaration.
6. The members of a class are private by default, and the members of a struct are public by default.
7. The inheritance for a class is also private by default, and the inheritance for a struct is public by default.
8. In C and C++, all definitions for class, struct, union and enum must end with a semicolon ;, while in Java, no such ; outside the closing brace for class and enum definitions. (There is no struct or union in Java.)

TreeSet vs HashSet vs LinkedHashSet

The post here nicely summarized the collections TreeSet, HashSet, and LinkedHashSet in Java. I mostly repeat that.

TreeSet	HashSet	LinkedHashSet
public class TreeSet extends AbstractSet implements SortedSet, Cloneable, Serializable	public class HashSet extends AbstractSet implements Set, Cloneable, Serializable	public class LinkedHashSet extends HashSet implements Set, Cloneable, Serializable
unique values	unique values	unique values
red-black tree	hash table	hash table with double links
ascending order	undefined order	insertion order
\(O(\log n)\) for add, remove and contains	\(O(1)\)	\(O(1)\), a littler slower than HashSet except for the operation of iteration

For more details, please see the reference blog.

References:

Vidya's Blog

Next Number in Order

Problem:
Given a number as string, output the next number in order. The digits you may use are only those already given, plus any number of 0's.

Example:
Given 1234, output 1243;
Given 4321, output 10234.

Solution:
In previous post, I discussed the ways using C++ library function next_permutation. What if we are not allowed to use this function? Can we write de novo code?

First, I tried Java. Since string in Java cannot be updated in place, and hence it needs many auxiliary variables, including StringBuffer objects that can be set at a specific index.

Here is the Java code.

Secondly, I tried to implement this function in C. Suppose the string given was stored in a char array, which is the C style.

Here is the C code.

Related Posts:

Next Number in Order with next_permutation

Collections in Java

First keep in mind that the elements of collections in Java should be reference type only, not primitive type.

There are four types of collections and each type includes several classes.

Type	Classes
List	ArrayList, LinkedList, CopyOnWriteArrayList
Set	HashSet, TreeSet, LinkedHashSet, CopyOnWriteArraySet, ConcurrentSkipListSet
Map	HashMap, TreeMap, LinkedHashMap, ConcurrentHashMap, ConcurrentSkipListMap
Queue	LinkedList, PriorityQueue, SynchronousQueue, DelayQueue, ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, ConcurrentLinkedQueue

Basic approach to choosing a collection:

1. Select the collection type;
2. Select specific class of that type, the one with extra functionality as few as possible.

Step 1: Select collection type

Type	Functionality	Typical uses
List	Essentially a variable-size array; You can usually add/remove items at any arbitrary position; The order of the items is well defined (i.e. you can say what position a given item goes in in the list).	Most cases where you just need to store or iterate through a "bunch of things" and later iterate through them.
Set	Things can be "there or not"— when you add items to a set, there's no notion of how many times the item was added, and usually no notion of ordering.	Remembering "which items you've already processed", e.g. when doing a web crawl; Making other yes-no decisions about an item, e.g. "is the item a word of English", "is the item in the database?" , "is the item in this category?" etc.
Map	Stores an association or mapping between "keys" and "values"	Used in cases where you need to say "for a given X, what is the Y"? It is often useful for implementing in-memory caches or indexes. For example: For a given user ID, what is their cached name/User object? For a given IP address, what is the cached country code? For a given string, how many instances have I seen?
Queue	Like a list, but where you only ever access the ends of the list (typically, you add to one end and remove from the other).	Often used in managing tasks performed by different threads in an application (e.g. one thread receives incomming connections and puts them on a queue; other "worker" threads take connections off the queue for processing); For traversing hierarchical structures such as a filing system, or in general where you need to remember "what data to process next", whilst also adding to that list of data; Related to the previous point, queues crop up in various algorithms, e.g. build the encoding tree for Huffman compression.

Step 2: Select specific class

List

Class	Features/implementation	When to use
ArrayList	Allows elements to be efficiently read by index. Adding/removing the last element is efficient. Not synchronized in any way.	In most cases.
LinkedList	First and last elements can be accessed efficiently; Other elements cannot be efficiently accessed by index; Not synchronized in any way.	Effectively, functions as a non-synchronized queue. In practice, rarely used: when you need a queue, you often need it to be concurrent or to provide other functionality; other implementations are often more useful.
CopyOnWriteArrayList	Allows safe concurrent access; Reads are efficient and non-blocking; Modifications are not efficient (since a brand new copy of the list is taken each time).	Where you need concurrent access and where frequency of reads far outweights frequency of modifications.

Set

Ordering of keys	Non-concurrent	Concurrent
No particular order	HashSet	—
Sorted	TreeSet	ConcurrentSkipListSet
Fixed	LinkedHashSet	CopyOnWriteArraySet

Map

Ordering of keys	Non-concurrent	Concurrent
No particular order	HashMap	ConcurrentHashMap
Sorted	TreeMap	ConcurrentSkipListMap
Fixed	LinkedHashMap	—

Queue

Blocking?	Other criteria	Bound	Non-bound
Blocking	None	ArrayBlockingQueue	LinkedBlockingQueue
	Priority-based		PriorityBlockingQueue
	Delayed		DelayQueue
Non-blocking	Thread-safe		ConcurrentLinkedQueue
	Non thread-safe		LinkedList
	Non thread-safe, priority-based		PriorityQueue

Reference:

http://www.javamex.com/tutorials/collections/how_to_choose.shtml

Nested Class or Function Definition?

(Short Notes)

Class composition is of course allowed for object-oriented programming languages. Also, the nested definition for classes is allowed in C++, Java and Python (from my own experience, and other languages may also support this).

But for nested function definition, there are some differences. For C++ and Java, neither allows nested function definition. However, Python does allow nested definition for functions, but such nested functions are only available within the outer function body, unlike the nested class definition which can be accessed from other scopes if defined properly (like defined as public).

Of course, nested function calls are always allowed.

Update:
Function defined in class?
==> member functions

Class defined in function?
==> local classes (link)

In this sense, it's allowed to define member functions of a local class in an enclosing function.

References:

IBM publib

Related Posts:

Class Templates in C++

Array Declaration and Initialization in C++ and Java

There are several ways to declare and initialize arrays, including the pointers in C++. The syntax for C++ and Java is kind of similar, but different and sometimes confusing. There are no pointers in Java, but the array variables in Java work like pointers in the sense that they both store the addresses and may change. The array names in C++ are constants and fixed at the time of declaration.

For 2- or higher dimensional arrays, the "array constant" way in C++ will give real arrays, and each array will take a contiguous block in memory. Because of this, multiple-dimension arrays can be treated as one-dimension in C++. For the same reason, programmers need know the size of array at the time of declaration. However, for Java arrays, the lengths of each element in a 2-D array can be totally different, where each element is a 1-D array. Hence, in Java, multiple-dimension arrays cannot be treated as one-dimension at all.

Here, I list and compare the ways to declare and initialize arrays in C++ and Java.

Statements	C++	Java
int array[5];	Y	N
int[5] array;	N	N
int array[];	N	Y
int[] array;	N	Y
int array[5] = {1,2,3,4,5};	Y	N
int array[] = {1,2,3,4,5};	Y	Y
int[] array = {1,2,3,4,5};	N	Y
int array[5] = new int[5];	N	N
int array[] = new int[5];	N	Y
int array[] = new int[5]{1,2,3,4,5};	N	N
int array[] = new int[]{1,2,3,4,5};	N	Y
int* array;	Y	N
int* array = new int[5];	Y	N
int* array = new int[]{1,2,3,4,5};	N	N
int* array = new int[5]{1,2,3,4,5};	N	N
int* array1, array2;	array2 is int	N
int[] array1, array2;	N	array2 is int[]
int []array1, array2;	N	array2 is int[]
int array1[], array2;	N	array2 is int
int []array1, []array2;	N	N
int []array1, array2[];	N	array2 is int[][]

Summary:

1. In C++, array name is a constant; in Java, array name is a variable.
2. In C++, pointers can be used for an array; in Java, there are no pointers.
3. In C++, brackets must appear after array name for declaration and access; in Java, brackets can appear before the array name for declaration.
4. In C++, if the array is not initialized during declaration, the size must be specified; in Java, no constants can exist within brackets when declaration.
5. In C++, initialization cannot be done using new for an array (not pointer here); in Java, this is possible, like the initialization of a pointer in C++.
6. In Java, if use new to initialize an array, the size in brackets and the value array cannot appear at the same time; otherwise, Java compiler doesn't know how to decide the size.
7. In C++, if use new to initialize a pointer array, no customized array can be specified. Instead, all elements of the array will be initialized with the default constructor. If the type doesn't have a default constructor, this is a compile-time error.
8. In C++, the * after type only specifies the first pointer variable; in Java, the [] after type specifies all array variables in that declaration line.
9. In Java, if declare more than one variables in a single line, all brackets for the second to last variables must be placed after the variable name, and the brackets before the first variable will apply to all variables in the line.

Related Posts:

new and delete

Object Initialization