JavaAlgorithms/0000755000076400007640000000000012227405377012440 5ustar iankiankJavaAlgorithms/src/0000755000076400007640000000000012160733333013217 5ustar iankiankJavaAlgorithms/src/treeAlgorithms/0000755000076400007640000000000012160733440016207 5ustar iankiankJavaAlgorithms/src/treeAlgorithms/TreeNode.java0000644000076400007640000000453512170321606020564 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; import java.util.Iterator; public class TreeNode> implements Iterable> { private Comparable mValue; private TreeNode mRight = null; private TreeNode mLeft = null; /** * @return the reference to the left branch of the tree */ public TreeNode getLeft() { return mLeft; } /** * @param node * a new left branch reference */ public void setLeft(TreeNode node) { this.mLeft = node; } /** * @return the reference to the right tree branch */ public TreeNode getRight() { return mRight; } /** * @param node * a new right branch reference */ public void setRight(TreeNode node) { this.mRight = node; } /** * Initialize a TreeNode object with an object value. * * @param value */ public TreeNode(Comparable value) { this.mValue = value; } /** * @return the value of the TreeNode */ public Comparable getValue() { return mValue; } /** * @param newVal * new value that will replace the existing value */ public void setValue(Comparable newVal) { this.mValue = newVal; } /** * Print the tree, from the root downward. * * @param root * the root of the tree * @param indent * an initial amount of space indentation. */ protected void printTree(TreeNode root, String indent) { if (root != null) { System.out.println(indent + root); String newIndent = indent + " "; for (TreeNode elem : root) { printTree(elem, newIndent); } } } // printTree /** * Print the tree, from the root downward * * @param root */ public void printTree() { printTree(this, ""); } @Override public Iterator> iterator() { Iterator> itr = new TreeNodeIterator(this); return itr; } @Override public String toString() { return this.getValue().toString(); } } JavaAlgorithms/src/treeAlgorithms/TreeNodeIterator.java0000644000076400007640000000273012211244625022272 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; import java.util.ArrayList; import java.util.Iterator; /** * TreeNodeIterator *

* Support for iteration over the children of a tree node. *

* Jun 16, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param */ public class TreeNodeIterator> implements Iterator> { private ArrayList> mSiblings; private int ix; /** * Initialize the Iterator. A small array is constructed from the node * children. It is this array that is iterated over. * * @param treeNode */ public TreeNodeIterator(TreeNode treeNode) { ix = 0; mSiblings = new ArrayList>(); if (treeNode != null) { if (treeNode.getLeft() != null) { mSiblings.add(treeNode.getLeft()); } if (treeNode.getRight() != null) { mSiblings.add(treeNode.getRight()); } } } @Override public boolean hasNext() { return (ix < mSiblings.size()); } @Override public TreeNode next() { TreeNode nextVal = null; if (hasNext()) { nextVal = mSiblings.get(ix); ix++; } return nextVal; } @Override public void remove() { // Not implemented } } JavaAlgorithms/src/treeAlgorithms/LeastCommonAncestor.java0000644000076400007640000000601412170331424022770 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; /** * * LeastCommonAncestor *

* Given a ordered binary tree and two values that exist in the tree, find their * least common ancestor. The least common ancestor is the ancestor tree node * with the least value. *

*

* In the tree we assume that the left node is less and the right node is * greater. *

* * Jun 15, 2013 * * @author Ian Kaplan, iank@bearcave.com * * @param * The type for the TreeNode. This type must implement the Comparable * interface. */ public class LeastCommonAncestor> { /** * Find the ancestor node in the tree such that valLess <= root.getValue() * <= valGT, where valLess < valGT. If valLess and ValGT exist in the tree, * then such a node must exist. * * @param root * the tree root * @param valLess * @param valGT * @return the node that is the least common ancestor */ public TreeNode findLCA(TreeNode root, T valLess, T valGT) { TreeNode found = null; if (root != null) { Comparable rootVal = root.getValue(); // if root != valLess && root != valGT if (rootVal.compareTo(valLess) != 0 && rootVal.compareTo(valGT) != 0) { if (root.getLeft() != null) { // if left == valLess || left == valGT then return root Comparable leftVal = root.getLeft().getValue(); if (leftVal.compareTo(valLess) == 0 || leftVal.compareTo(valGT) == 0) { return root; } } if (root.getRight() != null) { // if right == valLess || right == valGT then return root Comparable rightVal = root.getRight().getValue(); if (rightVal.compareTo(valLess) == 0 || rightVal.compareTo(valGT) == 0) { return root; } } // if valLess < root < valGT then return root if (rootVal.compareTo(valLess) > 0 && rootVal.compareTo(valGT) < 0) { return root; } // if root < valLess && root < valGT then findLCA(right, valLess, valGT) if (rootVal.compareTo(valLess) < 0 && rootVal.compareTo(valGT) < 0) { return findLCA(root.getRight(), valLess, valGT); } // if root > valLess && root > valGT then findLCA(left, valLess, valGT ) if (rootVal.compareTo(valLess) > 0 && rootVal.compareTo(valGT) > 0) { return findLCA(root.getLeft(), valLess, valGT); } } } return found; } } JavaAlgorithms/src/treeAlgorithms/TestTree.java0000644000076400007640000000700412170331500020602 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; import static org.junit.Assert.*; import java.util.ArrayList; import org.junit.Test; /** * TestTree Jun 16, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class TestTree { @Test public void testOrderedCheck() { TreeNode four = new TreeNode(4); TreeNode six = new TreeNode(6); TreeNode eight = new TreeNode(8); TreeNode twelve = new TreeNode(12); TreeNode ten = new TreeNode(10); TreeNode thirteen = new TreeNode(13); TreeNode sixteen = new TreeNode(16); TreeNode thirtyTwo = new TreeNode(32); TreeNode sixtyFour = new TreeNode(64); six.setLeft(four); twelve.setLeft(ten); twelve.setRight(thirteen); eight.setLeft(six); eight.setRight(twelve); thirtyTwo.setRight(sixtyFour); sixteen.setLeft(eight); sixteen.setRight(thirtyTwo); assertTrue("Tree is ordered by was not recognized", Algorithms.isOrdered(sixteen)); eight.setValue(96); assertFalse("Tree is not ordered but was not recognized", Algorithms.isOrdered(sixteen)); eight.setValue(8); thirteen.setValue(5); assertFalse("Tree is not ordered but was not recognized", Algorithms.isOrdered(sixteen)); } /** * Test tree construction for trees composed of String elements */ @Test public void testStringTreeBuild() { final String[] words = new String[] { "t'was", "brillig", "and", "the", "slighty", "toves", "did", "gyre", "and", "gimble", "in", "the", "wabe", "all", "mimsy", "were", "the", "borogroves", "and", "moonraths", "outgrabe" }; TreeBuilder builder = new TreeBuilder(); for (String word : words) { builder.addNode(word); } TreeNode root = builder.getTree(); assertTrue("String tree is not ordered", Algorithms.isOrdered(root)); } @Test public void testInOrder() { class OrderedVisit> implements Algorithms.NodeVisitor { private ArrayList mValues = new ArrayList(); @Override public void visit(TreeNode node) { Comparable val = node.getValue(); mValues.add((T) val); } public ArrayList getValues() { return mValues; } } // class OrderedVisit Character vals[] = new Character[] { 'A', 'B', 'D', 'E', 'H', 'I', 'F', 'C', 'G' }; Character ordered[] = new Character[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' }; TreeBuilder builder = new TreeBuilder(vals); TreeNode root = builder.getTree(); OrderedVisit visitor = new OrderedVisit(); Algorithms.inOrder(root, visitor); ArrayList treeVals = visitor.getValues(); int ix = 0; boolean OK = true; for (Character ch : ordered) { if (!ch.equals(treeVals.get(ix))) { OK = false; } ix++; } assertTrue("In order traversal failed", OK); } } JavaAlgorithms/src/treeAlgorithms/Algorithms.java0000644000076400007640000000625612170331320021164 0ustar iankiank/** \file * * Jun 20, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; /** * Algorithms Jun 20, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class Algorithms { /** * NodeVisitor Jun 20, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param */ public interface NodeVisitor> { /** * Do something when a node is visited. * * @param node */ void visit(TreeNode node); } // interface NodeVistor private Algorithms() { } /** * A function that tests whether a tree is ordered or not. One can imagine a * use for such a function. This is an interview question during a very * unpleasant interview at Sumo Logic. * * @param root * the root of a binary tree * @return true if the tree is ordered (where the left branch is the less * than branch and the right branch is the greater than branch), * false otherwise. */ public static > boolean isOrdered(TreeNode root) { boolean ordered = false; if (root != null) { ordered = true; if (root.getLeft() != null) { boolean orderedBranch = isOrdered(root.getLeft()); if (!orderedBranch) { ordered = false; } } if (root.getRight() != null) { boolean orderedBranch = isOrdered(root.getRight()); if (!orderedBranch) { ordered = false; } } if (ordered) { Comparable rootVal = root.getValue(); if (root.getLeft() != null) { @SuppressWarnings("unchecked") T leftVal = (T) root.getLeft().getValue(); if (rootVal.compareTo(leftVal) < 0) { ordered = false; } } if (root.getRight() != null) { @SuppressWarnings("unchecked") T rightVal = (T) root.getRight().getValue(); if (rootVal.compareTo(rightVal) > 0) { ordered = false; } } } } return ordered; } /** * In-order tree traversal. For an ordered tree, this will visit the nodes * in increasing order. * * @param root * the current root of the tree * @param visitor * a class that implements NodeVisitor that performs an operation * when the tree node is visited. * @param visit * an object that implements the visit() method to so something * when the node is visited. */ public static > void inOrder(TreeNode root, NodeVisitor visitor) { if (root != null) { inOrder(root.getLeft(), visitor); visitor.visit(root); inOrder(root.getRight(), visitor); } } // inOrder } JavaAlgorithms/src/treeAlgorithms/TestLCA.java0000644000076400007640000000204512170321606020310 0ustar iankiank/** \file * * Jun 16, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; import static org.junit.Assert.*; import org.junit.Test; /** * TestLCA Jun 19, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class TestLCA { @SuppressWarnings("javadoc") @Test public void test() { Integer numbers[] = new Integer[] { 20, 22, 8, 4, 12, 10, 14 }; TreeBuilder builder = new TreeBuilder(); for (Integer num : numbers) { builder.addNode(num); } TreeNode root = builder.getTree(); TestTree treeTest = new TestTree(); assertTrue("LCA tree should be ordered", Algorithms.isOrdered(root)); LeastCommonAncestor lca = new LeastCommonAncestor(); TreeNode lcaNode = lca.findLCA(root, 4, 14); int lcaValue = (Integer) lcaNode.getValue(); assertTrue("LCA value should be 8, but is " + lcaValue, (lcaValue == 8)); } } JavaAlgorithms/src/treeAlgorithms/TreeBuilder.java0000644000076400007640000000530012170321610021247 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package treeAlgorithms; /** * TreeBuilder *

* Build an ordered binary tree, where the left branch is the "less than" branch * and the right branch is the greater than branch. *

* Jun 15, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param */ public class TreeBuilder> { private TreeNode mRoot = null; /** * The constructor to build an empty tree */ public TreeBuilder() { } /** * The constructor to add to an existing tree (even if the tree consists of * a single root node). * * @param root * the root of the tree. */ public TreeBuilder(TreeNode root) { this.mRoot = root; } public TreeBuilder(T[] vals) { if (vals != null) { for (T val : vals) { this.addNode(val); } } } /** * The internal function to add a new value to the tree. * * @param root * the root of the tree or sub-tree * @param newVal * the new value to be added to the tree * @return true if the value is found in the tree, false otherwise */ protected boolean addNode(TreeNode root, T newVal) { Comparable rootVal = root.getValue(); boolean found = true; if (rootVal.compareTo(newVal) == 0) { found = true; } else if (rootVal.compareTo(newVal) < 0) { if (root.getRight() != null) { addNode(root.getRight(), newVal); } else { TreeNode newNode = new TreeNode(newVal); root.setRight(newNode); } } else if (rootVal.compareTo(newVal) > 0) { if (root.getLeft() != null) { addNode(root.getLeft(), newVal); } else { TreeNode newNode = new TreeNode(newVal); root.setLeft(newNode); } } return found; } /** * Add a new value to the tree * * @param newVal * @return true if the value is found in the tree, false otherwise. */ public boolean addNode(T newVal) { boolean found = false; if (newVal != null) { if (mRoot == null) { TreeNode newNode = new TreeNode(newVal); mRoot = newNode; } else { found = addNode(mRoot, newVal); } } return found; } /** * @return the root of the tree */ public TreeNode getTree() { return mRoot; } } JavaAlgorithms/src/listAlgorithms/0000755000076400007640000000000012160754111016221 5ustar iankiankJavaAlgorithms/src/listAlgorithms/ListNodeIterator.java0000644000076400007640000000213312170327100022311 0ustar iankiank/** \file * * Jun 15, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import java.util.Iterator; /** * ListNodeIterator *

* Support for iteration over a list. *

* Jun 16, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param */ public class ListNodeIterator> implements Iterator> { private ListNode mHead = null; /** * Initialize the Iterator. A small array is constructed from the node * children. It is this array that is iterated over. * * @param listNode * */ public ListNodeIterator(ListNode listNode) { this.mHead = listNode; } @Override public boolean hasNext() { return this.mHead != null; } @Override public ListNode next() { ListNode retVal = mHead; if (hasNext()) { mHead = mHead.getNext(); } return retVal; } @Override public void remove() { throw new UnsupportedOperationException(); } } JavaAlgorithms/src/listAlgorithms/TestStack.java0000644000076400007640000000147712170321606021002 0ustar iankiank/** \file * * Jun 20, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import static org.junit.Assert.*; import org.junit.Test; public class TestStack { @Test public void test() { Character vals[] = new Character[] { 'A', 'B', 'C', 'D', 'E' }; Stack charStack = new Stack(); for (Character ch : vals) { charStack.push(ch); } boolean OK = true; int ix = vals.length - 1; while (charStack.peek() != null) { Character ch = charStack.pop(); if (!ch.equals(vals[ix])) { OK = false; break; } ix--; } // while assertTrue("Queue failed", OK); } // test } JavaAlgorithms/src/listAlgorithms/Stack.java0000644000076400007640000000260112170321605020127 0ustar iankiank/** \file * * Jun 20, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; /** * Stack * * A stack based on a linked list. * * Jun 20, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param * a type that implements Comparable */ public class Stack> { private ListNode mTOS = null; /** * Push a value on top of the stack. * * @param val */ public void push(T val) { ListNode newElem = new ListNode(val); newElem.setNext(mTOS); mTOS = newElem; } /** * Remove the top element from the stack */ protected void popTop() { if (mTOS != null) { ListNode top = mTOS; mTOS = top.getNext(); top.setNext(null); } } /** * @return the top of stack value, without removing it. */ public T peek() { T tosVal = null; if (mTOS != null) { tosVal = mTOS.getValue(); } return tosVal; } /** * @return the top of stack value, removing the the top of stack element */ public T pop() { T tosVal = peek(); popTop(); return tosVal; } public void printStack() { if (mTOS != null) { mTOS.printList(); } } } JavaAlgorithms/src/listAlgorithms/TestQueue.java0000644000076400007640000000167112170323157021020 0ustar iankiank/** \file * * Jun 20, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import static org.junit.Assert.*; import org.junit.Test; /** * * TestQueue * Jul 13, 2013 * *

* Test for the TwoStackQueue algorithm. *

* * @author Ian Kaplan, iank@bearcave.com */ public class TestQueue { @Test public void test() { Character vals[] = new Character[] { 'A', 'B', 'C', 'D', 'E' }; TwoStackQueue queue = new TwoStackQueue(); for (Character ch : vals) { queue.enqueue(ch); } boolean OK = true; int ix = 0; while (queue.peek() != null) { Character ch = queue.dequeue(); if (!ch.equals(vals[ix])) { OK = false; break; } ix++; } assertTrue("Queue failed", OK); } } JavaAlgorithms/src/listAlgorithms/TwoStackQueue.java0000644000076400007640000000335712170331640021637 0ustar iankiank/** \file * * Jun 20, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; /** * TwoStackQueue *

* This code implements a queue (first in first out) with two stacks. *

*

* Before a new item is pushed onto the queue that serves as a stack, all * existing items are copied into a storage stack. The item is then added to the * stack and the other items are copied back. *

*

* The time complexity of N queue pushes is O(N^2) copy operations. All of * this could be avoided with a list head and a list tail pointer. *

*

* This is one of those alleged interview questions that would not actually come * up in actual software. The question came from Cracking the Coding * Interview by Gayle McDowell. *

* Jun 20, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class TwoStackQueue> { private Stack mStore = new Stack(); private Stack mQueue = new Stack(); protected void copyToStore() { while (mQueue.peek() != null) { mStore.push(mQueue.pop()); } } protected void copyFromStore() { while (mStore.peek() != null) { mQueue.push(mStore.pop()); } } /** * Enqueue a value * * @param val */ public void enqueue(T val) { copyToStore(); mQueue.push(val); copyFromStore(); } public T peek() { T queueVal = mQueue.peek(); return queueVal; } /** * dequeue a value * * @return the (logical) tail value of the queue */ public T dequeue() { T queueVal = mQueue.pop(); return queueVal; } } JavaAlgorithms/src/listAlgorithms/TestListAlgorithms.java0000644000076400007640000000505712170321606022700 0ustar iankiank/** \file * * Jun 18, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import static org.junit.Assert.*; import org.junit.Test; /** * TestListAlgorithms * * JUnit tests for methods in the listAlgorithms.Algorithms class * * Jun 19, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class TestListAlgorithms { /** * Test the reverse() algorithm. */ @Test public void testReverse() { Character[] vals = new Character[] { 'A', 'B', 'C', 'D', 'E' }; Character[] rvals = new Character[] { 'E', 'D', 'C', 'B', 'A' }; ListNode list = Algorithms.buildList(vals); ListNode rlist = Algorithms.buildList(rvals); ListNode newList = Algorithms.reverse(list); assertTrue("List reverse failed", Algorithms.listEquals(rlist, newList)); } @SuppressWarnings("javadoc") @Test public void testDedup() { Character[] vals = new Character[] { 'A', 'B', 'B', 'C', 'D', 'D', 'D', 'D', 'E', 'E', 'F', 'G', 'H', 'H', 'H' }; Character[] dedupVals = new Character[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; Character[] aVals = new Character[] { 'A', 'A', 'A', 'A', 'A', 'A', 'A' }; ListNode check = Algorithms.buildList(dedupVals); ListNode list = Algorithms.buildList(vals); Algorithms.dedup(list); assertTrue("1. List dedup failed", Algorithms.listEquals(list, check)); list = Algorithms.buildList(aVals); check = Algorithms.buildList(new Character[] { 'A' }); Algorithms.dedup(list); assertTrue("2. List dedup failed", Algorithms.listEquals(list, check)); } @SuppressWarnings("javadoc") @Test public void testKthElement() { Character[] vals = new Character[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; ListNode list = Algorithms.buildList(vals); Character elemVal = Algorithms.kthFromEnd(list, 2).getValue(); assertTrue("1. should have returned F, but returned " + elemVal, elemVal.compareTo('F') == 0); elemVal = Algorithms.kthFromEnd(list, 0).getValue(); assertTrue("2. should have returned H, but returned " + elemVal, elemVal.compareTo('H') == 0); elemVal = Algorithms.kthFromEnd(list, 7).getValue(); assertTrue("3. should have returned A, but returned " + elemVal, elemVal.compareTo('A') == 0); } } JavaAlgorithms/src/listAlgorithms/Algorithms.java0000644000076400007640000001051212170322107021171 0ustar iankiank/** \file * * Jun 18, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import java.util.HashSet; /** * * Algorithms * * A small collection of list algorithms * * Jun 19, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class Algorithms { private Algorithms() { } /** * Build a list from an array of values * * @param vals * an array of values * @return the list construdted from values */ public static > ListNode buildList(T[] vals) { ListNode head = null; ListNode current = null; for (T val : vals) { ListNode newNode = new ListNode(val); if (head == null) { head = newNode; current = newNode; } else { current.setNext(newNode); current = newNode; } } return head; } // buildList /** * Compare two lists * * @param listA * @param listB * @return true if the lists are equal (and have equal length), false * otherwise. */ public static > boolean listEquals(ListNode listA, ListNode listB) { boolean equal = false; if ((listA != null) && (listB != null)) { equal = true; while ((listA.getNext() != null) && (listB.getNext() != null)) { if (listA.getValue().compareTo(listB.getValue()) != 0) { equal = false; break; } listA = listA.getNext(); listB = listB.getNext(); } // while if (equal && ((listA.getNext() != null) || (listB.getNext() != null))) { equal = false; } } return equal; } /** * Reverse the element in a list * * 
     *                               A -> B -> C -> D
     *     A -> null                 B -> C -> D -> null
     *     B -> A -> null            C -> D -> null
     *     C -> B -> A -> null       D -> null
     *     D -> C-> B -> A -> null
     *
* * The input list is reversed, so its original structure is destroyed * * @param head * the start of a list * @return the head of the reversed list */ public static > ListNode reverse(ListNode head) { ListNode newRoot = null; if (head != null) { ListNode current = head; ListNode t = null; while (current != null) { t = current.getNext(); current.setNext(newRoot); newRoot = current; current = t; } } return newRoot; } // reverse /** * Remove duplicate elements from a list. The input list is modified. * * @param head */ public static > void dedup(ListNode head) { if (head != null) { HashSet hash = new HashSet(); ListNode trail = head; while (head != null) { T val = head.getValue(); if (!hash.add(val)) { // add() returns true if the value was not // in the hash set trail.setNext(head.getNext()); } else { trail = head; } head = head.getNext(); } } } // dedup /** * Return the kth element from the end of the list * * @param head * the start of the list * @param k * the value of k * @return the kth node from the end of the list, or if the list length is * less than k, null */ public static > ListNode kthFromEnd(ListNode head, int k) { ListNode kthNode = head; int cnt = 0; while (head.getNext() != null) { if (cnt >= k) { kthNode = kthNode.getNext(); } cnt++; head = head.getNext(); } if (cnt < k) { kthNode = null; } return kthNode; } } JavaAlgorithms/src/listAlgorithms/ListNode.java0000644000076400007640000000270512170321610020604 0ustar iankiank/** \file * * Jun 18, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package listAlgorithms; import java.util.Iterator; /** * ListNode Jun 19, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param * a type that implements Comparable */ public class ListNode> implements Iterable> { private T mValue; private ListNode mNext; @SuppressWarnings("javadoc") public ListNode(T value) { this.mValue = value; this.mNext = null; } @SuppressWarnings("javadoc") public T getValue() { return mValue; } @SuppressWarnings("javadoc") public void setValue(T value) { this.mValue = value; } @SuppressWarnings("javadoc") public ListNode getNext() { return mNext; } @SuppressWarnings("javadoc") public void setNext(ListNode next) { this.mNext = next; } @SuppressWarnings("javadoc") public void printList() { String s = this.getValue().toString(); System.out.print("[" + s + "]"); if (this.getNext() != null) { System.out.print("->"); this.getNext().printList(); } else { System.out.println(); } } @Override public Iterator> iterator() { Iterator> iter = new ListNodeIterator(this); return iter; } } JavaAlgorithms/src/stringAlgorithms/0000755000076400007640000000000012221466456016566 5ustar iankiankJavaAlgorithms/src/stringAlgorithms/SentenceRecognize.java0000644000076400007640000000626212227404235023042 0ustar iankiank/** \file * * Sep 27, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package stringAlgorithms; /** *

* SentenceRecognize *

*

* This little algorithm is yet another white board interview problem that I ran into at * a company named MapR. I can't think of any application for this algorithm. Hopefully * it will help you, dear reader. *

*

* The MapR recruiter contacted me and got me to interview with MapR. As is the case with * so many companies these days, after I took the time to interview with MapR * I never heard from them (or the recruiter) again. *

*

* Sep 28, 2013 *

* * @author Ian Kaplan, iank@bearcave.com */ @SuppressWarnings("javadoc") public class SentenceRecognize { // Note that not all words in the dictionary are properly spelled english words protected final static String dictionary[] = {"a", "an", "at", "attach", "attached", "he", "apple", "are", "area", "arean", "areana", "arm", "charm", "lever", "clever", "drop", "droped", "dope", "doped", "it", "the", "edith", "ball"}; public SentenceRecognize() { } /** * Search for a word in the dictionary * @param word the word being searched for * @return true if the word is found, false otherwise */ protected boolean isWord(String word) { boolean is = false; if (word != null) { for (String w : dictionary) { if (w.equals(word)) { is = true; break; } } } return is; } // isWord /** *

* Determine if a sentence, composed of a separator free set of words, is a valid * sentence (e.g., entirely composed of words from the dictionary). Some examples * are listed below (not all words are valid english words): *

* *
    *
  • * dropedapple : dropped apple *
    • *
  • * dropedith : drop edith *
    • *
  • * arearmarea : are arm area *
    • *
  • * aappledoped : a apple doped *
    • *
  • * hedropedtheball : he dropped the ball *
    • *
  • * areanaitcharm : areana it charm *
    • *
* * @param sentence the "sentence" to be tested * @return true if the separator free sentence is composed of words found in the * dictionary, false otherwise. */ public boolean isSentence(String sentence) { boolean is = false; if (sentence != null && sentence.length() > 0) { int start = 0; for (int end = 1; end <= sentence.length() && (!is); end++) { String word = sentence.substring(start, end); if (isWord(word)) { if (end == sentence.length()) { is = true; } else { is = isSentence( sentence.substring(end)); } } } } return is; } } JavaAlgorithms/src/stringAlgorithms/StringTests.java0000644000076400007640000000253212170331254021712 0ustar iankiank/** \file * * Jun 17, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package stringAlgorithms; import static org.junit.Assert.*; import org.junit.Test; public class StringTests { @Test public void testReverse() { String s1 = "abcdefgh"; String s1Rev = "hgfedcba"; String s2 = "abcdefghi"; String s2Rev = "ihgfedcba"; assertTrue("Failed to reverse " + s1, Algorithms.reverse(s1).equals(s1Rev)); assertTrue("Failed to reverse " + s2, Algorithms.reverse(s2).equals(s2Rev)); } @Test public void testisSubstring() { assertTrue("run should be a substring of running", Algorithms.isSubstring("run", "running")); assertTrue("read should be a substring of read", Algorithms.isSubstring("read", "read")); assertTrue("foo should be a substring of \"big foo deal\"", Algorithms.isSubstring("foo", "big foo deal")); assertTrue("read should be a substring of \"you can read\"", Algorithms.isSubstring("read", "you can read")); assertTrue("read should be a substring of \"she was reading\"", Algorithms.isSubstring("read", "she was reading")); assertFalse("rolling is not a substring of \"stone roll down\"", Algorithms.isSubstring("rolling", "stone roll down")); } } JavaAlgorithms/src/stringAlgorithms/Algorithms.java0000644000076400007640000000424112170331156021532 0ustar iankiank/** \file * * Jun 17, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package stringAlgorithms; /** * Algorithms * *

* Random string algorithms *

* Jun 17, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class Algorithms { private Algorithms() { } /** * Reverse the order of characters in a string. * * @param str * the input character sequence. * @return return a String object containing the characters of the input in * reverse order. */ public static String reverse(String str) { String newString = null; if (str != null) { char buf[] = str.toCharArray(); int l = 0; int r = buf.length - 1; while (l < r) { char t = buf[l]; buf[l] = buf[r]; buf[r] = t; l++; r--; } newString = new String(buf); } return newString; } // reverse /** * Return true of sub is a sub-string of str * * @param sub * the substring * @param str * the string * @return true if sub is a substring of str. If sub.equals(str) then the * function will return true */ public static boolean isSubstring(String sub, String str) { boolean match = false; if (sub != null && str != null) { int subLen = sub.length(); int strLen = str.length(); if (subLen <= strLen) { int delta = strLen - subLen; int i = 0; do { match = true; int j = i; for (int ix = 0; ix < subLen; ix++) { if (sub.charAt(ix) != str.charAt(j)) { match = false; break; } j++; } // for j i++; } while (i <= delta && (!match)); } } return match; } // isSubstring } JavaAlgorithms/src/stringAlgorithms/SentenceTest.java0000644000076400007640000000414412221477737022044 0ustar iankiank/** \file * * Sep 27, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package stringAlgorithms; import static org.junit.Assert.*; import org.junit.Test; public class SentenceTest { /** * *
    *
  • * dropedapple : dropped apple *
    • *
  • * dropedith : drop edith *
    • *
  • * arearmarea : are arm area *
    • *
  • * cleverllever : false - clever l lever *
    • *
  • * aappledoped : a apple doped *
    • *
  • * deadbeef : false - no recognized words *
    • *
  • * hedropedtheball : he dropped the ball *
    • *
  • * areanatcharm : arean at charm *
    • *
* * */ @Test public void testIsSentence() { SentenceRecognize rec = new SentenceRecognize(); if (! rec.isSentence("dropedapple") ) { // droped apple fail("Failed on dropedapple"); } if (! rec.isSentence("dropedith") ) { // drop edith fail("Failed on dropedith"); } if (rec.isSentence("dropedithh") ) { // fail - drop edith h fail("Failed on dropedithh"); } if (! rec.isSentence("arearmarea") ) { // are arm area fail("Failed on are arm area"); } if (rec.isSentence("cleverllever") ) { // clever l lever fail("Failed on cleverlever"); } if (! rec.isSentence("aappledoped")) { // a apple droped fail( "Failed on aappledoped" ); } if (rec.isSentence("deadbeef") ) { // deadbeef fail("Failed on deadbeef"); } if (! rec.isSentence("hedropedtheball") ) { // he droped the ball fail("Failed on hedropedtheball"); } if (! rec.isSentence("areanatcharm") ) { // arean at charm fail("Failed on areanatcharm"); } if (! rec.isSentence("atattachedith")) { // at attach edith fail("Failed on atattachedith"); } } } JavaAlgorithms/src/sort/0000755000076400007640000000000012162722362014210 5ustar iankiankJavaAlgorithms/src/sort/MergeSort.java0000644000076400007640000001073512170327346016772 0ustar iankiank/** \file * *

* In-memory generic merge sort. This merge sort will sort any object type that implements * the Comparable interface/class. *

* * May 30, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package sort; import java.util.ArrayList; /** *

* MergeSort *

*

* In-memory merge sort. *

*

* For N elements, the merge sort uses approximately 2N elements. The time * complexity is order N(log2(N)). *

*

* The merge sort code is implemented as a Java generic, so it can be used to * support any array that consists of objects that implement the Comparable * interface. *

*

* This merge sort algorithm is modeled after an algorithm, implemented in C, * published on Prof. Rashid Bin Muhammad on his web site: * http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm. *

* *

* May 31, 2013 *

* * @author Ian Kaplan, iank@bearcave.com * @param * A type that implements Comparable */ public class MergeSort> { /** * Merge two sorted regions. There is a left region that goes from left to * mid-1, and a right region that goes from mid to right. * * @param vals * the values array containing the sorted regions * @param temp * temporary storage, which is the same size as the vals array * @param left * the lower array index of the "left" region * @param mid * the middle, which divides the two regions to be merged * @param right * the upper array index for the "right" region. */ protected void merge(ArrayList vals, ArrayList temp, int left, int mid, int right) { // we have two halves, bounded by left, left_end, mid and right int left_end = mid - 1; int n = (right - left) + 1; int ix = left; // Do an ordered copy into the temp array while (left <= left_end && mid <= right) { if (vals.get(left).compareTo(vals.get(mid)) <= 0) { temp.set(ix, vals.get(left)); ix++; left++; } else { temp.set(ix, vals.get(mid)); ix++; mid++; } } // while // copy any remaining values that were not copied above while (left <= left_end) { temp.set(ix, vals.get(left)); ix++; left++; } while (mid <= right) { temp.set(ix, vals.get(mid)); ix++; mid++; } // copy the sorted values back into the val array from the temp array. // The only // reason the copy is being down from right down to (right - n) is that // right // the the only variable left that has the original index information // left. for (int i = 0; i < n; i++) { vals.set(right, temp.get(right)); right--; } } // merge /** * * @param vals * the values to be sorted * @param temp * temporary storage (the same size as the vals array) * @param left * the lower array index for the region to be sorted * @param right * the upper index for the region to be sorted. */ protected void m_sort(ArrayList vals, ArrayList temp, int left, int right) { if (right > left) { int mid = (right + left) / 2; // mid-point m_sort(vals, temp, left, mid); m_sort(vals, temp, mid + 1, right); merge(vals, temp, left, mid + 1, right); } } // m_sort /** *

* Use merge sort to sort an array of values. *

*

* The values are passed in the the vals array argument and the sorted * values are returned in the same array. *

* * @param vals * the values to be sorted * @param temp * temporary storage, which must be the same size as the vals * array. */ public void mergeSort(ArrayList vals) { if (vals != null && vals.size() > 1) { int len = vals.size(); ArrayList temp = new ArrayList(len); for (int i = 0; i < len; i++) { temp.add(null); } m_sort(vals, temp, 0, len - 1); } } } JavaAlgorithms/src/sort/TestMergeSortFile.java0000644000076400007640000002055712170331706020430 0ustar iankiank/** \file * * Jun 25, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package sort; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.ArrayList; import java.util.Random; import org.junit.Test; /** * TestMergeSortFile Jun 26, 2013 *

* A test for file merge sort. *

* * @author Ian Kaplan, iank@bearcave.com */ public class TestMergeSortFile { // A bad solution, since the path is system dependent. private final static String dirPath = "/home/iank/tmp"; /** * TestObj * * A test object * * @author Ian Kaplan (iank@bearcave.com) * * Created on: Jun 26, 2013 */ public static class TestObj implements Comparable, Serializable { private static final long serialVersionUID = 1; final String key; final int val; public TestObj(final String key, final int val) { this.key = key; this.val = val; } @Override public int compareTo(TestObj o) { TestObj other = (TestObj) o; int compareRslt = this.key.compareTo(other.key); return compareRslt; } } protected & Serializable> void writeObjs(T[] objs, File outFile) throws IOException { FileOutputStream fileStr = null; BufferedOutputStream bufStr = null; ObjectOutputStream objOutStr = null; try { fileStr = new FileOutputStream(outFile); bufStr = new BufferedOutputStream(fileStr); objOutStr = new ObjectOutputStream(bufStr); for (T obj : objs) { objOutStr.writeObject(obj); } objOutStr.flush(); } finally { try { if (fileStr != null) { fileStr.close(); } if (bufStr != null) { bufStr.close(); } if (objOutStr != null) { objOutStr.close(); } } catch (IOException e) { } } } protected & Serializable> boolean testFile(File sortedFile) throws IOException, ClassNotFoundException { boolean fileSorted = false; FileInputStream fileStr = null; BufferedInputStream bufStr = null; ObjectInputStream objStr = null; try { fileStr = new FileInputStream(sortedFile); bufStr = new BufferedInputStream(fileStr); objStr = new ObjectInputStream(bufStr); ArrayList objArray = new ArrayList(); while (bufStr.available() > 0) { T obj = (T) objStr.readObject(); objArray.add(obj); } int num = objArray.size(); fileSorted = true; if (num > 1) { for (int i = 0; i < num - 1; i++) { if (objArray.get(i).compareTo(objArray.get(i + 1)) > 0) { fileSorted = false; break; } } } } finally { try { if (fileStr != null) { fileStr.close(); } if (bufStr != null) { bufStr.close(); } if (objStr != null) { objStr.close(); } } catch (IOException e) { } } return fileSorted; } // testFile protected void cleanupFiles(File inFile, File outFile) { if (inFile.exists()) { inFile.delete(); } if (outFile.exists()) { outFile.delete(); } } /** * Test a simple file sort, where the buffer is an even multiple of the * number of objects in the file. * @param numVals Number of test values to sort * @param bufSize The number of objects to sort in memory * @return true if the random values in test file were sorted, false otherwise. */ public boolean testSortFile(final int numVals, final int bufSize) { final String inFileName = "randFile"; final String outFileName = "sortedFile"; final int seed = 127; boolean rslt = false; Random rand = new Random(seed); Integer[] valArray = new Integer[numVals]; for (int i = 0; i < numVals; i++) { valArray[i] = new Integer(rand.nextInt()); } File randFile = new File(dirPath, inFileName); File outFile = new File(dirPath, outFileName); try { writeObjs(valArray, randFile); MergeSortFile fileSort = new MergeSortFile(bufSize); fileSort.sortFile(randFile, outFile); rslt = this. testFile(outFile); } catch (IOException | ClassNotFoundException e) { System.err.println(e.getLocalizedMessage()); fail(e.getLocalizedMessage()); } finally { cleanupFiles(randFile, outFile); } return rslt; } /** * Make sure that the file check works correctly */ @Test public void testTheTester() { final String inFileName = "randFile"; final int seed = 127; final int numVals = 133; Random rand = new Random(seed); Integer[] valArray = new Integer[numVals]; for (int i = 0; i < numVals; i++) { valArray[i] = new Integer(rand.nextInt()); } File randFile = new File(dirPath, inFileName); try { this.writeObjs(valArray, randFile); assertFalse("The file check does not work correctly", this. testFile(randFile)); } catch (IOException | ClassNotFoundException e) { fail("testTheTester Error: " + e.getLocalizedMessage()); } finally { if (randFile.exists()) { randFile.delete(); } } } /** * Test for the case where the buffer/temporary file size is an even * multiple of the total number of Integer elements. */ @Test public void testEven() { assertTrue("Failed for the case where numVals mod bufSize == 0", testSortFile(90, 30)); } @Test public void testOdd() { assertTrue("Failed for the case where numVals mod bufSize != 0", testSortFile(111, 30)); } @Test public void testValsEqBuf() { assertTrue( "Failed for the case where the number of values is the same as the buffer", testSortFile(1000, 1000)); } /** * Test a case where a simple key/value object is sorted. The ability to * sort arbitrary comparable/serializable objects is where the merge sort * stands out. */ @Test public void testObjectSort() { final int seed = 127; final int bufSize = 1024; final int numObj = 3 * bufSize; final String inFileName = "randFile"; final String outFileName = "sortedFile"; TestObj[] objVec = new TestObj[numObj]; Random rand = new Random(seed); for (int i = 0; i < numObj; i++) { int randVal = rand.nextInt(); String key = Integer.toString(randVal); objVec[i] = new TestObj(key, randVal); } File randFile = new File(dirPath, inFileName); File outFile = new File(dirPath, outFileName); try { writeObjs(objVec, randFile); MergeSortFile fileSort = new MergeSortFile( bufSize); fileSort.sortFile(randFile, outFile); boolean rslt = this. testFile(outFile); assertTrue("Object test failed", rslt); } catch (IOException | ClassNotFoundException e) { System.err.println(e.getLocalizedMessage()); fail(e.getLocalizedMessage()); } finally { cleanupFiles(randFile, outFile); } } } JavaAlgorithms/src/sort/MergeSortTest.java0000644000076400007640000000560012170330236017615 0ustar iankiank/** \file * * May 31, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package sort; import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Random; import org.junit.Test; /** * MergeSortTest * *

* A test for in-memory merge sort. *

* * Jul 13, 2013 * * @author Ian Kaplan, iank@bearcave.com */ public class MergeSortTest { final static int seedVal = 127; private Random rand = null; private MergeSort mSort = null; public MergeSortTest() { rand = new Random(seedVal); mSort = new MergeSort(); } private void initArray(ArrayList a, final int N) { final int randRange = N * 2; for (int i = 0; i < N; i++) { a.add(rand.nextInt(randRange)); } } private > boolean isSortedArray(ArrayList a) { boolean isSorted = true; for (int i = 0; i < a.size() - 1; i++) { // a[i] should be <= a[i+1] of if a[i] is > a[i+1] then the sort // failed if (a.get(i).compareTo(a.get(i + 1)) > 0) { isSorted = false; break; } } return isSorted; } private boolean testSort(int N) { boolean passed = true; if (N > 0) { ArrayList vals = new ArrayList(); initArray(vals, N); mSort.mergeSort(vals); passed = isSortedArray(vals); } else { mSort.mergeSort(null); } return passed; } @Test public void testNullArray() { assertTrue("MergeSort test failed for null array", testSort(0)); } @Test public void testEvenElement() { // test sorting an even number of values assertTrue("MergeSort test failed for even numbers of values", testSort(64)); } @Test public void testOddElement() { assertTrue("MergeSort test failed for odd numbers of values", testSort(127)); } @Test public void testOneElement() { // test for 1 value assertTrue("MergeSort test failed for 1 value", testSort(1)); } @Test public void testTwoElements() { // test for 2 value assertTrue("MergeSort test failed for 2 values", testSort(2)); } @Test public void testStringSort() { ArrayList words = new ArrayList(Arrays.asList("T'was", "brillig", "and", "Slithey", "Toves", "all", "mimsy", "were", "the", "borogroves", "and", "moonraths", "outgrabe")); MergeSort strSort = new MergeSort(); strSort.mergeSort(words); boolean sorted = isSortedArray(words); assertTrue("MergeSort test failed for String sort", sorted); } } JavaAlgorithms/src/sort/MergeSortFile.java0000644000076400007640000003250312170330143017554 0ustar iankiank/** \file * * Jun 24, 2013 * * Copyright Ian Kaplan 2013 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package sort; import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.ArrayList; /** * MergeSortFile * *

* File based merge sort, implemented as a generic class that can sort objects that * extend Comparable and implement the Serializable interface. *

* * Jun 25, 2013 * * @author Ian Kaplan, iank@bearcave.com * @param */ public class MergeSortFile & Serializable> { private static String TEMP_ROOT_NAME = "tempFile"; private final int mNumObjects; private MergeSort mSort = new MergeSort(); private int mFileCnt = 0; /** * FileObjContainer *

* A container for the file InputStream objects. The InputStream objects are * allocated by the class constructor and released by the close() method. *

* * @author Ian Kaplan (iank@bearcave.com) * * Created on: Jun 25, 2013 */ protected class FileObjContainer { FileInputStream inStr = null; BufferedInputStream bufStr = null; ObjectInputStream objStr = null; boolean EOF = false; public FileObjContainer(File inFile) throws IOException { inStr = new FileInputStream(inFile); bufStr = new BufferedInputStream(inStr); objStr = new ObjectInputStream(bufStr); } public T readObj() throws IOException, ClassNotFoundException { T newObj = null; if ((!EOF) && bufStr.available() > 0) { newObj = (T) objStr.readObject(); } else { EOF = true; } return newObj; } public void close() throws Throwable { super.finalize(); try { if (inStr != null) { inStr.close(); } if (bufStr != null) { bufStr.close(); } if (objStr != null) { bufStr.close(); } } catch (IOException e) { } } // finalize } // ================< class FileObjContainer >====================== /** * A class to manage reading the values from the sorted files, in increasing * order. That is, read values from the files and always return the least * value. This object hides of complexity involved with making sure that * values are read from the files in increasing order. * * ReadFileValues Jun 25, 2013 * * @author Ian Kaplan, iank@bearcave.com */ protected class ReadFileValues { private ArrayList mObjFiles; private ArrayList mValues; public ReadFileValues(ArrayList objFiles) throws ClassNotFoundException, IOException { this.mObjFiles = objFiles; mValues = new ArrayList(); // initialize the mValues ArrayList with the first value from each // file for (FileObjContainer objFile : objFiles) { T obj = objFile.readObj(); mValues.add(obj); } } /** * Find the minimum value in the input ArrayList argument values. Some * of the elements in this array may be null (this occurs when the end * of one of the files that feeds values into this array is reached). * * @param values * @return the index of the minimum value or -1 if there is no minimum * value (e.g., all array elements are null). */ protected int minIx(ArrayList values) { int ix = -1; T minVal = null; for (int i = 0; i < values.size(); i++) { T tstVal = values.get(i); if (tstVal != null) { if (minVal == null) { minVal = tstVal; ix = i; } else if (minVal.compareTo((T) tstVal) > 0) { minVal = tstVal; ix = i; } } } return ix; } // minIx public T getLeastVal() throws ClassNotFoundException, IOException { T leastVal = null; int ix = minIx(mValues); if (ix >= 0) { leastVal = mValues.get(ix); // read a new value to replace the one that will be returned T newValue = mObjFiles.get(ix).readObj(); mValues.set(ix, newValue); } return leastVal; } } // ================< class ReadFileValues >========================== /** * @param numObjs * the number of objects to read into memory for sorting and, * correspondingly, the maximum number of objects written to the * temporary files. Since this code uses merge sort, twice this * amount of memory will be needed (since merge sort uses a * temporary array). */ public MergeSortFile(int numObjs) { this.mNumObjects = numObjs; } /** * Return a new temporary file name * * @return */ protected String nextTempFileName() { mFileCnt++; String tempFileName = String.format("%s%02d", TEMP_ROOT_NAME, mFileCnt); return tempFileName; } /** * Write am array of sorted objects to a File and return the associated * File. * * @param objList * An array of sorted objects * @param parentDir * the parent directory (where the temporary files will be * allocated). * @return the temporary File object for the file containing the sorted * objects * @throws IOException */ protected File writeSortedBlock(ArrayList objList, File parentDir) throws IOException { String tempFileName = nextTempFileName(); // create a temporary file in the parent directory File tempFile = new File(parentDir, tempFileName); FileOutputStream fileStr = null; BufferedOutputStream bufStr = null; ObjectOutputStream objOutStr = null; try { fileStr = new FileOutputStream(tempFile); bufStr = new BufferedOutputStream(fileStr); objOutStr = new ObjectOutputStream(bufStr); for (T obj : objList) { objOutStr.writeObject(obj); } objOutStr.flush(); } finally { try { if (fileStr != null) { fileStr.close(); } if (bufStr != null) { bufStr.close(); } if (objOutStr != null) { objOutStr.close(); } } catch (IOException e) { } } return tempFile; } // writeSortedBlock /** *

* Read a block of mNumObject unsorted objects, sort them and write them to * a file. Note that this requires at least 3x the memory for mNumObjects * due to the in-memory merge sort and the ArrayList in this function. *

*

* Both a BufferedInputStream and an ObjectInputStream are passed to this * method. The only way to tell if an ObjectInputStream has reached the end * of file is via an exception, which violates the idea that exceptions are * for exceptional circumstance (reaching the end of file is expected, not * exceptional). So the BufferedInputStream is also passed in so that the * end of stream can be recognized. * * @param bufStr * a buffered input stream for the file containing the unsorted * objects * @param objStr * an object input stream * @param parentDir * the parent directory (e.g., the directory that will contain * the temporary files) * @return the temporary file containing the sorted objects * @throws IOException * @throws ClassNotFoundException */ protected File readAndSortBlock(BufferedInputStream bufStr, ObjectInputStream objStr, File parentDir) throws IOException, ClassNotFoundException { File tempFile = null; ArrayList objList = new ArrayList(); int objCnt = 0; while (objCnt < mNumObjects && (bufStr.available() > 0)) { T obj = (T) objStr.readObject(); objList.add(obj); objCnt++; } if (objList.size() > 0) { mSort.mergeSort(objList); tempFile = writeSortedBlock(objList, parentDir); } return tempFile; } // readAndSortBlock /** * Merge the values in the sorted files into a single file. * * @param fileList * one or more files of sorted objects * @param outFile * the file for the complete sorted data * @throws IOException * @throws ClassNotFoundException */ protected void mergeFiles(ArrayList fileList, File outFile) throws IOException, ClassNotFoundException { if (fileList.size() > 0) { if (fileList.size() == 1) { File tempFile = fileList.get(0); tempFile.renameTo(outFile); } else { ArrayList fileObjs = new ArrayList(); for (int i = 0; i < fileList.size(); i++) { File file = fileList.get(i); fileObjs.add(new FileObjContainer(file)); } // for ReadFileValues fileReader = new ReadFileValues(fileObjs); FileOutputStream fileStr = null; BufferedOutputStream bufStr = null; ObjectOutputStream objOutStr = null; try { fileStr = new FileOutputStream(outFile); bufStr = new BufferedOutputStream(fileStr); objOutStr = new ObjectOutputStream(bufStr); T obj = null; while ((obj = fileReader.getLeastVal()) != null) { objOutStr.writeObject(obj); } objOutStr.flush(); } finally { try { for (FileObjContainer fileObj : fileObjs) { fileObj.close(); } } catch (Throwable t) { } try { if (fileStr != null) { fileStr.close(); } if (bufStr != null) { bufStr.close(); } if (objOutStr != null) { objOutStr.close(); } } catch (IOException e) { } } // finally } // else } // if } // mergeFiles /** * Read objects from an input file and sort them into a set of temporary * files (these temporary files will be merged into the final sorted file). * * @param inFile * a file containing unsorted objects * @return A files of file objects for the temporary files. * @throws IOException * @throws ClassNotFoundException */ protected ArrayList buildSortedFileList(File inFile) throws IOException, ClassNotFoundException { ArrayList fileList = new ArrayList(); FileInputStream fileStr = null; BufferedInputStream bufStr = null; ObjectInputStream objStr = null; try { fileStr = new FileInputStream(inFile); File parentDir = inFile.getParentFile(); bufStr = new BufferedInputStream(fileStr); objStr = new ObjectInputStream(bufStr); File tempFile = null; while ((tempFile = readAndSortBlock(bufStr, objStr, parentDir)) != null) { fileList.add(tempFile); } } finally { try { if (fileStr != null) { fileStr.close(); } if (bufStr != null) { bufStr.close(); } if (objStr != null) { objStr.close(); } } catch (IOException e) { } } return fileList; } // buildSortedFileList /** * Use merge sort to sort the values in inFile into outFile. The input file * and the output file may be the same file. * * @param inFile * @param outFile * @throws ClassNotFoundException * @throws IOException */ public void sortFile(File inFile, File outFile) throws ClassNotFoundException, IOException { ArrayList fileList = buildSortedFileList(inFile); mergeFiles(fileList, outFile); for (File file : fileList) { file.delete(); // delete the temporary files } } } JavaAlgorithms/.classpath0000644000076400007640000000045712160235225014416 0ustar iankiank JavaAlgorithms/.project0000644000076400007640000000056512160235115014100 0ustar iankiank JavaAlgorithms org.eclipse.jdt.core.javabuilder org.eclipse.jdt.core.javanature JavaAlgorithms/bin/0000755000076400007640000000000012227374554013212 5ustar iankiankJavaAlgorithms/bin/treeAlgorithms/0000755000076400007640000000000012227405436016175 5ustar iankiankJavaAlgorithms/bin/listAlgorithms/0000755000076400007640000000000012227405436016211 5ustar iankiankJavaAlgorithms/bin/stringAlgorithms/0000755000076400007640000000000012227405436016544 5ustar iankiankJavaAlgorithms/bin/sort/0000755000076400007640000000000012227405436014173 5ustar iankiank