// require lst
// require SafeMap

Lzw = {}

Lzw.generate_dict = function(length)
	result = {}
	for i in range(length - 1).sort
		result[char(i)] = char(i)
	end for
	return result
end function

Lzw.compress = function(uncompressed)
	dict_size = 256
	dictionary = self.generate_dict(dict_size)

	w = ""
	result = []

	for c in uncompressed.values
		wc = w + c
		//if dictionary.hasIndex(wc) then
		if SafeMap.hasIndex(dictionary, wc) then
			w = wc
		else
			//result.push(dictionary[w])
			result.push(SafeMap.get(dictionary, w))
			//dictionary[wc] = dict_size
			SafeMap.set(dictionary, wc, dict_size)
			dict_size = dict_size + 1
			w = c
		end if
	end for

	//if w != "" then result.push(dictionary[w])
	if w != "" then result.push(SafeMap.get(dictionary, w))
	return result
end function

Lzw.decompress = function(compressed)
	dict_size = 256
	dictionary = self.generate_dict(dict_size)
	
	w = compressed[0]
	result = compressed[0]
	compressed = compressed[1:]
	for k in compressed
		//if dictionary.hasIndex(k) then
		if SafeMap.hasIndex(dictionary, k) then
			//entry = dictionary[k]
			entry = SafeMap.get(dictionary, k)
		else if k == dict_size then
			entry = w + w[0]
		else
			exit("Bad compressed k: " + k)
		end if
		result = result + entry
		
		//dictionary[dict_size] = w + entry[0]
		SafeMap.set(dictionary, dict_size, w + entry[0])
		dict_size = dict_size + 1
		
		w = entry
	end for
	return result
end function