Tuesday, 23 May 2017

Print binary tree in Spiral order

Background

Sometime back we had seen how to traverse a binary tree and print it. We saw -
  • Pre-order 
  • post-order
  • In-order
  • level order traversals
Binary Tree Traversal

In this post we will see how to print them in a spiral order.  Consider following tree -




We need to print the tree in following order - 1, 2, 3, 4, 5, 6, 7.




Code

Following recursive approach will help achieve this. Idea is to keep a boolean toggle param to print nodes either from left to right or right to left.


    public static int getHeight(BTreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.getLeft());
            int rightHeight = getHeight(root.getRight());
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    }


    /**
     * 
     * @param root
     *            if the btrr Worst case time complexity - O(N^2) for skewed
     *            trees No extra space
     */
    public static void printSpiralRecurssive(BTreeNode root) {
        boolean leftToRight = false;
        int height = getHeight(root);
        for (int i = 1; i <= height; i++) {
            printLevelRecurssive(root, i, leftToRight);
            leftToRight = !leftToRight;
        }
    }

    public static void printLevelRecurssive(BTreeNode root, int level, boolean leftToRight) {
        if (level == 1) {
            System.out.println(root.getData());
        } else {
            if (leftToRight) {
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
            } else {
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
            }
        }
    }

Logic : We first calculate the height of the tree which are basically levels. We then iterate from 1 to height (basically all levels) and print them from left to right or right to left based on the boolean toggle. We toggle this value after each level. For each recursive call we start from root and we go down till we reach the level we want it to be (one next to previously iterated on) based on the height and print nodes.

Complete solution with example is provide under my github repo of Data Structures -
In the same link there is a recursive solution as well that takes O(N) extra space to give same result. Iterative solution  -

private static Stack<BTreeNode> leftToRight = new Stack<>();
private static Stack<BTreeNode> rightToLeft = new Stack<>();
public static void printSpiralIterative(BTreeNode root) {

        rightToLeft.push(root);

        while (!rightToLeft.isEmpty() && !leftToRight.isEmpty()) {
            while (!rightToLeft.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    leftToRight.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    leftToRight.push(node.getRight());
                }
            }

            while (!leftToRight.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    rightToLeft.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    rightToLeft.push(node.getRight());
                }
            }
        }

}


Let me know if you have any questions.

Related Links

Saturday, 20 May 2017

How ConcurrentHashMap Works Internally in Java

Background

In one of the previous posts we saw how HashMap works -
and how it's time complexity of insertion and deletion is O(1) is normal case. Though this is a great data structure to work with in terms of time complexity it is not thread safe which means you cannot use it directly in multi threaded environments without taking additional precautions like synchronizing put/get on your own. Instead Java has provided a thread safe implementation of concurrent hashmap. We can directly use it in case of multi threaded environments for thread safety. Eg. in case of parallel stream introduced in java 8.

How ConcurrentHashMap Works Internally in Java

Before we see how it is implemented in Java lets give it some though. What are possible problems with a HashMap. Race condition, invalid state. Lets say two writes happen at the same time. Since write is not an atomic operation one value may overwrite other and Map may go in inconsistent state. We can obviously add synchronization over read/writes of a HashMap but it would be very inefficient and have performance impact. I would be like single threaded application certainly the behavior we don't expect. To solve this issue Java provides ConcurrentHashMap that has built in thread safety. Let see how -

We know how HashMap works. Internally it stores an array of Entry object which essentially has key, value and pointer to next Entry object (linked list used in case of collision). You can think of each array element as bucket and each Entry object as a data point containing key (in case 2 keys have same hash - collision), value  and pointer to next data element. 

Working :
ConcurrentHashMap as the name suggests allows concurrent read/writes to the Map. But there are limitations. ConcurrentHashMap maintains another data structure internally called segments. Each bucket of HashMap is part of one of the segments. Number of segments is called Concurrency-Level which determines number of thread that can write simultaneous. This Segments gets locked when writing/updating/removing data. Think of Segments as locks used to prevent concurrent write to same bucket of hashmap leading to inconsistency. So as long as write to concurrent hashmap is on different segments it can happen in parallel. Reads are completely lock free i.e No need to acquire lock for reading. Last updated value is returned.


 Now lets go step by step -

 Concurrency-Level , Segment array and initialization :
  • First when you create a ConcurrentHashMap you can provide concurrency level. This determines size of Segment array. Size of segment array will always be equal or more than the concurrency level. If this is not provided default is used - 
    • static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
  • Note that the size of segment table will always be power of 2. So if you give  concurrency level as 10 then next best power of 2 match will be picked up i.e 16 and Segment array of size 16 will be created which implies 16 threads can simultaneously operate on the map.
static final class Segment<K,V> extends ReentrantLock implements Serializable {

    //The number of elements in this segment's region.
    transient volatile int count;
    //The per-segment table. 
    transient volatile HashEntry<K,V>[] table;
}

Putting element in ConcurrentHashMap :

  • For putting element in Map we first need to determine which segment the element should be processed for. For this we first get hascode of the key. Next we do a rehash of the existing hash to ensure
     /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because ConcurrentHashMap uses power-of-two length hash tables,
     * that otherwise encounter collisions for hashCodes that do not
     * differ in lower or upper bits.
     */
    private static int hash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }
  •  Once hash is calculated you can get the segment which it belongs to and delegate put method to segments put method as follows -
    public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

    final Segment<K,V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }


