using System;
using System.IO;

namespace Lumpio.Gif {
	public class GifCompressor {
		private BitPacker bp;
		private ulong nofdata;
		private ulong curordinal;
		private byte pixel;
		private byte[] data;
		private ushort datadepth;
		private ushort nbits;
		private ushort[] axon, next;
		private byte[] pix;
		private ulong cc, eoi;
		private ushort freecode;
		private Stream stream;
		
		private void iniroots() {
			ushort nofrootcodes = (ushort)(1 << Math.Max((ushort)2, datadepth));
			for (ushort i = 0; i < nofrootcodes; ++i) {
				axon[i] = 0;
				pix[i] = (byte)i;
			}
		}

		private void flushStringTable() {
			ushort nofrootcodes = (ushort)(1 << Math.Max((ushort)2, datadepth));
			for (ushort i = 0; i < nofrootcodes; ++i) {
				axon[i] = 0;
			}
		}

		private ushort findPixelOutlet(ushort headnode, byte pixel) {
			ushort outlet = axon[headnode];
			while (outlet > 0) {
				if (pix[outlet] == pixel) {
					return outlet;
				}
				outlet = next[outlet];
			}
			return 0;
		}

		private ulong weiter() {
			ushort up = (ushort)pixel, down;
			if (++curordinal > nofdata) {
				bp.Submit(up, nbits);
				return curordinal;
			}
			pixel = data[curordinal - 1];
			while ((down = findPixelOutlet(up, pixel)) != 0) {
				up = down;
				if (++curordinal > nofdata) {
					bp.Submit(up, nbits);
					return curordinal;
				}
				pixel = data[curordinal - 1];
			}
			bp.Submit(up, nbits);
			pix[freecode] = pixel;
			axon[freecode] = next[freecode] = 0;
			down = axon[up];
			if (down == 0) {
				axon[up] = freecode;
			} else {
				while (next[down] > 0) {
					down = next[down];
				}
				next[down] = freecode;
			}
			return curordinal;
		}

		public GifCompressor(Stream stream) {
			this.stream = stream;
		}

		public ulong WriteDataBlocks(byte[] pixeldata, ushort dd) {
			nofdata = (ulong)pixeldata.Length;
			data = pixeldata;
			curordinal = 1;
			pixel = data[curordinal - 1];
			datadepth = dd;
			nbits = (ushort)Math.Max(3, dd + 1);
			cc = (ulong)(1 << (nbits - 1));
			eoi = cc + 1;
			freecode = (ushort)(cc + 2);
			bp = new BitPacker(stream);
			axon = new ushort[4096];
			next = new ushort[4096];
			pix = new byte[4096];
			
			iniroots();
			
			stream.WriteByte(Math.Max((byte)datadepth, (byte)2));
			bp.Submit(cc, nbits);

			while(true) {
				weiter();
				if (curordinal > nofdata) {
					bp.Submit(eoi, nbits);
					bp.WriteFlush();
					stream.WriteByte(0x00);
					axon = null;
					next = null;
					pix = null;
					ulong bytesWritten = 2 + bp.BytesWritten;
					bp = null;
					return bytesWritten;
				}
				if (freecode == (ushort)(1 << nbits)) {
					nbits++;
				}
				freecode++;
				if (freecode == 0xFFF) {
					flushStringTable();
					bp.Submit(cc, nbits);
					nbits = (ushort)Math.Max(3, 1 + datadepth);
					freecode = (ushort)(cc + 2);
				}
			}
		}
	}
}