Map.v3

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

// Basic map interface that offers [] indexed access.
class Map<K, V> {
	def [key: K] -> V;
	def [key: K] = val: V;
}
// An extended map interface that also has methods to query whether a value
// exists for a particular element and to iterate over all key/value pairs.
class PartialMap<K, V> extends Map<K, V> {
	def has(key: K) -> bool;
	def apply(func: (K, V) -> void);
}
// A general-purpose HashMap implementation that provides the PartialMap interface.
// For maximum reusability, this implementation accepts the hash and equality functions
// as closures, and thus can map any key type to any value type.
class HashMap<K, V> extends PartialMap<K, V> {
	def hash: K -> int;		// user-supplied hash function
	def equals: (K, K) -> bool;	// user-supplied equality method
	private var table: Array<Bucket<K, V>>;	// lazily allocated hashtable
	private var cache: Bucket<K, V>;	// cache for last entry get/set

	// Cases for {cache} and {table}:
	// - {cache == null}, {table == null}: map is empty
	// - {cache == v}, {table == null}: map has a single entry {v}
	// - {cache == v}, {table == t}: {v} is an entry in {t} (cached an entry)
	// - {cache == null}, {table == t}: cache not populated

	new(hash, equals) { }

	// Get the value for {key}, if one exists; otherwise return the default value for {V}.
	def [key: K] -> V {
		var c = cache;
		if (c != null && (c.key == key || equals(c.key, key))) return c.val;
		// cache is empty or did not match, hash and do bucket search
		if (table != null) {
			for (bucket = table[dohash(key)]; bucket != null; bucket = bucket.next) {
				if (bucket.key == key || equals(bucket.key, key)) {
					cache = bucket;
					return bucket.val;
				}
			}
		}
		var none: V;
		return none;
	}
	// Set the value for {key} to {val}, overwriting any previous value.
	def [key: K] = val: V {
		var c = cache;
		// empty map: only populate {cache}
		// note that {cache} in single-element map will not be overwritten unless
		// by another insertion
		if (c == null && table == null) {
			cache = Bucket.new(key, val, null);
			return;
		}
		// cache hit
		if (c != null && (c.key == key || equals(c.key, key))) {
			c.val = val;
			return;
		}
		// cache miss
		if (table == null) {
			// missed the cache, table not yet allocated, insert both
			table = Array.new(16); // TUNABLE: initial HashMap table size
			if (c != null) insert(c);
			insert(cache = Bucket.new(key, val, null));
			return;
		}
		// missed the cache, hash and search the table
		var hashval = dohash(key);
		var i = 0;
		for (bucket = table[hashval]; bucket != null; bucket = bucket.next) {
			if (equals(bucket.key, key)) {
				bucket.val = val;
				cache = bucket;
				return;
			}
			i++;
		}
		// insert into table and cache
		table[hashval] = cache = Bucket.new(key, val, table[hashval]);
		if (i > 4 && table.length < 1001) balance();
	}
	// Check if this map has a value for the {key}.
	def has(key: K) -> bool {
		var c = cache;
		if (c != null && (c.key == key || equals(c.key, key))) return true;
		if (table == null) return false; // no table
		for (bucket = table[dohash(key)]; bucket != null; bucket = bucket.next) {
			if (bucket.key == key || equals(bucket.key, key)) return true;
		}
		return false;
	}
	// Apply {func} to every (key, value) pair in this map.
	def apply(func: (K, V) -> void) {
		if (table == null) {
			// zero or one entry
			if (cache != null) func(cache.key, cache.val);
			return;
		}
		// two or more entries
		for (b in table) {
			for (bucket = b; bucket != null; bucket = bucket.next) {
				func(bucket.key, bucket.val);
			}
		}
	}
	// Remove {key} from this map. Return true if {key} existed.
	def remove(key: K) -> bool {
		var c = cache;
		var found = false;
		// if cache hit, clear cache
		if (c != null && (c.key == key || equals(c.key, key))) {
			found = true;
			cache = null;
		}
		// search table
		if (table != null) {
			var hashval = dohash(key);
			var curr = table[hashval];
			if (curr == null) return found;
			if (curr.key == key || equals(curr.key, key)) {
				table[hashval] = curr.next;
				return true;
			}
			while (curr.next != null) {
				if (curr.next.key == key || equals(curr.next.key, key)) {
					curr.next = curr.next.next;
					return true;
				}
				curr = curr.next;
			}
		}
		return found;
	}
	private def insert(bucket: Bucket<K, V>) {
		var hashval = dohash(bucket.key);
		bucket.next = table[hashval];
		table[hashval] = bucket;
	}
	private def dohash(key: K) -> int {
		return hash(key) & (table.length - 1);
	}
	private def balance() {
		var old = table, olen = old.length;
		table = Array.new(olen * 4);
		for (i < olen) {
			for (b = old[i]; b != null; b = b.next) {
				var hashval = dohash(b.key);
				table[hashval] = Bucket.new(b.key, b.val, table[hashval]);
			}
		}
	}
}
// Utility class to implement a lazily-allocated map.
class LazyMap<K, V> extends PartialMap<K, V> {
	def hash: K -> int;
	def equals: (K, K) -> bool;
	def create: K -> V;
	var map: HashMap<K, V>;
	
	new(hash, equals, create) { }

	// Get the value for the specified {key}, creating it if necessary.
	def [key: K] -> V {
		if (map == null) map = HashMap.new(hash, equals);
		var v = map[key], none: V;
		if (v == none) {
			v = create(key);
			map[key] = v;
		}
		return v;
	}
	// Set the value associated with the {key} to be {val}.
	def [key: K] = val: V {
		if (map == null) map = HashMap.new(hash, equals);
		map[key] = val;
	}
	// Check if there is a value for {key}.
	def has(key: K) -> bool {
		return map != null && map.has(key);
	}
	// Apply the function {f} to every key/value pair in this map.
	def apply(f: (K, V) -> void) {
		if (map != null) map.apply(f);
	}
}

// Utility methods associated with maps.
component Maps {
	// Extract a list of valid keys from a {map}.
	def keyList<K, V>(map: PartialMap<K, V>) -> List<K> {
		if (map == null) return null;
		var k = MapKeyListGatherer<K, V>.new();
		map.apply(k.add);
		return k.list;
	}
	// Extract a list of valid values from a {map}.
	def valueList<K, V>(map: PartialMap<K, V>) -> List<V> {
		if (map == null) return null;
		var v = MapValueListGatherer<K, V>.new();
		map.apply(v.add);
		return v.list;
	}
}

// Internal data structure needed by HashMap to represent chained buckets.
private class Bucket<K, V> {
	def key: K;
	var val: V;
	var next: Bucket<K, V>;

	new(key, val: V, next: Bucket<K,V>) {
		this.next = next;
		this.val = val;
	}
}
// Utility class that is used in Maps to create a list of keys from a partial map.
private class MapKeyListGatherer<K, V> {
	var list: List<K>;
	def add(key: K, val: V) { list = List.new(key, list); }
}
// Utility class that is used in Maps to create a list of values from a partial map.
private class MapValueListGatherer<K, V> {
	var list: List<V>;
	def add(key: K, val: V) { list = List.new(val, list); }
}