We will see how segment is computed in some time with a proper example. Once put is delegated to segment , segment will add it to the appropriate bucket in the segment.

        V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }


Now this is very interesting method. Lets understand whats happening here.

  • First call is to lock(). Since it is a write/update operation on a bucket of same segment we need a lock. If you recollect Segment class it extends ReentrantLock so each segment is a lock. So you can call lock() and unlock() directly in Segment class.
  • Next it's like a normal HashMap. You find the index of the Entry table where your elements hash falls and add it there as linked list.
  • You can see similar code has HashMap that updates value if key is same, inserts in array if there is no element in the table and adds it in the linked list of the table if element already exists.
  • Finally once operation is complete it calls unlock() so that other threads can continue update.
  • Note the lock is a blocking call. 
  • You can also see call for rehash if threshold is reached. Like Entry array Segment also has a threshold and when it is reached Segment array is resized for performance. That's what rehash. 
NOTE : For getting index of Segment table first n bits are used where as for getting index of Entry table last N bits are used from enhanced hash integer (See details in example below).

Getting element from  ConcurrentHashMap : 

Get on ConcurrentHashMap is very simple no locks involved. You simply read the data and return -

        public V get(Object key) {
                int hash = hash(key.hashCode());
                return segmentFor(hash).get(key, hash);
        }

        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }


NOTE  : readValueUnderLock method is used as a backup in case a null (pre-initialized) value is ever seen in an unsynchronized access method.

Example

Above was just all code and some understanding. Now lets take an actual example.

Let's say we have created a ConcurrentHashMap with concurrency level lets say 10. Based on this Segment array will be created based on following code -

    private static void printSegmentDetails(int concurrencyLevel) {
        int sshift = 0;
        int segmentMask = 0;
        int segmentShift = 0;

        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        segmentShift = 32 - sshift;
        segmentMask = ssize - 1;
        System.out.println("Segment array size :" + ssize);
        System.out.println("segmentShift : " + segmentShift);
        System.out.println("segmentMask : " + segmentMask);
    }


Output for 10 concurrency level:
Segment array size : 16
segmentShift : 28
segmentMask : 15

NOTE  :As mentioned before segment array is of size 2^n such that 2^n >= concurrency level. In this case 2^4

Now that we have segment table in place lets simulate put. We need to put a String called "Aniket" as key. We don't care about value. Just make sure it's not null.

  1. First we will calculate hascode of the key.
  2. Then hash it so for better hash (as mentioned above)
  3. Then based on the result hash we will find which segment will it belong
Remember of Segment table was >= 2^N we now want first N bits to determine which segment this hash falls into. Since N bits will vary from 1 - 2^N which is our segment array size. Also remember code to get this index from above? -
  • int segmentIndex = (hash >>> segmentShift) & segmentMask
This essentially means logically right shift hash with segmentShift bits. Since int is 32 bit and segmentShift = 32 - sshift, hash >>> segmentShift will essentially give you first sshift bits (sshift is nothing but N in 2^N we saw above). segmentMask is to get the N bits post shift.

So in this case,
N  = sshift =  4
2^N = 16 -> Size of segment array
segmentShift = 32 - 4 = 28 (as we saw in output above)
segmentMask = 16 -1 - 15

    public static void main(String args[]) {    
        String key = "Aniket";
        //hascode of key
        System.out.println(key.hashCode());
        //better hash
        System.out.println(hash(key.hashCode()));
        //better hash in binary
        System.out.println(Integer.toBinaryString(hash(key.hashCode())));
        //logical right shift by segmentShift
        System.out.println("Right shifter hash : " + Integer.toBinaryString(hash(key.hashCode()) >>> 28));
        // segment index as binary and of right shift and segmentMask
        System.out.println("Segment Index : " + Integer.toBinaryString((hash(key.hashCode()) >>> 28 ) & 15));
        // segment index as decimal
        System.out.println("Segment Index : " + ((hash(key.hashCode()) >>> 28 ) & 15));
    }


Output :
1965716254
1839402854
1101101101000110000111101100110
Right shifter hash : 110
Segment Index : 110
Segment Index : 6


NOTE : 1101101101000110000111101100110 is 31 bits as rightmost bit is 0 and ignored.  Same goes for all subsequent binmary bit formats.

So your element with key "Aniket" will go in Segment array of index 6. Inside segments it's pretty simple to calculate index of Entry array.

  •  int entryArrayindex = hash & (tab.length - 1);
         int entryArrayindex = (hash(key.hashCode()) & (16 - 1));
         System.out.println("Entry array index : " + entryArrayindex);
         System.out.println("Entry array index in binary : " + Integer.toBinaryString(entryArrayindex));


Output :
Entry array index : 6
Entry array index in binary : 110


So finally Entry is inserted at index 6 of Entry table.

So to summarize for getting index of Segment table first n bits are used where as for getting index of Entry table last N bits are used from enhanced hash integer.


Related Links 

Left shift and right shift operators in Java

Left shift and right shift operators in Java

A lot of time we use >> , >>> or << and <<< operators in Java for bit operations. These operations essentially shift bits left or right depending on the operator. In this post we will see what exactly is the difference.
  • >> is arithmetic or signed shift right
  • >>> is logical or unsigned shift right
  • << is arithmetic or signed shift left
The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand.

The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.

