BufferedReader.readLine() and OutOfMemoryError

2015/11/20

https://github.com/farble1670/boundedlinereader

BufferedReader.readLine() cannot be hardened. There’s no way to restrict the number of characters read per line. If you cannot control the input to your reader, that’s a problem. Here’s a simple Reader implementation that can read lines, bounded by a maximum character length.

import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

class BoundedLineReader extends InputStreamReader {
  static final String NEWLINE = System.getProperty("line.separator");

  private final char[] buffer;

  public BoundedLineReader(InputStream in, int maxLineLength) {
    super(in);
    this.buffer = new char[maxLineLength];
  }

  public String readLine() throws IOException {
    char[] last = new char[NEWLINE.length()];

    int c;
    int i = 0;
    boolean nl = false;
    while ((c = read()) != -1 && i < buffer.length) {
      shiftIn(last, (char) c);
      buffer[i++] = (char) c;
      if (equals(NEWLINE, last)) {
        nl = true;
        break;
      }
    }

    // chomp any newline or newline segment from end of buffer
    for (int j = 0; j < NEWLINE.length() && i > 0; j++) {
      if (buffer[i - 1] == '\n' || buffer[i - 1] == '\r') {
        i--;
      }
    }

    if (i == 0) {
      return null;
    }

    String result = new String(buffer, 0, i);

    if (!nl) {
      // didn't read newline, consume until we read it
      while ((c = read()) != -1) {
        shiftIn(last, (char) c);
        if (equals(NEWLINE, last)) {
          break;
        }
      }
    }

    return result;
  }

  private boolean equals(String s, char[] a) {
    if (a.length != s.length()) {
      return false;
    }
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) != a[i]) {
        return false;
      }
    }
    return true;
  }

  private void shiftIn(char[] a, char c) {
    for (int i = a.length - 1; i >= 1; i--) {
      a[i - 1] = a[i];
    }
    a[a.length - 1] = c;
  }

  public int skipLines(int num) {
    int i = 0;
    try {
      while (readLine() != null && ++i <= num) {
      }
    } catch (IOException e) {
    }
    return i - 1;
  }
}

This is not a buffered reader. It reads one character at a time making it inefficient and not suited for production. Here’s a better implementation that’s a copy of Java’s BufferedReader with a few modifications to the readLine() method,

/**
 * This class is a copy of java.io.BufferedReader that can bound maximum line length when read using readLine(int).
 *
 * If the line length exceeds the passed length, the line up to the length is returned.
 * Subsequent readLine(int) calls will return the next line with the same restrictions.
 *
 * This class also provides a skipLines(int) method that will skip past the given number of lines, or less
 * if stream contains fewer lines.
 */

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;

/**
 * Wraps an existing {@link Reader} and <em>buffers</em> the input. Expensive
 * interaction with the underlying reader is minimized, since most (smaller)
 * requests can be satisfied by accessing the buffer alone. The drawback is that
 * some extra space is required to hold the buffer and that copying takes place
 * when filling that buffer, but this is usually outweighed by the performance
 * benefits.
 * <p/>
 * <p/>A typical application pattern for the class looks like this:<p/>
 * <p/>
 * <pre>
 * BufferedReader buf = new BufferedReader(new FileReader(&quot;file.java&quot;));
 * </pre>
 *
 * @see BufferedWriter
 * @since 1.1
 */
public class BoundedBufferedReader extends Reader {

  private Reader in;

  /**
   * The characters that can be read and refilled in bulk. We maintain three
   * indices into this buffer:<pre>
   *     { X X X X X X X X X X X X - - }
   *           ^     ^             ^
   *           |     |             |
   *         mark   pos           end</pre>
   * Pos points to the next readable character. End is one greater than the
   * last readable character. When {@code pos == end}, the buffer is empty and
   * must be {@link #fillBuf() filled} before characters can be read.
   * <p/>
   * <p>Mark is the value pos will be set to on calls to {@link #reset}. Its
   * value is in the range {@code [0...pos]}. If the mark is {@code -1}, the
   * buffer cannot be reset.
   * <p/>
   * <p>MarkLimit limits the distance between the mark and the pos. When this
   * limit is exceeded, {@link #reset} is permitted (but not required) to
   * throw an exception. For shorter distances, {@link #reset} shall not throw
   * (unless the reader is closed).
   */
  private char[] buf;

  private int pos;

  private int end;

  private int mark = -1;

  private int markLimit = -1;

