RunLength

RunLength.java

package tester;

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

public class RunLength {
	public static class Pair<T> {
		private T entry;
		private int length;

		public T getEntry() {
			return entry;
		}
		public int getLength() {
			return length;
		}

		protected Pair(T entry, int length) {
			this.entry = entry;
			this.length = length;
		}

		public String toString() {
			return String.format("(%s, %d)", entry, length);
		}
	}

	public static void main(String[] args) {
		List<Character> list = new ArrayList<Character>();
		for(Character c : "aaabbabbbdccbabaaabab".toCharArray()) list.add(c);
		
		for(Pair<Character> p : runlength(list)) {
			System.out.print(p + ", ");
		}
	}

	/*
	  def runlength[T](list: List[T]): List[(T, Int)] = list match {
	|   case Nil => Nil
	|   case x :: xs => val (first, rest) = xs.span(x ==)
	|     (x, first.length+1) :: runlength(rest)
	| }
	 */
	public static <T> List<Pair<T>> runlength(List<T> list) {
		return runlength0(list, new ArrayList<Pair<T>>());
	}

	private static <T> List<Pair<T>> runlength0(List<T> list, List<Pair<T>> accu) {
		if(list.isEmpty()) { return accu;
		} else {
			T head = list.get(0);
			int i = 1;
			for(; i<list.size() && head.equals(list.get(i)); i++);

			accu.add(new Pair<T>(head, i));

			return runlength0(list.subList(i, list.size()), accu);
		}
	}
}

RunLength.scala

def runlength[T](list: List[T]): List[(T, Int)] = list match {
  case Nil => Nil
  case x :: xs => val (first, rest) = xs.span(x ==)
    (x, first.length+1) :: runlength(rest)
}

runlength("aaabbabbbdccbabaaabab".toList)
res11: List[(Char, Int)] = List((a,3), (b,2), (a,1), (b,3), (d,1), (c,2), (b,1), (a,1), (b,1), (a,3), (b,1), (a,1), (b,1))