NOTE : There is no logic left shift as it is same as arithmetic left shift.

Example :

        System.out.println(Integer.toBinaryString(-121));
        // prints "11111111111111111111111110000111"
        System.out.println(Integer.toBinaryString(-121 >> 1));
        // prints "11111111111111111111111111000011"
        System.out.println(Integer.toBinaryString(-121 >>> 1));
        // prints "1111111111111111111111111000011"
        
        System.out.println(Integer.toBinaryString(121));
        // prints "1111001"
        System.out.println(Integer.toBinaryString(121 >> 1));
        // prints "111100"
        System.out.println(Integer.toBinaryString(121 >>> 1));
        // prints "111100"


As you can see in case of -121 since it is a negative number arithmetic or signed shift right adds a 1 to the rightmost bit where as in case if 121 it adds 0.

logical or unsigned shift does not care about sign. It just adds 0 to the shifted bits.


Related Links

Monday, 15 May 2017

How does database indexing work?

Background

Database indexing is a wide topic. Database indexing plays a important role in your query result performance. But like everything this too has a trade off.  In this post we will see what database indexing is and how does it work.


Clustered and Non clustered index

Before we go to how indexing actually works lets see the two types on indexes -
  1. Clustered index
  2. Non clustered index
Data in tables of a database need to be stored on a physical disk at the end of the day. It is important the way data is stored since data lookup is based on it. The way data is stored on physical disk is decided by an index which is known as Clustered index. Since data is physically stored only once , only one clustered index is possible for a DB table. Generally that's the primary key of the table. That's right. Primary key of your table is a Clustered index by default and data is stored physically based on it.

NOTE : You can change this though. You can create a primary key that is not clustered index but a non clustered one. However you need to define one clustered index for your table since physical storage order depends on it.

