Distinct intersecting values of two arrays

I have written two different methods that gives the same output. The output is a list of distinct intersecting values of two arrays. I am amazed with the different amount of time taken to solve this problem. It would be something interesting to investigate. Here are the suggested solutions:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class ArraysIntersection {

 private void findIntersectionMethod1(int[] a, int[] b){
  long start = System.nanoTime();
  int indexA = 0;
  int indexB = 0;
  ArrayList unique = new ArrayList();
  while (indexA < a.length && indexB < b.length) {
   if (a[indexA] == b[indexB]) {
    if (!unique.contains(a[indexA])) {
     unique.add(a[indexA]);
    }
    indexA++;
    indexB++;
   } else if (a[indexA] < b[indexB]) {
    indexA++;
   } else {
    indexB++;
   }
  }
  long elapsed = (System.nanoTime() - start);
  System.out.println("Elapsed time (findIntersectionMethod1): " + elapsed + "ns");
  System.out.println("Intersection of elements: " + unique);
 }

 private void findIntersectionMethod2(int[] arr1, int[] arr2){
  long start = System.nanoTime();
  ArrayList unique = new ArrayList();
  for (int i = 0; i < arr1.length; i++) {
   for (int j = 0; j < arr2.length; j++) {
    if (arr1[i] == arr2[j]) {
     if (!unique.contains(arr1[i])) {
      unique.add(arr1[i]);
     }
    }
   }
  }
  long elapsed = (System.nanoTime() - start);
  System.out.println("Elapsed time (findIntersectionMethod2): " + elapsed + "ns");
  System.out.println("Intersection of elements: " + unique);
 }

 private void findIntersectionMethod3(int[] a, int[] b){
  long start = System.nanoTime();
  Set unique = new HashSet();
  int indexA = 0;
  int indexB = 0;
  while (indexA < a.length && indexB < b.length) {
   if (a[indexA] == b[indexB]) {
    unique.add(a[indexA]);
    indexA++;
    indexB++;
   } else if (a[indexA] < b[indexB]) {
    indexA++;
   } else {
    indexB++;
   }
  }

  long elapsed = (System.nanoTime() - start);
  System.out.println("Elapsed time (findIntersectionMethod3): " + elapsed + "ns");
  System.out.println("Intersection of elements: " + unique);
 }

 public static void main(String[] args) {

  int a[]={1, 1, 2, 4, 4, 7, 8, 8, 9, 14, 14, 20, 20, 20};
  int b[]={1, 1, 1, 2, 2, 8, 8, 20};

  ArraysIntersection arrIntersect = new ArraysIntersection();
  arrIntersect.findIntersectionMethod1(a, b); 
  arrIntersect.findIntersectionMethod2(a, b); 
  arrIntersect.findIntersectionMethod3(a, b); 
 }
}

The output of these methods are as below (I'm telling you, you'll be amazed looking at the time taken for each method):

Elapsed time (findIntersectionMethod1): 455000ns
Intersection of elements: [1, 2, 8, 20]
Elapsed time (findIntersectionMethod2): 15000ns
Intersection of elements: [1, 2, 8, 20]
Elapsed time (findIntersectionMethod3): 65000ns
Intersection of elements: [2, 8, 1, 20]

I'm sure there are much better solutions to solve this interesting problem that I have not thought of.

Java Codes in Python (Part 4)

Here is a suggested solution to get unique values from a list without using a map or set data structure<br />def uniqueElements(input):<br /> uniqElems = []<br /> uniq = input[0]<br /> uniqElems.append(uniq)<br /> for i in input[1:]:<br /> if (i != uniq):<br /> uniqElems.append(i)<br /> uniq = i<br /> return uniqElems<br />

Extracting unique element(s) from a sorted list

PROBLEM: you have a list of sorted elements. All elements are sorted (it could be in ascending order or descending order). You are printing out the unique elements in the sorted list.
COMPLEXITY: O(n)

public class UniqueNumbers {
 public static void main(String[] args) {
  int a[]={1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20};
  //int a[]={1};
  //int a[]={2, 2, 4, 5};
  //int a[]={1, 1, 1, 2, 2, 8};
  //int a[]={1, 1, 1};
  int uniq = a[a.length-1];
  boolean numberExists = false;
  for (int i = 0; i < a.length; i++) {
   if (a[i] == uniq) {
    if (!numberExists) {
     System.out.println("Position: " + i + " Unique Element => " + a[i]);
     numberExists = true;
    }
   }
   else {
    System.out.println("Position: " + i + " Unique Element => " + a[i]);
    uniq = a[i];
    numberExists = true;
   }
  }
 }
}

The output is shown below:

{1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20}
Position: 0 Unique Element => 1
Position: 3 Unique Element => 2
Position: 4 Unique Element => 4
Position: 6 Unique Element => 7
Position: 7 Unique Element => 8
Position: 8 Unique Element => 9
Position: 9 Unique Element => 14
Position: 11 Unique Element => 20

{1}
Position: 0 Unique Element => 1

{2, 2, 4, 5}
Position: 0 Unique Element => 2
Position: 2 Unique Element => 4
Position: 3 Unique Element => 5

{1, 1, 1, 2, 2, 8}
Position: 0 Unique Element => 1
Position: 3 Unique Element => 2
Position: 5 Unique Element => 8

