//  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
    {
        #region Array

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

            public Unit(BinaryReader reader)
            {
                this.Base = reader.ReadInt32();
                this.Check = reader.ReadUInt32();
            }
        }

        private Unit[] array;

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

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

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

        #endregion

        #region Open

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

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

        #endregion

        #region Search

        public struct ResultPair
        {
            public int Value;

            public int Length;

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

        #region ExactMatchSearch

        public unsafe void ExactMatchSearch(byte* key, ResultPair* result, int len, int nodePos)
        {
            *result = this.ExactMatchSearch(key, len, nodePos);
        }

        public unsafe ResultPair ExactMatchSearch(byte* key, int len, int nodePos)
        {
            int b = this.array[nodePos].Base;
            Unit p;

            for (int i = 0; i < len; i++)
            {
                p = this.array[b + key[i] + 1];
                if (b == p.Check)
                {
                    b = p.Base;
                }
                else
                {
                    return new ResultPair(-1, 0);
                }
            }

            p = this.array[b];
            int n = p.Base;
            if (b == p.Check && n < 0)
            {
                return new ResultPair(-n - 1, len);
            }

            return new ResultPair(-1, 0);
        }

        #endregion

        #region CommonPrefixSearch

        public unsafe int CommonPrefixSearch(byte* key, ResultPair* result, int resultLen, int len, int nodePos = 0)
        {
            int b = this.array[nodePos].Base;
            int num = 0;
            int n;
            Unit p;

            for (int i = 0; i < len; i++)
            {
                p = this.array[b];
                n = p.Base;

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

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

            p = this.array[b];
            n = p.Base;

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

            return num;
        }

        #endregion

        #endregion
    }
}