Non clustered indexes are normal indexes. They order the data based on the column we have created non clustered index on. Note since data is stored only once on the disk and there is just one column(or group of columns ) which can be used to order stored data on disk we cannot store the same data with ordering specified by non clustered index (that's the job of clustered index). So new memory is allocated for non clustered indexes. These have the column on which it is created as the key of the data row and a pointer to the actual data row (which is ordered by clustered index - usually the primary key). So if a search is performed on this table based on the columns that have non clustered indexes then this new data set is searched (which is faster since records are ordered with respect to this column) and then the pointer in it is used to access the actual data record with all columns.


Now that we have knowledge of clustered and non clustered indexes lets see how it actually works.

Why is indexing needed?

When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.

Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire table space must be searched at N block accesses.

Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.

What is indexing?

This is rather a silly question given we already saw clustered and non clustered indexes but lets give it a try.

Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it. This index is obviously the non clustered one. There is no need to create separate data structure for Clustered indexes since the original data is stored physically sorted based on it.

The downside to (non clustered) indexing is that these indexes require additional space on the disk, since the indexes are stored together in a table using the MyISAM engine, this file can quickly reach the size limits of the underlying file system if many fields within the same table are indexed.

Performance

Indexes don't come free.  They have their own overhead. Each index creates an new data set ordered by the columns on which it is created. This takes extra space (though not as much as the original data set since this just has single data and pointer to actual row data). Also inserts are slower now since each insert will have to update this new index data set as well. Same goes for deletion.

Data structures used in indexes

Hash index :
 Think of this using a HashMap. Key here would be derived from columns that are used to create a index (non clustered index to be precise). Value would be pointer to the actual table row entry. They are good for equality lookups like get rows of data of all customer whose age is 24. But what happens when we need a query like set of data of customer with age greater than 24. Hash index does not work so go in this case.  Hash indexes are just good for equality lookups.
Eg.



B-tree Indexes:
These are most common types of indexes. It's kind of self balancing tree. It stores data in an ordered manner so that retrievals are fast. These are useful since they provide insertion, search and deletion in logarithmic time.
Eg.


Consider above picture. If we need rows with data less that 100 all we need are notes to the left of 100.

These are just common ones. Others are R-tree indexes, bitmap indexes etc.

Related Links

Sunday, 14 May 2017

Difference between ClassNotFoundException vs NoClassDefFoundError in Java

Background

In last post we how classloading works in Java -
In this post we will try to understand the difference between ClassNotFoundException vs NoClassDefFoundError thet generally bugs all Java developers.

If you have not gone through above link I strongly suggest you do it right away. It will give you very good understanding on class loading mechanism that we will be using shortly to understand these two situations.

Difference between ClassNotFoundException vs NoClassDefFoundError in Java

  • First point to note is their types. ClassNotFoundException is a checked exception. So you will need to handle it. Either catch it or throw it in method signature. NoClassDefFoundError is an error. Error are generally something you cannot recover from. You can still catch and handle it though.
  • Both things are related to class not available during runtime. Difference is the cause of non availability which we will see shortly. 
  • ClassNotFoundException is throw by running application where as NoClassDefFoundError is thrown by Java runtime.
ClassNotFoundException
We have already seen an example of ClassNotFoundException in last post when we tried to load our custom class with Extension classloader which was parent of Application classloader that actually loaded the class. We said parent classloader does not have visibility of classes loaded by child class loaders. So it threw ClassNotFoundException. Generally ClassNotFoundException is thrown when you try to load a custom class using methods like -
  • Class.forName()
  • ClassLoader.loadClass()
  • ClassLoader.findSystemClass()
and the required class is not found in the classpath. This could be because your classpath is incorrectly configured. Famous example is when you connect to a database using Jave you load the driver class using - Class.forName() [We do this explicit loading pre Java 6. From java 6 this class loading happens automatically. All you have to do is make sure driver jar is present in classpath] -
So for above usecase if you don have a driver class in your classpath then it will led to  ClassNotFoundException. Also you must have noticed by not you need to explicitly handle this exception since this is checked exception.

To resolve this issue you need to check that the class is available in your classpath.

NoClassDefFoundError:
Now this unlike ClassNotFoundException is an Error which is hard to recover from. This generally happens when class is available at compile time but not available at runtime.

One example can be static method/block of a class throws error due to which class does not load (though it was available at compile time and went through in compilation phase). Now if such a class is reference at runtime then it will throw NoClassDefFoundError.

To resolve this error you need check your classpath. It is possible that in your configuration (say in gradle files) you have added jar is lets say test configuration only and not in runtime or compile time configuration. You also need to lookout for any Initialization errors in the logs.


Related Links

How classloader works in Java

Background

We know how Java works. We create Java classes, create instances of it and they interact with each other. In this post we will see how classloaders work. We know javac is a compiler that converts human understandable Java code to class files containing bytecodes that JVM interpreted (java) understands. Classloaders are responsible for loading these classes at runtime. This is one of the good interview questions that is asked to experienced Java developers. This should also help you understand difference between NoClassDefFoundError and java.lang.ClassNotFoundException, So lets get to it.

Basic points

We will come to details of these but to begin with note down these points -
  1. Delegation - Each classloader first delegates loading of class to it's parent (goes all the way up the hierarchy). If parent is not able to load the class then class is tried to be loaded by it's child. If it cannot be loaded by any of the classloaders ClassNotFoundException exception is throws.
  2. Visibility  - Each classloader knows about the classes that it's parents have loaded. However it does not work the other way around. Parents will not know the classes loaded by their child. This brings us to the 3rd points.
  3. Uniqueness - Each class is loaded exactly once. Since each child delegates class loading to it's parent and know the classes it's parents have loaded, it will try to load classes only when it is not loaded by its parent.
Now these are ofcource default behavior of  classloaders that already exist. However you can write your own class loaders and break it (not recommended though).

Classloading in Java

Java has 3 main classloaders that are used to load classes at runtime -
  1. Bootstrap ClassLoader (Also called Primordial classLoader)
  2. Extension ClassLoader
  3. Application  ClassLoader
In that order. So  Bootstrap is parent of Extension and Extension is parent of Application classloader. Each of these classlaoders load classes from a predefined location


Above diagram says it all but let me reiterate -

  • Bootstrap ClassLoader is the topmost level classloader. It does not have any parent. This classloader is a native implementation . This class loader is responsible of loading all standard JDK classes. It does this from path - <JRE>/lib/rt.jar. Since this is native implementation it does not refer to ClassLoader class.
  • Extension ClassLoader is direct child of Bootstrap classLoader. When this classloader tries to load a class it first delegates it to it's parent - Bootstrap ClassLoader. If parent is unsuccessful then Extension ClassLoader will try to load classes from path <JRE>/lib/ext or from path specified in java.ext.dirs system variable. In JVM this is implemented by - sun.misc.Launcher$ExtClassLoader
  • Application classloader is child of Extension classloader. Execution sequence remains same. When a class is loaded from this classloader it delegates to it's parent Extension which in turn delegates it to it's parent Bootstrap. If parents are unsuccessful in loading classes then Application classloaded will try to load class from the classpath - you can give it with arguments -classpath or -cp or specify it in manifest file of jar. In JVM this is implemented by sun.misc.Launcher$AppClassLoader

If application classloader is not able to load the class then it throws ClassNotFoundException. When JVM loads this is the order in which classloaders execute and load classes.

 Code Demo

Let's try to understand few things with code now. First thing we discussed is Bootstrap classloader and how it's the topmost classloader with native implementation and that it does not have any parent. However you cannot refer to Bootstrap classloader in Java. It will give null - Since it is native implementation.

    public static void main(String args[]) throws InterruptedException, IOException {
        ClassLoader classLoader  = String.class.getClassLoader();
        System.out.println(classLoader==null?"Bootstrap classloader not available from Java":"Bootstrap classloader available from Java");
    }

and you should get -
Bootstrap classloader not available from Java

Now lets try to check our visibility principle. By that parent classes should not be able to load classes loaded by their child. We are going to create a new class called HelloWorld and from it check which classloader loaded it (from out previous knowledge all classpath classes are loaded by Application classloader) and well see it's parent (should be Extension classloader) and finally try to load the same HelloWorld class using parent classloader (should fail as parent should not have visibility to classes loaded by child) -

    public static void main(String args[]) throws InterruptedException, IOException {
        ClassLoader classLoader  = HelloWorld.class.getClassLoader();
        System.out.println("Current classloader : " + classLoader);
        System.out.println("Current classloaders parent : " + classLoader);
        try {
            Class.forName("HelloWorld", true, HelloWorld.class.getClassLoader().getParent());
        } catch (ClassNotFoundException e) {
            System.out.println("Class could not be loaded by the classloader");
            e.printStackTrace();
        }
    }


Output is -
Current classloader : sun.misc.Launcher$AppClassLoader@4554617c
Current classloaders parent : sun.misc.Launcher$AppClassLoader@4554617c
Class could not be loaded by the classloader
java.lang.ClassNotFoundException: HelloWorld
    at java.net.URLClassLoader.findClass(URLClassLoader.java:381)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
    at java.lang.Class.forName0(Native Method)
    at java.lang.Class.forName(Class.java:348)
    at HelloWorld.main(HelloWorld.java:93)

You can also see for yourself the way classes are loaded . Just use option -verbose:class while running Java. Example in screenshot below -


NOTE :
  • JVM maintains a runtime pool is permgen area where classes are loaded. Whenever a class is referenced default class loader finds the class is the class path and loads it into this pool. And this is not specific to user defined classes or classes provided in JDK. When a class id referenced it is loaded into the memory.
  •  Yes and ClassLoader instance does not get GCed as it is referenced by JVM thread. Infact that is why even if you have a Singleton class it is possible to create two instances with two different class loaders.
  •  No ClassLoader instances are same as any other Objects in the heap. The statement that it does not get GCed come from the fact that ClassLoaders have references from JVM threads which run till the java process is completed and JVM shuts down. For eg the Bootstrap Class Loader is a native implementation meaning its code is embedded in JVM. So it's reference will always be alive. Hence we say they are not the potential candidates for GC. Other than that GC treats them the same way.

Related Links

Monday, 1 May 2017

How to detect touch on any gameObject in Unity

Background

You can have multiple GameObjects on your scene in Unity. How can we determine if user has touched a particular element. We will see how in this post. We will use Physics2D.Raycast() for this.

Code 

You can do something like following -

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class GameInputs : MonoBehaviour {

    // Use this for initialization
    void Start () {
        
    }
    
    // Update is called once per frame
    void Update () {

        //We check if we have one or more touch happening.
        //We also check if the first touches phase is Ended (that the finger was lifted)
        if (Input.touchCount > 0 && Input.GetTouch (0).phase == TouchPhase.Ended) {
            //We transform the touch position into word space from screen space and store it.
            Vector3 touchPosWorld = Camera.main.ScreenToWorldPoint(Input.GetTouch(0).position);
            Vector2 touchPosWorld2D = new Vector2(touchPosWorld.x, touchPosWorld.y);
            //Debug.Log("Touched " + touchPosWorld.x + "" +  touchPosWorld.y);
            //We now raycast with this information. If we have hit something we can process it.
            RaycastHit2D hitInformation = Physics2D.Raycast (touchPosWorld2D, Camera.main.transform.forward);
            if (hitInformation.collider != null) {
                //We should have hit something with a 2D Physics collider!
                GameObject touchedObject = hitInformation.transform.gameObject;
                //touchedObject should be the object someone touched.
                Debug.Log("Touched " + touchedObject.transform.name);
                switch (touchedObject.tag) {
                case "StartGameButton":
                    Debug.Log("Touched StartGameButton " + touchedObject.transform.name);
                    break;
                case "LikeButton":
                    Debug.Log("Touched LikeButton " + touchedObject.transform.name);
                    Application.OpenURL("https://play.google.com/store/apps/details?id=com.osfg.ringtonesetter.main");
                    Application.OpenURL("market://details?id=com.osfg.ringtonesetter.main"); 
                    break;
                case "SettingsButton":
                    Debug.Log ("Touched SettingsButton " + touchedObject.transform.name);
                    Application.LoadLevel ("Settings");
                    break;
                }
            }

        }
    }
}

Explanation and setup

As you can see we are using Physics2D.Raycast() to case a ray from camera to point of touch and then detecting a collision. Finally if we have collision information we check the tag associated with it to check out element of interest.
  1. Make sure for each such elements you add a collider component like 2D Box collider. Only then collision will work.
  2. Make sure you tag each elements correctly and use it to get your object when touched.


Other Notes :

  1. You can create a prefab of background and use it in all your app screens to be consistent. That way changes made in prefab will be applicable to all instances of it.
  2. If your scene is not getting correctly displayed you can correct it by clicking on "Main Camera" and then Game Object -> Align view to selected

How to center a GUI button in Unity

Background

In previous post we saw how to setup unity for creating Android application. In this post we will see how to create a simple GUI button in a scene and put in in the center of your screen.

How to center a GUI button in Unity

Create or load an existing project. Next create a C# script and attach it to any of the objects on the screens. You can attach it to the camera as well. I am doing the same for this post. Now open this script in Monodevelop.


I have three different scenes in my project -
  1. GameStart
  2. GamePlay
  3. GameEnd
Since this post only deals with centering of a GUI button I will not bore you with other scene details. Well just concentrate on GameStart scene which will have a GUI button in the center of the screen that says - "Start Game".

So create a C# script called  GameStart.cs (you can name it anything you want)., attach it to camera in GameStart scene and open it in Monodevelop of editing.

Paste following code in it -

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class GameStart : MonoBehaviour {

    public void OnGUI(){
        if(GUI.Button(new Rect(Screen.width/2-50,Screen.height/2-25,100,50),"Start Game!")) {
            Debug.Log("Start Button clicked");
            Application.LoadLevel ("GamePlay");
        }
    }
}



Now lets understand whats going on. OnGUI() is the method that is called by Unity engine to render GUI components. We are going to add our button in this method.

Next we create a button using method GUI.Button() which takes its x position, y position, it's width and it's height as Rect object which is 1st argument to Button. 2nd argument is the text itself that will be shown on the button UI. We are showing "Start Game" there. What goes inside the wrapped if will get executed when the button is clicked. We are simply logging the click event and loading scene2 i.e GamePlay scene.

Point to note here is the x,y coordinates and the height/width of the Button. Notice how we have used Screen.width and Screen.height values here, then divided it by 2 to get mid and then adjusted the coordinates as per the actual width and height of the button we want.

It would look like below -



Now start up console. You can do so using
  • Windows -> Console
Now click on Start Game! button and notice console output.

 It will also load scene 2 but ignore that for now. Monodevelop code looks like below -




Related Links

Saturday, 29 April 2017

Setting up Unity platform to build android games

Background

This tutorial assumes you have already installed Unity.
You can download Unity from their official site - https://unity3d.com/
In this post we will see how to setup Unity to test android games that you develop.

For details you can visit their site - https://unity3d.com/
and you can also see list of games that are already created with Unity. So lets get started -

Setting up android build setup in Unity

Fire up your Unity. Once it is opened you can create a new project and add a new scene to it. It's like creating project in any IDE. Once Unity is up and running go to 
  • File -> Build Settings
 Then
  1. Select android as the platform
  2. Click Switch platform
  3. Click Add Open scenes - this should add all open scenes in build setting
  4. Finally click on build (This step will generate your android apk file. Skip this step if you are doing 1st time well come to this in a moment. Before this we need to have some more configurations.)


 Also you can see Player setting right besides switch platforms. Click this to open a new section of player settings. Here you will see settings that are specific to your android app. If you are developed android apps before then you would know it requires app/bundle id, app icon of different resolutions, app name, api version to build your app, certificate to sign your app for production build etc. all of this you can configure in this section.




 Next you need to tell Unity location of your Android SDK and JDK.  For this go to
  • Unity -> preferences.
This path will be different based on your operating System. For me it's Mac so preferences are in Unity -> Preferences. If you have windows it can be in File -> Preferences.

Once preferences window is opened go to External tools and provide path of your Android SDK and JDK as shown in screenshot below -



 After this your unity is all setup to create and run your android app. Lets see how we can test this setup.

Testing remote android apps

For testing Unity has provided an android app that you need to install on your android device. Before that make sure -
  • Your device has developer mode enabled and have enabled USB debugging
  • It is connected to your machine running Unity with USb cable.
Then you can install unity remote on your device -

Latest one when I am writing this post is unity remote 5. Check accordingly.

Once you have installed it go to Unity on your machine . Now go to
  • Edit -> Project Settings -> Editor
and select Any android device as device.



 That's it. You can just play and you can see your scene running in android unity remote app.

Following are screenshots in playmode from my laptop and android device running unity remote -






Enjoy :)

