Linked List Demo

One of my all time favorite book is Programming Pearls by Jon Bentley. Every time I read this book or some pages, I feel the urge to do some core computer science problem solving. Even though in the day time I work mostly on Java, at one point in college I did enjoy creating simple data structures, playing with pointers. While reading few chapters from this book in last couple of months made me go back and do some coding. I had never really coded LinkedList in Java. First reason is that we have a ready made implementation in java collections and also work never required it. I wanted to see how we can implement LinkedList in Java without using support of explicit pointers. I do not think I did any groundbreaking code here but it was my personal exploration and the most satisfying part of it was to code all these without looking up definitions and algorithms online. I created this demo of LinkedList and tried solving some interesting problems in it. I will probably keep updating this blog entry as I solve more interesting problems.

package introduction;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
This class is meant to give the demo of Singly Linked List operations. The user is required to input choice. The input choices are as followed.

A This choice demos Add operation on a singly linked list. This step adds 10 nodes to the list with the values 100..110. The list is printed at the end of the operation. For example a node might be printed in the following fashion.
 Node [8] = -->Node [value = 101, next = -->Node [value = 100, next = null]] 
 This print statement signifies that above node was 9th node inserted in
 the list. There are 8 other nodes behind of this node. Also 'next = -->Node [value = 100, next = null]' signifies that there is a node with value 100 is the last node of the list.
D This choice demos Add and Delete operation on a singly linked list. This steps adds 10 nodes to the list with the values 100..110. It deletes the nodes which have value 102 and 103. It then prints the remaining list.
F This choice demos the find step on linked list. In this choice we create the list of 10 nodes and we find the 3rd node from the end. This problem statement is important because when we have access to only head node of linked list, we do not know where the linked list ends.
J This choice demos the functionality where we try to find whether two linked lists are joined at a node.
S This choice demos the use of LinkedList as a stack.
R This choice demos the reversal operation of the linked list. This step adds 10 nodes to the list with the values 100..110. The list is printed at the end of the operation.Then the list is reversed. Now the head points to the last node of the original list.

* @author Shilpa Deshpande
*/
public class LinkedListDemo {
    public enum Choice {
        A("ADD"),
        D("DELETE"),
        F("FIND NTH NODE FROM END"),
        J("JOINT"),
        S("STACK"),
        R("REVERSE");

        private String str;

        private Choice(String str) {
            this.str = str;
        }
        public String getStr() {
            return str;
        }
    }
    public static void main(String[] args) throws IOException {
        LinkedList list = null;
        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String input = null;
            Choice choice = null;
            if ((input = reader.readLine()) != null) {
                try {
                    choice = Enum.valueOf(Choice.class, input);
                }
                catch (Exception e) {
                    // In case, user just presses the 'Enter' key.
                    choice = Choice.R;
                }
            }
            list = new LinkedList();
            switch (choice) {
                case A: {
                    list.createList(10);
                    // Print current linked list
                    list.print();
                    break;
                }
                case D: {
                    list.createList(10);
                    // Print current linked list
                    System.out.println("BEFORE DELETING");
                    list.print();
                    // Remove following nodes from the list.
                    list.delete(new int[] { 102, 103 });
                    // Print current linked list
                    System.out.println("AFTER DELETING 102, 103");
                    list.print();
                    break;
                }

                case F: {
                    list.createList(10);
                    // Find the next node given the value of previous node.
                    int nth = 3;
                    Node findNthNodeFromEnd = list.findNthNodeFromEnd(nth);
                    System.out.println(nth + " TH NODE FROM THE END IS " + findNthNodeFromEnd);
                    break;
                }

                case J: {
                    // Y-shaped lists
                    LinkedList list2 = new LinkedList();
                    list.createList(7);
                    list2.createList(2);
                    int joinElementValue = 105;
                    list.joinLists(list2, joinElementValue);
                    boolean areTwoListsJoined = list.areTwoListsJoined(list2);
                    System.out.println("ARE TWO LISTS JOINED " + areTwoListsJoined);
                    Node node = list.findJoint(list2);
                    System.out.println("THE TWO LISTS ARE JOINED AT " + node);
                    list2.truncate();
                    break;
                }
                case S: {
                    // LinkedList as stack
                    for (int i = 0; i < 6; i++) {
                        list.push(new Node(i + 100));
                    }
                    list.print();

                    for (int i = 0; i < 5; i++) {
                        Node pop = list.pop();
                        System.out.println("NODE POPPED " + pop);
                        list.listStack();
                    }
                    break;
                }
                case R:
                default: {
                    list.createList(5);
                    System.out.println("BEFORE REVERSING THE LIST ");
                    list.print();
                    list.reverse();
                    System.out.println("AFTER REVERSING THE LIST ");
                    list.print();
                    break;
                }
            }
        }
        catch (Exception e) {
            e.printStackTrace();
        }
        finally {
            // As a good practice clean up all the data structures.
            list.truncate();
        }
    }
}

