#ifndef GGAFCORE_GGAFLINEARTREEROUNDER_H_
#define GGAFCORE_GGAFLINEARTREEROUNDER_H_
#include "GgafCommonHeader.h"
#include "jp/ggaf/core/GgafObject.h"

#include "jp/ggaf/core/util/GgafLinearOctree.h"
#include "jp/ggaf/core/util/GgafTreeSpace.hpp"

namespace GgafCore {

#define MAX_COLLISIONSTACK_ACTOR_NUM (2000)
/**
 * Tを要素とし当たり判定機能を追加した線形八分木または四分木の各要素に処理を行う .
 * @version 1.00
 * @since 2009/11/23
 * @author Masatoshi Tsuge
 */
template<class T, uint32_t DIMENSION>
class GgafLinearTreeRounder : public GgafObject {

    uint32_t _num_space_minus_one;

public:
    /**
     * 当たり判定アクターを保持するスタック .
     * 速さの事しか考えてない危険なスタック
     */
    class TStack {
    public:
        /** [r]一つの空間にスタックするアクターの配列。使用するのは[0]〜[MAX_COLLISIONSTACK_ACTOR_NUM-1]。+1は、最後の要素を番兵にしている */
        T* _apT[MAX_COLLISIONSTACK_ACTOR_NUM+1]; //最後の要素(+1)は番兵
        /** [r]カーソルポインタ(次にPUSH出来る要素を指している)  */
        T** _papCur;
        /** [r]常にスタックの先頭要素を指している */
        T** _papFirst;
        /** [r]常にスタックの最後の要素の次を指している */
        T** _papBanpei;
    public:
        /**
         * コンストラクタ
         * @return
         */
        TStack() {
            _papFirst = &_apT[0];
            _papBanpei = &_apT[MAX_COLLISIONSTACK_ACTOR_NUM];
            _papCur = _papFirst;
        }
        /**
         * スタックに積む .
         * @param prm_pT 積むアクター
         */
        inline void push(T* prm_pObject) {
            if (_papCur == _papBanpei) {
                _TRACE_("＜警告＞ GgafLinearTreeRounder::push("<<prm_pObject<<") スタックを使い切りました。無視します。一箇所に当たり判定が塊過ぎです。");
                return;
            }
            (*_papCur) = prm_pObject;
            ++_papCur;
        }

        /**
         * スタックから取り出す .
         * @return 取り出されたアクター
         */
        inline T* pop() {
            if (_papCur == _papFirst) {
                return nullptr;
            } else {
                --_papCur;
                return (*_papCur);
            }
        }

        inline bool isExist() {
            return _papCur == _papFirst ? false : true;
        }

        /**
         * 引数のスタックから全て取り出し(pop)、出来る限り自身のスタックに積む(push) .
         * 引数のスタックは、必ず空になる。
         * @param prm_pTStack
         */
        inline void popush(TStack* prm_pTStack) {
            if (_papCur == _papBanpei) {
                _TRACE_("＜警告＞ GgafLinearTreeRounder::popush("<<prm_pTStack<<") スタックを使い切ってます。無視します。一箇所に当たり判定が塊過ぎです。");
                prm_pTStack->clear();
                return;
            }
            while ((*_papCur) = prm_pTStack->pop()) { //代入。pop出来なければ nullptr。 I know "=" , not "=="
                 ++_papCur;
                 if (_papCur == _papBanpei) {
                    _TRACE_("＜警告＞ GgafLinearTreeRounder::popush("<<prm_pTStack<<") スタックを使い切りました。無視します。一箇所に当たり判定が塊過ぎです。");
                    prm_pTStack->clear();
                    break;
                }
            }
        }
        /**
         * 積んだスタックをなかった事にする。 .
         */
        inline void clear() {
            _papCur = _papFirst;
        }
        ~TStack() {
            clear();
        }
    };

    GgafTreeSpace<DIMENSION>* _paTargetSpace;
    /** [r]全空間の当たり判定時、現在の空間に所属するアクター種別Aグループのスタック */
    TStack _stackGroupA_Current;
    /** [r]全空間の当たり判定時、現在の空間に所属するアクター種別Bグループのスタック */
    TStack _stackGroupB_Current;
    /** [r]ある空間の当たり判定時、それよりも親空間に所属した全アクター種別Aグループのスタック */
    TStack _stackGroupA;
    /** [r]ある空間の当たり判定時、それよりも親空間に所属した全アクター種別Bグループのスタック */
    TStack _stackGroupB;