{1, 1, 1}
Position: 0 Unique Element => 1

Update: my solution is not that elegant after all. I had the opportunity to discuss the algorithm with Mark and he has a much better way to solve this problem. Thank you, Mark (you know who you are :D).

 public static void main(String[] args) {
  int a[]={1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20};
  //int a[]={1};
  //int a[]={2, 2, 4, 5};
  //int a[]={1, 1, 1, 2, 2, 8};
  //int a[]={1, 1, 1};
  int uniq = a[0];
  System.out.println("Position: " + 0 + " Unique Element => " + uniq);
  for (int i = 1; i < a.length; i++) {
   if (a[i] != uniq) {
    System.out.println("Position: " + i + " Unique Element => " + a[i]);
    uniq = a[i];
   }
  }
 }

The 12 balls puzzle

A solution to solve the 12 ball puzzle.
Fact: you know that 11 balls are equally weighted and 1 of them is not
Constraint: you can only use the weighing machine at most 3 times to determine the heaviest ball

import java.util.Random;

public class TheHeaviestBall {

 private int count = 0;
 private int indexHeaviestBall = 0;
 private Random myRand = new Random();
 private int[] balls = {1,1,1,1,1,1,1,1,1,1,1,1};
 private int[] arrangeBalls(){
  balls[myRand.nextInt(12)] = 2;
  for (int aBall : balls) {
   System.out.print(aBall + " ");
  }
  return balls;
 }

 public void weighingCount(){
  count++;
  if (count > 3) {
   System.out.println("Your algorithm fails");
  }
 }

 public int theBALL(){
  int myBalls[] = arrangeBalls();
  weighingCount();
  if ((myBalls[0]+myBalls[1]+myBalls[2]+myBalls[3]) > (myBalls[4]+myBalls[5]+myBalls[6]+myBalls[7])) {
   weighingCount();
   if ((myBalls[0]+myBalls[1]) > (myBalls[2]+myBalls[3])) {
    weighingCount();
    if (myBalls[0] > myBalls[1]) {
     indexHeaviestBall = 0;
     return myBalls[0];
    } else {
     indexHeaviestBall = 1;
     return myBalls[1];
    }
   } else {
    weighingCount();
    if (myBalls[2] > myBalls[3]) {
     indexHeaviestBall = 2;
     return myBalls[2];
    } else {
     indexHeaviestBall = 3;
     return myBalls[3];
    }
   }
  }
  else if ((myBalls[4]+myBalls[5]+myBalls[6]+myBalls[7]) > (myBalls[0]+myBalls[1]+myBalls[2]+myBalls[3])) {
   weighingCount();
   if ((myBalls[4]+myBalls[5]) > (myBalls[6]+myBalls[7])) {
    weighingCount();
    if (myBalls[4] > myBalls[5]) {
     indexHeaviestBall = 4;
     return myBalls[4];
    } else {
     indexHeaviestBall = 5;
     return myBalls[5];
    }
   } else {
    weighingCount();
    if (myBalls[6] > myBalls[7]) {
     indexHeaviestBall = 6;
     return myBalls[6];
    } else {
     indexHeaviestBall = 7;
     return myBalls[7];
    }
   }
  }
  else {
   weighingCount();
   if ((myBalls[8]+myBalls[9]) > (myBalls[10]+myBalls[11])) {
    weighingCount();
    if (myBalls[8] > myBalls[9]) {
     indexHeaviestBall = 8;
     return myBalls[8];
    } else {
     indexHeaviestBall = 9;
     return myBalls[9];
    }
   } else {
    weighingCount();
    if (myBalls[10] > myBalls[11]) {
     indexHeaviestBall = 10;
     return myBalls[10];
    } else {
     indexHeaviestBall = 11;
     return myBalls[11];
    }
   }
  }
 }

 public static void getMyHeaviestBall(){
  TheHeaviestBall hb = new TheHeaviestBall();
  //Algorithm validation
  if (hb.count > 3) {
   System.out.println("You can do better");
  } else {
   System.out.println("\nThe heaviest ball [ " + hb.theBALL() + " ] is the " + (hb.indexHeaviestBall + 1) + "th ball from the left");
  }
 }

 public static void main(String[] args) {
  getMyHeaviestBall();
 }
}

Update: Click here to view the solution to solve the 8 balls puzzle

The 8 balls puzzle

Here is an interesting puzzle about selecting the heaviest ball among 7 other equally weighted balls. For example a collection of the 8 balls would look like this [2,1,1,1,1,1,1,1].

The goal is to choose the heaviest ball by performing only two weighings.
Fact: You know that all 7 other balls are equally weighted but you could not figure out the heaviest ball.
Solution: In order to do so, you are using the weighing machine but as a challenge you can only use the weighing machine at most twice

import java.util.Random;

public class TheHeaviestBall {

 private int count = 0;
 private int indexHeaviestBall = 0;
 private Random myRand = new Random();
 private int[] balls = {1,1,1,1,1,1,1,1};
 private int[] arrangeBalls(){
  balls[myRand.nextInt(8)] = 2;
  for (int aBall : balls) {
   System.out.print(aBall + " ");
  }
  return balls;
 }

 public void weighingCount(){
  count++;
  if (count > 2) {
   System.out.println("Your algorithm fails");
  }
 }

