/* -*- 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/invalid.h>

 #include <lemon/utility.h>

 #include <lemon/error.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 node(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::StaticGraph

   /// 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(_values[n], _first_value);

 	  }

 	  id >>= 1;

 	  ++n;

 	}

 	return val;

       }

     private:

       const Graph& _graph;

       std::vector<T> _values;

       T _first_value;

       BF _bin_func;

     };    

   };

 }

 #endif