  /**
   * readLine returns a line as soon as it sees '\n' or '\r'. In the latter
   * case, there might be a following '\n' that should be treated as part of
   * the same line ending. Both readLine and all read methods are supposed
   * to skip the '\n' (and clear this field) but only readLine looks for '\r'
   * and sets it.
   */
  private boolean lastWasCR;

  /**
   * We also need to keep the 'lastWasCR' state for the mark position, in case
   * we reset to there.
   */
  private boolean markedLastWasCR;

  /**
   * Constructs a new {@code BufferedReader}, providing {@code in} with a buffer
   * of 8192 characters.
   *
   * @param in the {@code Reader} the buffer reads from.
   */
  public BoundedBufferedReader(Reader in) {
    this(in, 8192);
  }

  /**
   * Constructs a new {@code BufferedReader}, providing {@code in} with {@code size} characters
   * of buffer.
   *
   * @param in   the {@code InputStream} the buffer reads from.
   * @param size the size of buffer in characters.
   * @throws IllegalArgumentException if {@code size <= 0}.
   */
  public BoundedBufferedReader(Reader in, int size) {
    super(in);
    if (size <= 0) {
      throw new IllegalArgumentException("size <= 0");
    }
    this.in = in;
    buf = new char[size];
  }

  /**
   * Closes this reader. This implementation closes the buffered source reader
   * and releases the buffer. Nothing is done if this reader has already been
   * closed.
   *
   * @throws IOException if an error occurs while closing this reader.
   */
  @Override
  public void close() throws IOException {
    synchronized (lock) {
      if (!isClosed()) {
        in.close();
        buf = null;
      }
    }
  }

  /**
   * Populates the buffer with data. It is an error to call this method when
   * the buffer still contains data; ie. if {@code pos < end}.
   *
   * @return the number of chars read into the buffer, or -1 if the end of the
   * source stream has been reached.
   */
  private int fillBuf() throws IOException {
    // assert(pos == end);

    if (mark == -1 || (pos - mark >= markLimit)) {
            /* mark isn't set or has exceeded its limit. use the whole buffer */
      int result = in.read(buf, 0, buf.length);
      if (result > 0) {
        mark = -1;
        pos = 0;
        end = result;
      }
      return result;
    }

    if (mark == 0 && markLimit > buf.length) {
            /* the only way to make room when mark=0 is by growing the buffer */
      int newLength = buf.length * 2;
      if (newLength > markLimit) {
        newLength = markLimit;
      }
      char[] newbuf = new char[newLength];
      System.arraycopy(buf, 0, newbuf, 0, buf.length);
      buf = newbuf;
    } else if (mark > 0) {
            /* make room by shifting the buffered data to left mark positions */
      System.arraycopy(buf, mark, buf, 0, buf.length - mark);
      pos -= mark;
      end -= mark;
      mark = 0;
    }

        /* Set the new position and mark position */
    int count = in.read(buf, pos, buf.length - pos);
    if (count != -1) {
      end += count;
    }
    return count;
  }

  /**
   * Indicates whether or not this reader is closed.
   *
   * @return {@code true} if this reader is closed, {@code false}
   * otherwise.
   */
  private boolean isClosed() {
    return buf == null;
  }

  /**
   * Sets a mark position in this reader. The parameter {@code markLimit}
   * indicates how many characters can be read before the mark is invalidated.
   * Calling {@code reset()} will reposition the reader back to the marked
   * position if {@code markLimit} has not been surpassed.
   *
   * @param markLimit the number of characters that can be read before the mark is
   *                  invalidated.
   * @throws IllegalArgumentException if {@code markLimit < 0}.
   * @throws IOException              if an error occurs while setting a mark in this reader.
   * @see #markSupported()
   * @see #reset()
   */
  @Override
  public void mark(int markLimit) throws IOException {
    if (markLimit < 0) {
      throw new IllegalArgumentException("markLimit < 0:" + markLimit);
    }
    synchronized (lock) {
      checkNotClosed();
      this.markLimit = markLimit;
      this.mark = pos;
      this.markedLastWasCR = lastWasCR;
    }
  }

  private void checkNotClosed() throws IOException {
    if (isClosed()) {
      throw new IOException("BufferedReader is closed");
    }
  }

  /**
   * Indicates whether this reader supports the {@code mark()} and
   * {@code reset()} methods. This implementation returns {@code true}.
   *
   * @return {@code true} for {@code BufferedReader}.
   * @see #mark(int)
   * @see #reset()
   */
  @Override
  public boolean markSupported() {
    return true;
  }