 public int theBALL(){
  int myBalls[] = arrangeBalls();
  weighingCount();
  if ((myBalls[0]+myBalls[1]+myBalls[2]) > (myBalls[3]+myBalls[4]+myBalls[5])) {
   weighingCount();
   if (myBalls[1] == myBalls[2]) {
    indexHeaviestBall = 0;
    return myBalls[0];
   } else {
    if (myBalls[1] >= myBalls[2]) {
     indexHeaviestBall = 1;
     return myBalls[1];
    } else {
     indexHeaviestBall = 2;
     return myBalls[2];
    }
   }
  }
  else if ((myBalls[3]+myBalls[4]+myBalls[5]) > (myBalls[0]+myBalls[1]+myBalls[2])) {
   weighingCount();
   if (myBalls[4] == myBalls[5]) {
    return myBalls[3];
   } else {
    if (myBalls[4] >= myBalls[5]) {
     indexHeaviestBall = 4;
     return myBalls[4];
    }
    else {
     indexHeaviestBall = 5;
     return myBalls[5];
    }
   }
  }
  else {
   weighingCount();
   if (myBalls[6] >= myBalls[7]) {
    indexHeaviestBall = 6;
    return myBalls[6];
   }
   else {
    indexHeaviestBall = 7;
    return myBalls[7];
   }
  }
 }

 public static void getMyHeaviestBall(){
  TheHeaviestBall hb = new TheHeaviestBall();
  //Algorithm validation
  if (hb.count > 2) {
   System.out.println("You can do better");
  } else {
   System.out.println("\nThe heaviest ball [ " + hb.theBALL() + " ] is the " + (hb.indexHeaviestBall + 1) + "th ball from the left");
  }
 }

 public static void main(String[] args) {
  getMyHeaviestBall();
 }
}

Update: Click here to view the solution to solve the 12 balls puzzle

My Java codes in Python (Part 3)

Prologue: I feel like making a tag cloud for the labels of my articles ;)

My Java codes in Python (Part 2)

CustomStack upgrades

My CustomStack now comes with several other new features. I can actually check if an Object exists in the Stack. Once the Object is found, a boolean true is returned. In addition to that, I've also added a method to retrieve an element with a given 0-based index number. I call it elementAt and it has a similar functionality of get. To the readers who are accustomed to the methods of a Stack, I have also added the method peek. Basically, it's a method to retrieve the element at the top of the Stack. The method search returns the 0-based index number of the first found element and -1 is returned if the element is not found. Here are the summary of methods of the newly improved CustomStack:
contains(Object input)
elementAt(int index)
peek()
search(Object input)
Below is the code snippet.

 public boolean contains(Object input){
  boolean found = false;
  if(empty()){
   throw new RuntimeException( "Stack is already empty. No elements to check." );
  }
  for(int i = 0; i<size(); i++) {
   if (stackElements[i].hashCode() == input.hashCode()) {
    found = true;
    break;
   }
  }
  return found;
 }

 public Object elementAt(int index){
  return get(index);
 }
 
 public Object peek(){
  return top();
 }
 
 public int search(Object input){
  int index = -1;
  if(empty()){
   throw new RuntimeException( "Stack is already empty. No elements to search." );
  }
  for(int i = 0; i<size(); i++) {
   if (stackElements[i].hashCode() == input.hashCode()) {
    index = i;
    break;
   }
  }
  return index;
 }
 

Click here to view the previous code of CustomStack.

Stack Implementation in Java

Below is my code to implement Stack from ground-up. I tried (in a very short time) to emulate the behavior of Stack in the Java Util package. The methods I have written are:
size()
get(int index)
empty()
clear()
pop()
push(Object input)
bottom()
top()

I call my Stack implementation as CustomStack as it may evolve over time. I have also provided some test cases to validate that the implementation actually works. The sample output is shown below the codes.

import java.lang.reflect.Array;

public class CustomStack {

 private Object[] stackElements;
 private int stackIndex = -1;
 private int stackSize = 0;
 private static final int INIT_SIZE = 3;
 private boolean stackSizeGiven = false;
 private int sizeHolder = 0;

 public CustomStack(){
  stackElements = new Object[ INIT_SIZE ];
  stackSizeGiven = false;
 }

 public CustomStack(int inputSize){
  sizeHolder = inputSize;
  stackElements = new Object[ sizeHolder ];
  stackSizeGiven = true;
 }
 
 public int size(){
  return stackSize;
 }

 public Object get(int index){
  if ((index < 0) || (index > (stackSize))) {
   throw new RuntimeException("Index out of bound. Supplied " + index);
  }
  return stackElements[ index ];
 }
 
 public boolean empty() {
  return stackIndex == -1;
 }

 public void clear() {
  if (stackSizeGiven) {
   stackElements = new Object[ sizeHolder ];
  } else {
   stackElements = new Object[ INIT_SIZE ];
  }
  stackIndex = -1;
  stackSize = 0;
 }
 
 public void pop() {
  if(empty()){
   throw new RuntimeException( "Stack is already empty. No elements to pop." );
  }
  stackIndex--;
  stackSize--;
 }

 public void push(Object input) {
  if( stackIndex + 1 == stackElements.length ) {
   int arrayLength = Array.getLength(stackElements);
   Object [] newArray = (Object[]) Array.newInstance(stackElements.getClass().getComponentType(), (arrayLength + arrayLength ));
   System.arraycopy(stackElements, 0, newArray, 0, arrayLength);
   stackElements = newArray;
  }
  stackElements[ ++stackIndex ] = input;
  stackSize++;
 }

