The Top 5 Most Common Beginner Problems in Java and How To Fix Them

Number 1:

Comparing Strings with == instead of equals()

Why isn't my code working? you say, It never exits even when I type "N"

In your code you have:

if (answer == "N") {
	// do stuff
}

This is because == can only be used to compare primitive types, such as int, float, byte, etc. String is an Object and so one must use the equals() method that every Object in Java inherits.

So, to fix:

if (answer.equals("N")) {
	// do stuff
}

or even:

if ("N".equals(answer)) // this will work even if answer is `null`

For more, see here

Number 2:

Why is my program not getting input properly? AKA Scanner and the Dangling Newline

Your program does somthing like this:

Scanner scanner = new Scanner(System.in);

System.out.println("Please enter your age:");
int age = scanner.nextInt();
System.out.println("Please enter your name:");
String name = scanner.nextLine();

The entry for name disappears!! What happened here?

The Scanner class will allow you to read, say, a bunch of different integers even if they are on the same line. So, it only reads the digits... that is it. However, when you type the number and hit the enter key, a newline character is also sent to the input buffer. When you call nextLine() right after that, it reads the next available token, up to the next newline character. Which is the one just sitting there, before where you typed the name and hit enter again. If you were to call nextLine() again, there is the name sitting right there.

To fix:

You have three main options:

1. Simply add another call to nextLine()

    Scanner scanner = new Scanner(System.in);
   
    System.out.println("Please enter your age:");
    int age = scanner.nextInt();
    scanner.nextLine();              // gets rid of that newline character
    System.out.println("Please enter your name:");
    String name = scanner.nextLine();

2. Don't use nextInt(), or nextDouble(), etc., always use nextLine(): and use the Parsing methods such as Integer.parseInt() and Double.parseDouble(). You will find later on, you can also encase these into a try-catch block and test for invalid input much more easily.

    Scanner scanner = new Scanner(System.in);
   
    System.out.println("Please enter your age:");
    int age = Integer.parseInt(scanner.nextLine()); // <---- see here
    System.out.println("Please enter your name:");
    String name = scanner.nextLine();

3. Don't use the Scanner class at all, use BufferedReader/InputStreamReader which will force you to both catch exceptions and parse the incoming input manually.

Number 3:

Why is my program giving me an ArrayIndexOutOfBoundsException?

Your program is giving you an ArrayIndexOutOfBoundsException because you have tried to access an index of the array that is out of bounds. Not being sarcastic, it is as simple as that. The main cause of this is usually an off-by-one error. Always remember that arrays are zero-indexed meaning if you declare an array of size[10], the index will start at 0 and go to 9. Trying to call index [10] will give you that error.

It's also good to get in the habit of bounds checking in your methods that use array indices, so that you can avoid this type of error, for example:

public int getAgeFromIndex(int[] ages, int index) {
	if (index < 0 || index >= ages.length) {
		System.out.println("Incorrect index: " + index);
		return -1;
	}
	return ages[index];
}

How to fix:

The error message you get is your friend:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
    at Snippets.main(Snippets.java:289)

The 5 there is the index you were trying to access. The Snippets.java:289 is the class and line number that caused the problem. go to that line number in your code and you should see the offending variable. You can set a debug point on that line and run in debug mode (if you are using an IDE) if you are still having problems figuring out what is happening.

Number 4:

Why am I getting a NullPointerException?

You are getting a NullPointerException because you are trying to access an Object that is null. There are literally thousands of reasons to get this exception, but, the majority of the time it's really very simple: You declared the Object/Data Structure, but forgot to instantiate it.

Say you have a class:

public class Employee {
	String name;
	String ID;
	List<Task> taskList;

	public Employee(String name, String ID) {
		this.name = name;
		this.ID = ID;
	}
}

Now you want to add tasks:

	public void addTask(Task t) {
		taskList.add(t);
	}

This will throw a Null Pointer exception, because nowhere did you instantiate the List. The constructor should have:

	this.taskList = new ArrayList<>();

How to fix:

Again, use the error message:

Exception in thread "main" java.lang.NullPointerException
    at Snippets.main(Snippets.java:291)

It tells you specifically what line number 291 caused the exception. Start from there and trace back the Objects in question and make sure they were properly initialized.

Number 5:

Why is my if/while/for loop not running?

Ah... this one gets all of us at one point or another, you have stared at your code for hours and just can't see it, but there it is, hiding in plain sight!

if (something.equals("something else")); {               // <---- that damn semi-colon
	System.out.println("Why am I not running???");
}

What's wrong here? It's an unnecessary semi-colon ; hanging out after the if() statement. This is perfectly valid syntax, so the compiler won't flag it, but it ends the conditional statement so the code inside the block {} never gets run.

How to fix? Delete the semi-colon, get another cup of coffee and shake your head.

That's all for now!! I realize there are actually a lot more than 5 common issues facing learning Java programmers, so look for more to come!

Understanding and using Exceptions in Java

Exceptions are a way to handle (gracefully if possible) when things go wrong with your program. They allow you to exit the program when a particular event happens and then let the user know what and where it happened.

Checked vs Unchecked

There are two types of exceptions, Checked and Unchecked. There is some considerable debate about them which I will not get into, but here is the prevailing modern philosophy behind them:

A Checked exception must be handled in some way by the method that is using it, either with a try/catch block or with a 'throws' clause in the method header. This is generally used for a failure caused by something outside of the JVM's control. Examples of this are File IO errors, database errors, network stream errors and the like.

An Unchecked exception can be used for any other type of error that you want to cause the system to exit. This tells you that there is an error within the program itself. Examples of this are ArrayIndexOutOfBounds or NullPointerException. These should not be 'caught' usually, but can be if necessary (i.e. parsing input)

Checked exceptions inherit from Exception and Unchecked inherit from RuntimeException.

Handling Checked Exceptions

Any method that uses checked exceptions will tell you with a compile-time error (or IDE warning). These are generally File, Stream or other IO operations, database operations and etc. You have probably used them before.

One way to handle them is to add a throws clause to the method header:

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String input = br.readLine();
}

In practice this is not the best way, because there will be no information given to the user when the exception is thrown. A better method is to use a try/catch block.

public static void main(String[] args) {

    String input = "";
    try {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
    } catch (IOException ioe) {
        ioe.printStackTrace();
    }
}

The try block is where the commands that might cause the exception go. Inside the catch block we can do something (doesn't necessarily have to be printStackTrace) that either better informs the user what happened wrong and why, or otherwise handles the problem without any damage, even sometimes preventing program termination.

Even better is the try-with-resources block, available since Java 7, which automatically handles things that need to be closed upon either success or failure.

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    input = br.readLine();
} catch (IOException ioe) {
    ioe.printStackTrace();
}

Checked Exceptions can be user-defined, but it is generally not recommended. If you want to use custom exceptions in your program, use unchecked.

Using Unchecked Exceptions

Using unchecked exception is actually very easy. Generally, you find the exception that most closely describes what you need (or create your own) and throw it.

The syntax goes like:

throw new ExceptionName("Message");

Where ExceptionName is a valid exception in java.lang.* or some other library or class. The message string is optional, but very useful to give a description back to the user.

Example:

public void enqueue(Item element) {
    if (element == null) {
        throw new NullPointerException("Null elements are not allowed.");
    }
    queue[size++] = element;
    checkSize();
}

Another:

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index : " + index);
    }
}

So, to define our own exception is also very simple:

public class DontLikeSevensException extends RuntimeException {

    public DontLikeSevensException() {
        super();
    }

    public DontLikeSevensException(String msg) {
        super(msg);
    }
}

And let's throw it:

public static void main(String[] args) {

    String input = "";

    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
        input = br.readLine();
    } catch (IOException ioe) {
        ioe.printStackTrace();
    }

    if (input.contains("7")) {
        throw new DontLikeSevensException("I really don't like sevens!!!");
    }


}

Some Don'ts with Exceptions

1. Don't just put a catch there and not do anything with the result. The most frequent times I see this, it is while using file functions and not informing the user of a FileNotFoundException, and then wondering why nothing is happening. At the very least, print the stack trace.

2. Don't use exceptions to control the flow of your program. Exceptions should generally be used to show errors in the program, so that they can be fixed. The only main 'exception' to this rule is for converting input from string to whatever number format. (For example, when using Integer.nextInt() you can place it inside of a try-catch block and catch NumberFormatException in order to re-prompt the user for correct input, without crashing the program.)

3. Don't use checked exceptions if you don't need to. If you want to make you own exceptions, go ahead, but try to keep them as unchecked (extending RuntimeException) unless it is a specific case such as mentioned above, something outside of the JVM's control.

I've been working on an open-source project for the past two months to learn Domain-Driven Design (DDD). I'd love to collaborate with others who are also interested in DDD and software architecture.

If you're curious, check out the project! If it interests you, feel free to clone the repo, get familiar with the codebase, and start contributing. I would appreciate any help to the project.

Let's build something awesome together.

Github repository : https://github.com/MstfTurgut/hotel-reservation-system

Hello everyone,

I am a software developer with several years of experience. As my side project and hobby I created a website with Java tutorials. If you are interested, please visit: https://simplecoding.net/

This project has the sole purpose of showing some examples of Java programs.

I will be happy if you manage to learn something from it :)

Have a nice day!

Using a String-Based Trie to make a Word Suggestion Program

Tries

A Trie is a data structure that is very useful for fast lookup of smaller sets of data in a larger set of data. It is particularly useful for Strings, but can also be used with byte and bit data, and more.

In a Trie of Strings, each Character in the string is a node. The last character of the word is the only node given a value. Words with prefixes in common share the common nodes, up until the point where there is a divergence.

See this example here of a simple GUI to test the trie. We load the text file enable1.txt which contains over 172 thousand English words. It takes about 1.5 seconds to load the data into the trie, and lookups are 1 - 3 milliseconds. The input text turns red when the text is not a word or prefix, black when it is a valid prefix, and blue when it is currently a complete word. The list of available words generates dynamically below as you type.

So, let's add the words "box", "boxed", "boxes", "boxing", "bar" to a Trie.

[root]
|
b
|
o - - - - - - a
|             |
[x]          [r]
|
e - - - -  - i
|            |
[d] - [s]    n
             |
            [g]

The character in [] brackets denotes the end of a word. Now, you can see that all words that start with b will start at the same node, and go from there. For lower case letters a - z each node can only have at most 26 children.

There are many different ways to implement a Trie. It can be done as a type of linked list that goes in two directions, called a Doubly-Chained Trie. This way is very memory efficient, but has longer lookup times. It can also be implemented using arrays, lists, sets or maps.

We will start our Trie, like many other data structures, with a Node class:

private class Node {
    final char key;
    int value;
    Map<Character, Node> children;

    public Node() {
        // default null character
        this('\u0000');
    }

    public Node(char key) {
        // default value of -1
        this(key, -1);
    }

    public Node(char key, int value) {
        this.key = key;
        this.value = value;
        children = new HashMap<>(32);
    }

    public boolean hasChildren() {
        return children.size() > 0;
    }

}

In this case we are using the HashMap implementation. It will be less memory efficient than a doubly-chained trie, but the lookup speed should be faster. The code is also much simpler and cleaner this way.

Now we make an interface for the Trie, that can be used with different implementations. This does not use generics, as the use of Strings/chars makes that more difficult.

public interface STrie {
    void add(String key);
    void add(String key, int value);
    void add(String[] words);
    void add(List<String> list);
    boolean contains(String prefix);
    boolean containsCompleteWord(String word);
    List<String> findWordsFromPrefix(String prefix);
    int get(String key);
    int size();
}

The Trie itself is pretty simple. The only member variables needed is a root Node (which is always a null character) and the size. We have a couple different constructors for creating the structure with a given list or array. Since many of the implementations may not need to store a particular value with each word, we simply use 0 as a default value, and -1 as a value for a non-ending character node.

For the add method, we loop through the string by character, see if a node exists for that character at each level, and if not, add it to the children Map for the associated parent node. when we hit the end of the string, we store the value in the last node and increase the overall size variable.

public void add(String key, int value) {
    Node current = root;
    key = key.toLowerCase();

    for (int i = 0; i < key.length(); i++) {
        Node found = current.children.getOrDefault(key.charAt(i), null);
        if (found == null) {
            found = new Node(key.charAt(i));
            current.children.put(key.charAt(i), found);
        }
        current = found;
    }
    current.value = value;
    size++;
}

The get, contains, and containsCompleteWord methods all are essentially the same algorithm with a different return value, so they are all passed to internal method search

private Node search(String key) {
    Node current = root;

    for (int i = 0; i < key.length(); i++) {
        Node found = current.children.getOrDefault(key.charAt(i), null);
        if (found == null) return null;
        current = found;
    }
    return current;
}

