#ifndef __OTHELLO_H__
#define __OTHELLO_H__

#include <exception>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <limits>

using namespace std;

class OthelloException: public exception{
  protected:
    string what_str;  ///< エラー内容
  public:
    
    OthelloException(const string &what_arg)
        : what_str(what_arg){}
    
    ~OthelloException() throw() {}
    
    const char *what() const throw(){
      return what_str.c_str(); 
    }
};

class Othello {
  public:
    class Stone {
      protected:
        const char *_str;
        const int _serial;
      public:
        Stone *_reverse;
        Stone(
            const char *str,
            const int serial) 
            : _str(str), _serial(serial), _reverse(NULL){}
        ~Stone(){}
        Stone *reverse() const {
          return _reverse;
        }
        const char *to_s() const {
          return _str;
        }
        const int to_i() const {
          return _serial;
        }
    };
    
  public:
    const class StoneHolder {
      protected :
        Stone singleton_black;
        Stone singleton_white;
        Stone singleton_empty;
      public:
        const Stone *black() const {
          return &singleton_black;
        }
        const Stone *white() const {
          return &singleton_white;
        }
        const Stone *empty() const {
          return &singleton_empty;
        }
      public :
        StoneHolder() 
            : singleton_black("●",  1),
              singleton_white("○", -1),
              singleton_empty("  ",  0){
          singleton_black._reverse = &singleton_white;
          singleton_white._reverse = &singleton_black;
          singleton_empty._reverse = &singleton_empty;
        }
        ~StoneHolder(){}
    } stone_holder;
    
  public:
    class Board {
      protected:
        int _size;
        Stone **elements;
        int *elements_ref; // 参照カウンタ
      public:
        virtual Stone &operator()(const int i, const int j){
          return *elements[i * _size + j];
        }
        virtual Stone *get(const int i, const int j) const {
          return elements[i * _size + j];
        }
        virtual Stone *set(const int i, const int j, const Stone *stone){
          return (elements[i * _size + j] = const_cast<Stone *>(stone));
        }
      public:
        Board(int size)
            : _size(size),
              elements(new Stone *[_size * _size]),
              elements_ref(new int(1)) {
        }
        // copy const => shallow copy
        Board(const Board &board)
            : _size(board._size),
              elements(board.elements),
              elements_ref(board.elements_ref) {
          (*elements_ref)++;
        }
        virtual ~Board(){
          if(elements_ref && (--(*elements_ref) <= 0)){
            delete elements_ref;
            delete [] elements;
          }
        }
        Board &operator=(const Board &board){
          if(this->elements != board.elements){
            if(elements_ref && (--(*elements_ref) <= 0)){
              delete elements_ref;
              delete [] elements;
            }
            if(elements = board.elements){
              (*(elements_ref = board.elements_ref))++;
            }
          }
          return *this;
        }
        Board clone() const {
          Board b(size());
          for(int i = 0; i < b.size(); i++){
            for(int j = 0; j < b.size(); j++){
              b.set(i, j, get(i, j));
            }
          }
          return b;
        }
        const int size() const{return _size;}
        bool valid_cordinate(const int i, const int j) const{
          return !((i < 0) || (i >= _size) || (j < 0) || (j >= _size)); 
        }
        
        template <class Functor>
        void all_map(Functor &f) const {
          for(int i = 0; i < _size; i++){
            for(int j = 0; j < _size; j++){
              f(i, j, get(i, j));
            }
          }
        }
        template <class Functor>
        void all_set(Functor &f) const {
          for(int i = 0; i < _size; i++){
            for(int j = 0; j < _size; j++){
              set(i, j, f(i, j, get(i, j)));
            }
          }
        }
        
      protected:
        struct StoneCounter{
          int count;
          const Stone *_target;
          StoneCounter(const Stone *target) 
              : count(0), _target(target) {}
          void operator()(
              const int i,
              const int j,
              const Stone *stone) {
            if(stone == _target) count++;
          }
        };
      public:
        int stone_count(const Stone *target) const {
          StoneCounter counter(target);
          all_map(counter);
          return counter.count;
        }
        