class LinkedList {

    private Node head; // This node always points to the first node in the linked list.

    /**
     * This method checks whether the current list and parameter list are joined at a Node.
     * @param list2
     *            non-null instance of {@link LinkedList}
     * @return true if the two lists are joined.
     */
    public boolean areTwoListsJoined(LinkedList list2) {
        if (list2 == null) {
            throw new IllegalArgumentException("LinkedList: areTwoListsJoined cannot accept null list2 parameter.");
        }
        boolean areJoined = false;
        Node head2 = list2.head;
        Node currentNode = head;
        Node lastNode1 = null, lastNode2 = null;
        while (currentNode != null) {
            lastNode1 = currentNode;
            currentNode = currentNode.getNext();
        }
        currentNode = head2;
        while (currentNode != null) {
            lastNode2 = currentNode;
            currentNode = currentNode.getNext();
        }
        if (lastNode1 == lastNode2) {
            areJoined = true;
        }
        return areJoined;
    }

    /**
     * This method deletes all the nodes in the list including the head node.
     */
    public void truncate() {
        while (head != null) {
            Node currentNode = head;
            head = head.getNext();
            currentNode = null;
        }
        System.out.println("AFTER CLEANUP THE LENGTH OF THE LIST " + findLength());
    }

    /**
     * This method create a list that contain 'number' of nodes.
     * @param number
     *            - a number that signifies how many nodes need to be created.
     * @return non-null instance of {@link Node} which points to the head.
     */
    public Node createList(int number) {
        for (int i = 0; i < number; i++) {
            Node node = new Node(i + 100);
            if (head == null) {
                head = node;
            }
            else {
                node.setNext(head);
                head = node;
            }
        }
        return head;
    }

    /**
     * This method finds the element at which these two lists are joined.
     * @param list2
     *            instance of {@link LinkedList}.
     * @return instance of Node at which two lists are joined. If the lists are not joined, this method will return null.
     */
    public Node findJoint(LinkedList list2) {
        if (list2 == null) {
            throw new IllegalArgumentException("LinkedList: areTwoListsJoined cannot accept null list2 parameter.");
        }
        Node joint = null;
        Node head2 = list2.head;
        int length1 = this.findLength(), length2 = list2.findLength();
        int length = 0;
        boolean firstListLonger = false;
        if (length1 > length2) {
            firstListLonger = true;
            length = length2;
        }
        else {
            length = length1;
        }
        Node currentNode1 = head;
        Node currentNode2 = head2;
        int absLength = Math.abs(length1 - length2);
        System.out.println("FIRST LENGTH " + length1 + " SECOND LENGTH " + length2 + " \nFIRST HEAD = " + currentNode1 + " \nSECOND HEAD = " + currentNode2);
        System.out.println("ABSOLUTE LENGTH " + absLength);
        // Advance first list length1-length2
        if (firstListLonger) {
            for (int i = 0; i < absLength; i++) {
                currentNode1 = currentNode1.getNext();
            }
        }
        else {
            for (int i = 0; i < absLength; i++) {
                currentNode2 = currentNode2.getNext();
            }
        }

        // Now we advance one position for each list and check whether we are referencing the same object
        for (int i = 0; i < length; i++) {
            System.out.println("CURRENTNODE 1 " + currentNode1 + "\nCURRENTNODE 2 " + currentNode2);
            // found the joint
            if (currentNode1 == currentNode2) {
                joint = currentNode1;
                break;
            }
            else {
                currentNode1 = currentNode1.getNext();
                currentNode2 = currentNode2.getNext();
            }
        }

        return joint;
    }

    /**
     * This method returns the length of the list.
     * @param head
     * @return
     */
    private int findLength() {
        int length = 0;
        Node currentNode = head;
        while (currentNode != null) {
            length++;
            currentNode = currentNode.getNext();
        }
        return length;
    }

