function newNode() {
	return {
		chars: new Map(),
		code: undefined,
	};
}

function create(strings) {
	const node = newNode();
	for (let i = 0; i < strings.length; i += 1) {
		const tok = strings[i];
		let root = node;
		for (let j = 0; j < tok.length; j += 1) {
			const c = tok.charCodeAt(j);
			let next = root.chars.get(c);
			if (next === undefined) {
				next = newNode();
				root.chars.set(c, next);
			}
			root = next;
		}
		root.code = i;
	}
	return node;
}

function lookup(trie, str) {
	let node = trie;
	for (let i = 0; i < str.length; i += 1) {
		if (node === undefined) {
			return false;
		}
		node = node.chars.get(str[i]);
	}
	return node !== undefined && node.code !== undefined;
}

const EMPTY_UINT8_ARRAY = new Uint8Array(0);

class SmazCompress {
	constructor(codebook, maxSize) {
		this.trie = create(codebook);
		this.buffer = new Uint8Array(maxSize);
		this.verbatim = new Uint8Array(256);
	}

	compress(str) {
		let bufferIndex = 0;
		let verbatimIndex = 0;
		let inputIndex = 0;

		while (inputIndex < str.length) {
			let indexAfterMatch = -1;
			let code = -1;
			let root = this.trie;
			for (let j = inputIndex; j < str.length; j += 1) {
				root = root.chars.get(str[j]);
				if (root === undefined) {
					break;
				}
				if (root.code !== undefined) {
					code = root.code;
					indexAfterMatch = j + 1;
				}
			}
			if (code === -1) {
				this.verbatim[verbatimIndex++] = str[inputIndex++];
				if (verbatimIndex === 255) {
					bufferIndex = this.flushVerbatim(verbatimIndex, bufferIndex);
					verbatimIndex = 0;
				}
			}
			else {
				if (verbatimIndex !== 0) {
					bufferIndex = this.flushVerbatim(verbatimIndex, bufferIndex);
					verbatimIndex = 0;
				}
				this.buffer[bufferIndex++] = code;
				inputIndex = indexAfterMatch;
			}
		}
		if (verbatimIndex !== 0) {
			bufferIndex = this.flushVerbatim(verbatimIndex, bufferIndex);
		}
		return this.buffer.slice(0, bufferIndex);
	}

	flushVerbatim(verbatimIndex, bufferIndex) {
		if (verbatimIndex === 1) {
			this.buffer[bufferIndex++] = 254;
			this.buffer[bufferIndex++] = this.verbatim[0];
		}
		else {
			this.buffer[bufferIndex++] = 255;
			this.buffer[bufferIndex++] = verbatimIndex - 1;
			for (let k = 0; k < verbatimIndex; k += 1) {
				this.buffer[bufferIndex++] = this.verbatim[k];
			}
		}
		return bufferIndex;
	}
}

class SmazDecompress {
	constructor(codebook, maxSize) {
		this.codebook = codebook;
		this.buffer = new Uint8Array(maxSize);
	}

	decompress(arr) {
		let pos = 0;
		let i = 0;
		while (i < arr.byteLength) {
			if (arr[i] === 254) {
				this.buffer[pos] = arr[i + 1];
				pos += 1;
				i += 2;
			}
			else if (arr[i] === 255) {
				for (let j = 0; j <= arr[i + 1]; j += 1) {
					this.buffer[pos] = arr[i + 2 + j];
					pos += 1;
				}
				i += 3 + arr[i + 1];
			}
			else {
				for (let j = 0; j < this.codebook[arr[i]].length; j++) {
					this.buffer[pos] = this.codebook[arr[i]].charCodeAt(j);
					pos += 1;
				}
				i += 1;
			}
		}
		return this.buffer.slice(0, pos);
	}
}

const dictionary = ' ;the;e;t;a;of;o;and;i;n;s;e ;r; th; t;in;he;th;h;he ;to;\r\n;l;s ;d; a;an;er;c; o;d ;on; of;re;of ;t ;, ;is;u;at;   ;n ;or;which;f;m;as;it;that;\n;was;en;  ; w;es; an; i;\r;f ;g;p;nd; s;nd ;ed ;w;ed;http://;for;te;ing;y ;The; c;ti;r ;his;st; in;ar;nt;,; to;y;ng; h;with;le;al;to ;b;ou;be;were; b;se;o ;ent;ha;ng ;their;";hi;from; f;in ;de;ion;me;v;.;ve;all;re ;ri;ro;is ;co;f t;are;ea;. ;her; m;er ; p;es ;by;they;di;ra;ic;not;s, ;d t;at ;ce;la;h ;ne;as ;tio;on ;n t;io;we; a ;om;, a;s o;ur;li;ll;ch;had;this;e t;g ;e\r\n; wh;ere; co;e o;a ;us; d;ss;\n\r\n;\r\n\r;="; be; e;s a;ma;one;t t;or ;but;el;so;l ;e s;s,;no;ter; wa;iv;ho;e a; r;hat;s t;ns;ch ;wh;tr;ut;/;have;ly ;ta; ha; on;tha;-; l;ati;en ;pe; re;there;ass;si; fo;wa;ec;our;who;its;z;fo;rs;>;ot;un;<;im;th ;nc;ate;><;ver;ad; we;ly;ee; n;id; cl;ac;il;</;rt; wi;div;e, ; it;whi; ma;ge;x;e c;men;.com'.split(";");

const compressor = new SmazCompress(dictionary, 30000);
const decompressor = new SmazDecompress(dictionary, 30000);

export function compress(str) {
	return compressor.compress(str);
}
export function decompress(str) {
	return decompressor.decompress(str);
}