        template <class Functor>
        void directional_map(
            int i, int j,
            const int down, const int right, 
            Functor &f) const {
          int move(0);
          while(true){
            i += down;
            if((i < 0) || (i >= size())){break;}
            j += right;
            if((j < 0) || (j >= size())){break;}
            if(!f(i, j, get(i, j), ++move)){break;}
          }
        }
        
        template <class Functor>
        void directional_set(
            int i, int j,
            const int down, const int right, 
            Functor &f){
          int move(0);
          while(true){
            i += down;
            if((i < 0) || (i >= size())){break;}
            j += right;
            if((j < 0) || (j >= size())){break;}
            Stone *stone(f(i, j, get(i, j), ++move));
            if(!stone){break;}
            set(i, j, stone);
          }
        }
        
        ostream &serialize(ostream &out) const {
          out << size();
          for(int i = 0; i < size(); i++){
            for(int j = 0; j < size(); j++){
              out << " " << get(i, j)->to_i();
            }  
          }
          out << endl;
          return out;
        }
        static Board deserialize(
            const StoneHolder &holder, 
            istream &in){
          int _size;
          in >> _size;
          if(_size < 0){_size = 0;}
          Board b(_size);
          {
            int black_num(holder.black()->to_i());
            int white_num(holder.white()->to_i());
            const Stone *black(holder.black());
            const Stone *white(holder.white());
            const Stone *empty(holder.empty());
            for(int i = 0; i < _size; i++){
              for(int j = 0; j < _size; j++){
                int num;
                in >> num;
                if(num == black_num){
                  b.set(i, j, black);
                }else if(num == white_num){
                  b.set(i, j, white);
                }else{
                  b.set(i, j, empty);
                }
              }
            }
          }
          return b; 
        }
        
        friend ostream &operator<<(ostream &out, const Board &board){
          out << "×";
          for(int j = 0; j < board.size(); j++){
            out << "," << setw(2) << std::right << j;
          }
          out << endl;
          for(int i = 0; i < board.size(); i++){
            out << setw(2) << std::left << i;
            for(int j = 0; j < board.size(); j++){
              out << "," << board.get(i, j)->to_s();
            }
            out << endl;
          }
          return out;
        }
    };
  public:
    class State {
      protected:
        const StoneHolder &_holder;
        Stone *_next;
        Board _board;
        bool order_skipped; // 直前の一回、order_skipをしたかどうか
      public:
        const int init_upper() const {
          return _board.size() / 2;
        }
        const int init_lower() const {
          return init_upper() - 1;
        }
        State(int board_size, const StoneHolder &holder)
            : _holder(holder),
              _board(board_size),
              order_skipped(false) {
          _next = const_cast<Stone *>(_holder.black()); // 黒が先手
          for(int i = 0; i < _board.size(); i++){
            for(int j = 0; j < _board.size(); j++){
              _board.set(i, j, _holder.empty());
            }
          }
          {
            int upper(init_upper());
            int lower(init_lower());
            
            _board.set(lower, lower, _holder.white());
            _board.set(lower, upper, _holder.black());
            _board.set(upper, lower, _holder.black());
            _board.set(upper, upper, _holder.white());
          }
        }
        State(const State &state, bool deep_copy = false)
            : _holder(state._holder),
              _next(state._next),
              _board(deep_copy ? state._board.clone() : state._board),
              order_skipped(state.order_skipped){
          
        }
        ~State() {}
        
        const Board &board() const {return _board;}
        const Stone *next() const {return _next;}
        
        int black_stones() const {
          return _board.stone_count(_holder.black());
        }
        int white_stones() const {
          return _board.stone_count(_holder.white());
        }
        int blanks() const {
          return _board.stone_count(_holder.empty());
        }
        