 public Object bottom(){
  if(empty())
   throw new RuntimeException( "Stack is already empty. No elements at bottom." );
  return stackElements[ 0 ];
 }
 
 public Object top() {
  if(empty())
   throw new RuntimeException( "Stack is already empty. No elements at top." );
  return stackElements[ stackIndex ];
 }

 public static void testCases(){
  CustomStack aStack = new CustomStack();
  System.out.println("Stack is empty: " + aStack.empty());
  aStack.push("Nicholas Key");
  aStack.push(3.142);
  aStack.push(false);
  // Prints false
  System.out.println("Element at top of Stack: " + aStack.top());
  System.out.println("Size of current Stack: " + aStack.size());

  aStack.push("Java Developer");
  aStack.push("Android App Developer");
  // Prints Android App Developer
  System.out.println("Element at top of Stack: " + aStack.top());
  
  aStack.push("Web App Developer");
  aStack.push("Blogger");
  aStack.push(2009);
  // Prints 2009
  System.out.println("Element at top of Stack: " + aStack.top());
  System.out.println("Size of current Stack: " + aStack.size());
  
  // Prints Stack elements
  for (int i= 0; i< aStack.size(); i++) {
   System.out.println("Index " + i + ": " + aStack.get(i));
  }

  // Pops 2009
  aStack.pop();
  // Prints Blogger
  System.out.println("Element at top of Stack: " + aStack.top());
  
  // Pops Blogger
  aStack.pop();
  // Prints Web App Developer
  System.out.println("Element at top of Stack: " + aStack.top());

  // Prints Stack elements
  for (int i= 0; i< aStack.size(); i++) {
   System.out.println("Index " + i + ": " + aStack.get(i));
  }

  System.out.println("Element at bottom of Stack: " + aStack.bottom());

  // Pops out all Stack elements
  aStack.clear();  
  System.out.println("Stack is empty: " + aStack.empty());

  System.out.println(aStack.get(1));
  
  System.out.println(aStack.get(aStack.size() + 300));
 }
 
 public static void main(String[] args) {
  testCases(); 
 }
}

Stack is empty: true
Element at top of Stack: false
Size of current Stack: 3
Element at top of Stack: Android App Developer
Element at top of Stack: 2009
Size of current Stack: 8
Index 0: Nicholas Key
Index 1: 3.142
Index 2: false
Index 3: Java Developer
Index 4: Android App Developer
Index 5: Web App Developer
Index 6: Blogger
Index 7: 2009
Element at top of Stack: Blogger
Element at top of Stack: Web App Developer
Index 0: Nicholas Key
Index 1: 3.142
Index 2: false
Index 3: Java Developer
Index 4: Android App Developer
Index 5: Web App Developer
Element at bottom of Stack: Nicholas Key
Stack is empty: true
Exception in thread "main" java.lang.RuntimeException: Index out of bound. Supplied 1
 at CustomStack.get(CustomStack.java:29)
 at CustomStack.testCases(CustomStack.java:128)
 at CustomStack.main(CustomStack.java:136)

Update: I've added several methods to make my CustomStack more robust ;) Click here to look at the improvements.

Sorting Algorithms (Bubble sort, Selection sort & Insertion Sort)

I want to refresh my mind about sorting algorithms and here are the first three simple sorting algorithms in this article - Bubble Sort, Selection Sort and Insertion Sort. I attribute the explanations to Wikipedia.

import java.util.Random;

public class SortingAlgorithm {

 private final int SIZE = 2000;
 private Random myRand = new Random();
 private int[] numbers = new int[SIZE];

 public SortingAlgorithm(){}

 private void randomizeNumbers(){
  for (int i = 0; i < numbers.length; i++) {
   numbers[i] = myRand.nextInt( 2000 ) + 1;
  } 
 }

 private void printArray(){
  for(int i: numbers){
   System.out.print(i + " ");
  }
  System.out.println();
 }

 public void bubbleSort() {
  randomizeNumbers();
  System.out.println("BUBBLE SORT");
  System.out.println("Presorted numbers: ");
  printArray();
  long start = System.nanoTime();

  /**
   * Bubblesort algorithm
   * Wikipedia:
   * works by repeatedly stepping through the list to be sorted, 
   * comparing each pair of adjacent items and swapping them if 
   * they are in the wrong order. The pass through the list is 
   * repeated until no swaps are needed, which indicates that the 
   * list is sorted. The algorithm gets its name from the way smaller 
   * elements "bubble" to the top of the list.
   * Complexity: 
   * Worst = O(n^2)
   * Average = O(n^2)
   * Best = O(n)
   */
  int n = numbers.length;
  for (int pass=1; pass < n; pass++) { 
   for (int i=0; i < n-pass; i++) {
    if (numbers[i] > numbers[i+1]) {
     int temp = numbers[i];  
     numbers[i] = numbers[i+1];  
     numbers[i+1] = temp;
    }
   }
  }

  long elapsed = (System.nanoTime() - start);
  System.out.println("Bubble-sorted numbers: ");
  printArray();
  System.out.println("Elapsed time: " + elapsed + "ns\n");
 }