public boolean contains(String key) {
    return search(key) != null;
}

public boolean containsCompleteWord(String key) {
    Node found = search(key);
    return found != null && found.value >= 0;
}

public int get(String key) {
    Node found = search(key);
    return found == null ? -1 : found.value;
}

Now we add a Pre-Order Traversal to return a mostly sorted list of the words, and a method findWordsFromPrefix which uses the helper part of the POT do get the list of words that start with the given prefix.

public List<String> preOrderTraversal() {
    List<String> list = new ArrayList<>();
    preOrderTraversal(list, root, "");
    return list;
}


private void preOrderTraversal(List<String> list, Node current, String prefix) {
    if (current.hasChildren()) {
        for (Map.Entry<Character, Node> each : current.children.entrySet()) {
            char temp = each.getKey();
            preOrderTraversal(list, each.getValue(), prefix + temp);
            current = each.getValue();
            if (current.value >=0) {
                list.add(prefix + temp);
            }
        }
    }
}

public List<String> findWordsFromPrefix(String prefix) {
    Node found = search(prefix);
    if (found == null) return null;
    List<String> list = new ArrayList<>();
    preOrderTraversal(list, found, prefix);
    return list;
}

Doubly-Chained Trie

Oddly enough, after running some tests, the Doubly-Chained Trie not only uses 1/4th of the memory of the MapTrie, but actually performs slightly faster. The StringTrie took 9 - 11 ms to find all 737 words that start with the prefix "car" while the doubly-chained trie took only 2 - 4 ms. Now, this difference is small enough to be negligible, so we should go with the smaller memory usage, right?

Here's the Node class for that type of trie, notice it has two links, one for next and one for child:

private class Node {
    final char key;
    int value;
    Node next;
    Node child;

    public Node() {
        this('\u0000');
    }

    public Node(char key) {
        this.key = key;
        this.value = -1;
    }

    public Node(char key, int value) {
        this.key = key;
        this.value = value;
    }

    public boolean hasChild() {
        return this.child != null;
    }

    public boolean hasNext() {
        return this.next != null;
    }
}

And here is the add method:

public void add(String word, int value) {
    Node current = root;

    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        Node found = null;
        if (!current.hasChild()) {
            current.child = new Node(c);
            current = current.child;
        }
        else {
            current = current.child;
            while (true) {
                if (current.key == c) {
                    found = current;
                    break;
                }
                if (!current.hasNext()) break;
                current = current.next;
            }
            if (found == null) {
                current.next = new Node(c);
                current = current.next;
            }
        }
    }
    current.value = value;
    size++;
}

The rest of this class, and all the other full files including the GUI class and FileIO are can be found here

Huffman Tree Entropy Encoding

A Huffman Tree is a type of Entropy Encoding which is very commonly used for data compression. It is not usually used by itself, but in concert with other forms of compression, usually as the final 'pass' in the compression algorithm. The Huffman Tree takes the most frequently used characters or bytes in the input stream, and uses smaller amounts of bits to represent them. Data is stored to disk/transferred over networks in bytes which are 8 bits each. So, to make a compressed stream, we need to represent the most common elements in the data with less than 8 bits.

Say we have the string "AAABBBAACCAADA"

We get the frequency count:

A = 8
B = 3
C = 2
D = 1

Next, we build a tree where a 0 means go to the left, and a 1 means go to the right. This tree is different than Binary Search Trees, as every non-leaf node must have two children. A leaf node, or a node with no children, means this is a value. So the tree created for the above string looks like this:

	   Root
	   / \	
	  /   \
	 /     \
	0       1 = A
   / \
  /   \
 /     \
0 = B  	1 
       / \
      /   \
     /     \
    0 = D   1 = C

You get the 'Huffman Codes' by traversing the tree until you get to a leaf node, and adding a '1' or a '0' accordingly, not counting the root.

So, the assigned codes for this tree would be:

A = 1
B = 00
C = 011
D = 010

Now, our string can be represented by the bits 111 000000 11 011011 11 010 1 Converted to bytes, with 1 extra bit at the end for padding, this is the bytes E0 6D EA in hex, so we have gone from 14 bytes long to three.

To properly decode the encoded stream, we read the bits back in one at a time, and traverse through the tree again until we hit a leaf node, then output the value at that node.

We have to have a way to save/send our tree information so that the data can be decoded. This can be done by saving the frequency information generated, but can be done in a more compressed way by bitstream encoding the tree itself. We do this by traversing the tree, and if we hit a leaf node, output a 1 plus the 8-bit value code, otherwise outputting a 0. The tree can then be easily reconstructed exactly using the reverse of this process. The frequency information is discarded and not necessary to recreate the tree.

To write bit information less than bytes, I have written a BitStream class found here. This code also uses my own BinaryHeap class from my example found here, although you can use java's PriorityQueue in its place.

First, we have our Node class:

class Node
{
	// actual ascii character value
	int index;

	// count
	int frequency;

	// integer value of huffman code
	int huffmanCode;

	// legth of huffman code in bits
	int huffmanLen;

	// left child
	Node left;

	//right child
	Node right;

	/**
	 * Create blank Node
	 */
	public Node()
	{

	}

	/**
	 * create Node based on index value and frequency count
	 */
	public Node(int index, int frequency)
	{
		this.index = index;
		this.frequency = frequency;
	}

	@Override
	public String toString()
	{
		return this.index + " : " + this.frequency;
	}
}

and the Tree class:

class Tree implements Comparable<Tree>
{
	Node root;

	/**
	 * Create tree with childless leaf node
	 * @param index integer of character/byte value
	 * @param frequency count of occuring frequency
	 */
	public Tree(int index, int frequency)
	{
		root = new Node(index, frequency);
	}

	/**
	 * Create subtree with null node as root
	 * and total of two subtree frequencies
	 * @param tree1 left subtree
	 * @param tree2 right subtree
	 */
	public Tree(Tree tree1, Tree tree2)
	{
		root = new Node();
		root.left = tree1.root;
		root.right = tree2.root;
		root.frequency = tree1.root.frequency + tree2.root.frequency;
	}

	/**
	 * Encode Huffman Tree to BitStream
	 * if leaf node pushes 1 + literal byte
	 * otherwise 0
	 * @return bs BitStream with encoded tree
	 */
	public BitStream encodedTree()
	{
		BitStream bs = new BitStream();
		encodedTree(root, bs);
		bs.close();
		//System.out.println(bs);
		return bs;
	}

	/**
	 * recursive helper method
	 */
	private void encodedTree(Node node, BitStream bs)
	{
		if (isLeaf(node))
		{
			bs.pushBit(true);
			bs.pushBits(node.index, 8);
		}
		else
		{
			bs.pushBit(false);
			encodedTree(node.left, bs);
			encodedTree(node.right, bs);
		}
	}

	/**
	 * Get individual huffman code from current spot in tree
	 * recurses until leaf node found
	 */
    public int getCode(BitStream bs)
    {
        Node current = root;
        boolean bit;
        while (!isLeaf(current))
        {
           bit = bs.readBit();
           if (bit) current = current.right;
           else current = current.left;
           
        }
        return current.index;
    }

    /**
     * is node a leaf node (childless)
     * @param n Node to test
     * @return true if node has no children
     */
	public boolean isLeaf(Node n)
	{
		return n.left == null;
	}

	@Override
	public int compareTo(Tree t)
	{
		return root.frequency - t.root.frequency;
	}
}

This must implement Comparable so it can be used by the Priority Queue in the tree creation process.

Our outer class start like this, with two constructors, one which takes the frequency data and created a Huffman Tree for encoding, and one which takes a BitStream of the encoded data and recreates the tree for decoding.

public class HuffmanTree
{
	// the Tree of Trees
	private Tree htree;

	// the bit codes and lengths
	private int[] huffmanCodes = new int[256];
	private int[] huffmanLengths = new int[256];

	/**
	 * Create Huffman Tree for encoding
	 * and populates the code/length arrays
	 * based on a 256 element array of frequency counts
	 * @param frequencies integer array of frequency counts
	 */
	public HuffmanTree(int[] frequencies)
	{
		this.htree = getHuffmanTree(frequencies);
		getCodes();
	}

	/**
	 * Create Huffman Tree for decoding
	 * from a BitStream of the encoded tree
	 * frequencies have been discarded
	 * @param bs BitStream of encoded tree
	 */
	public HuffmanTree(BitStream bs)
	{
		this.htree = getHuffmanTree(bs);
		getCodes();
	}

The getHuffmanTree method for encoding takes an int[256] array of frequencies, creates a node for each non-zero frequency and loads them into a Min Heap (Priority Queue). It then pulls out the two lowest frequency ones, adds the frequencies together and creates a new subtree out of them, and adds that subtree back to the queue. It does this until there is only one Tree left, which is now the completed Huffman tree.

private Tree getHuffmanTree(int[] frequencies)
{
	BinaryHeap<Tree> heap = new BinaryHeap<>();
	for (int i = 0; i < frequencies.length ; i++)
	{
		if (frequencies[i] > 0)
		{
			// add all frequencies > 0 as new subtree with no children
			heap.add(new Tree(i, frequencies[i]));
		}	
	}

	while (heap.length() > 1)
	{
		Tree t1 = heap.remove();
		Tree t2 = heap.remove();
		heap.add(new Tree(t1, t2));
	}

	return heap.remove();
}

The reverse method for recreating the tree recursively from a BitStream:

public Tree getHuffmanTree(BitStream bs)
{
	if (bs.readBit())
	{
		return new Tree(bs.readBits(8), 0);
	}
	else
	{
		Tree left = getHuffmanTree(bs);
		Tree right = getHuffmanTree(bs);
		return new Tree(left, right);
	}

}

Once the tree is made we can assign codes to the frequency values:

private void getCodes()
{
	if (htree.root == null) return;
	getCodes(htree.root);
}

/**
 * recursive helper class
 */
private void getCodes(Node root)
{
	if (!htree.isLeaf(root))
	{
		root.left.huffmanCode = root.huffmanCode << 1;
		root.left.huffmanLen = root.huffmanLen + 1;
        getCodes(root.left);
        
        root.right.huffmanCode = root.huffmanCode << 1 ^ 1;
        root.right.huffmanLen = root.huffmanLen + 1;
        getCodes(root.right);
    }
    else
    {
        huffmanCodes[root.index] = root.huffmanCode;
        huffmanLengths[root.index] = root.huffmanLen;
    }
}

This fills the huffmanCodes and huffmanLengths arrays. We have to have a 'length' value to account for padded zeroes, as we may have bit codes like '0010'. This could all be handled with Strings, but bitwise manipulation is faster and less memory intensive. Above, if the node is a non-leaf node, we append the left child with a zero (by simply bitshifting once to the left) and append the right child with a one (by bitshifting once to the left and XORing by one).

So now, to encode is simple. We loop through the input string (or byte[] array) and push the bit codes into a BitStream by using the lookup arrays.

public BitStream encode(String input)
{
	BitStream output = new BitStream();
	for (int i = 0; i < input.length() ;i++ )
	{
		output.pushBits(huffmanCodes[(int) input.charAt(i)], huffmanLengths[(int) input.charAt(i)]);
	}
	output.close();
	return output;		
}

public BitStream encode(byte[] input)
{
	BitStream output = new BitStream();
	for (int i = 0; i < input.length; i++)
	{
		output.pushBits(huffmanCodes[input[i]], huffmanLengths[input[i]]);
	}
	output.close();
	return output;
}

To decode we loop through the encoded BitStream until the EndOfBank flag is thrown, using the getCode() method from the Tree class to traverse through the tree and get the code for the bits pulled from the bitstream. The different lengths are handled automatically, as the method 'knows' when to stop by reaching a leaf node.

public String decode(BitStream input)
{
	String output = "";
	while (!input.EOB())
	{
		output += (char) htree.getCode(input);
	}
	return output;
}

and for bytes:

public byte[] decodeBytes(BitStream input)
{
 	byte[] output = new byte[input.length() * 4];
 	int counter = 0;
 	while (!input.EOB())
 	{
 		output[counter] = (byte) (htree.getCode(input) & 0xff);
 		counter++;
 	}
 	return Arrays.copyOfRange(output, 0, counter + 1);
} 

See the full code along with sample code here.

SQLite Database Access with a Swing GUI

Screenshot

Get full code here - Gist

This example builds upon this post here.

Developing a GUI program can be a challenge, and even though I like some of the builders out there (I like the NetBeans one specifically), I wanted to show how to develop it from scratch in a more Model-View-Controller style. I have split up the code into four classes:

1. InventoryGUI.java - the 'View' which only creates and places the graphical components

2. Inventory.java - The main object class that is used as the 'Model' in conjunction with

3. InventoryDBAccessor.java - All of the database access code abstracted away from the rest

4. InventoryController.java - Manages getting the data from the Model classes and controls the event handlers for the GUI, sending data to the GUI as requested, or back to the database.

The GUI is a simple one-record at a time CRUD program, that lets us step through the data forwards or backwards, add new records, edit the existing records, or delete records. Note that this is all extremely simplified for educational purposes and is not meant for large amounts of data, and does not even get into the relational aspect of DBMS.

The Database Accessor

Here we have our code that handles opening the database, reading all of the data into an ArrayList of Inventory objects, and handles adding, updating and deleting records from the table. Each method has to handle exceptions. Ideally, there shouldn't be any System.out/err.println messages here, they should be handled by a Logger, but for now I am sending the messages to the console.

class InventoryDBAccessor
{
    private final String JDBC_CONNECT = "jdbc:sqlite:Inventory.db";
    private final String JDBC_CLASS = "org.sqlite.JDBC";
    private final String DB_OPEN_SUCCESS = "Database connection opened successfully";
    private final String SQL_SELECT_ALL = "SELECT * FROM Inventory ORDER BY partnum ASC;";
    private final int SQL_DATABASE_ERROR = 1;