  /**
   * Reads a single character from this reader and returns it with the two
   * higher-order bytes set to 0. If possible, BufferedReader returns a
   * character from the buffer. If there are no characters available in the
   * buffer, it fills the buffer and then returns a character. It returns -1
   * if there are no more characters in the source reader.
   *
   * @return the character read or -1 if the end of the source reader has been
   * reached.
   * @throws IOException if this reader is closed or some other I/O error occurs.
   */
  @Override
  public int read() throws IOException {
    synchronized (lock) {
      checkNotClosed();
      int ch = readChar();
      if (lastWasCR && ch == '\n') {
        ch = readChar();
      }
      lastWasCR = false;
      return ch;
    }
  }

  private int readChar() throws IOException {
    if (pos < end || fillBuf() != -1) {
      return buf[pos++];
    }
    return -1;
  }

  /**
   * Reads up to {@code length} characters from this reader and stores them
   * at {@code offset} in the character array {@code buffer}. Returns the
   * number of characters actually read or -1 if the end of the source reader
   * has been reached. If all the buffered characters have been used, a mark
   * has not been set and the requested number of characters is larger than
   * this readers buffer size, BufferedReader bypasses the buffer and simply
   * places the results directly into {@code buffer}.
   *
   * @throws IndexOutOfBoundsException if {@code offset < 0 || length < 0 || offset + length > buffer.length}.
   * @throws IOException               if this reader is closed or some other I/O error occurs.
   */
  @Override
  public int read(char[] buffer, int offset, int length) throws IOException {
    synchronized (lock) {
      checkNotClosed();
      checkOffsetAndCount(buffer.length, offset, length);
      if (length == 0) {
        return 0;
      }

      maybeSwallowLF();

      int outstanding = length;
      while (outstanding > 0) {
        // If there are chars in the buffer, grab those first.
        int available = end - pos;
        if (available > 0) {
          int count = available >= outstanding ? outstanding : available;
          System.arraycopy(buf, pos, buffer, offset, count);
          pos += count;
          offset += count;
          outstanding -= count;
        }

                /*
                 * Before attempting to read from the underlying stream, make
                 * sure we really, really want to. We won't bother if we're
                 * done, or if we've already got some chars and reading from the
                 * underlying stream would block.
                 */
        if (outstanding == 0 || (outstanding < length && !in.ready())) {
          break;
        }

        // assert(pos == end);

                /*
                 * If we're unmarked and the requested size is greater than our
                 * buffer, read the chars directly into the caller's buffer. We
                 * don't read into smaller buffers because that could result in
                 * a many reads.
                 */
        if ((mark == -1 || (pos - mark >= markLimit)) && outstanding >= buf.length) {
          int count = in.read(buffer, offset, outstanding);
          if (count > 0) {
            outstanding -= count;
            mark = -1;
          }
          break; // assume the source stream gave us all that it could
        }

        if (fillBuf() == -1) {
          break; // source is exhausted
        }
      }

      int count = length - outstanding;
      if (count > 0) {
        return count;
      }
      return -1;
    }
  }

  /**
   * Peeks at the next input character, refilling the buffer if necessary. If
   * this character is a newline character ("\n"), it is discarded.
   */
  final void chompNewline() throws IOException {
    if ((pos != end || fillBuf() != -1) && buf[pos] == '\n') {
      ++pos;
    }
  }

  // If the last character was CR and the next character is LF, skip it.
  private void maybeSwallowLF() throws IOException {
    if (lastWasCR) {
      chompNewline();
      lastWasCR = false;
    }
  }

  /**
   * Returns the next line of text available from this reader. A line is
   * represented by zero or more characters followed by {@code '\n'},
   * {@code '\r'}, {@code "\r\n"} or the end of the reader. The string does
   * not include the newline sequence.
   *
   * @param maxLen The maximum String length to return.
   *
   * @return the contents of the line or {@code null} if no characters were
   * read before the end of the reader has been reached.
   * @throws IOException if this reader is closed or some other I/O error occurs.
   */
  public String readLine(int maxLen) throws IOException {
    synchronized (lock) {
      checkNotClosed();

      maybeSwallowLF();

      // Do we have a whole line in the buffer?
      for (int i = pos; i < end; ++i) {
        char ch = buf[i];
        if (ch == '\n' || ch == '\r') {
          String line = new String(buf, pos, Math.min(i - pos, maxLen));
          pos = i + 1;
          lastWasCR = (ch == '\r');
          return line;
        }
      }

      // Accumulate buffers in a StringBuilder until we've read a whole line.
      StringBuilder result = new StringBuilder(end - pos + 80);
      result.append(buf, pos, Math.min(end - pos, maxLen - result.length()));

      while (true) {
        pos = end;
        if (fillBuf() == -1) {
          // If there's no more input, return what we've read so far, if anything.
          return (result.length() > 0) ? result.toString() : null;
        }

        // Do we have a whole line in the buffer now?
        for (int i = pos; i < end; ++i) {
          char ch = buf[i];
          if (ch == '\n' || ch == '\r') {
            result.append(buf, pos, Math.min(i - pos, maxLen - result.length()));
            pos = i + 1;
            lastWasCR = (ch == '\r');
            return result.toString();
          }
        }

        // Add this whole buffer to the line-in-progress and try again...
        result.append(buf, pos, Math.min(end - pos, maxLen - result.length()));
      }
    }
  }