 public void selectionSort(){
  randomizeNumbers();
  System.out.println("SELECTION SORT");
  System.out.println("Presorted numbers: ");
  printArray();
  long start = System.nanoTime();

  /**
   * Selectionsort Algoritm
   * Wikipedia:
   * 1. Find the minimum value in the list
   * 2. Swap it with the value in the first position
   * 3. Repeat the steps above for the remainder of the list (starting 
   *    at the second position and advancing each time)
   * Complexity:
   * Worst = O(n^2)
   * Average = O(n^2)
   * Best = O(n^2)
   */
  for (int i=0; i<numbers.length-1; i++) {
   int minIndex = i;
   for (int j=i+1; j<numbers.length; j++) {
    if (numbers[minIndex] > numbers[j]) {
     minIndex = j;
    }
   }
   if (minIndex != i) { 
    int temp = numbers[i];
    numbers[i] = numbers[minIndex];
    numbers[minIndex] = temp;
   }
  }

  long elapsed = (System.nanoTime() - start);
  System.out.println("Selection-sorted numbers: ");
  printArray();
  System.out.println("Elapsed time: " + elapsed + "ns\n");
 }

 public void insertionSort(){
  randomizeNumbers();
  System.out.println("INSERTION SORT");
  System.out.println("Presorted numbers: ");
  printArray();
  long start = System.nanoTime();

  /**
   * Insertionsort Algorithm
   * Wikipedia:
   * much less efficient on large lists than more advanced algorithms 
   * such as quicksort, heapsort, or merge sort. However, insertion sort 
   * provides several advantages:
   * 1. simple implementation
   * 2. efficient for (quite) small data sets
   * 3. adaptive, i.e. efficient for data sets that are already substantially 
   *    sorted: the time complexity is O(n + d), where d is the number of inversions
   * 4. more efficient in practice than most other simple quadratic (i.e. O(n^2)) algorithms 
   *    such as selection sort or bubble sort
   * Complexity:
   * Worst = O(n^2)
   * Average = O(n^2)
   * Best = O(n)
   */
  int in, out;
  for(out=1; out<numbers.length; out++){
   int temp = numbers[out];
   in = out;
   while(in>0 && numbers[in-1] >= temp){
    numbers[in] = numbers[in-1];
    --in;
   }
   numbers[in] = temp;
  }

  long elapsed = (System.nanoTime() - start);
  System.out.println("Insertion-sorted numbers: ");
  printArray();
  System.out.println("Elapsed time: " + elapsed + "ns\n");
 }

 public static void main(String[] args) {
  SortingAlgorithm sa = new SortingAlgorithm();
  sa.bubbleSort();
  sa.selectionSort();
  sa.insertionSort();
 }
}

BFS and DFS (intro)

BFS:
- works in a queue manner (FIFO)

DFS:
- works in a stack manner (LIFO)

Traversing Folder and Files

Here is an updated code to inform you if the file or folder specified does not exists. You may take a look at the original code at this article.

 public void traverseFilesFolders () {
  if (referencedFile.exists()) {
   traverseFilesFolders(referencedFile);
  } else {
   System.out.println("File or Folder does not exist");
  }
 }

Traversing Folders and Files Recursively

Both files and folders are represented as File object in the java.io package. We are recognizing if an object is a file by using the method "isFile()" and a folder with the method "isDirectory()".

import java.io.File;

public class FilesFoldersTraversal {

 private final char SEPARATOR = File.separatorChar;
 private File originalFile;
 private File referencedFile;
 private String pad = null;
 private String absolutePathOriginalFile = null;

 public FilesFoldersTraversal(String inputFileString) {
  File inputFile = new File(inputFileString);
  originalFile = inputFile;
  referencedFile = inputFile;
  absolutePathOriginalFile = originalFile.getAbsolutePath();
 }

 public void traverseFilesFolders () {
  traverseFilesFolders(referencedFile);
 }

 private void traverseFilesFolders(File referencedFile){ 
  if (referencedFile.isDirectory()){
   pad = getPadding(referencedFile);
   processFolders(referencedFile);
  }
  else if (referencedFile.isFile()){
   processFiles(referencedFile);
  }
 }

 private void processFolders(File referencedFile){
  System.out.println(pad + "Folder: " + referencedFile.getName());
  File listFiles[] = referencedFile.listFiles();
  for(File singleFile : listFiles){
   traverseFilesFolders(singleFile);
  }
 }

 private void processFiles(File referencedFile){
  System.out.println(pad  + "  " + "File: " + referencedFile.getName());
 }

 private String getPadding(File referencedFile){
  String padding = ""; 
  String fileAbsolutePath = referencedFile.getAbsolutePath();  
  String filePathSubString = fileAbsolutePath.substring(absolutePathOriginalFile.length(), fileAbsolutePath.length());

  int index = 0;
  int subStringLength = filePathSubString.length();
  while (index < subStringLength) {
   if (filePathSubString.charAt(index) == SEPARATOR){
    padding += "  ";
   }
   index++;
  }

  return padding;
 }

 public static void main(String[] args) {
  FilesFoldersTraversal fft = new FilesFoldersTraversal("/Users/YOUR_USER_NAME/Documents");
  fft.traverseFilesFolders();
 }

}

There are many interesting things you can do with the example shown. You may add a few lines of codes to compile a list of files of a specific file extension, for example ".txt" or ".class".

