/* 
 * PROJECT: NyARToolkitCS(Extension)
 * --------------------------------------------------------------------------------
 * The NyARToolkitCS is C# edition ARToolKit class library.
 * Copyright (C)2008-2009 Ryo Iizuka
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * For further information please contact.
 *	http://nyatla.jp/nyatoolkit/
 *	<airmail(at)ebony.plala.or.jp> or <nyatla(at)nyatla.jp>
 * 
 */
using System;
using System.Collections.Generic;
using System.Text;
using jp.nyatla.nyartoolkit.cs.utils;

namespace jp.nyatla.nyartoolkit.cs.core
{
    class RleInfoStack : NyObjectStack<RleInfoStack.RleInfo>
    {
	    public class RleInfo
	    {
		    //継承メンバ
		    public int entry_x; // フラグメントラベルの位置
		    public int area;
		    public int clip_r;
		    public int clip_l;
		    public int clip_b;
		    public int clip_t;
		    public long pos_x;
		    public long pos_y;		
	    }	
	    public RleInfoStack(int i_length):base(i_length)
	    {
		    return;
	    }

	    protected override RleInfoStack.RleInfo createElement()
	    {
		    return new RleInfoStack.RleInfo();
	    }
    }


    /**
     * [strage class]
     */


    class RleElement
    {
        public int l;
        public int r;
        public int fid;
        public static RleElement[] createArray(int i_length)
        {
            RleElement[] ret = new RleElement[i_length];
            for (int i = 0; i < i_length; i++)
            {
                ret[i] = new RleElement();
            }
            return ret;
        }
    }

    // RleImageをラベリングする。
    public class NyARLabeling_Rle
    {
	    private const int AR_AREA_MAX = 100000;// #define AR_AREA_MAX 100000
        private const int AR_AREA_MIN = 70;// #define AR_AREA_MIN 70
    	
	    private RleInfoStack _rlestack;

        private RleElement[] _rle1;
        private RleElement[] _rle2;
        private int _max_area;
        private int _min_area;

        public NyARLabeling_Rle(int i_width, int i_height)
        {
            this._rlestack = new RleInfoStack(i_width * i_height * 2048 / (320 * 240) + 32);
            this._rle1 = RleElement.createArray(i_width / 2 + 1);
            this._rle2 = RleElement.createArray(i_width / 2 + 1);
            setAreaRange(AR_AREA_MAX, AR_AREA_MIN);

            return;
        }
        /**
         * 対象サイズ
         * @param i_max
         * @param i_min
         */
        public void setAreaRange(int i_max, int i_min)
        {
            this._max_area = i_max;
            this._min_area = i_min;
            return;
        }

        /**
         * i_bin_bufのbinイメージをREL圧縮する。
         * 
         * @param i_bin_raster
         */
        private int toRel(int[] i_bin_buf, int i_st, int i_len, RleElement[] i_out)
        {
            int current = 0;
            int r = -1;
            // 行確定開始
            int x = i_st;
            int right_edge = i_st + i_len - 1;
            while (x < right_edge)
            {
                // 暗点(0)スキャン
                if (i_bin_buf[x] != 0)
                {
                    x++;
                    continue;
                }
                // 暗点発見→暗点長を調べる
                r = (x - i_st);
                i_out[current].l = r;
                r++;// 暗点+1
                x++;
                while (x < right_edge)
                {
                    if (i_bin_buf[x] != 0)
                    {
                        // 明点(1)→暗点(0)配列終了>登録
                        i_out[current].r = r;
                        current++;
                        x++;// 次点の確認。
                        r = -1;// 右端の位置を0に。
                        break;
                    }
                    else
                    {
                        // 暗点(0)長追加
                        r++;
                        x++;
                    }
                }
            }
            // 最後の1点だけ判定方法が少し違うの。
            if (i_bin_buf[x] != 0)
            {
                // 明点→rカウント中なら暗点配列終了>登録
                if (r >= 0)
                {
                    i_out[current].r = r;
                    current++;
                }
            }
            else
            {
                // 暗点→カウント中でなければl1で追加
                if (r >= 0)
                {
                    i_out[current].r = (r + 1);
                }
                else
                {
                    // 最後の1点の場合
                    i_out[current].l = (i_len - 1);
                    i_out[current].r = (i_len);
                }
                current++;
            }
            // 行確定
            return current;
        }

