Saturday, June 28, 2014

Primitive data types of JavaScript

JavaScript is a loosely typed language so you can use a variable without declaring it. JavaScript determines the type based on the value contained in the variable.
JavaScript supports primitive data types along with objects. The simple/primitives types in JavaScript are number, string, boolean, null and undefiend. Everything except these are objects. Before starting on primitive data type; let's understand one of the important operator, typeof.

typeof operator : This operator returns data type of an argument as string.  This can be very helpful in determining the type. The return value of this operator for primitives could be - number, string, boolean or undefined. Apart from this everything else is of type object; so arrays are objects, functions are objects, and of course objects are objects.

Now, we are armed to start on data types in detail:

 Number

JavaScript uses number type to represent floating point numbers as well as integers. So 1 and 1.0 both are same value and of same type. It gets internally represented as 64-bit floating point (same as Java's double). This saves you from type errors because all you need to know about a number is that it is a number. It supports octal (starting with 0) and hex or hexadecimal number (starting with 0x) as well. Below screenshot shows some of the common operations on numbers.


String

In JavaScript, string is sequence of characters placed between either single quote or double quote. All characters are 16 bit wide. It doesn't support character type; so to represent character, make a string with just a single character. Strings in JavaScript are immutable; so once a string is created it can never be changed. It supports attributes and methods as well (just like normal objects).


Boolean

Boolean supports only two values true and false (without quotes). The operator typeof returns "boolean" if the value is either true or false. Boolean is also immutable and has methods just like numbers and strings

Undefined

When you declare a variable but don't initialize it then JavaScript will initialize it behind the scene for you with the value as undefined.

Null

Special data type which can have only one value i.e. null. It means no value. So if a variable has null value; it's still defined (contrary to undefined).


Monday, June 2, 2014

Wildcard in Generics

Generics is confusing (in fact one of the most confusing concepts of Java); and on top of it, wildcards (bounds) is even more confusing. That explains, the reason for this dedicated post :)
In the Generics post; I discussed that subtyping doesn't work with Generics. So, If Apple extends Fruit; list of Apple is not a subtype of list of Fruit. Does it mean that Generics can't be generic and you can't write a method which work for subtype? Luckily, wildcard helps you make Generics really generic.

Bounded Wildcard

Generics uses a wildcard character (?) to work with subtype. Let's go in detail on each.

upper-bounded wildcard: uses wildcard(?), followed by extends keyword, followed by its upper bound. 
List<? extends Number> will work for List of Number and list of its subtype (Integer, Double and Float).

List<Integer> li = new ArrayList<Integer>();
List<? extends Number> list = li;

lower-bounded wildcard: uses wildcard, followed by super keyword, followed by its lower bound. 
List<? super Integer> will work for list of Integer, list of Number and list of Object.

List<Number> ln = new ArrayList<Number>();
List<? super Integer> list1=ln;

Unbounded Wildcard

Using just the wildcard i.e. ? makes it unbounded. It means anything, so equivalent to using raw type. 
<?> says that; i wrote code keeping in mind Generics, but it can hold any type. 

List<?> is a non raw list of some specific type but we don't know what the type is. You can't pass any type. So the type is unknown but it doesn't mean that it can take any shit!

List<Integer> li2 = new ArrayList<Integer>();
List<?> l3 = li2;

 

Code Talk

Time to walk the talk through a simple example.

import java.util.ArrayList;
import java.util.List;

/**
 * Defines Base class Fruit and sub classes Apple and FujiApple. 
 * Uses BoundsGenericsTest for testing wildcard.
 * Save it as BoundsGenericsTest.java
 * 
 * @author Siddheshwar
 * 
 */
class Fruit {
 protected String name;

 public Fruit(String name) {
  super();
  this.name = name;
 }

 public String toString() {
  return name;
 }
}

class Apple extends Fruit {
 public Apple(String name) {
  super(name);
 }
}

class FujiApple extends Apple {
 public FujiApple(String name) {
  super(name);
 }
}

public class BoundsGenericsTest {
 List<? extends Fruit> list;

 public void add(List<? extends Fruit> f) {
  list = f;
 }