    private Connection connection;
    private Statement statement;
    private ResultSet resultSet;

    public InventoryDBAccessor()
    {
        try
        {
            connection = getConnection();
            statement = connection.createStatement();			
        }
        catch (SQLException e )
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
        }   
    }

    private Connection getConnection()
    {
        try
        {
            Class.forName(JDBC_CLASS);
            Connection c = DriverManager.getConnection(JDBC_CONNECT);
            System.out.println(DB_OPEN_SUCCESS);
            return c;
        }
        catch (ClassNotFoundException | SQLException e )
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
        }
        return null;
    }

    private void createTable()
    {
        try
        {
            String sql = "CREATE TABLE Inventory (partnum STRING (6)" +  
                    "UNIQUE ON CONFLICT FAIL PRIMARY KEY," +
                    "item STRING (100), description STRING (250)," + 
                    "qty INTEGER (6), price DOUBLE (8, 2));";

            // execute the statement string
            statement.executeUpdate(sql);                
        }
        catch ( SQLException e)
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());                
        }


    }

    public ArrayList<Inventory> loadInventoryFromDB()
    {
        try
        {
            System.out.println("Loading data from table...");
            ArrayList<Inventory> invList = new ArrayList<>();

            resultSet = statement.executeQuery( SQL_SELECT_ALL );

            while (resultSet.next())
            {
                    invList.add(new Inventory(resultSet));
            }
            System.out.println("Loaded " + invList.size() + " records.");
            return invList;			
        }
        catch ( SQLException e)
        {
            if (e.getErrorCode() == SQL_DATABASE_ERROR)
            {
                createTable();
                loadInventoryFromDB();
            }
            else
            {
                System.err.println( e.getClass().getName() + ": " + e.getErrorCode() );
                JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
            }
        }
        return null;
    }

    public void addToDB(Inventory item)
    {
            try
            {
                statement.executeUpdate(item.getSQLInsert());
            }
            catch ( SQLException e)
            {
                System.err.println( e.getClass().getName() + ": " + e.getMessage() );
                JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
            }
    }

    public void updateDB(Inventory item)
    {
        try
        {
            statement.executeUpdate(item.getSQLUpdate());
        }
        catch ( SQLException e)
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
        }
    }

    public void deleteFromDB(String partnum)
    {
        try
        {
            statement.executeUpdate("DELETE from Inventory WHERE partnum ='" + partnum + "';");
        }
        catch ( SQLException e)
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
        }
    }

    public void close()
    {
        try
        {
            statement.close();
            connection.close();	
            System.out.println("Database successfully closed.");		
        }
        catch (SQLException e)
        {
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
            JOptionPane.showMessageDialog(null, "Database error : " + e.getMessage());
        }   
    }
}

The GUI class

I decided to use a GroupLayout combined with a BorderLayout. The BorderLayout is used to put the text label at the top and the navigation buttons at the bottom. The group layout takes two definitions of the layout: the Horizontal Group and the Vertical group. See Oracle's tutorial here for more.

Here is the part of the code that defines the group layout:

	dataView = new JPanel();

	group = new GroupLayout(dataView);
		group.setAutoCreateGaps(true);
		group.setAutoCreateContainerGaps(true);
	dataView.setLayout(group);

	group.setHorizontalGroup(group.createSequentialGroup()
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.TRAILING)
			.addComponent(lblPartnum)
			.addComponent(lblItem)
			.addComponent(lblDescription)
			.addComponent(lblQty)
			.addComponent(lblPrice))
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.LEADING)
			.addComponent(scrollDesc)
			.addGroup(group.createSequentialGroup()
				.addGroup(group.createParallelGroup(GroupLayout.Alignment.LEADING)
					.addComponent(txtPartnum, GroupLayout.PREFERRED_SIZE, 80, GroupLayout.PREFERRED_SIZE)
					.addComponent(txtItem, GroupLayout.PREFERRED_SIZE, 150, GroupLayout.PREFERRED_SIZE)
					.addComponent(txtQty, GroupLayout.PREFERRED_SIZE, 100, GroupLayout.PREFERRED_SIZE)
					.addGroup(group.createSequentialGroup()
						.addComponent(txtPrice, GroupLayout.PREFERRED_SIZE, 100, GroupLayout.PREFERRED_SIZE)
						.addComponent(lblTotal)))))
		);

	group.setVerticalGroup(group.createSequentialGroup()
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.BASELINE)
			.addComponent(lblPartnum)
			.addComponent(txtPartnum))
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.BASELINE)
			.addComponent(lblItem)
			.addComponent(txtItem))
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.BASELINE)
			.addComponent(lblDescription)
			.addComponent(scrollDesc))
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.BASELINE)
			.addComponent(lblQty)
			.addComponent(txtQty))
		.addGroup(group.createParallelGroup(GroupLayout.Alignment.BASELINE)
			.addComponent(lblPrice)
			.addComponent(txtPrice)
			.addComponent(lblTotal))
			);

	this.add(dataView, BorderLayout.CENTER);

Another important part of the GUI is to set up methods so that another class can create the button action listeners, like this:

// methods for Controller to create listeners
public void addNextButtonActionListener(ActionListener listener)
{
    btnNext.addActionListener(listener);
}
public void addPrevButtonActionListener(ActionListener listener)
{
    btnPrevious.addActionListener(listener);
}

Now from our InventoryController class we can use anonymous inner classes to add the code for the listeners:

	// next button
   	frame.addNextButtonActionListener(new ActionListener()
   	{
        public void actionPerformed(ActionEvent evt)
        {
        	index++;
        	if (index >= invList.size()) index = 0;
        	getDataEntry();
        }
    });	

   	// previous button
    frame.addPrevButtonActionListener(new ActionListener()
    {
        public void actionPerformed(ActionEvent evt)
        {
        	index--;
        	if (index < 0) index = invList.size()-1;
        	getDataEntry();
        }
    });	

We also add public getters and setters for the text fields in the GUI so they can be accessed by the Controller class. We also add a method that sets up the screen for editing/adding records by enabling/disabling the proper fields and buttons.

The Inventory Class

We have our Inventory.java class file from previous examples, to which I have added a few minor things such as a default constructor, a full set of getter/setter methods, and I have added a 'getSQLUpdate()' method to create a SQL command statement to do an UPDATE action, and a bit of ugly code to generate the Part Number primary key:

// creates a SQL command string to update object
// part number is not updateable
public String getSQLUpdate()
{
    return "UPDATE INVENTORY "
        + "SET item = '" + item + "', description = '" + description
        + "', qty = " + qty + ", price = " + price
        + " WHERE partnum ='" + partnum + "';";
}

// generate part number
// if possible, uses first three letters
// of the first two words, 
// or fills with random digits
public String generatePartnum()
{
    Random rand = new Random();
    String retval = "";
    String[] words = item.toUpperCase().split(" ");
    for (int i = 0; i < words.length; i++)
    {
        if (i > 1) break;
        if (words[i].length() < 3)
        {
            retval += words[i];
            for (int j = 0; j < 3 - words[i].length(); j++)
            {
                retval += "" + rand.nextInt(10);
            }
        }
        else retval += words[i].substring(0,3);
        
    }
    return retval;
}

The Inventory Controller Class