        State *clone() const {
          return new State(*this, true);
        }
        
      protected:
        class MountingRule{
          protected:
            State *target;
            bool changed;
            MountingRule(State *current) 
                : target(current) {}
            static State *perform_1dir(
                State *state, const State *orig,
                const int i, const int j,
                const int down, const int right){
              MountingRule mounter(state->clone());
              mounter.changed = false;
              mounter.target->_board.directional_set(i, j, right, down, mounter);
              if(mounter.changed){
                if(state != orig){delete state;} // 中間要素の削除
                return mounter.target;
              }else{
                delete mounter.target;
                return state;
              }
            }
          public:
            Stone *operator()(
                const int i,
                const int j,
                const Stone *stone,
                const int move) {
              if(target->_holder.empty() == stone){return NULL;}
              if(target->next() == stone){
                if(move > 1){changed = true;}
                return NULL;
              }
              return stone->reverse();
            }
            
            static State *mount(
                const State *current,
                const int i, const int j){              
              State *state(const_cast<State *>(current));
              state = perform_1dir(state, current, i, j, -1,  0); //上
              state = perform_1dir(state, current, i, j,  1,  0); //下
              state = perform_1dir(state, current, i, j,  0, -1); //左
              state = perform_1dir(state, current, i, j,  0,  1); //右
              state = perform_1dir(state, current, i, j, -1,  1); //右上
              state = perform_1dir(state, current, i, j,  1,  1); //右下
              state = perform_1dir(state, current, i, j, -1, -1); //左上
              state = perform_1dir(state, current, i, j,  1, -1); //左下              
              return state;
            }
        };
      public:
        State *mount(const int i, const int j) const {
          if(_board.get(i, j) != _holder.empty()){return NULL;}
          
          State *after_mount(MountingRule::mount(this, i, j));
          if(this != after_mount){
            after_mount->_board.set(i, j, after_mount->_next);
            after_mount->_next = after_mount->_next->reverse();
            after_mount->order_skipped = false;
            return after_mount;
          }else{
            return NULL;
          }
        }
      protected:
        State *force_order_skip() const {
          State *state(clone());
          state->_next = state->_next->reverse();
          state->order_skipped = true;
          return state;
        }
      
      public:
        State *order_skip() const {
          for(int i = 0; i < _board.size(); i++){
            for(int j = 0; j < _board.size(); j++){
              State *mounted(mount(i, j));
              if(mounted){
                delete mounted;
                return NULL;
              }
            }
          }
          if(order_skipped || (blanks() == 0)){return NULL;}
          return force_order_skip();
        }
        
        struct candidate_t {
          int index;
          State *state;
        };
        
        class candidates_iterator_t
            : public iterator<input_iterator_tag, candidate_t>{
          protected:
            const State *_current;
            candidate_t next;
            int board_size;
            bool had_mount_place;
            candidates_iterator_t(const State *current, int index) 
                : _current(current), 
                  board_size(current->board().size()),
                  had_mount_place(false){
              next.index = index;
              next.state = NULL;
            }
          public:
            candidates_iterator_t &operator++() {
              delete next.state;
              next.state = NULL;
              while(++(next.index) < (board_size * board_size)){
                if(next.state = _current->mount(next.index / board_size, next.index % board_size)){
                  had_mount_place = true;
                  return *this;
                }
              }
              if(next.index == (board_size * board_size)){ 
                if((!had_mount_place) 
                    && (_current->blanks()) && !(_current->order_skipped)){
                  next.state = _current->force_order_skip();
                }else{
                  next.state = NULL;
                  ++(next.index);
                }
              }
              return *this;
            }
            candidates_iterator_t(const State *current) 
                : _current(current), 
                  board_size(current->board().size()),
                  had_mount_place(false) {
              next.index = -1;
              next.state = NULL;
              operator++();
            }
            static candidates_iterator_t end(const State *current) {
              int _board_size(current->board().size());
              return candidates_iterator_t(current, _board_size * _board_size + 1);
            }
            ~candidates_iterator_t(){
              delete next.state;
            }
            const candidate_t &operator*(){return next;}
            const candidate_t *operator->(){return &next;}
            bool operator!=(const candidates_iterator_t &it){
              return (next.index < it.next.index);
            }
        };
        