        private void addFragment(RleElement i_rel_img, int i_nof, int i_row_index, RleInfoStack o_stack)
        {
            int l = i_rel_img.l;
            int len = i_rel_img.r - l;
            i_rel_img.fid = i_nof;// REL毎の固有ID
            RleInfoStack.RleInfo v = o_stack.prePush();
            v.entry_x = l;
            v.area = len;
            v.clip_l = l;
            v.clip_r = i_rel_img.r - 1;
            v.clip_t = i_row_index;
            v.clip_b = i_row_index;
            v.pos_x = (len * (2 * l + (len - 1))) / 2;
            v.pos_y = i_row_index * len;

            return;
        }

        //
        public int labeling(NyARBinRaster i_bin_raster, int i_top, int i_bottom, RleLabelFragmentInfoStack o_stack)
        {
 		    // リセット処理
		    RleInfoStack rlestack=this._rlestack;
		    rlestack.clear();
                //
            RleElement[] rle_prev = this._rle1;
            RleElement[] rle_current = this._rle2;
            int len_prev = 0;
            int len_current = 0;
            int width = i_bin_raster.getWidth();
            int[] in_buf = (int[])i_bin_raster.getBufferReader().getBuffer();

            int id_max = 0;
            int label_count = 0;
            // 初段登録

            len_prev = toRel(in_buf, i_top, width, rle_prev);
            for (int i = 0; i < len_prev; i++)
            {
                // フラグメントID=フラグメント初期値、POS=Y値、RELインデクス=行
                addFragment(rle_prev[i], id_max, i_top, rlestack);
                id_max++;
                // nofの最大値チェック
                label_count++;
            }
            RleInfoStack.RleInfo[] f_array = rlestack.getArray();
            // 次段結合
            for (int y = i_top + 1; y < i_bottom; y++)
            {
                // カレント行の読込
                len_current = toRel(in_buf, y * width, width, rle_current);
                int index_prev = 0;

                for (int i = 0; i < len_current; i++)
                {
                    // index_prev,len_prevの位置を調整する
                    int id = -1;
                    // チェックすべきprevがあれば確認
                    while (index_prev < len_prev)
                    {
                        if (rle_current[i].l - rle_prev[index_prev].r > 0)
                        {// 0なら8方位ラベリング
                            // prevがcurの左方にある→次のフラグメントを探索
                            index_prev++;
                            continue;
                        }
                        else if (rle_prev[index_prev].l - rle_current[i].r > 0)
                        {// 0なら8方位ラベリングになる
                            // prevがcur右方にある→独立フラグメント
                            addFragment(rle_current[i], id_max, y, rlestack);
                            id_max++;
                            label_count++;
                            // 次のindexをしらべる
                            goto SCAN_CUR;
                        }
                        id = rle_prev[index_prev].fid;//ルートフラグメントid
                        RleInfoStack.RleInfo id_ptr = f_array[id];
                        //結合対象(初回)->prevのIDをコピーして、ルートフラグメントの情報を更新
                        rle_current[i].fid = id;//フラグメントIDを保存
                        //
                        int l = rle_current[i].l;
                        int r = rle_current[i].r;
                        int len = r - l;
                        //結合先フラグメントの情報を更新する。
                        id_ptr.area += len;
                        //tとentry_xは、結合先のを使うので更新しない。
                        id_ptr.clip_l = l < id_ptr.clip_l ? l : id_ptr.clip_l;
                        id_ptr.clip_r = r > id_ptr.clip_r ? r - 1 : id_ptr.clip_r;
                        id_ptr.clip_b = y;
                        id_ptr.pos_x += (len * (2 * l + (len - 1))) / 2;
                        id_ptr.pos_y += y * len;
                        //多重結合の確認（２個目以降）
                        index_prev++;
                        while (index_prev < len_prev)
                        {
                            if (rle_current[i].l - rle_prev[index_prev].r > 0)
                            {// 0なら8方位ラベリング
                                // prevがcurの左方にある→prevはcurに連結していない。
                                goto SCAN_PREV;
                            }
                            else if (rle_prev[index_prev].l - rle_current[i].r > 0)
                            {// 0なら8方位ラベリングになる
                                // prevがcurの右方にある→prevはcurに連結していない。
                                index_prev--;
                                goto SCAN_CUR;
                            }
                            // prevとcurは連結している→ルートフラグメントの統合

                            //結合するルートフラグメントを取得
                            int prev_id = rle_prev[index_prev].fid;
                            RleInfoStack.RleInfo prev_ptr = f_array[prev_id];
                            if (id != prev_id)
                            {
                                label_count--;
                                //prevとcurrentのフラグメントidを書き換える。
                                for (int i2 = index_prev; i2 < len_prev; i2++)
                                {
                                    //prevは現在のidから最後まで
                                    if (rle_prev[i2].fid == prev_id)
                                    {
                                        rle_prev[i2].fid = id;
                                    }
                                }
                                for (int i2 = 0; i2 < i; i2++)
                                {
                                    //currentは0から現在-1まで
                                    if (rle_current[i2].fid == prev_id)
                                    {
                                        rle_current[i2].fid = id;
                                    }
                                }

                                //現在のルートフラグメントに情報を集約
                                id_ptr.area += prev_ptr.area;
                                id_ptr.pos_x += prev_ptr.pos_x;
                                id_ptr.pos_y += prev_ptr.pos_y;
                                //tとentry_xの決定
                                if (id_ptr.clip_t > prev_ptr.clip_t)
                                {
                                    // 現在の方が下にある。
                                    id_ptr.clip_t = prev_ptr.clip_t;
                                    id_ptr.entry_x = prev_ptr.entry_x;
                                }
                                else if (id_ptr.clip_t < prev_ptr.clip_t)
                                {
                                    // 現在の方が上にある。prevにフィードバック
                                }
                                else
                                {
                                    // 水平方向で小さい方がエントリポイント。
                                    if (id_ptr.entry_x > prev_ptr.entry_x)
                                    {
                                        id_ptr.entry_x = prev_ptr.entry_x;
                                    }
                                    else
                                    {
                                    }
                                }
                                //lの決定
                                if (id_ptr.clip_l > prev_ptr.clip_l)
                                {
                                    id_ptr.clip_l = prev_ptr.clip_l;
                                }
                                else
                                {
                                }
                                //rの決定
                                if (id_ptr.clip_r < prev_ptr.clip_r)
                                {
                                    id_ptr.clip_r = prev_ptr.clip_r;
                                }
                                else
                                {
                                }
                                //bの決定

                                //結合済のルートフラグメントを無効化する。
                                prev_ptr.area = 0;
                            }


                            index_prev++;
                        }
                        index_prev--;
                        break;
                        SCAN_PREV: ;
                    }
                    // curにidが割り当てられたかを確認
                    // 右端独立フラグメントを追加
                    if (id < 0)
                    {
                        addFragment(rle_current[i], id_max, y, rlestack);
                        id_max++;
                        label_count++;
                    }
                SCAN_CUR: ;
                }
                // prevとrelの交換
                RleElement[] tmp = rle_prev;
                rle_prev = rle_current;
                len_prev = len_current;
                rle_current = tmp;
            }
		    //対象のラベルだけ転写
		    o_stack.reserv(label_count);
		    RleLabelFragmentInfoStack.RleLabelFragmentInfo[] o_dest_array=o_stack.getArray();
		    int max=this._max_area;
		    int min=this._min_area;
		    int active_labels=0;
		    for(int i=id_max-1;i>=0;i--){
			    int area=f_array[i].area;
			    if(area<min || area>max){//対象外のエリア0のもminではじく
				    continue;
			    }
			    //
			    RleInfoStack.RleInfo src_info=f_array[i];
			    RleLabelFragmentInfoStack.RleLabelFragmentInfo dest_info=o_dest_array[active_labels];
			    dest_info.area=area;
			    dest_info.clip_b=src_info.clip_b;
			    dest_info.clip_r=src_info.clip_r;
			    dest_info.clip_t=src_info.clip_t;
			    dest_info.clip_l=src_info.clip_l;
			    dest_info.entry_x=src_info.entry_x;
			    dest_info.pos_x=src_info.pos_x/src_info.area;
			    dest_info.pos_y=src_info.pos_y/src_info.area;
			    active_labels++;
		    }
		    //ラベル数を再設定
		    o_stack.pops(label_count-active_labels);
		    //ラベル数を返却
		    return active_labels;
        }
    }

}
