List.v3

// Copyright 2010 Google Inc. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// A basic immutable list utility class.
class List<T>(head: T, tail: List<T>) { }
// Common operations on Lists.
component Lists {
	// Reverse the list {rev}.
	def reverse<T>(rev: List<T>) -> List<T> {
		if (rev == null || rev.tail == null) return rev;
		var list: List<T> = null;
		while (rev != null) {
			list = List.new(rev.head, list);
			rev = rev.tail; 
		}
		return list;
	}
	// Create a 1 element list.
	def cons1<T>(elem1: T) -> List<T> {
		return List.new(elem1, null);
	}
	// Create a 2 element list.
	def cons2<T>(elem1: T, elem2: T) -> List<T> {
		return List.new(elem1, List.new(elem2, null));
	}
	// Create a 3 element list.
	def cons3<T>(elem1: T, elem2: T, elem3: T) -> List<T> {
		return List.new(elem1, List.new(elem2, List<T>.new(elem3, null)));
	}
	// Create a list from an {array}, with {array(0) == list.head}.
	def fromArray<T>(array: Array<T>) -> List<T> {
		var list: List<T> = null;
		for (i = array.length - 1; i >= 0; i--) {
			list = List.new(array[i], list);
		}
		return list;
	}
	// Create an array from a {list} with {array(0) == list.head}.
	def toArray<T>(list: List<T>) -> Array<T> {
		var length = length(list), array = Array<T>.new(length);
		for (i < length) {
			array[i] = list.head;
			list = list.tail;
		}
		return array;
	}
	// Compute the length of {list} (in linear time).
	def length<T>(list: List<T>) -> int {
		var length = 0;
		for (l = list; l != null; l = l.tail) length++;
		return length;
	}
	// Map {func} over elements of {list}, returning a new list.
	def map<A, B>(list: List<A>, func: A -> B) -> List<B> {
		if (list == null) return null;
		return List.new(func(list.head), map(list.tail, func));
	}
	// Apply {func} to elements of {list}.
	def apply<T>(list: List<T>, func: T -> void) {
		while (list != null) {
			func(list.head);
			list = list.tail;
		}
	}
	// Map {func} over pairs (A, B) from {a} and {b}, returning a new list of the results.
	def reduce<A, B, C>(a: List<A>, b: List<B>, func: (A, B) -> C) -> List<C> {
		if (a == null || b == null) return null;
		return List.new(func(a.head, b.head), reduce(a.tail, b.tail, func));
	}
	// Apply {func} to pairs (A, B) from {a} and {b} and discard result.
	def reduceV<A, B, R>(a: List<A>, b: List<B>, func: (A, B) -> R) {
		while (a != null && b != null) {
			func(a.head, b.head);
			a = a.tail;
			b = b.tail;
		}
	}
	// Check if {cond} is true for all elements of lists {a} and {b}.
	def allTrue<T>(a: List<T>, b: List<T>, cond: (T, T) -> bool) -> bool {
		while (a != null) {
			if (b == null) return false;
			if (!cond(a.head, b.head)) return false;
			a = a.tail;
			b = b.tail;
		}
		return b == null;
	}
	// Get the element at position {index} in {list} (in linear time).
	def get<T>(list: List<T>, index: int) -> T {
		while (index-- > 0) list = list.tail;
		return list.head;
	}
	// Create a new list of length {length} by padding {list} if necessary.
	def pad<T>(list: List<T>, item: T, length: int) -> List<T> {
		var n: List<T> = null;
		while (length-- > 0) {
			if (list == null) {
				n = List.new(item, n);
			} else {
				n = List.new(list.head, n);
				list = list.tail;
			}
		}
		return Lists.reverse(n);
	}
	// Render a comma-separated list into the given StringBuffer.
	def render<T>(buf: StringBuilder, append: (T, StringBuilder) -> StringBuilder,
		list: List<T>) -> StringBuilder {
		if (list == null) return buf;
		append(list.head, buf);
		for (l = list.tail; l != null; l = l.tail) {
			append(l.head, buf.csp());
		}
		return buf;
	}
}