Tokenizing String Recursively

This is an update to the blog entry "String tokenizer by hand". In this article, I am demonstrating an example of tokenizing a given string in a recursive manner. The code is as below:

import java.util.ArrayList;

public class StringTokenizer {
 
 private static ArrayList tokenizedStr = new ArrayList();
 private static StringBuffer str = new StringBuffer();
 
 public static ArrayList tokenizer(String input){
  int strLength = input.length();
  return tokenizer(input, 0, strLength);
 }

 public static ArrayList tokenizer(String input, int currentIndex, int strLength){
  if (currentIndex < strLength) {
   char curr = input.charAt(currentIndex);
   if (curr != ' ') {
    str.append(curr);
   } else {
    if (str.length() != 0) {
     tokenizedStr.add(str);
    }
    str = new StringBuffer();
   }
   if ((currentIndex == strLength-1 ) && (curr != ' ')) {
    tokenizedStr.add(str);
   }
   currentIndex++;
   tokenizer(input, currentIndex, strLength);
  }
  return tokenizedStr;
 }
 
 public static void main(String[] args) {
  System.out.println(tokenizer("  Hello World   This is     Nicholas Key.  How         are you?  "));
 }

}

Binary Tree and its popular methods

This is something convenient I think to do a brief revision on Binary Tree other than reading about it on Wikipedia. This implementation demonstrates the construction of binary tree with some elements and the typical methods related to it such as:
[1] Pre-Order Traversal
[2] In-Order Traversal
[3] Post-Order Traversal
[4] Getting the size of the binary tree
[5] Get the minimum value
[6] Get the maximum value
[7] Get root value
[8] Inserting new elements

