/* puzzle_state.h -- an 8-puzzle state. -*- c++ -*-
   Copyright (C) 2007  Casey Marshall <csm@soe.ucsc.edu> */


#ifndef __puzzle_state_h__
#define __puzzle_state_h__

#include <google/sparse_hash_map>
#include <iostream>
#include <sstream>
#include <string>

#define BLANK 9

class puzzle_state
{
public:
  unsigned char state[9];

  puzzle_state()
  {
    memset (state, 0, 9);
  }

  puzzle_state(unsigned char state[9])
  {
    memcpy (this->state, state, 9);
  }

  puzzle_state(puzzle_state& s)
  {
    memcpy (this->state, s.state, 9);
  }

  puzzle_state(const puzzle_state& s)
  {
    memcpy (this->state, s.state, 9);
  }

  bool equal_to (const puzzle_state& s) const
  {
    return memcmp (state, s.state, sizeof (state)) == 0;
  }

  std::string to_id() const
  {
    std::ostringstream s;
    s << "n"
      << (int) state[0]
      << (int) state[1]
      << (int) state[2]
      << (int) state[3]
      << (int) state[4]
      << (int) state[5]
      << (int) state[6]
      << (int) state[7]
      << (int) state[8];
    return s.str();
  }
};

inline std::ostream &
operator<<(std::ostream& out, const puzzle_state& state)
{
  out << "("
      << ((int) state.state[0]) << ", "
      << ((int) state.state[1]) << ", "
      << ((int) state.state[2]) << ", "
      << ((int) state.state[3]) << ", "
      << ((int) state.state[4]) << ", "
      << ((int) state.state[5]) << ", "
      << ((int) state.state[6]) << ", "
      << ((int) state.state[7]) << ", "
      << ((int) state.state[8]) << ")";
  return out;
}

struct puzzle_hash : __gnu_cxx::hash<const puzzle_state>
{
  size_t operator()(const puzzle_state& s) const
  {
    return ((s.state[0] << 24) ^ (s.state[1] << 16)
            ^ (s.state[2] <<  8) ^ (s.state[3])
            ^ (s.state[4] << 24) ^ (s.state[5] << 16)
            ^ (s.state[6] <<  8) ^ (s.state[7])
            ^ (s.state[8]));
  }
};

struct puzzle_equal : std::equal_to<const puzzle_state>
{
  bool operator()(const puzzle_state& s1, const puzzle_state& s2) const
  {
    return s1.equal_to (s2);
  }
};

typedef google::sparse_hash_map<puzzle_state, unsigned int, puzzle_hash, puzzle_equal> state_map;

int edge_distance(puzzle_state& state);
int manhattan_distance(puzzle_state& state, bool withBlank=true);
int neighbor_distance(puzzle_state& state, bool withBlank=true);

#endif // __puzzle_state_h__