    /** [r]今回当たり判定を行うアクター種別A */
    actorkind _kind_groupA;
    /** [r]今回当たり判定を行うアクター種別B */
    actorkind _kind_groupB;
    /** [r]実行するTのメンバ関数 */
    void (T::*_pFunc)(T*);

public:
    /**
     * コンストラクタ
     * @param prm_level 作成する八分木空間レベル
     */
    GgafLinearTreeRounder(GgafTreeSpace<DIMENSION>* prm_paTargetSpace, int prm_num_space, void (T::*prm_pFunc)(T*)) {
        _paTargetSpace = prm_paTargetSpace;
        _num_space_minus_one = prm_num_space;
        _pFunc = prm_pFunc;
        _kind_groupA = 0;
        _kind_groupB = 0;
    }

    /**
     * 八分木所属の「アクター種別Aグループ 対 アクター種別Bグループ」を行う  .
     * アプリ側は本メソッドを呼ぶだけでよい。<BR>
     * ただし executeAllHitChk は processJudgement() で呼ぶ必要あり。<BR>
     * @param prm_kind_groupA アクター種別Aグループ
     * @param prm_kind_groupB アクター種別Bグループ
     */
    void executeAll(actorkind prm_kind_groupA, actorkind prm_kind_groupB) {
        _kind_groupA = prm_kind_groupA;
        _kind_groupB = prm_kind_groupB;
        if ( (_paTargetSpace[0]._kind_bit_field & prm_kind_groupA) && (_paTargetSpace[0]._kind_bit_field & prm_kind_groupB) ) {
            //では八分木を巡る旅へ行ってらっしゃい
            execute(0); //いってきます
            //はいお帰りなさい。
            _stackGroupA.clear();
            _stackGroupB.clear();
        }
    }

    /**
     * 引数の空間の当たり判定を行う  .
     * executeAllHitChk から使用される。
     * @param prm_index 線形八分木配列の配列要素番号
     */
    void execute(uint32_t prm_index) {
        GgafTreeSpace<DIMENSION>* pOctant_this_level = &(_paTargetSpace[prm_index]);
        GgafTreeElem<DIMENSION>* pElem = pOctant_this_level->_pElem_first;
        const actorkind kind_groupA = _kind_groupA;
        const actorkind kind_groupB = _kind_groupB;
        if (pElem) {
            GgafTreeElem<DIMENSION>* pElem_last = pOctant_this_level->_pElem_last;
            while (true) {
                if (pElem->_kindbit & kind_groupA) {
                    _stackGroupA_Current.push((T*)(pElem->_pObject));
                }
                if (pElem->_kindbit & kind_groupB) {
                    _stackGroupB_Current.push((T*)(pElem->_pObject));
                }
                if (pElem == pElem_last) {
                    break;
                }
                pElem = pElem->_pNext;
            }
            //現在の空間のグループAとグループB総当り
            executeRoundRobin(&_stackGroupA_Current, &_stackGroupB_Current);
            //現在の空間のグループAと親空間所属のグループB総当り
            executeRoundRobin(&_stackGroupA_Current, &_stackGroupB );
            //親空間所属のグループAと現在の空間のグループB総当り
            executeRoundRobin(&_stackGroupA , &_stackGroupB_Current);
        }
        const uint32_t lower_level_index = (prm_index<<DIMENSION) + 1; //_papOctant[prm_index] 空間の子空間のモートン順序位置0番の配列要素番号
        if ( lower_level_index > _num_space_minus_one) {
            //要素数オーバー、つまりリーフ
            _stackGroupA_Current.clear();
            _stackGroupB_Current.clear();
            return; //親空間へ戻る
        } else {

            //もぐる。が、その前に現空間アクターを親空間アクターのスタックへ追加。
            //もぐった空間から見た場合の親空間アクター累計を作っておいてやる。
            //(同時に現空間スタックも開放)
            T** temp_stackGroupA = _stackGroupA._papCur; //スタックポインタ保存(潜った後のリセットに使用)
            T** temp_stackGroupB = _stackGroupB._papCur; //スタックポインタ保存(潜った後のリセットに使用)
            _stackGroupA.popush(&_stackGroupA_Current); //Current を Parent に追加。同時にCurrentはクリアされる。
            _stackGroupB.popush(&_stackGroupB_Current); //Current を Parent に追加。同時にCurrentはクリアされる。
            bool isExistGroupA = _stackGroupA.isExist();
            bool isExistGroupB = _stackGroupB.isExist();

            //ヒットチェックを行いに、子空間(８個)へ潜りに行こう〜。
            //次のレベルの空間に種別AとBが登録されていれば潜る。
            //又は、次のレベルの空間に種別Aがあり、かつストックに種別Bがあれば潜る。
            //又は、次のレベルの空間に種別Bがあり、かつストックに種別Aがあれば潜る。
            //それ以外は潜らない
            GgafTreeSpace<DIMENSION>* pOctant_lower_level = &(_paTargetSpace[lower_level_index]);
            actorkind kind_bit_field_lower_level = pOctant_lower_level->_kind_bit_field;
            if (kind_bit_field_lower_level & kind_groupA) {
                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
                    execute(lower_level_index);
                }
            } else if (kind_bit_field_lower_level & kind_groupB) {
                if (isExistGroupA) {
                    execute(lower_level_index);
                }
            }


            for (int i = 1; i < (1<<DIMENSION); i++) {
                kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
                if (kind_bit_field_lower_level & kind_groupA) {
                    if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
                        execute(lower_level_index+i);
                    }
                } else if (kind_bit_field_lower_level & kind_groupB) {
                    if (isExistGroupA) {
                        execute(lower_level_index+i);
                    }
                }
            }




