Debugging the Galaxy Tab 10.1

When I first plug the tab in, my computer automatically install all the drivers, but it won’t show up in ADB and Eclipse. I did a little searching but people were pointing me to Samsung’s developer page with a USB driver for phones. Sadly that driver just isn’t for the tab, a search on their site found nothing interesting either. It looks like Samsung can’t keep information for developers updated while they are still battling legal issues around the tab.

Fortunately, I remembered I haven’t turned debugging mode on the tab on, so I went ahead and do it, this time… Success!

Where to turn on debugging

Device in Eclipse

Now I’m installing Android 3.1 platform and looking forward for a happy time debugging ­čÖé

Debug on Android device

I once thought I just have to plug the device in, install all the driver and when it appeared in ADT’s device window I can just start debugging; but sadly this is not the case. Here’s a very informative guide on how to do so by Google.

Because I was too lazy to read that, I can start the program but it will not hit any breakpoint I set. I missed the first point in the guide above: I have to set debug=”true” in the application’s manifest!

<application android:icon="@drawable/icon" android:label="@string/app_name" android:debuggable="true">

Expression parsing

It’s a classic problem and there are many ways to do it. The problem is, it is quite difficult for us laymen who doesn’t think like state machines. The problem lies in our education itself. We wasn’t taught the most effective notation system, and nobody wanted to fix it. Our current notation system was originally intended for simple calculation: two operand with a operator in between, that’s it! Merchants can purchase, early banks can operate, heads can be counted…

It’s not until mathematics have developed into a science beyond (most human’s) comprehension that someone realized there’s a more efficient way to write 3 * 4 + 2 * (4 + 1) ^ (3 / 2) without remembering operator precedence and remove the need of cumbersome parentheses.

Well, we’ve got to live with it and luckily, we have┬áversatile┬ácomputing devices that can make us coffee, the only problem left is to make them understand the mess we created…

Before we dig in…

We need something capable of splitting the expression into chewable parts, namely operators, operands and sign. It will iteratively navigate through the expression, returning one element at a time. Separating this from the rest of the parsing will make you a lot more healthy!

ExpressionTokenizer.java

public class ExpressionTokenizer
{

   public ExpressionTokenizer(String anInput)
   {
      input = anInput.toLowerCase();
      start = 0;
      end = 0;
      nextToken();
   }

   public boolean hasMoreToken() {
       return !(start >= input.length());
   }

   public String peekToken()
   {
      if (start >= input.length()) return null;
      else return input.substring(start, end).trim();
   }

   public String nextToken()
   {
      String r = peekToken();
      start = end;
      if (start >= input.length()) return r;
      if (Character.isDigit(input.charAt(start)) || input.charAt(start) == '.')
      {
         end = start + 1;
         while (end < input.length()
               && (Character.isDigit(input.charAt(end)) || input.charAt(start) == '.'))
            end++;
      }
      else if(input.substring(start).startsWith("cos")) {
          end = start + 3;
      } else if(input.substring(start).startsWith("sin")) {
          end = start + 3;
      } else if(input.substring(start).startsWith("sqrt")) {
          end = start + 4;
      } else
         end = start + 1;
      return r.trim();
   }

   private String input;
   private int start;
   private int end;
}
  • Constructor: give it the expression
  • peekToken: previews the next token
  • nextToken: returns the next token and move the cursor to the next one
  • hasNextToken: true if there are still more unprocessed tokens in the string

In short, it works like an iterator.

Method 1: Recursive parsing

This method, as the name implies, uses the power of recursion. The parsers is divided into several function to process different levels of operator precedence, for example:

Call stack

Each function does the following:

  • Call the higher level function to calculate the expression, this will ensure that operators with higher precedence get processed first, with the exception of the final function, which parses number
  • Check if the operator is at the function’s level, if it is, calculate the operator by getting the next value (by calling the higher function) and add it to the value returned form the first call, loop until the next operator does not belong to the function;┬áotherwise ignore the operator and return calculation result (returned from the first call)

In my implementation, the least important function is named getExpressionValue() (for + and -), and consecutive ones are getTermValue() (for * and -), getHigherTermValue() (for ^), getFactorValue() (for cos, sin, parentheses and numbers)

Evaluator.java

public class Evaluator {

    public Evaluator(String anExpression) {
        tokenizer = new ExpressionTokenizer(anExpression);
    }