  /**
   * Indicates whether this reader is ready to be read without blocking.
   *
   * @return {@code true} if this reader will not block when {@code read} is
   * called, {@code false} if unknown or blocking will occur.
   * @throws IOException if this reader is closed or some other I/O error occurs.
   * @see #read()
   * @see #read(char[], int, int)
   * @see #readLine()
   */
  @Override
  public boolean ready() throws IOException {
    synchronized (lock) {
      checkNotClosed();
      return ((end - pos) > 0) || in.ready();
    }
  }

  /**
   * Resets this reader's position to the last {@code mark()} location.
   * Invocations of {@code read()} and {@code skip()} will occur from this new
   * location.
   *
   * @throws IOException if this reader is closed or no mark has been set.
   * @see #mark(int)
   * @see #markSupported()
   */
  @Override
  public void reset() throws IOException {
    synchronized (lock) {
      checkNotClosed();
      if (mark == -1) {
        throw new IOException("Invalid mark");
      }
      this.pos = mark;
      this.lastWasCR = this.markedLastWasCR;
    }
  }

  /**
   * Skips at most {@code charCount} chars in this stream. Subsequent calls to
   * {@code read} will not return these chars unless {@code reset} is
   * used.
   * <p/>
   * <p>Skipping characters may invalidate a mark if {@code markLimit}
   * is surpassed.
   *
   * @return the number of characters actually skipped.
   * @throws IllegalArgumentException if {@code charCount < 0}.
   * @throws IOException              if this reader is closed or some other I/O error occurs.
   */
  @Override
  public long skip(long charCount) throws IOException {
    if (charCount < 0) {
      throw new IllegalArgumentException("charCount < 0: " + charCount);
    }
    synchronized (lock) {
      checkNotClosed();
      if (end - pos >= charCount) {
        pos += charCount;
        return charCount;
      }

      long read = end - pos;
      pos = end;
      while (read < charCount) {
        if (fillBuf() == -1) {
          return read;
        }
        if (end - pos >= charCount - read) {
          pos += charCount - read;
          return charCount;
        }
        // Couldn't get all the characters, skip what we read
        read += (end - pos);
        pos = end;
      }
      return charCount;
    }
  }

  private static void checkOffsetAndCount(int arrayLength, int offset, int count) {
    if ((offset | count) < 0 || offset > arrayLength || arrayLength - offset < count) {
      throw new ArrayIndexOutOfBoundsException(String.format("length: %s, offset: %d, count: %d", arrayLength, offset, count));
    }
  }

  /**
   * Skip (read past) the given number of lines.
   */
  public int skipLines(int num) {
    if (num == 0) {
      return 0;
    }

    int i = 0;
    try {
      while (readLine(0) != null) {
        if (++i >= num) {
          break;
        }
      }
    } catch (IOException e) {
    }
    return i;
  }
}
Advertisements

Linear Grid Layout

2014/12/18

Pre API-21, GridLayout has no concept of weights. That means it’s impossible to make a GridLayout that stretches it’s rows and columns to fill the available space. Apparently API 21 fixes this, so says the Javadocs,

As of API 21, GridLayout’s distribution of excess space accomodates the principle of weight. In the event that no weights are specified, the previous conventions are respected and columns and rows are taken as flexible if their views specify some form of alignment within their groups.

Pre API 21, here’s a simple solution. LinearGridLayout is a view that simulates a grid layout by nesting LinearLayouts. This is just sample code and while it worked for my particular situation you may need to tweak it to your requirements.