My implementation does not include duplication of elements. You may copy the code and test it yourself.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class BinaryTree {

 private static class TreeNode {
  TreeNode left;
  TreeNode right;
  int nodeValue;
  TreeNode(int data) {
   left = null;
   right = null;
   nodeValue = data;
  }
 }

 private TreeNode root;
 
 public BinaryTree() {
  root = null;
 } 

 public void constructBinaryTreeHardCoded() {
  root = null;
  
  root = new TreeNode(6);   
  //root = insertData(root, 6);
  
  root = insertData(root, 2);
  root = insertData(root, 7);
  root = insertData(root, 1);
  root = insertData(root, 4);
  root = insertData(root, 9);
  root = insertData(root, 3);
  root = insertData(root, 5);
  root = insertData(root, 8);
 } 
 
 public void testHarness(){
  root = null;
  
  Random rand = new Random();
  int rootValue = rand.nextInt( 20 ) + 1;
  root = new TreeNode(rootValue);
  System.out.println("Random seeded root value: " + rootValue);
  int numberOfNodes = rand.nextInt( 18 ) + 1;
  System.out.println("Random number of children to be generated: " + numberOfNodes);
  for (int i = 0; i < numberOfNodes; i++) {
   int randValue = rand.nextInt( 30 ) + 1;
   System.out.println("Inserting: " + randValue);
   root = insertData(root, randValue);
  }
 }
 
 public TreeNode insertData(TreeNode node, int data) {
  if (node == null) {
   node = new TreeNode(data);
  } else {
   if (data < node.nodeValue) {
    if (node.left != null) {
     node.left = insertData(node.left, data);
    } else {
     node.left = new TreeNode(data);
     System.out.println("Inserted " + data + " to the left of " + node.nodeValue);
    }
   } else if (data > node.nodeValue) {
    if (node.right != null) {
     node.right = insertData(node.right, data);
    } else {
     node.right = new TreeNode(data);     
     System.out.println("Inserted " + data + " to the right of " + node.nodeValue);
    }
   } else {
    System.out.println("Not inserting " + data + " because it already exists in the tree");
   }   
  }
  return(node);
 } 

 public boolean isIdenticalTree(BinaryTree comparedTree) {
  return (isIdenticalTree(root, comparedTree.root));
 }

 private boolean isIdenticalTree(TreeNode first, TreeNode second) {
  if (first == null && second == null) {
   return true;
  } else if (first != null && second != null) {
   return (
    first.nodeValue == second.nodeValue &&
    isIdenticalTree(first.left, second.left) &&
    isIdenticalTree(first.right, second.right)
   );
  } else {
   return false;
  }
 } 
 
 public int getSize() {
  return(setSize(root));
 }

 private int setSize(TreeNode node) {
  if (node == null) { 
   return 0;
  } else {
   return(setSize(node.left) + 1 + setSize(node.right));
  }
 } 

 public void printTreeTraversal() {
  System.out.print("Inorder Traversal: ");
  printInOrder(root);
  System.out.print("\nPreorder Traversal: ");
  printPreOrder(root);
  System.out.print("\nPostorder Traversal: ");
  printPostOrder(root);
  System.out.println();
 }


 private void printInOrder(TreeNode node) {
  if (node == null) {
   return;  
  }
  printInOrder(node.left);
  visitTreeNode(node);
  printInOrder(node.right);
 } 

 private void printPreOrder(TreeNode node) {
  if (node == null) {
   return;  
  }
  visitTreeNode(node);
  printPreOrder(node.left);
  printPreOrder(node.right);
 } 
 
 private void printPostOrder(TreeNode node) {
  if (node == null) {
   return;  
  }
  printPostOrder(node.left);
  printPostOrder(node.right);
  visitTreeNode(node);
 } 

 private void visitTreeNode(TreeNode node){
  System.out.print(node.nodeValue + "  ");  
 }
 
 public int getMinValue() {
  return (getMinValue(root));
 }

 private int getMinValue(TreeNode node) {
  while (node.left != null) {
   node = node.left;
  }
  return (node.nodeValue);
 } 
 

 public int getMaxValue() {
  return (getMaxValue(root));
 }

 private int getMaxValue(TreeNode node) {
  while (node.right != null) {
   node = node.right;
  }
  return (node.nodeValue);
 } 

 public int getMaxDepth() {
  int depth = getMaxDepth(root);
  return ((depth > 0) ? (depth - 1) : 0);
 }

 private int getMaxDepth(TreeNode node) {
  if (node == null) {
   return 0;
  } else {
   int leftDepth = getMaxDepth(node.left);
   int rightDepth = getMaxDepth(node.right);
   return (((leftDepth > rightDepth) ? leftDepth : rightDepth) + 1);
  }
 } 

 public boolean containsData(int data) {
  return(containsData(root, data));
 }

 private boolean containsData(TreeNode node, int data) {
  if (node == null) {
   return false;
  } 
  if (data == node.nodeValue) {
   return true;
  } else if (data < node.nodeValue) {
   return(containsData(node.left, data));
  } else {
   return(containsData(node.right, data));
  }
 } 
 
 public int getRootValue(){
  return root.nodeValue;
 }
 
 public boolean containsSumInPath(int total) {
  return( containsSumInPath(root, total) );
 }

 private boolean containsSumInPath(TreeNode node, int total) {
  if (node == null) {
   return(total == 0);
  } else {
   int remainder = total - node.nodeValue;
   if (containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder)) {
    addPaths( remainder, node.nodeValue, total);     
   } 
   return(containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder));
  }
 } 

 private ArrayList path = new ArrayList();
 
 private void addPaths(int remainder, int currentNodeValue, int total){
  if (!path.contains(currentNodeValue)) {
   path.add(currentNodeValue);
  }
 }
 
 public ArrayList getSumOfPath(){
  Collections.reverse(path);
  return path;
 }
 
 public static void main(String[] args) {
  BinaryTree bTree1 = new BinaryTree();
  BinaryTree bTree2 = new BinaryTree();

  bTree1.constructBinaryTreeHardCoded();  
  System.out.println("Size of the binary tree: " + bTree1.getSize());
  System.out.println("Root value in the binary tree: " + bTree1.getRootValue());
  System.out.println("Smallest value in the binary tree: " + bTree1.getMinValue());
  System.out.println("Largest value in the binary tree: " + bTree1.getMaxValue());
  System.out.println("Maximum depth of the binary tree: " + bTree1.getMaxDepth());
  System.out.println("Contains node value 4: " + bTree1.containsData(4));
  System.out.println("Path has sum of 30: " + bTree1.containsSumInPath(30) + " = " + bTree1.getSumOfPath());
  bTree1.printTreeTraversal();

  System.out.println();

  bTree2.testHarness();
  System.out.println("Size of the binary tree: " + bTree2.getSize());
  System.out.println("Root value in the binary tree: " + bTree2.getRootValue());
  System.out.println("Smallest value in the binary tree: " + bTree2.getMinValue());
  System.out.println("Largest value in the binary tree: " + bTree2.getMaxValue());
  System.out.println("Maximum depth of the binary tree: " + bTree2.getMaxDepth());
  System.out.println("Contains node value 11: " + bTree2.containsData(11));
  
  Random rand = new Random();
  int find = rand.nextInt( 30 ) + 1;
  System.out.println("Path has sum of "+ find +": " + bTree2.containsSumInPath(find) + " = " + bTree2.getSumOfPath());
  bTree2.printTreeTraversal();
  
  System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));
  
  System.out.println("\nChanged elements in binary tree");
  bTree2.constructBinaryTreeHardCoded();
  System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));
 }
}

Grabbing Files from Remote Server