We start the Controller class by instantiating the GUI class, creating the event listeners as described above, and then instantiating the Database Accessor class and loading all the data into an ArrayList. (In a real-world situation you would probably only load chunks of the data at a time. You could also use Dependency Injection here, but that's the topic for another example.)

public class InventoryController
{
	private final InventoryGUI frame = new InventoryGUI();
	private InventoryDBAccessor dao;
	private ArrayList<Inventory> invList;
	// current displayed record index
	private int index;
	// flag for whether 'save' and 'cancel' commands should treat as an 'add' or 'edit'
	private boolean editNotAdd;

	public InventoryController() throws SQLException
	{

		initListeners();

       	dao = new InventoryDBAccessor();
		invList = dao.loadInventoryFromDB();
		dao.close();
		index = 0;
		editNotAdd = false;
		frame.setVisible(true);
	}

We add the rest of the button listeners (see rest of code on Gist), and add very simple methods to use the DB Accessor:

public void addToDB(Inventory obj) throws SQLException
{
	System.out.println("Adding record to database...");
	dao = new InventoryDBAccessor();
	dao.addToDB(obj);
	dao.close();
}

public void updateDB(Inventory obj) throws SQLException
{
	System.out.println("Updating record...");
	dao = new InventoryDBAccessor();
	dao.updateDB(obj);
	dao.close();
}

public void deleteFromDB(String partnum) throws SQLException
{
	System.out.println("Deleting " + partnum + "...");
	dao = new InventoryDBAccessor();
	dao.deleteFromDB(partnum);
	dao.close();
}

We add a setDataObject() method used for add/edit records which does some minor validation and then sends the object either to the update or insert methods, and a getDataEntry() method which simply grabs the Inventory object from the ArrayList and populates the GUI fields with the info. The controller class also houses the main method.

Thanks for reading!!!

Full code here - Gist

Radix Sort

A radix sort is a type of sorting algorithm for integers which can be quite efficient in relation to comparison-based sorting algorithms. Internally it uses another sorting algorithm, a counting sort. The way the radix sort works is by going through the digits of the list of numbers one exponential place at a time, and sorting by that digit. It starts at the Least Significant Digit or the right-most. Consider the following list:

209
3
48
91
66
101
30
795

first we take the digits in the '1s' place and count the frequencies:

20[9]
  [3]
 4[8]
 9[1]
 6[6]
10[1]
 3[0]
79[5]

frequencies:

0 : 1
1 : 2
2 : 0
3 : 1
4 : 0
5 : 1
6 : 1
7 : 0
8 : 1
9 : 1

Now, we take the frequency table and make each element the sum of the previous elements:

0 : 1
1 : 3
2 : 3
3 : 4
4 : 4
5 : 5
6 : 6
7 : 6
8 : 7
9 : 8

This actually gives us the proper index to place the integer from the original array so that they are sorted by that digit. Iterate through the original array, extracting the digit for the current place, and use it as the index for the count array. The value at that index, minus 1, is where that number should go. Make a temporary array and assign the value, and then subtract one from the count at the current index.

First value is 509 with the extracted index being 9. Value at count[9] is 8, so now the number 509 will go into the 7th index of the temporary array. The value of the count array at index 9 is changed to 7. This is only important if there is more than one of that digit. But, we actually want to work backwards, from the last element to the first, so that larger numbers will be in the higher indices. So, after the first pass we have:

30
91
101
3
795
66
48
509

Now we take the digits at the 10s place:

 [3]0
 [9]1
1[0]1
 [0]3
7[9]5
 [6]6
 [4]8
5[0]9

0 : 3
1 : 0
2 : 0
3 : 1
4 : 1
5 : 0
6 : 1
7 : 0
8 : 0
9 : 2

0 : 3
1 : 3
2 : 3
3 : 4
4 : 5
5 : 5
6 : 6
7 : 6
8 : 6
9 : 8

new array order:
    
101
3
509
30
48
66
91
795

And then the third pass, in the 100s place:

[1]01
[0]03
[5]09
[0]30
[0]48
[0]66
[0]91
[7]95

which will result in the sorted list

3, 30, 48, 66, 91, 101, 509, 795

So, here is the Java code for that:

public void radixSort(int array[])
{
    int digitPlace = 1;
    int n = array.length;
    int result[] = new int[n];

    int max = 0;


    // loop until we reach the largest digit place
    while ( digitPlace == 1 || max / digitPlace > 0) {
        int count[] = new int[10];


        // get frequency count of digits at current digit place
        for (int each : array) {

            // on first pass, find max
            if (digitPlace == 1) {
                if (each > max) {
                    max = each;
                }
            }

            count[(each / digitPlace) % 10]++;
        }

        // counting sort algorithm
        // make each element in the frequency array
        // store the sum of previous counts
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }


        // get index from count array and place original elements
        // into temp array
        for (int i = n - 1; i >= 0; i--) {
            
            // extract correct digit
            int current = (array[i] / digitPlace) % 10;
            
            result[count[current] - 1] = array[i];
            count[current]--;
        }

        // copy temp array back to original
        System.arraycopy(result, 0, array, 0, n);

        // Move to next digit place
        digitPlace *= 10;
    }
}

Now, you might notice this algorithm will be inefficient in space complexity, as it cannot sort the elements in place and requires a temporary array of size n and also uses the count array of size radix. This we cannot easily remedy, although there are in-place algorithms for a MSD(Most Significant Digit) radix sort. You might also notice that frequent usage of division and the modulus operator may also be a source of slowdown in this implementation. This brings us to the radix part of the radix sort... we have made our sort use a radix of ten. However, if we change that to base 16, we can use the added speed benefit of bit shifting and masking.

Hexadecimal Radix Sort

Every hex digit is 4 bits. so, instead of using division, multiplication and modulus, we can use bit shifting and masking.

So, instead of this, for example:

// extract correct digit
int current = (array[i] / digitPlace) % 10;    

we use this:

int current = (array[i] >> pos) & 0xf;

This takes the value at array[i], shifts it to the right by the current amount of bits for the digit place, and then masks it by 0xf (binary 1111) to mask it to one hexadecimal digit.

Here is the code for that:

public void radixSortHex(int[] array) {

    // we now start at 0 or the rightmost bit position
    int pos = 0; 
    int n = array.length;
    int[] result = new int[n];
    int max = 1;

    while (max >> pos > 0) {
    
        // note our frequency array is now 16 instead of ten
        int[] count = new int[16];

        for (int each : array) {
            if (pos == 0) {
                if (each > max) max = each;
            }
            count[(each >> pos) & 0xf]++;
        }

        for (int i = 1; i < 16; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int current = (array[i] >> pos) & 0xf;
            result[count[current] - 1] = array[i];
            count[current]--;
        }

        System.arraycopy(result, 0, array, 0, n);
        pos += 4;
    }
}

Now, testing these in comparison to Arrays.sort:

Testing an array of 1 million numbers in the range 0 - 10,000,000, Arrays.sort takes around 0.3 to 0.5 seconds on my slow laptop. The base-10 radix sort takes similar times, but slightly slower at around 0.4 to 0.6 seconds. However, the base-16 radix implementation consistently gets times around 0.15 - 0.16 seconds, which is significantly faster.

Thanks again for reading!!!

I have often wondered why Java's array data type and the associated classes Arrays don't include a number of really simple methods that everyone learning Java is forced to write anyway, so I have made a static utility class for reference and ease of use.

Remember that

1. Arrays are immutable, so you must always assign the return value of the method back to the original variable name, or to a new one like:

     int[] a = { 1, 2, 3, 4 };
     a = ArrayUtils.reverse(a);

2. Arrays of a primitive type cannot be used in generic methods, so either use the Object version (i.e. Integer for int) or use the conversion methods given like:

    int[] a = { 1, 2, 3, 4};
    Integer[] b = ArrayUtils.append(ArrayUtils.objectifyInt(a), 5);

Methods:

Here is the code: https://gist.github.com/anonymous/fc17995ad169942bf8f2c210b1924268

Dynamic Array

Chances are you have experienced the difference between using Arrays and ArrayLists, but have you ever wondered how ArrayLists work under the hood? Let's make our own DynamicArray class and see how it can be done!! Inside we will discover the difficulties of using Arrays with Generic types, and how to easily manipulate the size of Arrays.

We all know the main problem with arrays is that you have to know the size upon declaration, and that it cannot be changed once defined. Did you know that ArrayLists use an Object array internally?

Now, we can grow an array by creating a new one of the proper type and size, then manually copying the old elements into the new:

int[] newArray = new int[newSize];
for (int i = 0; i < oldArray.length; i++) {
    newArray[i] = oldArray[i];
}
oldArray = newArray;

Luckily, there is already a class in java.util.Arrays to handle this, Arrays.copyOf(), so to make it easier we can go:

oldArray = Arrays.copyOf(oldArray, newSize);

The same can be done to shrink the array, just be careful not to overwrite any important data.

This obviously takes linear time, meaning for every n elements in the array it will take n operations, so we do not want to perform this operation every single time you add something to the array. In order to handle this, we keep two different member variables, one that keeps the size of the array in terms of how many actual elements have been added to it, and then we keep a capacity which is how many elements the internal array can hold. For memory's sake, we want to keep the initial capacity low, such as 10, and then when we grow the capacity, we will make it somewhat larger each time. There are different ways to handle this. One suggestion is to start at 1 and increase the capacity by powers of two each time, 1 - 2 - 4 - 8 - 16 - 32 - 64 and so on. I prefer the way that Java's ArrayList handles it, by starting at ten and then increasing by 1.5 times the size each time.

So, let's set up our class header:

public class DynamicArray<E> implements Iterable<E>, RandomAccess {

    private static final int INITIAL_CAPACITY = 10;

    private int size;
    private int capacity = INITIAL_CAPACITY;

    private Object[] array;

Arrays and Generic types

Now you might ask at this point, why use an array of Objects, why not just use the generic E type for the internal array? Well, Java doesn't work that way (See here for explanation) So, we need to work with an array of Object types and cast to the generic type as necessary.

We add three different constructors, first a basic one that initializes the array to the default capacity:

public DynamicArray() {
    array = new Object[INITIAL_CAPACITY];
}

One that lets the user specify the capacity:

public DynamicArray(int capacity) {
    if (capacity <= 0) throw new IllegalArgumentException("Illegal initial capacity : " + capacity);
    this.capacity = capacity;
    array = new Object[capacity];
}

And one that takes an array of type E and loads it in:

public DynamicArray(E[] inputArray) {
    this(inputArray.length + INITIAL_CAPACITY);
    for (int i = 0; i < inputArray.length; i++) {
        array[i] = inputArray[i];
        size++;
    }
}

Now, we need a couple of private methods that will handle changing the array size, and testing input ranges.

private void sizeCheck() {
    if (size + 1 >= capacity) {
        grow();
    }
}

private void grow() {
    capacity += (capacity * 3)/2; // new capacity roughly 1.5 times the current capacity
    array = Arrays.copyOf(array, capacity);
}

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index : " + index);
    }
}

We can now have our simple add method which appends the element to the end of the list:

public void add(E element) {
    sizeCheck();
    array[size++] = element;
}

This action takes amortized constant time which means it averages out to constant time, even though the array resizing takes linear time.

A little more complicated is adding an element to a specific index:

public void add(E element, int index) {
    if (index == size) {
        add(element);
    } else {
        rangeCheck(index);
        sizeCheck();
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;

    }
}

Here we first test if the requested index is at the end of the list and if so, just perform a normal add operation. Otherwise, we want to test that the index is in the proper range, check the new size if the array needs to grow, set the element at the requested index and then use System.arrayCopy to move the rest of the elements up one.

Here is our get method, now see how we have to cast it from Object back to the generic type E:

@SuppressWarnings("unchecked")
public E get(int index) {
    rangeCheck(index);
    return (E) array[index];
}

We use the 'SuppressWarnings` annotation to get rid of the compiler warning for this action.

And a set method:

public E set(E element, int index) {
    rangeCheck(index);
    E value = get(index);
    array[index] = element;
    return value;
}

Now we want an indexOf() function, which will also be used by contains(). We will allow for the possibility of a null value being passed as a parameter, and just return the index of the first null value in the list, if there is one, otherwise we just go through the list and search for the item. Note, the type of object being tested for must have a valid equals method in order to work properly. For contains we just see if indexOf returns a negative value.

public int indexOf(Object obj) {
    if (obj == null) {
        for (int i = 0; i < size; i++) {
            if (array[i] == null) return i;
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (obj.equals(array[i])) return i;
        }
    }
    return -1;
}

public boolean contains(Object obj) {
    return indexOf(obj) >= 0;
}

Now we need two different remove() functions, one which takes an index as a parameter and one which removes a specific object.

@SuppressWarnings("unchecked")
public E remove(int index) {
    rangeCheck(index);
    E value = (E) array[index];
    int numberToMove = size - index - 1;
    if (numberToMove > 0) {
        System.arraycopy(array, index + 1, array, index, numberToMove);
    }
    array[--size] = null; // don't leave an orphan
    return value;
}

public boolean remove(Object o) {
    int found = this.indexOf(o);
    if (found < 0) return false;
    this.remove(found);
    return true;
}

Note that remove would have a worst-case of O(n) for removing from the head of the list. This is good to know, if you are using that option exclusively then perhaps you should be using a LinkedList instead.

When we try make a toArray method, we run into the same problem discussed above with Generics and Arrays. We can easily return an array of Objects

public Object[] toArray() {
    return Arrays.copyOf(array, size);
}

But, returning an Array of the original generic type is more difficult. It requires that the calling class send an already declared array of the proper type to the method: (And, requires some special casting)

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    return (T[]) Arrays.copyOf(array, size, a.getClass());
}

Lastly, we provide an iterator:

@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        int cursor = 0;

        @Override
        @SuppressWarnings("unchecked")
        public E next() {
            if (!hasNext()) {
                throw new IllegalArgumentException("No more elements available.");
            }
            E value = (E) array[cursor];
            cursor++;
            return value;
        }

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public void remove() {
            rangeCheck(cursor);
            DynamicArray.this.remove(cursor);
        }
    };
}

What have we learned?

We have learned that it's really not that hard to manipulate the size of arrays. We have learned that you cannot easily use arrays with generic types. We have learned that you still need to think about time complexity when using ArrayList - always try to specify a reasonable capacity if you can, to avoid frequent array resizing. Don't use an ArrayList if what you need is frequent remove(0) operations - use a LinkedList for that.

Here's the full code on Gist

Enum Classes in Java

Enums are a special type of class in Java that is incredibly useful and powerful. At its simplest, it is just a list of related items or states:

enum Color = { BLACK, WHITE, RED, GREEN, BLUE }

Which you can use like:

Color myColor = Color.RED;

System.out.println(myColor.name()); // outputs RED
System.out.println(myColor.ordinal(); // outputs 2

These can make your code much more organized and readable. Enums are final and can be in their own class or as an inner class. You can use them in switch/cases and many other ways.

The neat part

Now, here's the neat part. You can assign member variables and methods to an enum also! This is awesome for a set of constant values that you can use with the enums.

Here's an example, a style often used for movement in a grid:

public enum Direction {
    NORTH (0 , -1),
    EAST (1, 0),
    SOUTH (0, 1),
    WEST (-1, 0);

    private int dx, dy;

    // 'constructor'
    private Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }

    public int getDx() { return dx; }
    public int getDy() { return dy; }
}

This assigns the proper delta values for movement in the direction of the given name, considering an x,y 2d grid. In other words, for North, we want to subtract 1 from the Y-axis, and keep the X-axis the same. The constructor for the enum takes the values inside the parentheses and assigns them to the member variables. This saves you from needing a switch statement or a whole bunch of if statements.

We are going to add another possibility: Instead of using the parentheses and the constructor, you can also use a static initialization block to fill a member variable:

In that same class, add this before the constructor:

private Direction opposite;

static {
    NORTH.opposite = SOUTH;
    EAST.opposite = WEST;
    SOUTH.opposite = NORTH;
    WEST.opposite = EAST;
}

And then add this to the getters:

public Direction getOpposite() { return opposite; }

Now some testing code:

public class DirectionTester {
    static class Bot {
        int x;
        int y;

        public Bot(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void move(Direction dir) {
            x += dir.getDx();
            y += dir.getDy();
        }

        @Override
        public String toString() {
            return "Bot{" + "x=" + x + ", y=" + y + '}';
        }
    }

    public static void main(String[] args) {
        Bot robby = new Bot(0,0);

        Direction myDir = Direction.WEST;

        System.out.println(myDir.name());
        System.out.println(myDir.ordinal());

        robby.move(Direction.NORTH);
        robby.move(Direction.NORTH);
        robby.move(Direction.EAST);
        robby.move(Direction.EAST);
        robby.move(Direction.SOUTH);

        System.out.println(robby); // to 2, -1

        String[] moves = { "north", "east", "south", "south", "west", "west", "west"};

        for (String each : moves) {
            robby.move(Direction.valueOf(each.toUpperCase()));
        }

        System.out.println(robby); // back to 0,0


        robby.move(myDir);
        if (robby.x < 0) robby.move(myDir.getOpposite());

        System.out.println(robby); // did not move


    }
}

And the output:

WEST
3
Bot{x=2, y=-1}
Bot{x=0, y=0}
Bot{x=0, y=0}

Let's Get Even More Funky

Here's an even more powerful way to use Enums: Using Java 8 Lambda expressions, we can put Functions into the enum.

A simple calculator example:

import java.util.function.DoubleBinaryOperator;

public enum Calculate {
    ADD ((x, y) -> (x + y)),
    SUBTRACT ((x, y) -> ( x - y)),
    MULTIPLY ( (x, y) -> ( x * y)) ,
    DIVIDE ((x, y) -> ( x / y)),
    POWER (Math::pow);