    /**
     * This method finds Nth node from the end of the list. This is an important method because in linked list, we do not know the end of the list and also the position of current node in the list
     * from the end.
     * @param nth
     *            , signifies the position of the {@link Node} which is to be found.
     * @return nth node if found; may return null if the nth node cannot be found.
     */
    public Node findNthNodeFromEnd(int nth) {
        int count = 0;
        Node nthNode = head;
        Node currentNode = head;
        while (currentNode != null) {
            count++;
            // If there are less than n elements in the list, break.
            if (currentNode.getNext() == null && count < nth) {
                break;
            }
            if (count > nth) {
                nthNode = nthNode.getNext();
            }
            currentNode = currentNode.getNext();
        }
        if (nthNode == head) {
            return null;
        }
        return nthNode;
    }

    /**
     * This method joins the parameter List with the current list at a node whose value is specified by parameter joinElementValue. By the end of the method, two lists are joined at a Node creating a
     * 'Y' shape.
     * @param list2
     *            non-null instance of {@link LinkedList}. It is assumed that list2 contains
     * @param joinElementValue
     *            this is the value of the Node which is a joint node between two lists.
     */
    public void joinLists(LinkedList list2, int joinElementValue) {
        if (list2 == null) {
            throw new IllegalArgumentException("LinkedList: areTwoListsJoined cannot accept null list2 parameter.");
        }
        Node head1 = head;
        Node head2 = list2.head;
        System.out.println("FIRST LIST");
        this.print();
        System.out.println("SECOND LIST");
        list2.print();
        // Add nodes to second list manually
        // Traverse to the end of second list.
        Node currentNode2 = head2;
        while (currentNode2.getNext() != null) {
            currentNode2 = currentNode2.getNext();
        }
        // Traverse to the node whose value matches joinElementValue.
        Node currentNode1 = head1;
        while (currentNode1.getValue() != joinElementValue) {
            currentNode1 = currentNode1.getNext();
        }
        // Now point second list to the node whose value is joinElementValue.
        currentNode2.setNext(currentNode1);
        System.out.println("After joining second list");
        list2.print();
    }

    /**
     * This method lists all the nodes in the stack starting at the top of the stack.
     */
    public void listStack() {
        print();
    }

    /**
     * This method removes the node from the top of the stack.
     * @return
     */
    public Node pop() {
        Node currentNode = head;
        head = head.getNext();
        return currentNode;
    }

    /**
     * This method prints all the {@link Node} of the list.
     * @param head
     *            points to the first node of the linked list.
     */
    public void print() {
        if (head == null) {
            throw new IllegalArgumentException("LinkedList: print method cannot work with null head Node.");
        }
        Node currentNode = head;
        int counter = 0;
        do {
            // counter signify its insertion time in the linked list.
            System.out.println("Node [" + counter++ + "] = " + currentNode);
            if (currentNode.getNext() == null) {
                break;
            }
            currentNode = currentNode.getNext();
        } while (true);

    }

    /**
     * This method pushes the parameter node onto the stack. This means that the new element now works as the top of the stack.
     * @param node
     *            non-null instance of {@link Node}.
     */
    public void push(Node node) {
        if (node == null) {
            throw new IllegalArgumentException("LinkedList: push method cannot accept null Node parameter.");
        }
        node.setNext(head);
        head = node;
    }

    /**
     * This method delete the nodes from the list. The parameter array provides the values of the nodes.
     * @param deleteArray
     *            contains values of the nodes.
     */
    public void delete(int[] deleteArray) {
        for (int i = 0; i < deleteArray.length; i++) {
            Node previousNode = null, currentNode = null;;
            int findElementVal = deleteArray[i];
            currentNode = head;
            previousNode = head;
            while (currentNode != null) {
                // We have found the node
                if (currentNode.getValue() == findElementVal) {
                    Node nextNode = currentNode.getNext();
                    // Assign nextNode as next of previous node
                    if (nextNode != null) {
                        previousNode.setNext(nextNode);
                    }
                    currentNode = null;
                }
                else {
                    // Increment previousNode and currentNode to point to next node respectively.
                    previousNode = currentNode;
                    currentNode = currentNode.getNext();
                }
            }
        }
    }