I have written a helpful method to grab files from remote server and save them into a local folder. This example works as follow:
[1] The input file will be read line by line
[2] The resource names will be appended to the URL of the remote server
[3] Resources that are found in the remote server will be written to the local folder
[4] Otherwise, show error messages if the resources are not found<br />import java.io.BufferedInputStream;<br />import java.io.BufferedOutputStream;<br />import java.io.BufferedReader;<br />import java.io.File;<br />import java.io.FileNotFoundException;<br />import java.io.FileOutputStream;<br />import java.io.FileReader;<br />import java.io.IOException;<br />import java.net.MalformedURLException;<br />import java.net.URL;<br /><br />public class FileDownloader {<br /> private final static String templatePath = FileDownloader.class.getResource("").getPath().replaceAll("%20", " ");<br /><br /> private static final String folderStr = templatePath + "/pics";<br /> <br /> private static void readText() {<br /> File folder = new File(folderStr);<br /> if (!folder.exists()) {<br /> folder.mkdir();<br /> }<br /> BufferedReader br;<br /> FileReader fr;<br /> String line;<br /> try {<br /> fr = new FileReader(YOUR_FILE_NAME);<br /> br = new BufferedReader(fr);<br /> while ((line = br.readLine()) != null) {<br /> grabFile(line, folderStr);<br /> }<br /> } catch (FileNotFoundException e) {<br /> System.err.println("File not found!");<br /> e.printStackTrace();<br /> }catch (IOException e) {<br /> System.err.println("Error reading file");<br /> e.printStackTrace();<br /> }<br /> }<br /><br /> private static void grabFile(String input, String folder){<br /> byte[] bytes = new byte[4096];<br /> BufferedInputStream in;<br /> BufferedOutputStream out;<br /> URL URLsource = null;<br /> try {<br /> URLsource = new URL(REMOTE_SERVER_URL + input.trim());<br /> in = new BufferedInputStream (URLsource.openStream());<br /> out = new BufferedOutputStream(new FileOutputStream( new File( folder + "/" + input.trim() )));<br /> int pos = in.read( bytes );<br /> while ( pos != -1 ){<br /> out.write( bytes, 0, pos );<br /> pos = in.read( bytes );<br /> }<br /> out.close();<br /> System.out.println("Downloaded: " + input);<br /> } catch (MalformedURLException e) {<br /> e.printStackTrace();<br /> } catch (IOException e) {<br /> System.err.println("Fail to download: " + input);<br /> e.printStackTrace();<br /> } catch (InterruptedException e) {<br /> e.printStackTrace();<br /> }<br /> }<br /><br /> public static void main(String[] args) {<br /> readText();<br /> }<br />}Happy coding everyone :)

Replacing whitespace characters in a string

Here is an example of method overloading - same method name with different number of parameters. The complexity of this algorithm is O(n) because the input string is scanned character by character.

But what if there is a input with a massive size? I would want to partition out the string into several portion depending on the size threshold which can be set in the method and the hash the partitioned texts into a hashmap. Threading is possible in this context because the texts will be processed synchronously instead of sequentially.

public static StringBuffer removeSpace(String input){
  return removeSpace(input, "%20");
}

public static StringBuffer removeSpace(String input, String fillerString){
  StringBuffer sb = new StringBuffer();
  int strLength = input.length();
  int index = 0;
  while(index != (strLength)){
    if (input.charAt(index) != ' ') {
      sb.append(input.charAt(index));
    } else {
      sb.append(fillerString);
    }
    index++;
  }
  return sb;
}

You may test this code with this sample method calls:

System.out.println(removeSpace("Hello World, I am Nicholas Key"));
System.out.println(removeSpace("Hello World, I am Nicholas Key", "[SPACE]"));

Usefulness of BigInteger

It's way much better than Integer, the primitive type; simply because we won't be restricted with arithmetic overflow issue. An example is in this method to compute factorial.

public static BigInteger factorial(int n){
  BigInteger result = BigInteger.ONE;
  for (int count = 1; count <= n; count++) {
    result = result.multiply(BigInteger.valueOf(count));
  }
  return result;
}

The precision is still well maintained even if you iterate through the first 38 numbers. Give it a try if you are not convinced :)
UPDATE: there is a fundamental flaw in this loop. In the previous code, I demonstrated for (int count = 1; count < n; count++). It has changed to for (int count = 1; count <= n; count++)

Numbers with commas

Here's a simple method to include commas after every third digit from the right:

public class Utilities{
  private static int startingPivot;
  private static final int INDENT = 3;

  public static StringBuffer decimalize(int input){
    String conv = Integer.toString(input);
    StringBuffer sb = new StringBuffer();

    int commaIndex = conv.length() / INDENT ; 
    int strLength = conv.length();

    startingPivot = (strLength) - (commaIndex * INDENT );
    if (startingPivot == 0) {
      startingPivot = INDENT ;
    }

    for (int index = 0; index < strLength; index++) {
      if (index == startingPivot) {
        sb.append(",");
        startingPivot = startingPivot + INDENT;
      }
      sb.append(conv.charAt(index));
    }
    return sb;
  }
}

You may try this code by making this method call

System.out.println(Utilities.decimalize(1234567890));

and the output is 1,234,567,890
NEAT :D

String tokenizer by hand

I was thinking of implementing my custom "StringTokenizer" and here it is. The complexity is O(n) which means it depends on the size of the string.

public static ArrayList tokenizer(String input){
  ArrayList tokenizedStr = new ArrayList();
  StringBuffer str = new StringBuffer();
  int strLength = input.length();
  int index = 0;
  while (index < strLength) {
    char curr = input.charAt(index);
    if (curr != ' '){
      str.append(curr);
    } else {
      tokenizedStr.add(str);
      str = new StringBuffer();
    } 
    if ((index == strLength-1 ) && (curr != ' ')) {
      tokenizedStr.add(str);
    }
    index++;
  }
  return tokenizedStr;
}

The most interesting part of this method if the condition to check if we have reached the last character of the string and to make sure if it is also not a whitespace character.

UPDATE:
On a second thought, the algorithm in this method is not perfect because it will still retain inline whitespace characters. This is a much better way to tokenize the strings

  while (index < strLength) {
    char curr = input.charAt(index);
    if (curr != ' '){
      str.append(curr);
    } else {
      if (str.length() != 0) {
        tokenizedStr.add(str);
      }
      str = new StringBuffer();
    } 
    if ((index == strLength-1 ) && (curr != ' ')) {
      tokenizedStr.add(str);
    }
    index++;
  }

An example of solving this in recursion is at "Tokenizing String Recursively".