 public static void main(String[] args) {
  BoundsGenericsTest obj = new BoundsGenericsTest();

  List<Apple> apples = new ArrayList<Apple>();
  apples.add(new Apple("apple1"));
  apples.add(new Apple("apple2"));

  obj.add(apples);
  System.out.println(" list of Apples: " + obj.list);

  List<FujiApple> fujiApples = new ArrayList<FujiApple>();
  fujiApples.add(new FujiApple("fujiapple1"));
  fujiApples.add(new FujiApple("fujiapple2"));
  obj.add(fujiApples);
  System.out.println(" list of FujiApples : " + obj.list);

  List<? super FujiApple> another = 
                            (List<? super FujiApple>) obj.list;
  System.out.println(" val :" + another);
  List<? super FujiApple> another1 = fujiApples;
  System.out.println(" val :" + another);

  //unbounded wildcard
  List<?> fruits = apples;
  System.out.println("Fruits:" + fruits);
 }
}

Output:
 list of Apples: [apple1, apple2]
 list of FujiApples : [fujiapple1, fujiapple2]
 val :[fujiapple1, fujiapple2]
 val :[fujiapple1, fujiapple2]
Fruits:[apple1, apple2]

Related Post : Java Generics

Sunday, June 1, 2014

TreeMap Implementation in Java

As the name suggests; TreeMap (i.e. TreeMap<K, V>) is a map implementation which is based on a binary search tree. It's an ordered map implementation where keys are comparable.  HashMap doesn't guarantee any order for keys, but TreeMap stores key in a sorted way. This allows you to use queries like find all keys lesser than a given value, find the smallest, largest etc. It sorts the keys in natural order i.e. considers them an instance of a Comparable interface (if Comparable is implemented). During creation, we can also provide an optional Comparator instance(discussed in detail, here). 

This post, I will be focusing mostly on the implementation aspect of TreeMap. It might be helpful to go through earlier post where I have talked about implementation of HashMap and LinkedHashMap.

Building Blocks

Let's cover major components of  TreeMap.

Red-Black Tree: TreeMap uses a Red-Black tree based NavigableMap implementation. A red-black tree is a self-balancing binary search tree; so most of the operations like search, get, put, remove take O(log n) time. This gets guaranteed by ensuring that after every insertion/deletion the upper bound on height is O(log n) i.e. tree is balanced. Red-Black tree colors every node as either red or black and follows certain rules to ensure that the tree remains balanced. Although AVL trees are more balanced compared to the Red-Black tree, Red-Black tree performs better if there are many frequent insertions and deletions.

The tree uses these two techniques for balancing :
  • Recoloring
  • Rotation 
The red-black tree first tries to re-color the node/s to balance the tree; if it doesn't work then it goes for rotation technique.


More details of this tree can be found, wikipedia.
I have discussed generic binary search tree implementation in Java, here.

Entry: Just like HashMap and LinkedHashMap; TreeMap also uses Entry node to store key, values pairs of each entry.

static final class Entry<K,V> implements Map.Entry<K,V>{
        K key;
        V value;         
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;  
        
       //other methods
}

Entry class represents the node of the tree. Along with key and value pairs, it stores references to the left and the right subtree as well. Also, unlike a normal Binary search tree, every node stores reference to its parent. This is required for rotating nodes to balance the tree. And as discussed above; it colors all nodes either red or black. Root node gets colored as black.

Note, one important difference in Entry class of TreeMap compared with HashMap and LinkedHashMap. TreeMap doesn't use hashing to perform operations. (i.e. Entry class doesn't have hash attribute)


Root: Stores the root node of the tree for traversal.
  private transient Entry<K,V> root;

Put Method: Put method is used to inserting key, value pair in the map. Insertion is similar to inserting a new node in the binary search tree. It uses Comparable or Comparator interface to compare key with the key of root node. And based on the returned value (-1, 0 or +1 ) it takes appropriate action. To get an idea of how it works; please go through this post
Another important thing worth mentioning is; after every insertion, TreeMap ensures that the tree is balanced, here.

Get Method: Get also works similar to the get of a binary search tree. Recursively traverses the tree until it finds the node. It traverses by using the binary search tree property (i.e. root.data > root.left.data and root.data < root. right.data).


Related Posts: HashMap Implementation, LinkedHashMap Implementation

--- 
happy learning!!!