To use, just insert into your XML,

    <LinearGridLayout
        auto:columns="2"
        auto:margins="10dp"
        android:layout_width="match_parent"
        android:layout_height="match_parent"/>

And in your code, add some views,

LinearGridLayout layout = ...;
layout.addViews(myViews);

Here’s the source …

public class LinearGridLayout extends LinearLayout {

  private int columns;
  private int margins;

  public LinearGridLayout(Context context) {
    super(context);
  }

  public LinearGridLayout(Context context, AttributeSet attrs) {
    super(context, attrs);
    applyAttrs(context, attrs);
  }

  public LinearGridLayout(Context context, AttributeSet attrs, int defStyle) {
    super(context, attrs, defStyle);
    applyAttrs(context, attrs);
  }

  private void applyAttrs(Context context, AttributeSet attrs) {
    TypedArray a = context.getTheme().obtainStyledAttributes(attrs, R.styleable.ContactlessLogosView, 0, 0);

    try {
        columns = a.getInt(R.styleable.ContactlessLogosView_columns, Integer.MAX_VALUE);
        margins = a.getDimensionPixelSize(R.styleable.ContactlessLogosView_margins, 0);
    } finally {
      a.recycle();
    }

    setOrientation(VERTICAL);
  }

  public void addViews(Collection<View> views) {
    Preconditions.checkArgument(columns != 0);

    removeAllViews();

    int c = 0;
    LinearLayout layout = null;

    for (View v: views) {
      if (c == columns) {
        c = 0;
        layout = null;
      }

      if (layout == null) {
        layout = new LinearLayout(getContext());
        layout.setOrientation(HORIZONTAL);
        LayoutParams rowParams = new LayoutParams(LayoutParams.MATCH_PARENT, 0, 1);
        layout.setLayoutParams(rowParams);
        addView(layout);
      }

      LayoutParams lp = new LayoutParams(0, LayoutParams.WRAP_CONTENT, 1);
      lp.setMargins(margins, margins, margins, margins);
      v.setLayoutParams(lp);
      layout.addView(v);

      c++;
    }

    if (columns != Integer.MAX_VALUE) {
      for (int i = c; i < columns; i++) {
        LayoutParams lp = new LayoutParams(0, LayoutParams.WRAP_CONTENT, 1);
        View v = new View(getContext());
        v.setLayoutParams(lp);
        layout.addView(v);
      }
    }
  }
}

Reflective toString()

2013/01/15

Tired of writing toString() on all your classes? Annoyed when your co-workers forget to do so? Here’s a simple solution that uses reflection to implement toString().

Find two source files. ToString.java is a helper class for implementing toString(). It’s a revision of the Google Guava’s ToStringHelper.

public class ToString {
	private final List<ValueHolder> valueHolders = new LinkedList<ValueHolder>();
	private boolean omitNullValues = false;

	protected final Object obj;

	public ToString(Object obj) {
		this.obj = obj;
	}

	public ToString add(String name, Object value) {
		addHolder(value).builder.append(name).append('=').append(value);
		return this;
	}