    public double getExpressionValue() {
        double value = getTermValue();
        boolean done = false;
        while (!done) {
            String next = tokenizer.peekToken();
            if ("+".equals(next) || "-".equals(next)) {
                tokenizer.nextToken();
                double value2 = getTermValue();
                if ("+".equals(next)) {
                    value = value + value2;
                } else {
                    value = value - value2;
                }
            } else {
                done = true;
            }
        }
        return value;
    }

    public double getTermValue() {
        double value = getHigherTermValue();
        boolean done = false;
        while (!done) {
            String next = tokenizer.peekToken();
            if ("*".equals(next) || "/".equals(next)) {
                tokenizer.nextToken();
                double value2 = getHigherTermValue();
                if ("*".equals(next)) {
                    value = value * value2;
                } else {
                    value = value / value2;
                }
            } else {
                done = true;
            }
        }
        return value;
    }

    public double getHigherTermValue() {
        double value = getFactorValue();
        boolean done = false;
        while (!done) {
            String next = tokenizer.peekToken();
            if ("^".equals(next)) {
                tokenizer.nextToken();
                double value2 = getFactorValue();
                if ("^".equals(next)) {
                    value = Math.pow(value, value2);
                }
            } else {
                done = true;
            }
        }
        return value;
    }

    public double getFactorValue() {
        double value;
        String next = tokenizer.peekToken();
        if ("cos".equals(next)) {
            tokenizer.nextToken();
            tokenizer.nextToken();
            value = Math.cos(getExpressionValue());
            tokenizer.nextToken();
        } else if ("sin".equals(next)) {
            tokenizer.nextToken();
            tokenizer.nextToken();
            value = Math.sin(getExpressionValue());
            tokenizer.nextToken();
        } else if ("sqrt".equals(next)) {
            tokenizer.nextToken();
            tokenizer.nextToken();
            value = Math.sqrt(getExpressionValue());
            tokenizer.nextToken();
        } else if ("(".equals(next)) {
            tokenizer.nextToken();
            value = getExpressionValue();
            tokenizer.nextToken();
        } else {
            value = Double.parseDouble(tokenizer.nextToken());
        }
        return value;
    }
    private ExpressionTokenizer tokenizer;
}

Finally, the test:

EvaluatorTester.java

import java.util.Scanner;

public class EvaluatorTester {

    public static void main(String[] args) {
        Evaluator e;
        double value;
        String input;

        input = "3+sqrt(9)*2^3";
        e = new Evaluator(input);
        value = e.getExpressionValue();
        System.out.println(input + "=" + value);

        input = "cos(3)-sqrt(9)*2^sin(4)+100";
        e = new Evaluator(input);
        value = e.getExpressionValue();
        System.out.println(input + "=" + value);

        Scanner in = new Scanner(System.in);
        System.out.print("Enter an expression: ");
        input = in.nextLine();
        if (input.length() > 0) {
            e = new Evaluator(input);
            value = e.getExpressionValue();
            System.out.println(input + "=" + value);
        }
    }
}

Result

Method 1 result

Method 2: Building a stack

You might have noticed that all these functions looked a lot alike, is there any way to simplify it? Well, when we used recursion, the runtime environment created us a stack, this stack keep track of which function should return value to which function. Recursion incurs a lot of overhead because of all the initialization, so if we change the purpose of the stack to store only operators, instead of calling a higher function, we store the operator in the stack, waiting until we meet a lower precedence operator.

We don’t have to use recursion, and it is faster, though you won’t notice the difference if the expression is short enough.

Evaluator.java

import java.util.Stack;

public class Evaluator {

    /*
     * Initializes the parser with an expression
     */
    public Evaluator(String anExpression) {
        tokenizer = new ExpressionTokenizer(anExpression);
    }

    /**
     * Calculates the operator's precedence for stack pushing, taking into account the current
     * parenthesis level of the operator
     * @param token
     * @param parenthesisLevel
     * @return an integer, more important operators are guaranteed to return a higher value
     */
    int getTokenPrecedence(String token, int parenthesisLevel) {
        final String operators[][] = {{"+", "-"}, {"*", "/"}, {"^"}, {"cos", "sin", "sqrt"}, {"(", ")"}};
        if (token == null) {
            return -1;
        }
        for (int i = 0; i < operators.length; i++) {
            for (int j = 0; j < operators[i].length; j++) {
                if (token.equals(operators[i][j])) {
                    return i + parenthesisLevel * operators.length;
                }
            }
        }
        return -1;
    }

