Spiral Order, Java

2012/03/19

This is a problem I’ve heard mentioned but never really had a reason to look into. As they say, the science is gone from computer science. I sat down today and put some thought into it.

Spiral order is what you’d think. Given a 2D array, you move from left to right, top to bottom, right to left, and bottom to top printing out the values in order. For example,

  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16

The spiral order of this matrix is,

{  1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 }

The algorithm to walk in spiral order works nicely with recursion. You recursively, “peel” off the top, right, bottom, left portions of the matrix until there’s nothing left. For example (forgive the ASCII art), peel off the top,

  1 2 3 4

  5  6  7  8
  9 10 11 12
 13 14 15 16

peel off the right,

  5  6  7     8
  9 10 11    12
 13 14 15    16

peel off the bottom,

  5  6  7
  9 10 11 

 13 14 15

peel off the left,

 5     6  7
 9    10 11

peel off the top (again, starting over here),

 6 7

 10 11

peel the right again,

 10    11

and finally, one more peel of the bottom gets the last element,

 10

and we are done.

The code is below. spiralOrderR() implements the recursive algorithm. It calls peelTop(), which calls peelLeft(), which calls peelBottom(),which calls peelLeft(), and so on, until it’s done.  The peeling happens in the arguments to the recursive call, where the bounds of the matrix are reduced as appropriate at each pass.

public class SpiralOrder {
	public static <T> List<T> spiralOrderR(T[][] matrix) {
		int startx = 0;
		int starty = 0;
		int endx = matrix.length - 1;
		int endy = matrix.length - 1;

		List<T> spiral = new ArrayList<T>();

		peelTopRight(matrix, startx, endx, starty, endy, spiral);
		return spiral;
	}

	private static <T> void peelTop(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		if (startx > matrix.length / 2) {
			return;
		}
		for (int i = startx; i <= endx; i++) {
			spiral.add(matrix[i][starty]);
		}
		peelRight(matrix, startx, endx, starty+1, endy, spiral);
	}

	private static <T> void peelRight(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = starty; i <= endy; i++) {
			spiral.add(matrix[endx][i]);
		}
		peelBottom(matrix, startx, endx-1, starty, endy, spiral);
	}

	private static <T> void peelBottom(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = endx; i >= startx; i--) {
			spiral.add(matrix[i][endy]);
		}
		peelLeft(matrix, startx, endx, starty, endy-1, spiral);
	}

	private static <T> void peelLeft(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = endy; i >= starty; i--) {
			spiral.add(matrix[startx][i]);
		}
		peelTop(matrix, startx+1, endx, starty, endy, spiral);
	}

	public static void main(String[] args) {
		Integer[][] ints = new Integer[5][5];
		int count = 1;
		for (int i = 0; i < ints.length; i++) {
			for (int j = 0; j < ints[i].length; j++) {
				ints[j][i] = count++;
			}
		}

		List<Integer> spiral = spiralOrder(ints);
		System.out.println(spiral);
		spiral = spiralOrderR(ints);
		System.out.println(spiral);
	}
}
Advertisements

Android Advanced Logger

2012/03/08

The Android Log utility class is simple enough and does the job, but there are a few nagging problems I’ve found with it.

No context. There is no supplied as to what triggered the log statement. This leads to log records like,

D/MyApp: Something happened ...

Great, but happened where? What class? Which method? For small apps with a single developer this isn’t a problem, but for larger projects where the person that’s doing the debugging did not write the code … By convention, developers can add contextual information into the log statements but this requires everyone to remember to do this, consistently. Can’t the log utility do it for us?

Tag inconsistencies. Some apps use different tags for each class, others use the same tag across the entire app. The former makes it impossible to tell which log statements came from the same app, unless you keep a mapping from tab to class to app around. That’s why I prefer the latter. However, now we are forced to pass the exact same argument (TAG) into every log statement. Can the logging framework insert it for us?

Level. The Android logger does not allow me to change the level, only filter the log output by level via logcat arguments. What if i simply want to avoid logging things at particular levels?

Argument evaluation. A common logging anti-pattern,

Log.i("here's the object: " + myObj);

This is problematic because regardless of the level, regardless whether the statement will actually get into the log, myObj.toString() is called and a new String object that is the concatenation of “here’s the object: ” and myObj.toString() is created. Over a large app with many log statements, this can significantly hamper performance. Commonly, the antidote is something like,

if (LOG_LEVEL == Level.INFO) {
    Log.i("here's the object: " + myObj);
}

But this really crufts up the code. Can we avoid this sort of check?

Small log window. The Android log buffer is about 50k. On a device with a good number of apps installed, the entire log window can scroll in a matter of minutes. This makes it impossible to go back and examine the log for specific events.

To solve these problems, I created a simple utility class, ALog (advanced log).

To add context, it automatically appends the class and method name, and line number to the beginning of every statement. The result is clear, contextual log statements like this,

W/my-app(23659): InstallManager.<init>@120: failed to make APK dir: /mnt/sdcard/Download

ALog avoids evaluating arguments by accepting a log pattern plus arguments,

ALog.w("oh noes, a problem occured when i %s and then also at %s", msg1, msg2);

The first argument, the format, must conform to the interface dedefined by String.format().

ALog support setting a global tag for the entire app, and setting the level. Do so in your application class,