	public ToString add(String name, boolean value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	public ToString add(String name, char value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	public ToString add(String name, double value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	public ToString add(String name, float value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	public ToString add(String name, int value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	public ToString add(String name, long value) {
		checkNameAndAppend(name).append(value);
		return this;
	}

	private StringBuilder checkNameAndAppend(String name) {
		return addHolder().builder.append(name).append('=');
	}

	@Override
	public String toString() {
		// create a copy to keep it consistent in case value changes
		boolean omitNullValuesSnapshot = omitNullValues;
		boolean needsSeparator = false;
		StringBuilder builder = new StringBuilder(32).append(
				obj.getClass().getSimpleName()).append('{');
		for (ValueHolder valueHolder : valueHolders) {
			if (!omitNullValuesSnapshot || !valueHolder.isNull) {
				if (needsSeparator) {
					builder.append(", ");
				} else {
					needsSeparator = true;
				}
				CharSequence sequence = valueHolder.builder;
				builder.append(sequence);
			}
		}
		return builder.append('}').toString();
	}

	private ValueHolder addHolder() {
		ValueHolder valueHolder = new ValueHolder();
		valueHolders.add(valueHolder);
		return valueHolder;
	}

	private ValueHolder addHolder(Object value) {
		ValueHolder valueHolder = addHolder();
		valueHolder.isNull = (value == null);
		return valueHolder;
	}

	private static final class ValueHolder {
		final StringBuilder builder = new StringBuilder();
		boolean isNull;
	}
}

ReflectiveToString.java extends the former, and re-implements toString() to automatically add all (most) fields.

public class ReflectiveToString extends ToString {
	private static final Pattern[] IGNORE_FIELD_PATTERNS = new Pattern[] {
			Pattern.compile("^this\\$\\d+$"),
			Pattern.compile("^serialVersionUID$") };

	public ReflectiveToString(Object obj) {
		super(obj);
	}

	@Override
	public String toString() {
		Set<Field> fields = getFields();
		fields: for (Field f : fields) {
			String fn = f.getName();
			for (Pattern p : IGNORE_FIELD_PATTERNS) {
				Matcher m = p.matcher(fn);
				if (m.matches()) {
					continue fields;
				}
			}

			f.setAccessible(true);
			try {
				add(fn, f.get(obj));
			} catch (IllegalArgumentException e) {
				// silently skip, should never happen
			} catch (IllegalAccessException e) {
				// silently skip, should never happen
			}
		}

		return super.toString();
	}

	private Set<Field> getFields() {
		Set<Field> fields = new HashSet<Field>();
		getFields(obj.getClass(), fields);

		return fields;
	}

	private static void getFields(Class<? extends Object> cls, Set<Field> fields) {
		Class<? extends Object> superclass = cls.getSuperclass();
		if (superclass != null) {
			getFields(superclass, fields);
		}
		fields.addAll(Arrays.asList(cls.getDeclaredFields()));
	}
}

To use it, implement toString() on your classes like this,

@Override
public String toString() {
    return new ReflectiveToString(this).toString();
}

You could of course extend Guava’s ToStringHelper directly. I didn’t want to pull in the entire library however.

Of course the string output can be tuned by modifying ToString.java.


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);
	}
}

JSON Flattener

2012/01/21

I recently ran into the problem of needing to store a JSON object in a key, value store. I pasted a little utility class that does the job below. Here’s an example run against some nasty JSON,

ORIGINAL:

{ string: 'aString', integer: -1, nested: { x: 1, y: 2, z: 3}, moreNested: { a: [1,2,3], b: [4,5,6], c: [7,8,9]}, arrayFromHell: [{ innerArray: [{ innerInnerArray: [1,2,3]}]}]}

ENCODED:

{"arrayFromHell.0.innerArray.0.innerInnerArray.0":1,"arrayFromHell.0.innerArray.0.innerInnerArray.1":2,"arrayFromHell.0.innerArray.0.innerInnerArray.2":3,"nested.z":3,"nested.y":2,"nested.x":1,"integer":-1,"string":"aString","moreNested.b.0":4,"moreNested.b.1":5,"moreNested.b.2":6,"moreNested.c.0":7,"moreNested.c.1":8,"moreNested.c.2":9,"moreNested.a.0":1,"moreNested.a.1":2,"moreNested.a.2":3}

DECODED:

{"nested":{"z":3,"y":2,"x":1},"arrayFromHell":[{"innerArray":[{"innerInnerArray":[1,2,3]}]}],"integer":-1,"string":"aString","moreNested":{"b":[4,5,6],"c":[7,8,9],"a":[1,2,3]}}

As you can see, it simply looks at every leaf value (string, int) and derives the key path and stores the value there. For example,

{ x: { y: { z: 1 } } }

becomes,

{ x.y.z: 1 }

Arrays are a special case. Each value in an array becomes the path so far to the array appended with the array index. For example,

{ anArray: [1,2,3] }

becomes,

{ anArray.0: 1, anArray.1: 2, anArray.2: 3 }
Of course this isn’t foolproof. If you have dots in your key names, it will break. If you use numbers as keys, it will break as it makes an assumption that a numbered key path element indicates an array. Here’s the source.
package org.test.flatjson;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;

public class JsonFlattener {
	public static String encode(JSONObject jo) throws JSONException {
		String s = "{" + encode(null, jo) + "}";
		return s;

	}

	public static String encode(String json) throws JSONException {
		JSONObject jo = new JSONObject(json);
		return encode(jo);
	}

	private static String encode(String parent, Object val)
			throws JSONException {
		StringBuilder sb = new StringBuilder();
		if (val instanceof JSONObject) {
			JSONObject jo = (JSONObject) val;
			for (Iterator<String> i = jo.keys(); i.hasNext();) {
				String key = i.next();
				String hkey = (parent == null) ? key : parent + "." + key;
				Object jval = jo.get(key);
				String json = encode(hkey, jval);
				sb.append(json);
				if (i.hasNext()) {
					sb.append(",");
				}
			}
		} else if (val instanceof JSONArray) {
			JSONArray ja = (JSONArray) val;
			for (int i = 0; i < ja.length(); i++) {
				String hkey = (parent == null) ? "" + i : parent + "." + i;
				Object aval = ja.get(i);
				String json = encode(hkey, aval);
				sb.append(json);
				if (i < ja.length() - 1) {
					sb.append(",");
				}
			}
		} else if (val instanceof String) {
			sb.append("\"").append(parent).append("\"").append(":");
			String s = (String) val;
			sb.append(JSONObject.quote(s));
		} else if (val instanceof Integer) {
			sb.append("\"").append(parent).append("\"").append(":");
			Integer integer = (Integer) val;
			sb.append(integer);
		}

		return sb.toString();
	}

	public static String decode(String flatJson) throws JSONException {
		JSONObject encoded = new JSONObject(flatJson);
		return decodeToString(encoded);
	}

	public static String decodeToString(JSONObject encoded)
			throws JSONException {
		return decodeToObject(encoded).toString();
	}

	public static JSONObject decodeToObject(JSONObject encoded)
			throws JSONException {
		JSONObject decoded = new JSONObject();

		for (Iterator<String> i = encoded.keys(); i.hasNext();) {
			String hkey = i.next();
			String[] keys = hkey.split("\\.");

			Object json = decoded;

			for (int j = 0; j < keys.length; j++) {
				if (j == keys.length - 1) {
					Object val = encoded.get(hkey);
					if (json instanceof JSONObject) {
						JSONObject jo = (JSONObject)json;
						jo.put(keys[j], val);
					} else if (json instanceof JSONArray) {
						JSONArray ja = (JSONArray)json;
						int index = Integer.parseInt(keys[j]);
						ja.put(index, val);
					}
				} else {
					// we're NOT at a leaf key

					if (!isNumber(keys[j + 1])) {
						// next index is an object

						JSONObject joChild;

						if (json instanceof JSONObject) {
							// last index was an object
							// we're creating an object in an object
							JSONObject jo = (JSONObject)json;
							if (jo.has(keys[j])) {
								joChild = jo.getJSONObject(keys[j]);
							} else {
								joChild = new JSONObject();
								jo.put(keys[j], joChild);
							}
						} else if (json instanceof JSONArray) {
							// last index was an array
							// we're creating an object in an array
							JSONArray ja = (JSONArray)json;
							int index = Integer.parseInt(keys[j]);
							if (!ja.isNull(index)) {
								joChild = ja.getJSONObject(index);
							} else {
								joChild = new JSONObject();
								ja.put(index, joChild);
							}
						} else {
							throw new AssertionError("unhandled object type");
						}
						json = joChild;
					} else {
						// next index is an array element

						JSONArray jaChild;

						if (json instanceof JSONObject) {
							// last index was an object,
							// we're creating an array in an object
							JSONObject jo = (JSONObject)json;
							if (jo.has(keys[j])) {
								jaChild = jo.getJSONArray(keys[j]);
							} else {
								jaChild = new JSONArray();
								jo.put(keys[j], jaChild);
							}
						} else if (json instanceof JSONArray) {
							// last index was an array
							// we're creating an array in an array
							JSONArray ja = (JSONArray)json;
							int index = Integer.parseInt(keys[j + 1]);
							if (!ja.isNull(index)) {
								jaChild = ja.getJSONArray(index);
							} else {
								jaChild = new JSONArray();
								ja.put(index, jaChild);
							}
						} else {
							throw new AssertionError("unhandled object type");
						}
						json = jaChild;
					}
				}
			}
		}
		return decoded;
	}

	private static boolean isNumber(String s) {
		try {
			Integer.parseInt(s);
			return true;
		} catch (NumberFormatException e) {
			return false;
		}

	}
}

Iterative Tree Traversal

2010/11/16

While studying for an interview, I some how got it into my head that I should understand the iterative algorithms for the three standard tree traversal methods (pre-, post-, in-). While the recursive algorithms for these are straightforward and intuitive, the iterative ones are most certainly not. Worse, googling on this topic turned up a lot of incomplete or just plain wrong solutions.

With some painstaking work I believe I came up with some nearly as simple as possible solutions. Some solutions I found required parent pointers, some required visit markers. These require neither of these.

After each algorithm, I include a walkthrough of the algorithm based on this sample tree from the Wikipedia tree traversal page.

Pre-order,

void preOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		n.visit();

		if (n.right != null) {
			s.push(n.right);
		}
		if (n.left != null) {
			s.push(n.left);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={}, visited={F}, s={B,G}
2: s={G}, visited={F,B}, s={A,D,G}
3: s={D,G}, visited={F,B,A}, s={D,G}
4: s={G}, visited={F,B,A,D}, s={C,E,G}
5: s={E,G}, visited={F,B,A,D,C}, s={E,G}
6: s={G}, visited={F,B,A,D,C,E}, s={G}
7: s={}, visited={F,B,A,D,C,E,G}, s={I}
8: s={}, visited={F,B,A,D,C,E,G,I}, s={H}
9: s={}, visited={F,B,A,D,C,E,G,I,H}, s={}

Post-order,

This one uses two stacks. It consumes the input stack and builds the output stack. At the end of the method, it pops each node from the output stack and visits it.

void postOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	Stack<Node> o = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		o.push(n);

		if (n.left != null) {
			s.push(n.left);
		if (n.right != null) {
			s.push(n.right);
		}
	}
	while (!o.empty()) {
		o.pop().visit();
	}
}

Each line of the example below shows state of the input stack and output stack after the iteration.

1: out={F}, in={G,B}
2: out={G,F}, in={I,B}
3: out={I,G,F}, in={H,B}
4: out={H,I,G,F}, in={B}
5: out={B,H,I,G,F}, in={D,A}
6: out={D,B,H,I,G,F}, in={E,C,A}
7: out={E,D,B,H,I,G,F}, in={C,A}
8: out={C,E,D,B,H,I,G,F}, in={A}
9: out={A,C,E,D,B,H,I,G,F}, in={}

In-order,

void inOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		while (n.left != null) {
			n = n.left;
			s.push(n);
		}
		n = s.pop();
		n.visit();
		if (n.right != null) {
			s.push(n.right);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={A,B,F}, v={A}, s={B,F}
2: s={B,F}, v={A,B}, s={D,F}
3: s={C,D,F}, v={A,B,C}, s={D,F}
4: s={D,F}, v={A,B,C,D}, s={E,F}
5: s={E,F}, v={A,B,C,D,E}, s={F}
6: s={F}, v={A,B,C,D,E,F}, s={G}
7: s={G}, v={A,B,C,D,E,F,G}, s={I}
8: s={H,I}, v={A,B,C,D,E,F,G,H}, s={I}
9: s={I}, v={A,B,C,D,E,F,G,H,I}, s={}

Java EE Got it Wrong

2009/11/17

After working on two large-scale, cross contains / platform, web application projects, I’ve come to the conclusion that Java EE is fatally flawed.

If someone asked you to state the most important, guiding principle of the Java language, what would you say? You would would probably say “write once, run anywhere.” Indeed, for Java SE this holds true most all of the time. In Java EE however, it is hopelessly broken. The reality is that every web container is slightly different in ways that force developers work around problems, avoid certain features, or even have different code paths. Different code paths in a language that was never designed for it.

Different aspects of Java EE have different levels of stability. JSP works almost the same across all containers. Things like JSF and Java Persistence (JPA) however are hopeless. My most recent experience is writing a web administration console using JSF for the OpenSSO project. OpenSSO claims to support at at least 8 different web containers. Every container required JSF tweaking that ranged from annoying to just plain terrible. Needless to say I had egg on my face to some degree over the choice to use JSF. It was a no-brainer for me. JSF is the chosen MVC framework for Java EE. My mistake.

The only container where JSF “just worked” was Tomcat. Tomcat isn’t a Java EE container at all.Tomcat doesn’t include JSF or any of it’s dependencies. We might be on to something here. Let’s look at another example: Spring. Spring is essentially a lighter-weight, simpler replacement for Java EE. Why is Spring so popular? One reason is that it is an elegant design. But another, perhaps more important reasons is that no matter what container you are developing on, Spring is Spring. It’s the same JAR, the same code, the same implementation. It makes very few assumptions about the capabilities of the underlying container. Another example is Facelets, a light-weight JSP replacment. I use JSF+Facelets on the OpenSSO project, and it has been flawless (the Facelets part). Why? Because I include the Facelets JAR, it is not provided by the system.

What if Java EE had followed the same model? Java EE should have been nothing more than a plugin framework and some base services. Want to use JSF in your project? Just include it from a managed, networked Java EE module repository. Include the one, common implementation of JSF. Include the approved version for your level of Java EE. If you support Java EE 5, you get JSF version X, across all web containers.