Related Links

Wednesday, 12 April 2017

Using HttpUrlConnection in Android

Background

Android has two options for doing network operations using Http clients -
  1. Apache HttpClient
    1. DefaultHttpClient
    2. AndroidHttpClient
  2. HttpUrlConnection


Back in 2011 Android developers announced that Android team is not actively working on Apache HTTP Client and that  new android applications should use HttpURLConnection and that is where they will be spending their energy going forward.

For more details you can read their blog -  Android’s HTTP Clients 

It's been a long way since they has posted that post and here we are. Android Http client was totally removed from Android 6.0 (M). Ofcourse you can manually plug it in. But android developer site says the following -

Android 6.0 release removes support for the Apache HTTP client. If your app is using this client and targets Android 2.3 (API level 9) or higher, use the HttpURLConnection class instead. This API is more efficient because it reduces network use through transparent compression and response caching, and minimizes power consumption. To continue using the Apache HTTP APIs, you must first declare the following compile-time dependency in your build.gradle file:

android {
    useLibrary 'org.apache.http.legacy'
}


But I would recommend don't do this unless some legacy API needs this. Move on to HttpUrlConenction. In this post we will see how we can use HttpUrlConnection for network operations in android.

Using HttpUrlConnection in Android

HttpURLConnection is a general-purpose, lightweight HTTP client suitable for most applications. A simple snippet would be- 

        URL url = new URL("http://google.com");
        HttpURLConnection urlConnection = (HttpURLConnection) url.openConnection();
        urlConnection.setRequestMethod("GET");
        try {
            InputStream in = new BufferedInputStream(urlConnection.getInputStream());
            readStream(in);
        } finally {
            urlConnection.disconnect();
        }

