/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2006

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef HYPERCUBE_GRAPH_H

#define HYPERCUBE_GRAPH_H

#include <iostream>

#include <vector>

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/error.h>

#include <lemon/bits/base_extender.h>

#include <lemon/bits/graph_extender.h>

///\ingroup graphs

///\file

///\brief HyperCubeGraph class.

namespace lemon {

  /// \brief Base graph for HyperCubeGraph.

  ///

  /// Base graph for hyper-cube graph. It describes some member functions

  /// which can be used in the HyperCubeGraph.

  ///

  /// \warning Always use the HyperCubeGraph instead of this.

  /// \see HyperCubeGraph

  class HyperCubeGraphBase {

  public:

    typedef HyperCubeGraphBase Graph;

    class Node;

    class Edge;

  public:

    HyperCubeGraphBase() {}

  protected:

    /// \brief Creates a hypercube graph with the given size.

    ///

    /// Creates a hypercube graph with the given size.

    void construct(int dim) {

      _dim = dim;

      _nodeNum = 1 << dim;

    }

  public:

    typedef True NodeNumTag;

    typedef True EdgeNumTag;

    ///Number of nodes.

    int nodeNum() const { return _nodeNum; }

    ///Number of edges.

    int edgeNum() const { return _nodeNum * _dim; }

    /// Maximum node ID.

    /// Maximum node ID.

    ///\sa id(Node)

    int maxNodeId() const { return nodeNum() - 1; }

    /// Maximum edge ID.

    /// Maximum edge ID.

    ///\sa id(Edge)

    int maxEdgeId() const { return edgeNum() - 1; }

    /// \brief Gives back the source node of an edge.

    ///    

    /// Gives back the source node of an edge.

    Node source(Edge e) const {

      return e.id / _dim;

    }

    /// \brief Gives back the target node of an edge.

    ///    

    /// Gives back the target node of an edge.

    Node target(Edge e) const {

      return (e.id / _dim) ^ ( 1 << (e.id % _dim));

    }

    /// Node ID.

    /// The ID of a valid Node is a nonnegative integer not greater than

    /// \ref maxNodeId(). The range of the ID's is not surely continuous

    /// and the greatest node ID can be actually less then \ref maxNodeId().

    ///

    /// The ID of the \ref INVALID node is -1.

    ///\return The ID of the node \c v. 

    static int id(Node v) { return v.id; }

    /// Edge ID.

    /// The ID of a valid Edge is a nonnegative integer not greater than

    /// \ref maxEdgeId(). The range of the ID's is not surely continuous

    /// and the greatest edge ID can be actually less then \ref maxEdgeId().

    ///

    /// The ID of the \ref INVALID edge is -1.

    ///\return The ID of the edge \c e. 

    static int id(Edge e) { return e.id; }

    static Node nodeFromId(int id) { return Node(id);}

    static Edge edgeFromId(int id) { return Edge(id);}

    class Node {

      friend class HyperCubeGraphBase;

    protected:

      int id;

      Node(int _id) { id = _id;}

    public:

      Node() {}

      Node (Invalid) { id = -1; }

      bool operator==(const Node node) const {return id == node.id;}

      bool operator!=(const Node node) const {return id != node.id;}

      bool operator<(const Node node) const {return id < node.id;}

    };

    class Edge {

      friend class HyperCubeGraphBase;

    protected:

      int id; 

      Edge(int _id) : id(_id) {}

    public:

      Edge() { }

      Edge (Invalid) { id = -1; }

      bool operator==(const Edge edge) const {return id == edge.id;}

      bool operator!=(const Edge edge) const {return id != edge.id;}

      bool operator<(const Edge edge) const {return id < edge.id;}

    };

    void first(Node& node) const {

      node.id = nodeNum() - 1;

    }

    static void next(Node& node) {

      --node.id;

    }

    void first(Edge& edge) const {

      edge.id = edgeNum() - 1;

    }

    static void next(Edge& edge) {

      --edge.id;

    }

    void firstOut(Edge& edge, const Node& node) const {

      edge.id = node.id * _dim;

    }

    void nextOut(Edge& edge) const {

      ++edge.id;

      if (edge.id % _dim == 0) edge.id = -1;

    }

    void firstIn(Edge& edge, const Node& node) const {

      edge.id = (node.id ^ 1) * _dim;

    }

    void nextIn(Edge& edge) const {

      int cnt = edge.id % _dim;

      if ((cnt + 1) % _dim == 0) {

	edge.id = -1;

      } else {

	edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; 

      }

    }