public class MyApplication extends Application {
    @Override
    public void onCreate() {
        ALog.setTag("MyApp");
        ALog.setLevel(CLog.Level.D);
    }
}
ALog optionally writes every log record to a file on your SD card, to keep a nearly infinite log of exactly what happened in your app. Just enable file logging like,
ALog.setFileLogging(true);
Files are created at: <Environment.getExternalStorageDirectory()>/alog/<tag>.log
Note that this is extremely inefficient. It should only be used temporarily to find bugs then disabled. It should never be used in production. You can look at the code below, but it starts a thread that take()’s from a blocking queue. Logging a message offers()’s into this queue. The file is opened, appended, and closed at each log statement; it does not keep the file open.
Here’s the source,
public class ALog {
	private static class LogContext {
		LogContext(StackTraceElement element) {
			// this.className = element.getClassName();
			this.simpleClassName = getSimpleClassName(element.getClassName());
			this.methodName = element.getMethodName();
			this.lineNumber = element.getLineNumber();
		}

		// String className;
		String simpleClassName;
		String methodName;
		int lineNumber;
	}

	public enum Level {
		V(1), D(2), I(3), W(4), E(5);

		private int value;

		private Level(int value) {
			this.value = value;
		}

		int getValue() {
			return value;
		}
	};

	private static final DateFormat FLOG_FORMAT = new SimpleDateFormat(
			"yyyy-MM-dd HH:mm:ss.SSS");
	private static final File LOG_DIR = new File(
			Environment.getExternalStorageDirectory() + File.separator + "alog");
	private static boolean fileLogging = false;
	private static String tag = "<tag unset>";
	private static Level level = Level.V;
	private static final BlockingQueue<String> logQueue = new LinkedBlockingQueue<String>();
	private static Runnable queueRunner = new Runnable() {
		@Override
		public void run() {
			String line;
			try {
				while ((line = logQueue.take()) != null) {

					if (!Environment.getExternalStorageState().equals(
							Environment.MEDIA_MOUNTED)) {
						continue;
					}
					if (!LOG_DIR.exists() && !LOG_DIR.mkdirs()) {
						continue;
					}

					File logFile = new File(LOG_DIR, tag + ".log");
					Writer w = null;
					try {
						w = new FileWriter(logFile, true);
						w.write(line);
						w.close();
					} catch (IOException e) {
					} finally {
						if (w != null) {
							try {
								w.close();
							} catch (IOException e1) {
							}
						}
					}
				}
			} catch (InterruptedException e) {
			}
		}
	};

	static {
		new Thread(queueRunner).start();
	}

	private static LogContext getContext() {
		StackTraceElement[] trace = Thread.currentThread().getStackTrace();
		StackTraceElement element = trace[5]; // frame below us; the caller
		LogContext context = new LogContext(element);
		return context;
	}

	private static final String getMessage(String s, Object... args) {
		s = String.format(s, args);
		LogContext c = getContext();
		String msg = c.simpleClassName + "." + c.methodName + "@"
				+ c.lineNumber + ": " + s;
		return msg;
	}

	private static String getSimpleClassName(String className) {
		int i = className.lastIndexOf(".");
		if (i == -1) {
			return className;
		}
		return className.substring(i + 1);
	}

	public static void setLevel(Level l) {
		level = l;
	}

	public static void setTag(String t) {
		tag = t;
	}

	public static void setFileLogging(boolean enable) {
		fileLogging = enable;
	}

	public static void v(String format, Object... args) {
		if (level.getValue() > Level.V.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.v(tag, msg);
		if (fileLogging) {
			flog(Level.V, msg);
		}
	}

	public static void d(String format, Object... args) {
		if (level.getValue() > Level.D.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.d(tag, msg);
		if (fileLogging) {
			flog(Level.D, msg);
		}
	}

	public static void i(String format, Object... args) {
		if (level.getValue() > Level.I.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.i(tag, msg);
		if (fileLogging) {
			flog(Level.I, msg);
		}
	}

	public static void w(String format, Object... args) {
		if (level.getValue() > Level.W.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.w(tag, msg);
		if (fileLogging) {
			flog(Level.W, msg);
		}
	}

	public static void w(String format, Throwable t, Object... args) {
		if (level.getValue() > Level.W.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.w(tag, msg, t);
		if (fileLogging) {
			flog(Level.W, msg, t);
		}
	}

	public static void e(String format, Object... args) {
		if (level.getValue() > Level.E.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.e(tag, msg);
		if (fileLogging) {
			flog(Level.E, msg);
		}
	}

	public static void e(String format, Throwable t, Object... args) {
		if (level.getValue() > Level.E.getValue()) {
			return;
		}
		String msg = getMessage(format, args);
		Log.e(tag, msg, t);
		if (fileLogging) {
			flog(Level.E, msg, t);
		}
	}

	public static void trace() {
		try {
			throw new Throwable("dumping stack trace ...");
		} catch (Throwable t) {
			ALog.e("trace:", t);
		}
	}

	public static String getStackTraceString(Throwable tr) {
		if (tr == null) {
			return "";
		}

		Throwable t = tr;
		while (t != null) {
			if (t instanceof UnknownHostException) {
				return "";
			}
			t = t.getCause();
		}

		StringWriter sw = new StringWriter();
		PrintWriter pw = new PrintWriter(sw);
		tr.printStackTrace(pw);
		return sw.toString();
	}

	private static void flog(Level l, String msg) {
		flog(l, msg, null);
	}

	private static void flog(Level l, String msg, Throwable t) {
		String timeString = FLOG_FORMAT.format(new Date());
		String line = timeString + " " + l.toString() + "/" + tag + ": " + msg
				+ "\n";
		if (t != null) {
			line += getStackTraceString(t) + "\n";
		}
		logQueue.offer(line);
	}
}