    private final DoubleBinaryOperator function;

    Calculate(DoubleBinaryOperator function) {
        this.function = function;
    }

    public DoubleBinaryOperator getFunction() {
        return function;
    }
}

And the test class:

public class Calculator {
    public static double calc(double x, double y, Calculate operation) {
        return operation.getFunction().applyAsDouble(x, y);
    }
    public static void main(String[] args) {
        double a = 2;
        double b = 6;
        double c = calc(a, b, Calculate.POWER);
        double d = calc(c, b, Calculate.MULTIPLY);
        System.out.println(calc(d, a, Calculate.DIVIDE));

    }
}

Now, this may seem overly complicated, but the power comes from the fact that you can use almost any kind of function you want, including more complicated methods. This example specifically uses methods that take two double values as parameters and return a double, although you can use any of the functions on this list to make extremely powerful enum types. Here's an example I made to solve AdventOfCode - Day 23 using similar methods.

Course Contents

• Introduction to JMS – Java Message Service

• Install and Setup Glassfish for JMS

• Send and Receive a message in JMS

• JMS Message Model

• JMS Prioritize Messages

• JMS Point-to-point messaging in Action

• JMS pub-sub messaging model

• JMS Message Selectors in Action to Filter Messages

• Guaranteed Delivery using JMS Message Acknowledgement

• JMS Transactions in Action

1. How Can we reflect on the changes without restarting the server?

2. What is ELK Stack and why do we use this?

3. How will you monitor the health of Spring Boot microservices?

4. Spring Boot is known for AutoConfiguration, how this Autoconfiguration works actually?

5. How to write a custom auto-configuration class?

6. What are ControllerAdvice and ExceptionHandler, state the difference?

7. What is Spring CLI, how this is beneficial to Programmers?

8. What is Swagger, how swagger boost the efficiency of Springboot?

9. Explain default Embedded Server in Spring-boot? Explain the benefit of the same?

10. What is the default port of Embedded Tomcat in Springboot, how can we change it?

11. What are the log levels in Springboot?

12. What are profiles in the spring-boot?

13. Can we run the spring-boot application through the command line?

14. What are the differences between .yml and .properties config file, which one we should use in spring-boot?

15. How do we generate an executable JAR from Spring-boot?

Password Managing: Salt and Hash

Often in the news the last few years are stories like this where a large, trusted company has kept user passwords in plain text files on their servers. This is very bad, as large files of known passwords and user information get leaked and passed around by hackers.

Salting and Hashing

While it sounds like a delicious breakfast dish, this is an excellent way to increase the security for your password store. For a long time, the accepted idea was to not actually store a user's password on the system, but to apply a cryptographic hash function to the password, and save that. The more bits in the hash function, the higher the security. Note that a hash function is not the same as encryption. A hash cannot generally be reversed. So, the hash is applied to the password when entered and then checked against the hash in storage.

SHA-256

In this example we will be using the hash function called SHA-256 which is extremely common and generally accepted to be reasonably secure. This generates a 256 bit (32 byte) value for a given string. This value is usually kept as a String of hexadecimal values.

So, for the password ******** (I mean, 'Hunter2') the following hash will be generated:

52D766A8574BB9374FCAE0AD395D50D24705D7F6C3989C38F4355B2CFCDE19CF

Seems pretty secure, right? Now, go here: https://crackstation.net/, enter that hash, check the box that you are not a robot (AND ARE OF COURSE A NORMAL HUMAN PERSON LIKE I AM HAHAHA) and hit 'crack hash'.

You will see that it finds the password!!! That's because there are freely available tables of millions of common passwords hashed with different algorithms that can be easily reverse looked-up.

Adding a little salt

So a simple method to avoid this type of attack is to add a random value to the password before we hash it. This is called a salt, and we can actually store it in the same database as the hash - what this does is make it so that, even if the server was compromised and someone had the salt/hash list, they would still have to brute force every possible password combination until they found one that worked with the given salt and hash, and, in combination with a strong password, would take far too much computational time to complete.

Now, we take the original pass and add some random gibberish to it:

Hunter2ldk45kaidhnf111

new hash: CEAE042EA4B05826AE1CDF0054450E0C879BD4BE33775AF19F78A85A74C5E3C3

Now if we try that one on crack station, it comes back with 'not found!'

There's other steps that can be taken, such as hashing the value hundreds of times, to literally make the process slower and less efficient which further prevents brute force attacks.

How to use in Java

Luckily, Java provides really simple libraries to accomplish this.

The Hash

First, let's see how to generate the hash. We use java.security.MessageDigest:

    String password = "Hunter2";
    String hash = "";
    try {
 
        // get instance of MessageDigest using 'SHA-256' algorithm
        MessageDigest md = MessageDigest.getInstance("SHA-256");
 
        // convert password to byte array of its ASCII digits
        // use the digest method to create the hash, and fill
        // a byte array with the resulting values.
        byte[] bytes = md.digest(password.getBytes());
        
        // convert the hash from a byte array to a hexadecimal string
        // note that we have to use our own method here
        // see below
        hash = BitUtils.bytesToHex(bytes);
        
    } catch (NoSuchAlgorithmException e) {
        e.printStackTrace();
    }

As described above, the MessageDigest class' digest method returns a byte array containing the 32 bytes of the hash, with 0 index being the Most Significant Byte (The leftmost byte). We need to convert this to a String. Each byte will need to be padded to two characters, (i.e. the decimal value 10 will need to be 0a) and Java's Integer.toHexString is not up the the task. We could use String.format("%02x", b) but that is slow, so I will use my own methods here, from my BitUtils class that will be the subject of another post.

public static String bytesToHex(byte[] in) {
    StringBuilder sb = new StringBuilder();
    for (byte each : in) {
        sb.append(toHexString(each & 0xff, 8));
    }
    return sb.toString();
}

    /**
     * Returns a padded hex string of integer n
     * @param n integer
     * @param pad bit depth to pad to, i.e. 8 for 2 hex digits
     *            will be padded with leading zeroes
     * @return hex string
     */
    public static String toHexString(int n, int pad) {
        StringBuilder result = new StringBuilder();
        while (n != 0) {
            result.insert(0, Character.forDigit(n & 0xf, 16));
            n >>>= 4;
        }
        pad -= result.length() * 4;
        while (pad > 0) {
            result.insert(0, "0");
            pad -= 4;
        }
        return result.toString();
    }

This will return the same hash as shown in our first example above,

52d766a8574bb9374fcae0ad395d50d24705d7f6c3989c38f4355b2cfcde19cf

(Note the 'letter' digits of a hex string can be either upper or lower case, doesn't really matter, so long as the same convention is kept throughout your code.)

The Salt

The salt can be really any random string of printable characters. Personally I like using a hex string with the same bit depth as the hash. The most important part is to use a cryptographically secure random number generator, which for java is SecureRandom.

So, to generate the salt is as simple as:

    SecureRandom random = new SecureRandom();
    byte[] bytes = new byte[32];
    random.nextBytes(bytes);
    String salt = BitUtils.bytesToHex(bytes);

Now let's create a class we can use both to create and test our salt/hash combos:

public class PasswordHasher {
    private String salt;
    private String hash;

    private PasswordHasher(String pass) {
        generateSalt();
        generateHash(pass);
    }

    private PasswordHasher(String pass, String salt) {
        this.salt = salt;
        generateHash(pass);
    }

    public static PasswordHasher getNewFromPass(String pass) {
        return new PasswordHasher(pass);
    }

    public static PasswordHasher getWithSalt(String pass, String salt) {
        return new PasswordHasher(pass, salt);
    }

    public String getSalt() { return salt; }
    public String getHash() { return hash; }

    private void generateSalt() {
        SecureRandom random = new SecureRandom();
        byte[] bytes = new byte[32];
        random.nextBytes(bytes);
        salt = BitUtils.bytesToHex(bytes);
    }

    private void generateHash(String pass) {
        pass += salt;
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] bytes = md.digest(pass.getBytes());
            hash = BitUtils.bytesToHex(bytes);
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
    }
    
}

So, say we have a new user who has entered and verified their password. We create an instance of PasswordHasher using the static constructor method:

PasswordHasher ph = PasswordHasher.getNewFromPass("Hunter2");
System.out.println("Salt: " + ph.getSalt());
System.out.println("Hash: " + ph.getHash());

Results:

Salt: 6d4766de7c1cd9816a4a1b0619b23986c93bec5ca6d841e5984d61b20d086468
Hash: 7301ba687f1ad736bea10a4c7822fbb769324a8f34d34a26278087ecdd5322b2

You would now store these, along with the userID and any other applicable information in your database, JSON file or text file. When you want to verify the password, you look up the salt and hash for the specified userID and do the following:

PasswordHasher ph = PasswordHasher.getWithSalt(password, user.getSalt());
return user.getHash().equalsIgnoreCase(ph.getHash());

Now, this just barely scratches the surface of user security. We haven't even gotten in to the argument about whether the hashing/salting should be done client-side or server-side (hint: it's server-side) but this should be a start. Thanks for reading!!!

HashMap is an important class and every Java dev should be aware of it. Here are 10 examples of using HashMap in Java:

https://www.java67.com/2013/02/10-examples-of-hashmap-in-java-programming-tutorial.html

I've been coding this app live on Twitch (https://twitch.tv/jitterted), and then editing them and posting them on my YouTube channel (https://www.youtube.com/channel/UCx8qMdZ6JoZgOcOQxWlyV8A).

Come join me live, or watch the videos later. Full source code is on GitHub (https://github.com/tedyoung/kid-bank) and the public roadmap is on Trello (https://trello.com/b/Tkldfg4X/kidbank).

Find out more on my web page: https://www.tedmyoung.com/kid-bank-the-money-tracker-for-kids/

This isn't just a toy app, it's a real-live application (professionally developed with unit tests and cloud deployment) that I'll be using for my son. Just added SMS text message support so my son can use his phone to request his current balance.

Introduction to JavaFX: Future Value of Investment Calculator

sample gif

JavaFX GUI

JavaFX is Oracle's replacement for the Swing GUI library, it has been out for a few years now, but many have been slow to adopt it. Here's a quick run-down of the pros and cons vs Swing:

-Pros

1. The ability to use FXML makes separation of the Model, View and Controller elements fairly easy.

2. FXML lets you remove the 'ugly' component initialization code and stick it in an XML-style schema

3. The ability to use CSS makes styling your application/skinning it easy.

4. The layout managers are much easier to use than Swing

-Cons

1. The documentation is confusing and vague at best.

2. Some elements are still buggy/incomplete, and Oracle has been very slow to update.

3. Did I mention the documentation sucks?

4. The use of annotations/reflection which some people don't like. However, you can create all the elements in Java without using FXML.

That being said, let's get started!! This tutorial will assume you are using IntelliJ IDEA (and really, why the heck aren't you using it?):

Open up IDEA and hit File -> New -> Project... and then select Java FX Application. Name the project FutureValue.

Now, the IDE has already created a basic framework for you, but let's rename things. First, change the package name from example to fvcalc by right clicking on the package folder in the project view on the left, selecting refactor -> rename. Change the name of the Controller class to FVController, and the Main class to FutureValue, and the FXML file to fv_calc.fxml using the same methods.

Right-Click on the package folder fvcalc and select new -> file and name the file fv_style.css

Logic

Let's put our logic class into a different package. Right-click on the src folder in the Project view and select new -> package and title it logic. Right-click on that new package and select new -> Java class and name it FVLogic.

We are making a calculator to determine the Future Value of an Investment explained here. To allow for different methods of compounding the interest, let's make an enum:

public enum CompoundType {
    YEARLY(1), BIANNUALLY(2), QUARTERLY(4), MONTHLY(12), WEEKLY(52), DAILY(356);
    private int compounding;
    CompoundType(int compounding) { this.compounding = compounding; }
    public int getCompounding() { return compounding; }
}

and now the method which does the calculation:

public static double futureValue(double investment, double rate, int periods, CompoundType cmp) {
    rate = 1 + (rate / 100) / cmp.getCompounding();
    periods *= cmp.getCompounding();

    // FV = PV * R^n
    return investment * Math.pow(rate, periods);

The GUI

Now, let's go to the main method, FutureValue.java. Notice that IDEA has already done most of the work here, just change the 'hello world' lines and the size to look like this:

    primaryStage.setTitle("Future Value of Investment Calculator");
    primaryStage.setScene(new Scene(root, 400, 275));

Note the line here:

    Parent root = FXMLLoader.load(getClass().getResource("fv_calc.fxml"));

This gets all of the component details from the listed FXML file.

FXML

All of the GUI components and layout can be defined by an FXML file described here.

If you look at the IDE generated FXML file, you see it already set up a GridPane. The GridPane is a grid layout where items are specified by row and column index. Anything we define inside of the GridPane tags will be added to the pane. Note that the pane is connected to the FVController class already:

<GridPane fx:controller="fvcalc.FVController"

We tweak some of the values and add 'padding' around the pane:

<GridPane fx:controller="fvcalc.FVController"
      xmlns:fx="http://javafx.com/fxml" alignment="center" hgap="10" vgap="8">
      <padding><Insets top="40" right="25" bottom="10" left="35"/></padding>

The HGap and VGap are horizontal and vertical gaps between the components.

Now we add the rest of our components in the form of Labels and TextFields for the user input, and a ComboBox to select the type of compounding interest, a button to perform the calculation, and a final label for the result.

 <Label text="Initial Investment:"
        GridPane.columnIndex="0" GridPane.rowIndex="0"/>
 <TextField fx:id="textInvestment"
            GridPane.columnIndex="1" GridPane.rowIndex="0"/>
 <Label text="Interest Rate:"
        GridPane.columnIndex="0" GridPane.rowIndex="1"/>
 <TextField fx:id="textRate" GridPane.columnIndex="1" GridPane.rowIndex="1"/>
 <Label text="Years:"
        GridPane.columnIndex="0" GridPane.rowIndex="2"/>
 <TextField fx:id="textYears"
            GridPane.columnIndex="1" GridPane.rowIndex="2"/>
 <Label text="Compounded:"
        GridPane.columnIndex="0" GridPane.rowIndex="3"/>
<ComboBox fx:id="comboCompound"
          GridPane.columnIndex="1" GridPane.rowIndex="3"
          onAction="#getSelected">
    <items><FXCollections fx:factory="observableArrayList">
        <String fx:value="Yearly"/>
        <String fx:value="Biannually"/>
        <String fx:value="Quarterly"/>
        <String fx:value="Monthly"/>
        <String fx:value="Weekly"/>
        <String fx:value="Daily"/>
    </FXCollections></items>
    <value><String fx:value="Yearly"/></value>
</ComboBox>
 <Button text="Calculate"
         GridPane.columnIndex="1" GridPane.rowIndex="4"
         onAction="#calculate"/>
 <Label fx:id="result" id="result_text" GridPane.columnIndex="0" GridPane.rowIndex="5"
        GridPane.columnSpan="3"/>
</GridPane>

Any element that will need to be referenced by the controller class has a fx:id= tag. This will show up as red for now, as we have not set it up in the controller class yet. Any element that needs special CSS styling needs a regular id= tag, we set this up for the result label. Elements that perform an action, specifically the Button and ComboBox, need an onAction="#someMethod" tag. This will also be highlighted in red until we set up the corresponding methods in the controller class. Note the setup for the ComboBox, it's a somewhat complicated series of tags to define the options for selection, and setting the default.

The Controller Class

First, we need to declare and annotate the component that have a fx:id tag in the FXML file:

@FXML private Label result;                 // these fields here
@FXML private TextField textInvestment;     // must be declared with the
@FXML private TextField textRate;           // @FXML annotation
@FXML private TextField textYears;          // so they can be referenced
@FXML private ComboBox<String> comboCompound; // from the FXML document

We need to add a normal member field for the current compounding interest value and set it to the default:

private CompoundType comp = CompoundType.YEARLY;   // current type of compounding interest

next, let's add the Event Action Handler methods that we named in the FXML file:

First, for the comboBox to handle when the value is changed by the user:

@FXML public void getSelected(ActionEvent e) {
    comp = FVLogic.CompoundType.valueOf(comboCompound.getSelectionModel().getSelectedItem().toUpperCase());
}

Note the @FXML annotation, this ties it in to the onAction tag from the FXML file.

Next, the event handler for the button:

@FXML public void calculate(ActionEvent event) {
    double principal = getDouble(textInvestment.getText());
    double rate = getDouble(textRate.getText());
    double years = getDouble(textYears.getText());
    if (principal > 0 && rate > 0 && years > 0) {
        double calc = FVLogic.futureValue(principal, rate, (int) years, comp);
        result.setText("$ " + String.format("%,.2f", calc));
    }
    else {
        result.setText("Invalid Entry.");
    }
}

This needs another method to extract the double value and check for invalid entries, such as letters, punctuation or negative numbers. I'm sure there's a way to do this using FXML, but again, theDocumentation="vague_at_best".

 private double getDouble(String text) {
     if (text.length() > 0) {
         double d;
         try {
             d = Double.parseDouble(text);
             return d;
         }
         catch (NumberFormatException e) {
             return 0.0;
         }
     }
     return 0.0;
 }

Any invalid entries will be set to zero, since the calculation needs non-zero, positive values. So, the calculate method pulls the three values from the text fields, converts them to double value, and then calls the Logic method to calculate our result, then displays the result, or displays an error message if any of the entries are invalid.

Ok, the application now runs, but it's kinda bland. This is where the CSS comes in.

CSS

Now we can prettify things using CSS. Note that it is special to JavaFX, and again has some wonderfully 'simple' documentation.

Open the fv_style.css file we created earlier. First, let's use a cool background image here, save it as 'yellow_lined.png' in your src folder and set the root:

.root {
    -fx-background-image: url("yellow_lined.png");
    -fx-background-size: stretch;
}

Let' play with the fonts for the labels and textfields:

.label {
    -fx-font-family: "sans-serif";
    -fx-font-size: 14px;
    -fx-font-weight: bold;
    -fx-font-style: italic;
}

.text-field {
    -fx-font-family: "Verdana";
    -fx-font-size: 12px;
}

And lastly, for no good reason lets add some effects to the result label:

#result_text {
    -fx-font-family: "Arial Black";
    -fx-font-size: 24px;
    -fx-text-fill: red;
    -fx-effect: dropshadow( gaussian , black , 2,0.2,0,1);
}

Add this to the FXML file before the </GridPane>

<stylesheets> <URL value="@fv_style.css"/> </stylesheets>

Now it looks like the GIF shown at the top!!

Here's the full code on Gist

There we have our basic JavaFX tutorial, thanks again for checking it out!!

Frequency Tables

Frequency tables can be very useful for various types of situations, such as statistical analysis and encoding. A frequency table tracks the number of times a data value has occured in a given set.

The two most effective ways of implementing a Frequency Table in Java are using Arrays or HashMaps.

Frequency Table Arrays

If the data values you are tabulating are simple integers (or can simply be converted to integer, i.e. char), and the range of the frequencies is known, then it is easiest to use an array. Array lookup and insertion run in constant ( O(1) ) time, and the memory usage is simply 4n bytes ( + a little overhead).

So, to make the frequency table, we make the size of the array equal to the total range of elements. Then, we go through the data, and use the integer value as the index of the array, and add one to it.

Suppose we are counting the frequency of individual digits in a number, we want an array of size 10 to stand for the digits from 0 - 9. Say the first digit is 5, we go to array index 5 and add one.

int[] frequencyDigits = new int[10];

int n = 5;

frequencyDigits[n]++;

Say we want to count the occurrences of letters in a string. Let's assume the input has been sanitized to only lower case letters with no punctuation.

 int[] freq = new int[26];
 String str = "hello world nice to meet you";

 for (int i = 0; i < str.length(); i++) {
     if (Character.isLowerCase(str.charAt(i))) {

         // turn char into an int from 0 - 25
         int c = str.charAt(i) - 'a';
         freq[c]++;
     }
 }

     // or, if you want to impress your friends and humiliate your enemies with java 8,

     /*
     str.chars()
             .filter(Character::isLowerCase)
             .forEach(x -> freq[x - 'a']++);
        */

     // now display the frequencies

     for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            String c = new Character((char)(i + 'a')).toString();
            System.out.println( c + " : " + freq[i]);
        }
     }

And the output:

c : 1
d : 1
e : 4
h : 1
i : 1
l : 3
m : 1
n : 1
o : 4
r : 1
t : 2
u : 1
w : 1
y : 1

See my Huffman Encoding Example for an example using byte data.

Now this is all well and good for integer-type data, and when you know exactly the range of the frequencies, but what if you don't?

HashMap as Frequency Table

You can use Java's HashMap data structure to record the frequencies of Strings, or any class you want (provided it has an overridden equals method). The syntax is a little more involved, but not too challenging. Let's take a look.

Let's say you want to count the occurrences of individual words in a string. (Again, assuming lower case and punctuation has been removed):

First, we make the Map:

Map<String, Integer> frequencyTable = new HashMap<>();

Let's split up our string into an array of words:

String str = "a man is at the door but the door is locked";
String[] words = str.split(" ");

Loop through and increment the count, or add a new entry:

for (String each : words) {
    if (frequencyTable.containsKey(each)) {
        frequencyTable.put(each, frequencyTable.get(each) + 1);
    } else {
        frequencyTable.put(each, 1);
    }
}

With Java 8 syntax, this can be simplified to:

for (String each : words) {
    frequencyTable.put(each, frequencyTable.getOrDefault(each, 0) + 1);
}

And to iterate through them, you use a keySet or an entrySet:

for (String each : frequencyTable.keySet()) {
    System.out.println(each + " : " + frequencyTable.get(each));
}

Entry Set version:

for (Map.Entry<String, Integer> each : frequencyTable.entrySet()) {
    System.out.println(each.getKey() + " : " + each.getValue());
}

Output:

the : 2
but : 1
a : 1
door : 2
at : 1
is : 2
man : 1
locked : 1

Extended Example : Scoring a Poker Hand

In this example, we will use three different frequency tables, two in the process of scoring a poker hand, and one for accumulating statistics while running a test.

I have made a simple Cards class which creates a deck of 52 cards. (The link to the gist will be at the bottom of the post since RES auto-displays gist posts now).

We have another class called ScoreHand which takes a 5-card hand and performs various tests on it to come up with an overall scoring rank based on traditional poker rules.

For this, we use two array-based frequency tables, one for face values, and one for suits:

int[] faceFrequency = new int[13];  // frequency table for face values
int[] suitFrequency = new int[4];   // frequency table for suits

And a method that processes the hand into the tables:

/**
 * fill frequency tables with hand data
 */
private void getFrequencies() {
    for (int each : hand) {

        // kill three birds with one for-loop
        if (Cards.getFaceValue(each) == 0) hasAce = true;
        faceFrequency[Cards.getFaceValue(each)]++;
        suitFrequency[Cards.getSuit(each)]++;
    }
}

The suit table is only used to find a Flush:

private boolean isFlush() {
    for (int each : suitFrequency) {
        if (each == 5) return true;
    }
    return false;
}

The face frequency table is used to find the possible combinations of multiple cards, pairs, three of a kind, etc. It generates a unique number based on the combination, which is tested against some constants. (See full code)

private int getPairSum() {
    int sum = 0;
    for (int each : faceFrequency) {
        sum += each * each;
    }
    return sum;
}

If there is one pair, the sum will be 7 (2 * 2 + 1 * 1 + 1 * 1 + 1 * 1). Two pairs, the sum would be 9, and so on.

I could have used the face table to test for straights, but instead opted for an easier method of using a sorted array of the hand.

So now, with the help of an Enum, we have our final scored hand rank.

Now, we will use a Map-based frequency table to get the percentage of the different outcomes based on testing a certain number of poker hands.

public class PokerHandTester {
    public static void main(String[] args) {
        Cards deck = new Cards();
        deck.shuffle();

        Map<PokerHand, Integer> frequencyMap = new HashMap<>();
        int total = 1000000;

        for (int i = 0; i < total; i++) {
            List<Integer> hand = deck.deal(5);

            PokerHand temp = new ScoreHand(hand).getRank();
            frequencyMap.put(temp, frequencyMap.getOrDefault(temp, 0) + 1);
        }

        for (PokerHand each : PokerHand.values()) {
            int count = frequencyMap.getOrDefault(each, 0);
            System.out.println(each.getName() + " : " + count);
            System.out.printf("%.4f%%%n", (( count / (double) total) * 100));
        }
    }
}

In this example, we score a million hands. Here is the output:

High Card : 500287
50.0287%
One Pair : 417921
41.7921%
Two Pairs : 45315
4.5315%
Three of a Kind : 20369
2.0369%
Straight : 12168
1.2168%
Royal Straight : 354
0.0354%
Flush : 1931
0.1931%
Full House : 1409
0.1409%
Four of a Kind : 225
0.0225%
Straight Flush : 18
0.0018%
Royal Flush : 3
0.0003%

Now you understand why, on the Poker shows on TV, you will see someone bet millions with only one pair in his hand!!

Here's the gist with the full code

Object Serialization in Java

Serialization is a way for java to take instances of objects that you have made and save/load them directly to a file or stream. Instead of writing information to a file line by line, or using a database (although a database is preferred in many instances) we can take an object or list of objects or any other data structure that implements serializable and dump it directly to a file or stream with only a few lines of code. When you de-serialize it, all the data goes back into the proper fields of the class automatically, provided the package that is doing the deserialization has access to the exact same class.

Say we have a class like this:

public class Box implements Serializable {
    int width;
    int height;
    int depth;
    String name;

    // constructors, etc...
}

We can create a box object:

Box b = new Box(10, 20, 5, "Tools");

We can serialize b directly to an output stream with the command

outputStream.writeObject(b);

and read it back in with:

Box b = (Box) inputStream.readObject();

Note: This does not save it to file as readable (to humans) text, but as byte data.

If you have a member variable you do not wish to save with the object, you can mark it as transient.

private transient int notNeeded;

Only non-static member variables are saved.

We do this with the help of java.io classes such as ObjectOutputStream, ObjectInputStream, FileInputStream and FileOutputStream.

Any class you attempt to serialize must implement the serializable interface, although it is very easy as there are no methods to implement. The only change you need to make to your class is adding a constant for serialVersionUID. See the comments in the code about that.

A note of warning: Any changes you make to the structure of the class being used will make any previously serialized data unreadable. you will have to reserialize any data with the changes.

So, we take our Inventory class we have used in other examples:

import java.io.Serializable;

public class Inventory implements Serializable, Comparable<Inventory>
{
    // Serial Version Number - can be anything you wish, or generate it using 
    // 'serialver <classname>.class' from the command line.
    // If you make any changes to the structure of this class, change this number
    private static final long serialVersionUID = 1L;

    private String partnum;
    private String item;
    private String description;
    private int qty;
    private transient float price; // <-- this will not be saved to the file

    public Inventory(String partnum, String item, String description, int qty, float price)
    {
        this.partnum = partnum;
        this.item = item;
        this.description = description;
        this.qty = qty;
        this.price = price;
    }

    // getters/setters & other methods etc...
}

To save a single object to file, the code would look like this:

public static void main(String[] args)
{

	Inventory item = new Inventory("001", "Baby Bottles", "Rubber Baby Bumper Bottles, Blue", 25, 1.99F);


    // try-with-resources
    try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("test.dat")))
    {
        // write object
        oos.writeObject(item);

    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }

}

and to read it back in:

public static void main(String[] args) {

	Inventory item = null;

    // try-with-resources
    try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream("test.dat"))) {

        // load inventory object, cast to proper data type
        item = (Inventory) ois.readObject();

    } catch (FileNotFoundException | ClassNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }

    System.out.println(item);

output:

=====================
Part #:001	Item: Baby Bottles
Quantity: 25
Description: Rubber Baby Bumper Bottles, Blue
Price: 1.99
====================

Saving Lists and other Data Structures

Here's the really neat part. With serialization, you can dump the entire contents of a data structure directly to the stream or file, without iterating through the items, with essentially one line of code. So long as: The data structure itself implements Serializable (and most java.util ones do), and any other classes that are used in the structure also implement Serializable.

We are going to take our Inventory class, make both a simple ArrayList and a HashMap, and then serialize them to disk:

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Serialization Example for <a>http://www.reddit.com/r/javaexamples</a>
 * @author /u/Philboyd_Studge
 */
public class SerializeTest
{
    public static void main(String[] args)
    {
        // List of Inventory objects
        List<Inventory> invList = new ArrayList<>();

        // HashMap for lookup
        Map<String, Inventory> invMap = new HashMap<>();

        // add items to list
        invList.add(new Inventory("001", "Baby Bottles", "Rubber Baby Bumper Bottles, Blue", 25, 1.99F));
        invList.add(new Inventory("002", "Robot Leg", "Left leg for AutoBot 2000k", 3, 200.50F));
        invList.add(new Inventory("003", "Paper Bag", "Plain Brown Paper Bags", 1000, 0.25F));

        // add items to hashmap with key = partnum and value = Inventory object
        for (Inventory each : invList)
        {
            invMap.put(each.getPartnum(), each);
        }

        // try-with-resources
        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("test.dat")))
        {
            // write list as complete object
            oos.writeObject(invList);

            // write map as complete object
            oos.writeObject(invMap);

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

Note we just use writeObject just like in the one object example. We can also write both the list and the map to the same stream and save to file that way.

And to de-serialize:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Deserialization of list and map example
 * @author /u/Philboyd_Studge
 */
public class DeserializeTest
{
    public static void main(String[] args) {

        // list for Inventory objects
        List<Inventory> invList = null;

        // Map for Object lookup table
        Map<String, Inventory> invMap = null;

        // try-with-resources
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream("test.dat"))) {

            // load inventory list object, cast to proper data type
            invList = (ArrayList<Inventory>)ois.readObject();

            // load hashmap, cast to proper data type
            invMap = (HashMap<String, Inventory>)ois.readObject();

        } catch (FileNotFoundException | ClassNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

        // show inventory list
        for (Inventory each : invList) {
            System.out.println(each);
        }

        // lookup up particular item using hashmap
        System.out.println("Item#002 is :\n" + invMap.get("002"));

    }

}

The important part of the deserialization is casting the object back to the correct data type. Just make the type exactly like it was originally.

Output:

=====================
Part #:001	Item: Baby Bottles
Quantity: 25
Description: Rubber Baby Bumper Bottles, Blue
Price: 1.99
====================

=====================
Part #:002	Item: Robot Leg
Quantity: 3
Description: Left leg for AutoBot 2000k
Price: 200.5
====================

=====================
Part #:003	Item: Paper Bag
Quantity: 1000
Description: Plain Brown Paper Bags
Price: 0.25
====================

Item#002 is :
=====================
Part #:002	Item: Robot Leg
Quantity: 3
Description: Left leg for AutoBot 2000k
Price: 200.5
====================

That's really all there is to it! There are more advanced ways to serialize to JSON or XML, or directly to a database. Most of those require using third-party libraries, so that would be for another article.

Reading and Parsing Data from a File

As you learn Java, one thing that comes up early and often is reading from/ writing to files, and doing something useful with that data. In this example we will:

1. Read data from a CSV text file.

2. Parse that data into several different data types.

3. Load the data into an object.

4. Load those objects into an ArrayList.

5. Display them and do a simple calculation.

Data for a program is often stored in different types of file formats, with one of the simplest being CSV, a format using .txt files where each data item is simply separated by commas and put on different lines.

Here we have a sample inventory file, with the data in the order item, quantity, price

Blinker Fluid,10,10.99
Duncel Component,100,27.85
Widget1a,25,15.25
Widget2b,100,4.99

Save this as "inventory.txt"

we have a simple Inventory class: (save as Inventory.java in same directory)

public class Inventory
{
	private String item;
	private int qty;
	private float price;

	public Inventory(String item, int qty, float price)
	{
		this.item = item;
		this.qty = qty;
		this.price = price;
	}

	public float getTotal()
	{
		return qty * price;
	}

	public String toString()
	{
		return "Item: " + item + "\n" + "Quantity: " + qty + "\n"
					+ "Price: " + price;
	}
}

Reading the File

To read the file we are going to be using a BufferedReader in combination with a FileReader.

We will read one line at a time from the file using readLine() until the End Of File is reached (readLine will return a null)

String.split()

We take the string that we read and split it up using the comma as the 'delimiter' (the character that tells the function when to start a new word and is discarded). This creates an array with the data we want, however still in Strings, so we need to convert the values that are not supposed to be strings into the proper values, using Integer.parseInt() and Float.parseFloat()

We pass those values to the constructor for our Inventory object, and then simply add that object to our ArrayList.

The full program: (save in same directory as others as FileFunctions.java)

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class FileFunctions
{

	public static void main( String [] args )
	{
		// create ArrayList to store the invetory objects
		List<Inventory> invItem = new ArrayList<>();
		try
		{
			// create a Buffered Reader object instance with a FileReader
			BufferedReader br = new BufferedReader(new FileReader("inventory.txt"));

			// read the first line from the text file
			String fileRead = br.readLine();

			// loop until all lines are read
			while (fileRead != null)
			{

				// use string.split to load a string array with the values from each line of
				// the file, using a comma as the delimiter
				String[] tokenize = fileRead.split(",");

				// assume file is made correctly
				// and make temporary variables for the three types of data
				String tempItem = tokenize[0];
				int tempQty = Integer.parseInt(tokenize[1]);
				float tempPrice = Float.parseFloat(tokenize[2]);

				// creat temporary instance of Inventory object
				// and load with three data values
				Inventory tempObj = new Inventory(tempItem, tempQty, tempPrice);

				// add to array list
				invItem.add(tempObj);

				// read next line before looping
				// if end of file reached 
				fileRead = br.readLine();
			}

			// close file stream
			br.close();
		}
		
		// handle exceptions
		catch (FileNotFoundException fnfe)
		{
			System.out.println("file not found");
		}

		catch (IOException ioe)
		{
			ioe.printStackTrace();
		}

		// display inventory
		for (Inventory each : invItem)
		{
			System.out.println("====================");
			System.out.println(each);
			System.out.println();
			System.out.printf("Total value = %8.2f %n", each.getTotal());
		}

	}

}

Here is the output:

====================
Item: Blinker Fluid
Quantity: 10
Price: 10.99

Total value =   109.90
====================
Item: Duncel Component
Quantity: 100
Price: 27.85

Total value =  2785.00
====================
Item: Widget1a
Quantity: 25
Price: 15.25

Total value =   381.25
====================
Item: Widget2b
Quantity: 100
Price: 4.99

Total value =   499.00

A view on internal representation, memory allocation and how immutability is achieved by Strings in Java

https://medium.com/@vivekts90/java-strings-60d2eeed1e15

Welcome to the new blog related to Java Memory Management. We will look at “Under The Hood” Today. This blog gives Java developers a glimpse of what is going on beneath their running Java programs. Most of the time Java Developers look into this part at the time of Interview preparation and try to understand Heap and Stack memory areas. Today we will look a little more in-depth than that. We will have a look at High-level JVM architecture, Method Arean, and class loading concept as well.

Every Java developer knows that bytecode will be executed by the JRE (Java Runtime Environment). But many don’t know the fact that JRE is the implementation of Java Virtual Machine (JVM), which analyzes the bytecode, interprets the code, and executes it. We will look at different JVM memory areas Today.

Please have look at the blog for the complete detailed explanation

https://teachalesson.in/java-memory-management/

Finite State Machines

FSMs are an abstract concept of algorithmic modelling that has many uses in software design, from lexical analyzing to event-driven systems to Artificial Intelligence.

In a FSM you have a pre-determined list of States, and a way to keep track of the current State. Each State has a pre-defined number of Events (or types of input) that cause a Transition to another State, called the Accept state. In it's simplest form imagine a lightswitch. The switch is OFF so the current state of the light attached to it is OFF. An Event occurs, switching the light to the ON position. The state of the light is now transitioned to ON.

This is a Finite system as there are only two possible states, and each state has only 1 allowable input.

Garage Door Opener

Now let's think of a sightly more complicated example. I'm sure you are familiar with an automated garage door opener. You have a little clicker box with a button that can open or close the door.

The door's initial state is closed. The button is clicked. The door starts to open. When the mechanism has determined that the door is fully open, it stops. Click the button again, and the door will start to close. Now, if you click the button while the door is in the process of opening or closing, what happens? Normally, the door will stop in place. Then, when the button is clicked gain, it will reverse direction. So we need to 'remember' which direction it was cycling so that we can move to the proper next state.

So the possible states we have now are: OPEN, CLOSED, OPENING, CLOSING, STOPPED_OPENING, STOPPED_CLOSING and as of now we have two events: BUTTON_CLICKED and CYCLE_COMPLETE.

And our transition table now looks like this:

Now, most automated garage doors also have an infrared sensor to detect if something is blocking the door such as a car, cat or small child. So we now have two new Events, BLOCK_DETECTED and BLOCK_CLEARED. If a block is detected while the door is closing, it will automatically change to opening. If the door is in a non-moving state no further movement may be triggered until the block is cleared. So we add a new state EMERGENCY_OPENING. But then, since we need to remember what state the door was in before it became blocked, we add more states: BLOCKED_OPEN, BLOCKED_CLOSED, BLOCKED_STOPPED_OPENING, BLOCKED_STOPPED_CLOSED.