    /// \brief Gives back the number of the dimensions.

    ///

    /// Gives back the number of the dimensions.

    int dimension() const {

      return _dim;

    }

    /// \brief Returns true if the n'th bit of the node is one.

    ///

    /// Returns true if the n'th bit of the node is one. 

    bool projection(Node node, int n) const {

      return (bool)(node.id & (1 << n));

    }

    /// \brief The dimension id of the edge.

    ///

    /// It returns the dimension id of the edge. It can

    /// be in the ${0, 1, dim-1}$ intervall.

    int dimension(Edge edge) const {

      return edge.id % _dim;

    }

    /// \brief Gives back the index of the node.

    ///

    /// Gives back the index of the node. The lower bits of the

    /// integer describe the node.

    int index(Node node) const {

      return node.id;

    }

    /// \brief Gives back the node by its index.

    ///

    ///  Gives back the node by its index.

    Node operator()(int index) const {

      return Node(index);

    }

  private:

    int _dim, _nodeNum;

  };

  typedef GraphExtender<HyperCubeGraphBase> ExtendedHyperCubeGraphBase;

  /// \ingroup graphs

  ///

  /// \brief HyperCube graph class

  ///

  /// This class implements a special graph type. The nodes of the

  /// graph can be indiced with integers with at most \c dim binary length.

  /// Two nodes are connected in the graph if the indices differ only

  /// on one position in the binary form. 

  ///

  /// \note The type of the \c ids is chosen to \c int because efficiency

  /// reasons. This way the maximal dimension of this implementation

  /// is 26. 

  ///

  /// The graph type is fully conform to the \ref concept::Graph

  /// concept but it does not conform to the \ref concept::UGraph.

  ///

  /// \see HyperCubeGraphBase

  /// \author Balazs Dezso

  class HyperCubeGraph : public ExtendedHyperCubeGraphBase {

  public:

    /// \brief Construct a graph with \c dim dimension.

    ///

    /// Construct a graph with \c dim dimension.

    HyperCubeGraph(int dim) { construct(dim); }

    /// \brief Linear combination map.

    ///

    /// It makes possible to give back a linear combination

    /// for each node. This function works like the \c std::accumulate

    /// so it accumulates the \c bf binary function with the \c fv

    /// first value. The map accumulates only on that dimensions where

    /// the node's index is one. The accumulated values should be

    /// given by the \c begin and \c end iterators and this range's length

    /// should be the dimension number of the graph.

    /// 

    ///\code

    /// const int DIM = 3;

    /// HyperCubeGraph graph(DIM);

    /// xy<double> base[DIM];

    /// for (int k = 0; k < DIM; ++k) {

    ///   base[k].x = rand() / (RAND_MAX + 1.0);

    ///   base[k].y = rand() / (RAND_MAX + 1.0);

    /// } 

    /// HyperCubeGraph::HyperMap<xy<double> > 

    ///   pos(graph, base, base + DIM, xy<double>(0.0, 0.0));

    ///\endcode

    ///

    /// \see HyperCubeGraph

    template <typename T, typename BF = std::plus<T> >

    class HyperMap {

    public:

      typedef Node Key;

      typedef T Value;

      /// \brief Constructor for HyperMap. 

      ///

      /// Construct a HyperMap for the given graph. The accumulated values 

      /// should be given by the \c begin and \c end iterators and this 

      /// range's length should be the dimension number of the graph.

      ///

      /// This function accumulates the \c bf binary function with 

      /// the \c fv first value. The map accumulates only on that dimensions 

      /// where the node's index is one.           

      template <typename It>

      HyperMap(const Graph& graph, It begin, It end, 

		   T fv = 0.0, const BF& bf = BF()) 

	: _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {

	LEMON_ASSERT(_values.size() == graph.dimension(), 

		     "Wrong size of dimension");

      }

      /// \brief Gives back the partial accumulated value.

      ///

      /// Gives back the partial accumulated value.

      Value operator[](Key k) const {

	Value val = _first_value;

	int id = _graph.index(k); 

	int n = 0;

	while (id != 0) {

	  if (id & 1) {

	    val = _bin_func(val, _values[n]);

	  }

	  id >>= 1;

	  ++n;

	}

	return val;

      }

    private:

      const Graph& _graph;

      std::vector<T> _values;

      T _first_value;

      BF _bin_func;

    };    

  };

}

#endif