So you open a connection by calling openConnection() on an URL instance. You can then set the type of request using setRequestMethod(). It can be GET, POST etc. Then you read the stream by calling urlConnection.getInputStream(). Finally you call disconnect() to release your connection.


NOTE : By default HttpUrlConnection will use GET as request type i.e you dont have to mention  urlConnection.setRequestMethod("GET"); . For others as started above you can use - setRequestMethod();

NOTE :  Connection is actually established when you call getInputStream() or getOutputStream() or getResponseCode() on your httpUrlConenction instance.

NOTE : If your response is not 2** then it would be an error(You can read the response code by calling getResponseCode() method). In that case you need tor read error stream. You can do that by using getErrorStream() to read the error response. The headers can be read in the normal way using getHeaderFields().
 

How disconnect() works?

    Each HttpURLConnection instance is used to make a single request but the underlying network connection to the HTTP server may be transparently shared by other instances. Calling the close() methods on the InputStream or OutputStream of an HttpURLConnection after a request may free network resources associated with this instance but has no effect on any shared persistent connection. Calling the disconnect() method may close the underlying socket if a persistent connection is otherwise idle at that time.   

 -> So basically your HttpUrlConnection instance may get GCed but the underlying TCP socket will get pooled and reused unless you call disconnect() on it in which case it may or may not close the socket. So if you are not reconnecting to same URL it is safe to always call disconnect and let android handle the socket pooling and closing part.

