//  MeCab -- Yet Another Part-of-Speech and Morphological Analyzer
//
//  Copyright(C) 2001-2006 Taku Kudo <taku@chasen.org>
//  Copyright(C) 2004-2006 Nippon Telegraph and Telephone Corporation
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace NMeCab.Core
{
	/// <summary>
	/// Double-Array Trie の実装
	/// </summary>
	public class DoubleArray : IDisposable
	{
        #region Array

		private struct Unit
		{
			public readonly int Base;
			public readonly uint Check;

			public Unit (int b, uint c)
			{
				this.Base = b;
				this.Check = c;
			}
		}

		public const int UnitSize = sizeof(int) + sizeof(uint);

		private Unit[] array;

		public int Size {
			get { return this.array.Length; }
		}

		public int TotalSize {
			get { return this.Size * UnitSize; }
		}

        #endregion

        #region Open

		public void Open (BinaryReader reader, uint size)
		{
			this.array = new Unit[size / UnitSize];

			for (int i = 0; i < array.Length; i++) {
				this.array [i] = new Unit (reader.ReadInt32 (), reader.ReadUInt32 ());
			}
		}

        #endregion

        #region Search

		public struct ResultPair
		{
			public int Value;

			public int Length;

			public ResultPair (int r, int t)
			{
				this.Value = r;
				this.Length = t;
			}
		}

		public void ExactMatchSearch (byte[] key, ref ResultPair result, int len, int nodePos)
		{
			result = this.ExactMatchSearch (key, nodePos);
		}

		public ResultPair ExactMatchSearch (byte[] keys, int nodePos)
		{
			int b = this.ReadBase (nodePos);
			Unit p;

			foreach (var key in keys) {
				this.ReadUnit (b + key + 1, out p);
				if (b == p.Check) {
					b = p.Base;
				} else {
					return new ResultPair (-1, 0);
				}
			}

			this.ReadUnit (b, out p);
			int n = p.Base;
			if (b == p.Check && n < 0) {
				return new ResultPair (-n - 1, keys.Length);
			}

			return new ResultPair (-1, 0);
		}

		public int CommonPrefixSearch (byte[] key, ResultPair[] result, int nodePos = 0)
		{
			int b = this.ReadBase (nodePos);
			int num = 0;
			int n;
			Unit p;

			for (int i = 0; i < key.Length; i++) {
				this.ReadUnit (b, out p);
				n = p.Base;

				if (b == p.Check && n < 0) {
					if (num < result.Length)
						result [num] = new ResultPair (-n - 1, i);
					num++;
				}

				this.ReadUnit (b + key [i] + 1, out p);
				if (b == p.Check) {
					b = p.Base;
				} else {
					return num;
				}
			}

			this.ReadUnit (b, out p);
			n = p.Base;

			if (b == p.Check && n < 0) {
				if (num < result.Length)
					result [num] = new ResultPair (-n - 1, key.Length);
				num++;
			}

			return num;
		}

		private int ReadBase (int pos)
		{
			return this.array [pos].Base;
		}

		private void ReadUnit (int pos, out Unit unit)
		{
			unit = this.array [pos];
		}

        #endregion

        #region Dispose

		private bool disposed;

		public void Dispose ()
		{
			this.Dispose (true);
			GC.SuppressFinalize (this);
		}

		protected virtual void Dispose (bool disposing)
		{
			if (disposed)
				return;

			this.disposed = true;
		}

		~DoubleArray ()
		{
			this.Dispose (false);
		}

        #endregion
	}
}