    /**
     * Test if a token is number
     * @param test number to test
     * @return true if it is a valid number, false otherwise
     */
    public boolean isNumber(String test) {
        try {
            Double.parseDouble(test);
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    /**
     * Evaluates the expression
     * @return expression value
     */
    public double getExpressionValue() {
        Stack numbers = new Stack();
        Stack operators = new Stack();
        // Store operator's precedence, used to handle parentheses
        Stack operatorsPrecedence = new Stack();
        int level = 0;
        while(true) {
            String next = tokenizer.nextToken();
            if (next != null) {
                if (isNumber(next)) {
                    numbers.push(Double.parseDouble(next));
                    continue;
                }
				// Parentheses are a special case, it makes all operators inside it more important than
				// anything outside, we won't store them in the stack because it will become very complicated,
				// so we only store the operator's precedence (affected by parenthesis level)
                if (next.equals("(")) {
                    level++;
                    continue;
                } else if (next.equals(")")) {
                    level--;
                    continue;
                }
            }
			// While we still have operators in the stack and the one in the stack is more important than the next one...
            while (!operators.empty() && getTokenPrecedence(next, level) <= operatorsPrecedence.peek()) {
				// We get the operator and its priority
                String operator = operators.pop();
                int p = operatorsPrecedence.pop();
				// One parameter operations. Why 5? because there are 5 level of operator
				// precedence in operators[][] in getTokenPrecedence. The fourth operations
				// have only one operand
                if (p % 5 == 3) {
                    Double value = numbers.pop();

                    if (operator.equals("cos")) {
                        numbers.push(Math.cos(value));
                    } else if (operator.equals("sin")) {
                        numbers.push(Math.sin(value));
                    } else if (operator.equals("sqrt")) {
                        numbers.push(Math.sqrt(value));
                    }
                } else {

					// We have only one number left
                    if (numbers.size() < 2) {
                        return numbers.pop();
                    }

					// Because stack is LIFO, the first number is the second operand
                    Double value2 = numbers.pop();
                    Double value1 = numbers.pop();

                    if (operator.equals("+")) {
                        numbers.push(value1 + value2);
                    } else if (operator.equals("-")) {
                        numbers.push(value1 - value2);
                    } else if (operator.equals("*")) {
                        numbers.push(value1 * value2);
                    } else if (operator.equals("/")) {
                        numbers.push(value1 / value2);
                    } else if (operator.equals("^")) {
                        numbers.push(Math.pow(value1, value2));
                    }
                }
            }
			// The operator in the stack is now less important, put the next one into the stack
            operators.push(next);
            operatorsPrecedence.push(getTokenPrecedence(next, level));
        }
    }

    private ExpressionTokenizer tokenizer;
}

Result

Result of method 2

Method 3: Build an expression tree

This is useful if you want the user to be able to edit the expression or process a certain part of it, the previous expression will look like this

Expression tree

You still iterate though the expression. When you encounter a number, you create a number node and attach it to the current operator, if you encounter a same level operator, push it to the right of the current operator, if the operator is more important, push it down to the right too, if it is less important, put it as the parent of current operator. Some operator like sin and cos will have only one child, and it will be on the right side.

We need some sort of data structure to store the node, I call it arithmetic node. It stores a token and whether that token is a number or an operator and its precedence if it’s an operator.

ArithmeticNode.java

/**
 * Nodes of a binary tree, with backtrack capabilities
 * Arithmetic node contains either operator (+-/*) or operands (numbers)
 */
public class ArithmeticNode {

    public ArithmeticNode(String _data, int _type, int _level) {
        data = _data;
        type = _type;
        level = _level;
    }

    /**
     * Inserts a new node as a descendant of this node.
     * @param onLeft false to insert to the right, else to the left
     * @param newNode node to insert
     */
    public void addChildNode(boolean onLeft, ArithmeticNode newNode) {
        if (onLeft) {
            left = newNode;
            left.parent = this;
        } else {
            right = newNode;
            right.parent = this;
        }
    }

    /**
    Prints this node and all of its descendants
    in sorted order.
     */
    public String printNodes() {
        String result = "";
        if (left != null) {
            result += left.printNodes();
        }
        result += (data);
        if (right != null) {
            result += right.printNodes();
        }
        return result;
    }

    /**
     * Calculates the result of this node and all child nodes
     * @return
     * @throws Exception if there are any error like wrong number format or
     * somehow the tree is wrongly structured
     */
    public Double calculate() throws Exception {
        if (this.type == OPERAND) {
            return Double.parseDouble(this.data);
        } else {
            if (this.left != null && this.right != null) {
                String operator = this.data;
                double value1 = 0, value2 = 0;
                if (this.left.type == OPERATOR)
                    value1 = this.left.calculate();
                else
                    value1 = Double.parseDouble(this.left.data.toString());
                if (this.right.type == OPERATOR)
                    value2 = this.right.calculate();
                else
                    value2 = Double.parseDouble(this.right.data.toString());
                if (operator.equals("+")) {
                    return (value1 + value2);
                } else if (operator.equals("-")) {
                    return (value1 - value2);
                } else if (operator.equals("*")) {
                    return (value1 * value2);
                } else if (operator.equals("/")) {
                    return (value1 / value2);
                } else if (operator.equals("^")) {
                    return (Math.pow(value1, value2));
                }

            }
            throw new Exception("Expression tree is malformed!");
        }
    }

    /**
     * Calculates the operator's precedence, taking into account the current
     * parenthesis level of the operator
     * @param token
     * @param parenthesisLevel
     * @return an integer, more important operators are guaranteed to return a higher value
     */
    public int getNodePrecedence() {
        final String operators[][] = {{"+", "-"}, {"*", "/"}, {"^"}};
        if (this.type != OPERATOR) {
            return -1;
        }
        String token = data.toString();
        for (int i = 0; i < operators.length; i++) {
            for (int j = 0; j < operators[i].length; j++) {
                if (token.equals(operators[i][j])) {
                    return i + level * operators.length;
                }
            }
        }
        return -1;
    }

    /**
     * Main data of this node, can be a string for operator or a double for
     * operand
     */
    public String data;
    /**
     * either OPERATOR or OPERAND, describe the node
     */
    public int type;
    /**
     * Parentheses level of this node, used for precedence evaluation
     */
    public int level;
    public ArithmeticNode left;
    public ArithmeticNode right;
    public ArithmeticNode parent;
    public static final int OPERATOR = 0;
    public static final int OPERAND = 1;
}

When the tree is built, to get the expression value, you simply call the calculate() function on the root node. The calculate() function uses in-order traversal to loop trough all nodes and return their value if it’s a number, combine and calculate if it’s an operator node.

Evaluator.java

public class Evaluator {

    /*
     * Initializes the parser
     */
    public Evaluator(String anExpression) {
        tokenizer = new ExpressionTokenizer(anExpression);
    }

    /**
     * Test if a token is number
     * @param test
     * @return
     */
    public boolean isNumber(String test) {
        try {
            Double.parseDouble(test);
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    /**
     * Evaluates the expression, this method builds a binary tree with nodes
     * representing tokens in the expression
     * @return result of the expression
     */
    public double getExpressionValue() {
        ArithmeticNode lastOperand = null, lastOperator = null, root = null;
        int level = 0;
        boolean nextIsLeft = true;
        while (tokenizer.hasMoreToken()) {
            String token = tokenizer.nextToken();
            if (token.equals("(")) {
                level++;
                continue;
            } else if (token.equals(")")) {
                level--;
                continue;
            }
            ArithmeticNode aNode;
            if (isNumber(token)) {
                aNode = new ArithmeticNode(token, ArithmeticNode.OPERAND, level);

                if (lastOperator != null && !nextIsLeft) {
                    lastOperator.addChildNode(nextIsLeft, aNode);
                }
                lastOperand = aNode;
                nextIsLeft = !nextIsLeft;
            } else {
                aNode = new ArithmeticNode(token, ArithmeticNode.OPERATOR, level);
                if (root == null) {
                    aNode.addChildNode(true, lastOperand);
                    root = aNode;
                } else if (aNode.getNodePrecedence() < lastOperator.getNodePrecedence()) {
                    ArithmeticNode nextParent = lastOperator;
                    // Backtrack until there is a compatible node (a node that
                    // have precedence smaller than the current, or root
                    while (nextParent.parent != null && aNode.getNodePrecedence()
                            < nextParent.getNodePrecedence())
                        nextParent = nextParent.parent;
                    aNode.addChildNode(true, nextParent);
                    root = aNode;
                } else {
                    // Swap the new node with the previous operand
                    aNode.addChildNode(true, lastOperator.right);
                    lastOperator.addChildNode(false, aNode);
                }
                lastOperator = aNode;
                // We always need a number or something after a operator
                nextIsLeft = false;
            }

        }
        double result = 0;
        try {
            result = root.calculate();
        } catch (Exception e) {
            System.out.println("Some error happened: " + e.getMessage());
        }
        return result;
    }    

    private ExpressionTokenizer tokenizer;
}

With this tree, you can re-export the expression in Polish notation easily

Things to note when developing on Android

Putting files onto the emulator

There are two: using adb (see below) and through file explorer (in ADT)

File explorer

Oh, and one file at a time only

Update music

Maybe on real phones, there’s supposed to be an Intent to process your music files when they are copied over to the device. The emulator doesn’t do this, so any music you threw in using the file explorer won’t show up in your “Music” or “Media” application (depends on the version).

You have to start developer tools > Media scanner to scan for music files

Media scanner

Controlling the emulator

There’s more to the emulator than what your can control with ADT. ADT is quite nice to use, but it only let you:

  • Simulate incoming SMS and call
  • Simulate geolocation
  • View / terminate processes
  • Manage files

Actually you can use several tools that come with the SDK and talk to the emulator itself to get more out of it. To connect to the emulator, telnet to local host with the port as the emulator’s number (5554, 5556 and so on). These numbers can be used as phone numbers so the emulators can call / SMS each other, but not receive calls from a connected phone.

The list of commands can be found here

Setting the battery to full

There’s a tool called ADB (android debug bridge) that can install packages and put files on to the sdcard. ADB is used internally by ADT itself, but you can use it to manually control the emulator, doing things like setting the telnet listening port, view system log (logcat) or issuing shell commands on the device (alternatively you can do this with Dev tools inside the phone)

Solving errors that appear to came out of nowhere

In addition to usual Java errors like forgetting to add imports, put some files in the wrong folder… Sometimes when you import a project from somewhere (like… from Google’s examples :p), the project turns all red (indicating error), you checked the import, they are there, you checked the classes, they are there, you cleaned the project and rebuild as a routine habit when things go wrong with Android, the errors are still there!

Check your project’s properties (default.properties) to see if the target is right. For example, if you are using 2.2 platform, it should be target=android-8 for 2.1 it should be android-7 and so on… assumed you installed the platform with the AVD manager.

Also, when you change API level requirement in AndroidManifest.xml, the project doesn’t seem to build right and it just can’t run, saying something like “Android requires .class compatibility set to 5.0. Please┬áfix project properties”

You know you need to use this

ADT's magic wand

Java snippets of the day

Palindrome test

import java.util.Scanner;

public class PalindromeTest {
    static boolean isPalindrome(String source) {
		// Trivial case
        if (source == null)
            return false;
		// We ignore case when checking for palidrome
        String toTest = source.toLowerCase();
		// We start at the two ends of the string
        int start = 0;
        int end = toTest.length() - 1;
		// When the ends doesn't meet
        while (start < end) {
			// If they are not characters (like punctuation and spaces, we ignore them by
			// moving the pointer to the next character
            while (!Character.isLetter(toTest.charAt(start)))
                start++;
			// Similiar for the end pointer
            while (!Character.isLetter(toTest.charAt(end)))
                end--;

			// Compares the end and start pointer
            if (toTest.charAt(start) != toTest.charAt(end))
                return false;

			// Match, move to the next position
            start++;
            end--;
        }
		// The whole string has been testetd, so it's a palidrome
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("Dammit I'm mad"));
        System.out.println(isPalindrome("Was it a car or a cat I saw"));
        System.out.println(isPalindrome("A man, a plan, a canal - Panama!"));
        System.out.println(isPalindrome("Are we not drawn onward, we few, drawn onward to new era?"));
        System.out.println(isPalindrome("Go hang a salami; I'm a lasagna hog!"));
        System.out.println(isPalindrome("aaaaaaaaaaao"));
    }
}

String permutation

	import java.util.ArrayList;

	public class PermutationPrinter {

		// Returns the list of possible permutations
		static ArrayList getPermutations(String target) {
			ArrayList result = new ArrayList();
			if (target.length() == 1) {
				// There's only one permutation for "a", right?
				result.add(target);
			} else {
				// There's target.length() way to select a character from a string, so...
				for (int i = 0; i < target.length(); i++) {
					// We iteratively pick characters
					char theChar = target.charAt(i);
					// Take them out of the question, then find the rest 's permutation, the string is
					// smaller by one character, and it will keep getting smaller until there's only 1
					// character left
					ArrayList smaller = getPermutations(target.substring(0, i) + target.substring(i + 1));
					// For each permutation string of the smaller string, add the original character into it
					for (String s: smaller) {
						 result.add(theChar + s);
					}
				}
			}
			// Return theh result
			return result;
		}

		public static void main(String[] args) {
			ArrayList p = getPermutations("1234");
			for (String s: p) {
					System.out.println(s);
			}
		}
	}