Android docs clearly states -  Disconnecting releases the resources held by a connection so they may be closed or reused.

Handling request body

Sometime a request made to a server may need a request body to be supplied. For that you can use the httpUrlConnection instance's outputStream.

        URL url = new URL("http://test.com");
        HttpURLConnection urlConnection = (HttpURLConnection) url.openConnection();
        urlConnection.setRequestMethod("POST");
        urlConnection.setDoOutput(true);
        urlConnection.setChunkedStreamingMode(0);
        try {
            OutputStream out = new BufferedOutputStream(urlConnection.getOutputStream());
            writeStream(out);

            InputStream in = new BufferedInputStream(urlConnection.getInputStream());
            readStream(in);
        } finally {
            urlConnection.disconnect();
        }

Make sure you set setDoOutput(true) if you have request body to be sent. Similarly set setDoInput(true) if you are reading back from the connenction. If you just want to see response code using - getResponseCode() method that these are not required.

NOTE : Notice how we have use BufferedStreams over input/output streams. They are used for performance reasons - so that data is buffered and we can easily read/write it.

Setting headers and connection timeouts

If you are familiar with HttpClient then you must have set connection and socket timeouts. In HttpUrlConenction you need to do following -

        urlConnection.setConnectTimeout(30000);
        urlConnection.setReadTimeout(30000);

These are in milliseconds. I have set it to half a minute above. To set headers in the request you can do -

urlConnection.setRequestProperty("headerName", "headerValue");

So lets say you want to set user-agent in your request you do -

urlConnection.setRequestProperty("User-Agent", "Mozilla");

Similarly you can enable disable redirects using -
urlConnection.setInstanceFollowRedirects(false);

Making secure connection (https)

If you are working with https (secure connection) protocol then your actual class would be - HttpsUrlConnection.

NOTE :  You can still use HttpUrlConnection since HttpUrlConenction extends HttpsURLConnection (by polymorphism).

HttpsUrlConnection will allow you to override HostnameVerifier and SSLSocketFactory.

Eg.