        candidates_iterator_t candidates_begin() const {
          return candidates_iterator_t(this); 
        }
        candidates_iterator_t candidates_end() const {
          return candidates_iterator_t::end(this); 
        }
        
        struct candidates_t : public map<int, State *>{
          typedef map<int, State *> super_t;
          candidates_t() : super_t() {}
          ~candidates_t(){
            for(super_t::iterator it = super_t::begin();
                it != super_t::end(); 
                it++){
              delete it->second;
            }
          }
        };
        candidates_t candidates() const {
          candidates_t res;
          for(candidates_iterator_t it(candidates_begin());
                it != candidates_end();
                ++it){
            res.insert(candidates_t::value_type(it->index, it->state));
            const_cast<State *>(it->state) = NULL; // delete防止
          }
          return res;
        }
        bool has_next() const {
          for(candidates_iterator_t it(candidates_begin());
                it != candidates_end();
                ++it){
            return true;
          }
          return false;
        }
        
        friend ostream &operator<<(ostream &out, const State &state){
          out << state.board();
          out << "NEXT: " << state.next()->to_s() << endl;
          return out;
        }
    };
    
  protected:
    typedef vector<State *> state_tree_t;
    state_tree_t state_tree;
  
  public:
    Othello(const int board_size)
        : stone_holder(),
          state_tree() {
      state_tree.push_back(new State(board_size, stone_holder)); 
    }
    ~Othello() {
      for(state_tree_t::iterator it(state_tree.begin());
          it < state_tree.end();
          it++){
        delete *it;
      }
      state_tree.clear();
    }
    
    /**
     * いくつ状態を経過したか返す関数
     * (初期状態では0が返却されることに注意)
     * 
     * @return 
     */
    int transit_count() const{
      return state_tree.size() - 1;
    }
    
    /**
     * 前の状態を取得する関数
     * 
     * @param step いくつ前の状態を取得するか、正の数で指定のこと
     * @return (const State &) step分だけ前の状態
     */
    const State &previous(int step = 1) const throw(OthelloException) {
      int state_tree_size(state_tree.size());
      int target_index(state_tree_size - step);
      if((state_tree_size <= 1) || (target_index < 0)){
        throw OthelloException("前の状態はありません");
      }
      return *(state_tree[target_index]);
    }
    
    const State &current() const {
      return *(state_tree.back());
    }
    
    /**
     * @return 遷移後の状態
     */
    Othello &mount(const int i, const int j)
        throw(OthelloException){
      while(true){
        if(!current().board().valid_cordinate(i, j)){break;}
        State *next(current().mount(i, j));
        if(next){
          state_tree.push_back(next);
          return *this;
        }
        break;
      }
      throw OthelloException("認められない手!!");
    }
    
    /**
     * @return 遷移後の状態
     */
    Othello &order_skip()
        throw(OthelloException){
      while(true){
        State *next(current().order_skip());
        if(next){
          state_tree.push_back(next);
          return *this;
        }
        break;
      }
      throw OthelloException("認められない手!!");
    }
    
    /**
     * current().candidates()で返された番号を元に次の手を決める
     */
    Othello &next(const int index){
      int board_size(current().board().size());
      if(index == board_size * board_size){
        return order_skip();
      }else{
        int i(index / board_size), j(index % board_size);
        return mount(i, j);
      }
    }
    
    /**
     * 
     * @return ロールバック後の状態
     */
    Othello &rollback(){
      if(state_tree.size() > 1){
        delete state_tree.back();
        state_tree.pop_back();
      }
      return *this;
    }
};

#endif