So let's do this programmatically. Java's Enum is great for modelling FSMs. First, we make an enum for the States:

public enum State {
    CLOSED, OPENING, STOPPED_OPENING, OPEN, CLOSING, STOPPED_CLOSING,
    BLOCKED_OPEN, BLOCKED_CLOSED, EMERGENCY_OPENING, BLOCKED_STOPPED_OPENING,
    BLOCKED_STOPPED_CLOSING;

And a separate enum for the Events:

public enum Event {
    BUTTON_CLICK, CYCLE_COMPLETE, BLOCK_DETECTED, BLOCK_CLEARED
}

Now back in the State enum we can use a HashMap to make our Transition map:

Map<Event, State> transitions = new HashMap<>();

public void addTransition(Event event, State accept) {
    transitions.put(event, accept);
}


// returns accept state, or if not found returns current state
public State getTransition(Event event) {
    return transitions.getOrDefault(event, this);
}

Pre-Java 8 version of that getTransition method:

public State getTransition(Event event) {
    State accept = transitions.get(event);
    if (accept == null) return this;
    return accept;
}

Now a class to set up our machine and initialize the transition maps:

public class GarageDoorFSM {

    private State current;

    public GarageDoorFSM() {
        current = State.CLOSED;
        init();
        System.out.println("Door: " + current);
    }

    private void init() {
        State.CLOSED.addTransition(Event.BUTTON_CLICK, State.OPENING);
        State.CLOSED.addTransition(Event.BLOCK_DETECTED, State.BLOCKED_CLOSED);

        State.OPEN.addTransition(Event.BUTTON_CLICK, State.CLOSING);
        State.OPEN.addTransition(Event.BLOCK_DETECTED, State.BLOCKED_OPEN);

        State.OPENING.addTransition(Event.CYCLE_COMPLETE, State.OPEN);
        State.OPENING.addTransition(Event.BUTTON_CLICK, State.STOPPED_OPENING);
        State.OPENING.addTransition(Event.BLOCK_DETECTED, State.EMERGENCY_OPENING);

        State.CLOSING.addTransition(Event.CYCLE_COMPLETE, State.CLOSED);
        State.CLOSING.addTransition(Event.BUTTON_CLICK, State.STOPPED_CLOSING);
        State.CLOSING.addTransition(Event.BLOCK_DETECTED, State.EMERGENCY_OPENING);

        State.STOPPED_OPENING.addTransition(Event.BUTTON_CLICK, State.CLOSING);
        State.STOPPED_OPENING.addTransition(Event.BLOCK_DETECTED, State.BLOCKED_STOPPED_OPENING);

        State.STOPPED_CLOSING.addTransition(Event.BUTTON_CLICK, State.OPENING);
        State.STOPPED_CLOSING.addTransition(Event.BLOCK_DETECTED, State.BLOCKED_STOPPED_CLOSING);

        State.BLOCKED_OPEN.addTransition(Event.BLOCK_CLEARED, State.OPEN);

        State.BLOCKED_CLOSED.addTransition(Event.BLOCK_CLEARED, State.CLOSED);

        State.BLOCKED_STOPPED_OPENING.addTransition(Event.BLOCK_CLEARED, State.STOPPED_OPENING);
        State.BLOCKED_STOPPED_CLOSING.addTransition(Event.BLOCK_CLEARED, State.STOPPED_CLOSING);

        State.EMERGENCY_OPENING.addTransition(Event.BLOCK_CLEARED, State.OPENING);
        State.EMERGENCY_OPENING.addTransition(Event.CYCLE_COMPLETE, State.BLOCKED_OPEN);

    }

Note that the states could also have been set up within the State enum using a static block. This also could be automated to use a file-based method to load, such as JSON, CSV or a plain text file.

Here we add a method to process a given event:

private void process(Event e) {
    System.out.println("Event -> " + e);
    current = current.getTransition(e);
    System.out.println("Door: " + current);
}

And then public methods to wrap the events in plain english:

public void click() {
    process(Event.BUTTON_CLICK);
}

public void cycleComplete() {
    process(Event.CYCLE_COMPLETE);
}

public void block() {
    process(Event.BLOCK_DETECTED);
}

public void unBlock() {
    process(Event.BLOCK_CLEARED);
}

Now our program to test it all:

public class FSM {
    public static void main(String[] args) {
        GarageDoorFSM door = new GarageDoorFSM();

        door.click();
        door.cycleComplete();
        door.click();
        door.block();
        door.cycleComplete();
        door.click();
        door.unBlock();
        door.click();
        door.click();
        door.block();
        door.click();
        door.unBlock();
        door.click();
        door.cycleComplete();
    }
}

And the output:

Door: CLOSED
Event -> BUTTON_CLICK
Door: OPENING
Event -> CYCLE_COMPLETE
Door: OPEN
Event -> BUTTON_CLICK
Door: CLOSING
Event -> BLOCK_DETECTED
Door: EMERGENCY_OPENING
Event -> CYCLE_COMPLETE
Door: BLOCKED_OPEN
Event -> BUTTON_CLICK
Door: BLOCKED_OPEN
Event -> BLOCK_CLEARED
Door: OPEN
Event -> BUTTON_CLICK
Door: CLOSING
Event -> BUTTON_CLICK
Door: STOPPED_CLOSING
Event -> BLOCK_DETECTED
Door: BLOCKED_STOPPED_CLOSING
Event -> BUTTON_CLICK
Door: BLOCKED_STOPPED_CLOSING
Event -> BLOCK_CLEARED
Door: STOPPED_CLOSING
Event -> BUTTON_CLICK
Door: OPENING
Event -> CYCLE_COMPLETE
Door: OPEN

There we go. Now, this is obviously just a model, but this same concept is very useful for a wide range of software needs. Thanks again for reading!!

Heap Sort

Another common sorting algorithm is the HeapSort. The heap sort uses a Max Binary Heap, (see my post here,) as the basis for the sorting algorithm, since it is fairly quick to set the data into a heap structure, then simply pull the largest items off the heap and move them to the end of the array. It is all done in the same array and in less than O(n log n) time.

Here's an example, based on the psuedocode in the wikipedia article above, converted to Java and then made into static, generic methods that can be readily called by another program.

A note on sorting algorithms: While interesting, and good to learn in terms of just understanding the algorithm itself, in the real world it is almost always better to use the built-in sorting mechanisms for the language you are using. You will never write an algorithm that matches or exceeds the speed of the built-in methods.

/**
 * Generic HeapSort Array-based implementation
 * can be used with either the 'sift up' or 'sift down' algorithms
 * as described <a href="https://en.wikipedia.org/?title=Heapsort#Pseudocode">Here</a>
 * Usage <code>Type[] array = HeapSort.sort(inputArray);</code>
 * will default to the sift down, use
 * <code>Type[] array = HeapSort.sort(inputArray, false);</code> for sift up.
 * 
 * @author /u/Philboyd_Studge
 */
class HeapSort
{

	/**
	 * sort array of type T using the sift down method
	 * @param array array of type T
	 * @return sorted array of type T
	 */
	public static <T extends Comparable<T>> T[] sort(T[] array)
	{
		return sort(array, true);
	}

	/** 
	 * sort array of type T using either sift up or down method
	 * @param array array of type T
	 * @param down true for sift down, false for aift up
	 * @return sorted array of type T
	 */
	public static <T extends Comparable<T>> T[] sort(T[] array, boolean down)
	{
		if (down) 
		{
			heapify(array, array.length);
		}
		else
		{
			heapifyUp(array, array.length);
		} 

		int end = array.length - 1;
		while (end >= 0)
		{
			swap(array, end, 0);
			end--;

			// with either method, you have to use siftDown here.
			siftDown(array, 0, end);
		}
		return array;

	}

	/**
	 * Swap two members of array
	 * @param array array of type T
	 * @param index1 first index of element to swap
	 * @param index2 second index of element to swap with first
	 * @return array of type T
	 */
	private static <T extends Comparable<T>> T[] swap(T[] array, int index1, int index2)
	{
		T temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		return array;
	}

	/**
	 * Heapify array into max heap using sift down
	 * @param array array of type T
	 * @param count integer length of array
	 * @return array of type T as a max heap
	 */
	private static <T extends Comparable<T>> T[] heapify(T[] array, int count)
	{
		int start = (int) Math.floor((count - 2)/2);
		while (start >= 0)
		{
			siftDown(array, start, count - 1);
			start--;
		}
		return array;
	}

	/**
	 * Heapify array into max heap using sift up
	 * @param array array of type T
	 * @param count integer length of array
	 * @return array of type T as a max heap
	 */
	private static <T extends Comparable<T>> T[] heapifyUp(T[] array, int count)
	{
		int end = 1;
		while (end < count)
		{
			siftUp(array, 0, end);
			end++;
		}
		return array;
	}

	/**
	 * Sift Up
	 * @param array array of type T
	 * @param start index to start from
	 * @param end node to sift up
	 * @return array of type T
	 */
	private static<T extends Comparable<T>> T[] siftUp(T[] array, int start, int end)
	{
		int child = end;
		while (child > start)
		{
			int parent = (int) Math.floor((child - 1) /2);
			if (array[parent].compareTo(array[child]) < 0)
			{
				swap(array, parent, child);
				child = parent;
			}
			else
			{
				return array;
			}
		}
		return array;
	}

	/**
	 * Sift Down
	 * @param array array of type T
	 * @param start index to start from
	 * @param end index to end at
	 * @return array of type T
	 */
	private static <T extends Comparable<T>> T[] siftDown(T[] array, int start, int end)
	{
		int root = start;
		while (root * 2 + 1 <= end)
		{
			int child = root * 2 + 1;
			int swap = root;
			if (array[swap].compareTo(array[child]) < 0)
			{
				swap = child;
			}
			if ((child + 1 <= end) && (array[swap].compareTo(array[child + 1]) < 0))
			{
				swap = child + 1;
			}
			if (swap==root)
			{
				return array;
			}
			else
			{
				swap(array, root, swap);
				root = swap;
			}
		}
		return array;
	}	
}

Test Code

/*
* Test HeapSort for HeapSort.java
* /u/Philboyd_Studge
*/
import java.util.Arrays;
import java.util.Random;


public class TestHeapSort
{

	public static void main(String[] args) 
	{

		// create array of random ints size 100 or command line args[0]
        Integer[] numbers = new Integer[(args.length == 0) ? 100 : Integer.parseInt(args[0])];
        Random rand = new Random();

        for (int i = 0; i < numbers.length; i++)
        {
        	// using random numbers from 0 to 1000 - 1 or args[1]
            numbers[i] = rand.nextInt((args.length <= 1) ? 1000 : Integer.parseInt(args[1]));
        }

        long oldtime = System.nanoTime();
		Integer[] b = HeapSort.sort(numbers);
		long newtime = System.nanoTime();
		System.out.println("HeapSort Down : Time: " + (double)((newtime - oldtime)/1000000.0));

		oldtime = System.nanoTime();
		Integer[] c = HeapSort.sort(numbers, false);
		newtime = System.nanoTime();

		System.out.println("HeapSort Up : Time: " + (double)((newtime - oldtime)/1000000.0));

		// test against Arrays.sort()
		oldtime = System.nanoTime();
		Arrays.sort(numbers);
		newtime = System.nanoTime();


		System.out.println("Arrays.sort : Time: " + (double)((newtime - oldtime)/1000000.0));
		System.out.println(Arrays.toString(b));

        // test Strings
        String[] names = { "Pierce", "Chang", "Britta", "Abed", "Dean", "Jeff", "Shirley", "Annie", "Troy"} ;
        for (String each : HeapSort.sort(names)) System.out.println(each);

	}
}

Output

C:\Users\Documents>java TestHeapSort 100 1000
HeapSort Down : Time: 2.030354
HeapSort Up : Time: 1.199024
Arrays.sort : Time: 0.665442
[18, 22, 47, 49, 59, 90, 111, 118, 128, 136, 138, 167, 175, 207, 209, 212, 216, 225, 239, 244, 245,
252, 257, 271, 281, 285, 298, 315, 320, 331, 332, 386, 386, 395, 407, 413, 423, 426, 432, 432, 448,
461, 462, 466, 475, 477, 489, 499, 503, 506, 513, 517, 519, 541, 551, 555, 566, 568, 600, 613, 621,
623, 623, 670, 678, 679, 699, 700, 703, 712, 725, 738, 741, 752, 754, 763, 768, 775, 792, 798, 806,
815, 832, 850, 850, 873, 891, 898, 904, 909, 917, 924, 934, 941, 957, 957, 972, 983, 983, 988]
Abed
Annie
Britta
Chang
Dean
Jeff
Pierce
Shirley
Troy