static {
    TrustManager[] trustAllCertificates = new TrustManager[] {
        new X509TrustManager() {
            @Override
            public X509Certificate[] getAcceptedIssuers() {
                return null; // Not relevant.
            }
            @Override
            public void checkClientTrusted(X509Certificate[] certs, String authType) {
                // Do nothing. Just allow them all.
            }
            @Override
            public void checkServerTrusted(X509Certificate[] certs, String authType) {
                // Do nothing. Just allow them all.
            }
        }
    };

    HostnameVerifier trustAllHostnames = new HostnameVerifier() {
        @Override
        public boolean verify(String hostname, SSLSession session) {
            return true; // Just allow them all.
        }
    };

    try {
        System.setProperty("jsse.enableSNIExtension", "false");
        SSLContext sc = SSLContext.getInstance("SSL");
        sc.init(null, trustAllCertificates, new SecureRandom());
        HttpsURLConnection.setDefaultSSLSocketFactory(sc.getSocketFactory());
        HttpsURLConnection.setDefaultHostnameVerifier(trustAllHostnames);
    }
    catch (GeneralSecurityException e) {
        throw new ExceptionInInitializerError(e);
    }


Sample take from this SO discussion.

NOTE :   Calling HttpsURLConnection.setDefaultSSLSocketFactory() or HttpsURLConnection.setDefaultHostnameVerifier() will set it up for all Https connections. If you want to set it for specific connections then type cast it to HttpsUrlConenction instance and then call set methods on it.

Handling multipart/ form-data

 You'd normally use multipart/form-data encoding for mixed POST content (binary and character data). The encoding is in more detail described in RFC2388.

String param = "value";
File textFile = new File("/path/to/file.txt");
File binaryFile = new File("/path/to/file.bin");
String boundary = Long.toHexString(System.currentTimeMillis()); // Just generate some unique random value.
String CRLF = "\r\n"; // Line separator required by multipart/form-data.
URLConnection connection = new URL(url).openConnection();
connection.setDoOutput(true);
connection.setRequestProperty("Content-Type", "multipart/form-data; boundary=" + boundary);

try (
    OutputStream output = connection.getOutputStream();
    PrintWriter writer = new PrintWriter(new OutputStreamWriter(output, charset), true);
) {
    // Send normal param.
    writer.append("--" + boundary).append(CRLF);
    writer.append("Content-Disposition: form-data; name=\"param\"").append(CRLF);
    writer.append("Content-Type: text/plain; charset=" + charset).append(CRLF);
    writer.append(CRLF).append(param).append(CRLF).flush();

    // Send text file.
    writer.append("--" + boundary).append(CRLF);
    writer.append("Content-Disposition: form-data; name=\"textFile\"; filename=\"" + textFile.getName() + "\"").append(CRLF);
    writer.append("Content-Type: text/plain; charset=" + charset).append(CRLF); // Text file itself must be saved in this charset!
    writer.append(CRLF).flush();
    Files.copy(textFile.toPath(), output);
    output.flush(); // Important before continuing with writer!
    writer.append(CRLF).flush(); // CRLF is important! It indicates end of boundary.

    // Send binary file.
    writer.append("--" + boundary).append(CRLF);
    writer.append("Content-Disposition: form-data; name=\"binaryFile\"; filename=\"" + binaryFile.getName() + "\"").append(CRLF);
    writer.append("Content-Type: " + URLConnection.guessContentTypeFromName(binaryFile.getName())).append(CRLF);
    writer.append("Content-Transfer-Encoding: binary").append(CRLF);
    writer.append(CRLF).flush();
    Files.copy(binaryFile.toPath(), output);
    output.flush(); // Important before continuing with writer!
    writer.append(CRLF).flush(); // CRLF is important! It indicates end of boundary.

    // End of multipart/form-data.
    writer.append("--" + boundary + "--").append(CRLF).flush();

Again code is taken from this SO discussion.

Other advantages of using HttpUrlConnection

  • HttpUrlConnection by default honors system proxy. However if you want to specify a custom proxy then you can do so with API - url.openConnection(proxy)
  • It also has transparent response compression. It will automatically add the header - Accept-Encoding: gzip to outgoing responses and also handle it automatically for incoming connections.
  •  It also attempts to connect with Server Name Indication (SNI) which allows multiple HTTPS hosts to share an IP address.

Related Links

Sunday, 2 April 2017

Android material design floating labels on EditText and Password visibility Toggle

Background

With android design support library new element - TextInputLayout was introduced. With this we can totally omit static labels that we put before text input elements (EditText for example). With this label will float on the top of the EditText when user focuses on that field for entering data. Also we can show error on the same field post validation. That gets show floating below the EditText. It also has passwordToggleEnabled   which lets you toggle the visibility of your password field with an eye icon (it can be customized to use a different icon too). We will see all of these in this post.

Android material design floating labels on EditText and Password visibility Toggle

Make sure your app level gradle has following dependencies added -

    compile 'com.android.support:appcompat-v7:25.1.1'
    compile 'com.android.support:design:25.3.1'

NOTE : Base version of you appcompat and your design library should be same. For eg. it's 25 for this case.

Next lets go straight to the layout. The feature that we are looking for goes something like this -

        <android.support.design.widget.TextInputLayout
            android:id="@+id/input_layout_password"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
 app:passwordToggleContentDescription="@string/passwordToggleContentDescription"
            app:passwordToggleEnabled="true"
            app:passwordToggleTint="@color/colorAccent">

            <EditText
                android:id="@+id/input_password"
                android:layout_width="match_parent"
                android:layout_height="wrap_content"
                android:hint="@string/hint_password"
                android:inputType="textPassword"/>

        </android.support.design.widget.TextInputLayout>



Now I have combined both floating labels and password toggle in a single example. Lets see how it works now.

  • First of all you need to wrap  EditText element inside TextInputLayout element. 
  • Next android:hint value of EditText will come out on top as a floating label.
  • For password visibility to be toggle we need to provide app:passwordToggleEnabled="true" attribute. Others are optional really. Lets see what all attributes it supports.

  1.  passwordToggleEnabled : allows you choose whether or not you want the password visibility to be toggled.
  2. passwordToggleContentDescription :  allows a string to be set for the content description. This is used for accessibility feature.
  3. passwordToggleDrawable : allows one set a different icon other than the default visibility toggle icon (eye icon). 
  4. passwordToggleTint : allows the visibility toggle icon to be tinted to whatever colors you indicate.
  5. passwordToggleTintMode : sets the blending mode used to apply the background tint.
You can see the complete specs in android developers site. It would look like below -








Final screen is just showing a toast when you press login and all validations have gone though successfully.Speaking of validation lets come to it.

Do not worry about the minute code details like string resources. You can find the complete code on my github repo -
Lets just focus on concepts for now.

We said in our initial discussion that TextInputLayout can handle errors as well and they are shown floating just below the EditText. Lets look at the code for it.

  1. In your activity's onCreate() method get a reference to the TextInputLayout element and reference to the EditText wrapped in it.
  2. Next you can addTextChangedListener() to your EditText and do validations there.
  3. To set and display an error you simply need to call setError()on textInputLayout element. To remove error you can simply call setErrorEnabled(false).
Lets see how we can do it in case of our Email field. First of all get a reference to TextInputLayout and the EditeText in it -

        inputLayoutEmail = (TextInputLayout) findViewById(R.id.input_layout_email);

        inputEmail = (EditText) findViewById(R.id.input_email);


Next add addTextChangedListener to inputEmail and in it's afterTextChanged() method simply do your validations. In this case we are just calling a private validate method from afterTextChanged() method as follows -

    private boolean validateEmail(String text) {
        if(!isValidEmail(text)) {
            inputLayoutEmail.setError(getString(R.string.error_email));
            inputEmail.requestFocus();
            return false;
        }
        else {
            inputLayoutEmail.setErrorEnabled(false);
        }
        return true;
    }



    private boolean isValidEmail(String email) {
        return !TextUtils.isEmpty(email) && android.util.Patterns.EMAIL_ADDRESS.matcher(email).matches();
    }


and you are done. You should see error as shown in following screenshots -




Again for complete code please refer to my github repo -

Related Links



t> UA-39527780-1 back to top