    /**
     * This method reverses the linked list. By the end of this method, the head pointer will point to the previous last node of the list.
     * @return new head of the linked list.
     */
    public void reverse() {
        /*
         * First point next and previous reference. currentHead and newHead reference will point to the next node of current head node.
         * previous reference will point to current head node.
         */
        Node newHead = head.getNext();
        Node previousNode = head;
        Node currentNode = head.getNext();

        // When currentNode has reached null, we have traveled the end of the list.
        while (currentNode != null) {
            // Now find out next to next element.
            Node next = newHead.getNext();
            if (next != null) {
                newHead = next;
                if (previousNode == head) {
                    previousNode.setNext(null);
                }
                currentNode.setNext(previousNode);
                previousNode = currentNode;
                currentNode = next;
            }
            else {
                currentNode = null;
                newHead.setNext(previousNode);
            }
        }
        head = newHead;
    }

}

/**
 * 
 * This class represents a {@link Node} in a singly linked list. This class assumes that every instance of the {@link Node} contains two pieces of information.

The integer value
The pointer that points to the next instance of {@link Node} in a singly linked list

 * @author Shilpa Deshpande
 */
class Node {

    private int value;
    private Node next;

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

    public void setValue(int value) {
        this.value = value;
    }

    /**
     * This method sets the parameter node as the next node of current node. // We assume that current node is the head node of the list. non-null instance of {@link Node}
     */
    public void setNext(Node node) {
        this.next = node;
    }

    public int getValue() {
        return value;
    }

    /**
     * This method return the reference to the {@link Node} which is the next node from current node.
     * @return instance of {@link Node}. It may be null.
     */
    public Node getNext() {
        return next;
    }

    /**
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return " -->Node [value = " + value + ", next = " + next + "]";
    }
}

Microsoft Excel and BOM character

BOM Character? What is that? What does it have to do with Microsoft Excel?

Yes, I know a lot of questions do arise in the title of the blog itself.
This blog is to tell a story about how file encoding and its interpretations by Microsoft Excel can cause big issues. In one of the project, we had to create CSV files. CSV files are really simple to construct. The columns are separated with commas and the rows are separated with newline characters. Our development machines are mostly Linux. During development, we used Open Office Excel to open the document and check the validity of the data. All the data would show perfectly. It did not matter what language is used to create the file. During the whole development cycle we did not think we would spend 2 weeks on solving a mystery why the same file contains gibberish characters when opened with Microsoft Excel but Open Office Excel would shows everything nice and dandy. Our Quality Assurance guy documented the issue, I almost did not want to believe him but eventually I saw the truth in his tests. Now the mystery had to solved.

Even though we have built CSV files before this project, XML/XSL transformations (some proprietary stuff) took care of encoding. After doing lots of google search and forum reads, we found a good stackoverflow discussion that had valuable discussion about MS-Excel and CSV files. -  . There are a lot of ways suggested on this page, we tried many of them but only one finally worked. Adding Byte Order Marker character to the first row of the file. We did a small experiment by testing only file creation related code and found that file could be read successfully in Microsoft Excel.

Giveaways:

A] Two absolute great readings -

1) Joel Spolsky's blog on character encoding.
2) BOM Character Wikipedia Entry

B] Write a small and specialized class that only solves given problem, this reduces test time.

Next time you have to construct a CSV file which may/may not have foreign characters, use BOM :)

An easy way to find Quartz scheduler queries

We had a very interesting issue on production couple of weeks ago. This issue entailed the alert email to all the DBA's in the team. The issue was related to

ORA 03137 TTC protocol internal error

The error email contained the query but we had not written this query so we did not have much idea about it. Even though investigation of the issue is a whole new topic of blog, this blog is to tell you a small trick to find the query in Quartz scheduler code base. I had to find following query in the code base.

SELECT TRIGGER_NAME, TRIGGER_GROUP, NEXT_FIRE_TIME, PRIORITY FROM 
{0}TRIGGERS WHERE TRIGGER_STATE = ? AND NEXT_FIRE_TIME < ? AND 
(NEXT_FIRE_TIME >= ?) ORDER BY NEXT_FIRE_TIME ASC, PRIORITY DESC

Quartz scheduler constructs the queries on the fly so one can never find it easily in their code base. Even though one looks at their files called as StdJDBCConstants.java, one may not be able to read and pick through it. This file contains most of the queries for standard databases.

After some frantic search, I used the first part of the query to grep on the entire source code (actual source code and related documentation).

grep -lir "SELECT TRIGGER_NAME, TRIGGER_GROUP" *

Finally the search came up with the result. Now I could understand the context of the query and then could investigate the issue further on.. Grep saved the day!
docs/api/constant-values.html