            //ヒットチェックを行いに、子空間(８個)へ潜りに行こう〜。
            //次のレベルの空間に種別AとBが登録されていれば潜る。
            //又は、次のレベルの空間に種別Aがあり、かつストックに種別Bがあれば潜る。
            //又は、次のレベルの空間に種別Bがあり、かつストックに種別Aがあれば潜る。
            //それ以外は潜らない
//            GgafTreeSpace<DIMENSION>* pOctant_lower_level = &(_paTargetSpace[lower_level_index]);
//            uint32_t kind_bit_field_lower_level = pOctant_lower_level->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+1);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+1);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+2);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+2);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+3);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+3);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+4);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+4);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+5);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+5);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+6);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+6);
//                }
//            }
//
//            kind_bit_field_lower_level = (++pOctant_lower_level)->_kind_bit_field;
//            if (kind_bit_field_lower_level & kind_groupA) {
//                if (isExistGroupB || (kind_bit_field_lower_level & kind_groupB)) {
//                    execute(lower_level_index+7);
//                }
//            } else if (kind_bit_field_lower_level & kind_groupB) {
//                if (isExistGroupA) {
//                    execute(lower_level_index+7);
//                }
//            }

            //お帰りなさい
            //スタックの解放（pushした分、元に戻す）
            _stackGroupA._papCur = temp_stackGroupA;
            _stackGroupB._papCur = temp_stackGroupB;
            return; //親空間へ戻る
        }
    }
    /**
     * アクター種別Aグループのスタックと、アクター種別Bグループのスタックの総当りの当たり判定を行う  .
     * executeHitChk から使用される。
     * @param prm_pStackA アクター種別Aグループのスタック
     * @param prm_pStackB アクター種別Bグループのスタック
     */
    void executeRoundRobin(TStack* prm_pStackA, TStack* prm_pStackB) {
        //GgafLinearTreeRounderでは、要素の指す(GgafObject*)インスタンスは Tが前提
        if (prm_pStackA->isExist() && prm_pStackB->isExist()) {
            void (T::*pFunc)(T*) = _pFunc;
            T** papStackT_A_Cur = prm_pStackA->_papCur;
            T** papStackT_B_Cur = prm_pStackB->_papCur;
            T** papStackT_A = prm_pStackA->_papFirst;
            while (papStackT_A != papStackT_A_Cur) {
                T** papStackT_B = prm_pStackB->_papFirst;
                while (papStackT_B != papStackT_B_Cur) {
                    ((*papStackT_A)->*pFunc)(*papStackT_B);
                    ++papStackT_B;
                }
                ++papStackT_A;
            }
        }
    }

    virtual ~GgafLinearTreeRounder() {
    }
};


}
#endif /*GGAFCORE_GGAFLINEARTREEROUNDER_H_*/

