// A simple hierarchy, using hierarchy, shared_ptr and flyweight.
//
// When run, I get something like:
//
// a: 0x1:1
// b: 0x1:1
// a: 0x2:1
// b: 0x2:1
// a: 0x1:1
// b: 0x1:1
// bin: 0x3:(0x4:(0x2:1+0x2:1)*0x4:(0x2:1+0x2:1))

// which shows that (i), yes, the common values are shared (they have
// the same address), and (ii), yes, they are cleaned up (the
// addresses 0x1 and 0x2 show that the value "1" was represented at
// two different times with different addresses).

#include <iostream>
#include <functional> // std::hash
#include <map>
#include <memory>

#include <boost/flyweight.hpp>
#include <boost/functional/hash.hpp>

// http://stackoverflow.com/questions/2590677
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

// A means to name pointers, to be easier to read.
std::map<void*, int> addresses;
template <typename T>
int address(const T& t)
{
  auto p = addresses.emplace((void*)&t, 0);
  if (p.second)
    p.first->second = addresses.size();
  return p.first->second;
}


/*-------.
| Base.  |
`-------*/

struct Base
{
  virtual std::ostream& print(std::ostream& o) const = 0;
  virtual size_t hash() const = 0;
  virtual bool equals(const Base& rhs) const = 0;
};

std::ostream& operator<<(std::ostream& o, const Base& b)
{
  o << "0x" << address(b) << ":";
  return b.print(o);
}

bool operator==(const Base& l, const Base& r)
{
  auto res = l.equals(r);
#ifdef DEBUG
  std::cerr << l << (res ? " == " : " != ") << r << '\n';
#endif
  return res;
}

bool operator!=(const Base& l, const Base& r)
{
  return !(l == r);
}

namespace std
{
  template<>
  struct hash<Base>
  {
    size_t operator()(const Base& e) const
    {
      size_t res = e.hash();
#ifdef DEBUG
      std::cerr << res << " = hash(" << e << ")\n";
#endif
      return res;
    }
  };
}

std::size_t hash_value(const Base& b)
{
  return std::hash<Base>()(b);
}

/*-------.
| Exp_.  |
`-------*/

using Exp_ = std::shared_ptr<Base>;
namespace std
{
  template<>
  struct hash<Exp_>
  {
    size_t operator()(const Exp_& e) const
    {
      return hash_value(*e);
    }
  };
}

std::ostream& operator<<(std::ostream& o, const Exp_& b)
{
  return o << *b;
}

// Boost.Flyweight uses Boost's convention of an existing hash_value
// function, not C++'s std::hash.
std::size_t hash_value(const Exp_& b)
{
  return std::hash<Exp_>()(b);
}

bool operator==(const Exp_& l, const Exp_& r)
{
  return *l == *r;
}

bool operator!=(const Exp_& l, const Exp_& r)
{
  return !(l == r);
}



/*------.
| Exp.  |
`------*/

using Exp = boost::flyweight<Exp_>;



/*------.
| Bin.  |
`------*/

struct Bin: Base
{
  Bin(char o, Exp lhs, Exp rhs)
    : op(o)
    , l(lhs)
    , r(rhs)
  {}
  std::ostream& print(std::ostream& o) const
  {
    return o << "(" << l << op << r << ")";
  }
  size_t hash() const
  {
    size_t res = 0;
    hash_combine(res, boost::hash_value(op));
    hash_combine(res, l.get()->hash());
    hash_combine(res, r.get()->hash());
    return res;
  }
  bool equals(const Base& rhs_) const
  {
    if (auto rhs = dynamic_cast<const Bin*>(&rhs_))
      return (op == rhs->op
              && l == rhs->r
              && r == rhs->r);
    else
      return false;
  }

  char op;
  Exp l, r;
};

Exp bin(char op, Exp l, Exp r)
{
  return Exp(std::make_shared<Bin>(op, l, r));
}



/*------.
| Num.  |
`------*/
struct Num: Base
{
  Num(int v)
    : val(v)
  {}
  std::ostream& print(std::ostream& o) const
  {
    return o << val;
  }
  size_t hash() const
  {
    return boost::hash_value(val);
  }
  bool equals(const Base& rhs) const
  {
    if (auto r = dynamic_cast<const Num*>(&rhs))
      return val == r->val;
    else
      return false;
  }
  int val;
};

Exp num(int val)
{
  return Exp(std::make_shared<Num>(val));
}



/*-------.
| main.  |
`-------*/

int main()
{
  for (auto i: {1, 2, 3})
  {
    auto a = num(1);
    auto b = num(1);
    std::cout << "a: " << a << '\n';
    std::cout << "b: " << b << '\n';

#ifdef DEBUG
    std::cout << hash_value(*a.get())
              << ' ' << hash_value(*b.get())
              << ' ' << (a == b) << '\n';
    std::cout << a.get()->hash()
              << ' ' << b.get()->hash()
              << ' ' << (a == b) << '\n';
#endif
  }

  Exp e = bin('*',
              bin('+', num(1), num(1)),
              bin('+', num(1), num(1)));
  std::cout << "bin: " << e << '\n';
}