/* 
 * PROJECT: NyARToolkitCS(Extension)
 * --------------------------------------------------------------------------------
 * The NyARToolkitCS is Java 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;
namespace jp.nyatla.nyartoolkit.cs.core
{



    /**
     * このクラスは、距離マップを利用した、頂点集合同士のマッチング処理機能を提供します。
     * 2つの点集合同士を比較して、集合の各点同士の距離が最も近くになる組み合わせを計算します。
     * <p>アルゴリズム - 
     * 2つの点集合の総当たりの距離マップを作り、その距離が小さいのものから順に抽出することで、
     * 其々の点の移動距離が最小になる組み合わせを計算します。
     * </p>
     * <p>使い方　-
     * このクラスは、まず距離マップを作るために距離値をセットして、次に組み合わせを得る手順で使います。
     * 距離マップには行と列があります。列を基準値、行を比較値として、その距離値を格納します。
     * 行と列の距離マップを作り終えたら、組合せを計算します。
     * <ol>
     * <li>{@link #setMapSize}関数で、マップサイズ（比較する頂点数）を設定する。
     * <li>{@link #setDist},または{@link #setPointDists}で、距離マップに全ての値を書き込む。
     * <li>
     * </ol>
     * </p>
     */
    public class NyARDistMap
    {
        /** 処理用のデータ型*/
        protected class DistItem
        {
            public int row;
            public int col;
            public int dist;
        }
        /**　距離マップ用の配列*/
        protected DistItem[] _map;
        /**　ワーク変数*/
        protected int _min_dist;
        /**　ワーク変数*/
        protected int _min_dist_index;
        /**　ワーク変数*/
        protected int _size_row;
        /**　ワーク変数*/
        protected int _size_col;
        /**
         * コンストラクタです。
         * マップの最大サイズを指定して、インスタンスを作成します。
         * @param i_max_col
         * マップの最大列数
         * @param i_max_row
         * マップの最大行数
         */
        public NyARDistMap(int i_max_col, int i_max_row)
        {
            this._min_dist = int.MaxValue;
            this._min_dist_index = 0;
            this._size_col = i_max_col;
            this._size_row = i_max_row;
            this._map = new DistItem[i_max_col * i_max_row];
            for (int i = 0; i < i_max_col * i_max_row; i++)
            {
                this._map[i] = new DistItem();
            }
        }
        /**
         * この関数は、マップのサイズを指定します。
         * 値は初期化されません。
         * @param i_col
         * 新しい列数。
         * @param i_row
         * 新しい行数。
         */
        public void setMapSize(int i_col, int i_row)
        {
            this._size_row = i_row;
            this._size_col = i_col;
        }
        /**
         * この関数は、列と行を指定して、距離値1個をマップにセットします。
         * <p>注意 -
         * このAPIは低速です。性能が必要な時は、{@link #setPointDists}を参考に、一括書込みする関数を検討してください。
         * </p>
         * @param i_col
         * 列のインデクスを指定します。
         * @param i_row
         * 行のインデクスを指定します。
         * @param i_dist
         * その行と列の距離値を指定します。
         */
        public void setDist(int i_col, int i_row, int i_dist)
        {
            this._min_dist_index = this._size_col * i_row + i_col;
            DistItem item = this._map[this._min_dist_index];
            item.col = i_col;
            item.row = i_row;
            item.dist = i_dist;
            //最小値・最大値の再計算
            if (i_dist < this._min_dist)
            {
                this._min_dist = i_dist;
            }
            return;
        }
        /**
         * この関数は、２つの座標点配列同士の距離値を一括してマップにセットします。
         * <p>
         * 実装メモ - 
         * 点のフォーマットが合わない場合は、この関数参考にオーバーロードしてください。
         * </p>
         * @param i_vertex_r
         * 比較する頂点群を格納した配列。
         * @param i_row_len
         * i_vertex_rの有効な要素数
         * @param i_vertex_c
         * 基準となる頂点群を格納した配列
         * @param i_col_len
         * i_vertex_cの有効な要素数
         */
        public void setPointDists(NyARIntPoint2d[] i_vertex_r, int i_row_len, NyARIntPoint2d[] i_vertex_c, int i_col_len)
        {
            DistItem[] map = this._map;
            //distortionMapを作成。ついでに最小値のインデクスも取得
            int min_index = 0;
            int min_dist = int.MaxValue;
            int idx = 0;
            for (int r = 0; r < i_row_len; r++)
            {
                for (int c = 0; c < i_col_len; c++)
                {
                    map[idx].col = c;
                    map[idx].row = r;
                    int d = i_vertex_r[r].sqDist(i_vertex_c[c]);
                    map[idx].dist = d;
                    if (min_dist > d)
                    {
                        min_index = idx;
                        min_dist = d;
                    }
                    idx++;
                }
            }
            this._min_dist = min_dist;
            this._min_dist_index = min_index;
            this._size_col = i_col_len;
            this._size_row = i_row_len;
            return;
        }
        /**
         * この関数は、現在の距離マップから、col要素に対するrow要素の組合せを計算します。
         * colに対して適したrow要素が見つからない場合は、o_rowindexの該当要素に-1を設定します。
         * この関数は内部データを不可逆に変更します。計算後は、距離マップの再セットが必要です。
         * @param o_rowindex
         * 組合せを受け取る配列です。
         * col[n]に対するrow[m]のインデクス番号mを、o_rowindex[n]に返します。
         */
        public void getMinimumPair(int[] o_rowindex)
        {
            DistItem[] map = this._map;
            int map_length = this._size_col * this._size_row;
            int col_len = this._size_col;
            //[0]と差し替え
            DistItem temp_map;
            temp_map = map[0];
            map[0] = map[this._min_dist_index];
            map[this._min_dist_index] = temp_map;
            for (int i = 0; i < o_rowindex.Length; i++)
            {
                o_rowindex[i] = -1;
            }
            if (map_length == 0)
            {
                return;
            }
            //値の保管
            o_rowindex[map[0].col] = map[0].row;

            //ソートして、0番目以降のデータを探す
            for (int i = 1; i < col_len; i++)
            {
                int min_index = 0;
                //r,cのものを除外しながら最小値を得る。
                int reject_c = map[i - 1].col;
                int reject_r = map[i - 1].row;
                int min_dist = int.MaxValue;
                if (1 >= map_length - col_len)
                {
                    break;
                }
                for (int i2 = i; i2 < map_length; )
                {
                    //除外条件？
                    if (map[i2].col == reject_c || map[i2].row == reject_r)
                    {
                        //非検索対象→インスタンスの差し替えと、検索長の減算
                        temp_map = map[i2];
                        map[i2] = map[map_length - 1];
                        map[map_length - 1] = temp_map;
                        map_length--;
                    }
                    else
                    {
                        int d = map[i2].dist;
                        if (min_dist > d)
                        {
                            min_index = i2;
                            min_dist = d;
                        }
                        i2++;
                    }
                }
                //[i]の値の差し替え
                temp_map = map[i];
                map[i] = map[min_index];
                map[min_index] = temp_map;
                //値の保管
                o_rowindex[map[i].col] = map[i].row;
            }
            return;
        }
    }
}