/* -*- 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 LEMON_FULL_BPUGRAPH_H

#define LEMON_FULL_BPUGRAPH_H

#include <cmath>

#include <lemon/bits/bpugraph_extender.h>

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

///\ingroup graphs

///\file

///\brief FullBpUGraph class.

namespace lemon {

  class FullBpUGraphBase {

  protected:

    int _aNodeNum;

    int _bNodeNum;

    int _edgeNum;

  public:

    class NodeSetError : public LogicError {

      virtual const char* exceptionName() const { 

	return "lemon::FullBpUGraph::NodeSetError";

      }

    };

    class Node {

      friend class FullBpUGraphBase;

    protected:

      int id;

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

    public:

      Node() {}

      Node(Invalid) { id = -1; }

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

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

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

    };

    class UEdge {

      friend class FullBpUGraphBase;

    protected:

      int id;

      UEdge(int _id) { id = _id;}

    public:

      UEdge() {}

      UEdge (Invalid) { id = -1; }

      bool operator==(const UEdge i) const {return id==i.id;}

      bool operator!=(const UEdge i) const {return id!=i.id;}

      bool operator<(const UEdge i) const {return id<i.id;}

    };

    void construct(int aNodeNum, int bNodeNum) {

      _aNodeNum = aNodeNum;

      _bNodeNum = bNodeNum;

      _edgeNum = aNodeNum * bNodeNum;

    }

    void firstANode(Node& node) const {

      node.id = 2 * _aNodeNum - 2;

      if (node.id < 0) node.id = -1; 

    }

    void nextANode(Node& node) const {

      node.id -= 2;

      if (node.id < 0) node.id = -1; 

    }

    void firstBNode(Node& node) const {

      node.id = 2 * _bNodeNum - 1;

    }

    void nextBNode(Node& node) const {

      node.id -= 2;

    }

    void first(Node& node) const {

      if (_aNodeNum > 0) {

	node.id = 2 * _aNodeNum - 2;

      } else {

	node.id = 2 * _bNodeNum - 1;

      }

    }

    void next(Node& node) const {

      node.id -= 2;

      if (node.id == -2) {

	node.id = 2 * _bNodeNum - 1;

      }

    }

    void first(UEdge& edge) const {

      edge.id = _edgeNum - 1;

    }

    void next(UEdge& edge) const {

      --edge.id;

    }

    void firstFromANode(UEdge& edge, const Node& node) const {

      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());

      edge.id = (node.id >> 1) * _bNodeNum;

    }

    void nextFromANode(UEdge& edge) const {

      ++(edge.id);

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

    }

    void firstFromBNode(UEdge& edge, const Node& node) const {

      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());

      edge.id = (node.id >> 1);

    }

    void nextFromBNode(UEdge& edge) const {

      edge.id += _bNodeNum;

      if (edge.id >= _edgeNum) edge.id = -1;

    }

    static int id(const Node& node) {

      return node.id;

    }

    static Node nodeFromId(int id) {

      return Node(id);

    }

    int maxNodeId() const {

      return _aNodeNum > _bNodeNum ? 

	_aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;

    }

    static int id(const UEdge& edge) {

      return edge.id;

    }

    static UEdge uEdgeFromId(int id) {

      return UEdge(id);

    }

    int maxUEdgeId() const {

      return _edgeNum - 1;

    }

    static int aNodeId(const Node& node) {

      return node.id >> 1;

    }

    static Node fromANodeId(int id) {

      return Node(id << 1);

    }

    int maxANodeId() const {

      return _aNodeNum;

    }

    static int bNodeId(const Node& node) {

      return node.id >> 1;

    }

    static Node fromBNodeId(int id) {

      return Node((id << 1) + 1);

    }

    int maxBNodeId() const {

      return _bNodeNum;

    }

    Node aNode(const UEdge& edge) const {

      return Node((edge.id / _bNodeNum) << 1);

    }

    Node bNode(const UEdge& edge) const {

      return Node(((edge.id % _bNodeNum) << 1) + 1);

    }

    static bool aNode(const Node& node) {

      return (node.id & 1) == 0;

    }

    static bool bNode(const Node& node) {

      return (node.id & 1) == 1;

    }

    static Node aNode(int index) {

      return Node(index << 1);

    }

    static Node bNode(int index) {

      return Node((index << 1) + 1);

    }

    typedef True NodeNumTag;

    int nodeNum() const { return _aNodeNum + _bNodeNum; }

    int aNodeNum() const { return _aNodeNum; }

    int bNodeNum() const { return _bNodeNum; }

    typedef True EdgeNumTag;

    int uEdgeNum() const { return _edgeNum; }

  };

  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;

  /// \ingroup graphs

  ///

  /// \brief An undirected full bipartite graph class.

  ///

  /// This is a simple and fast bipartite undirected full graph implementation.

  /// It is completely static, so you can neither add nor delete either

  /// edges or nodes.

  ///

  /// \sa FullUGraphBase

  /// \sa FullGraph

  ///

  /// \author Balazs Dezso

  class FullBpUGraph : 

    public ExtendedFullBpUGraphBase {

  public:

    typedef ExtendedFullBpUGraphBase Parent;

    FullBpUGraph() {

      Parent::construct(0, 0);

    }

    FullBpUGraph(int aNodeNum, int bNodeNum) {

      Parent::construct(aNodeNum, bNodeNum);

    }

    /// \brief Resize the graph

    ///

    void resize(int n, int m) {

      Parent::getNotifier(Edge()).clear();

      Parent::getNotifier(UEdge()).clear();

      Parent::getNotifier(Node()).clear();

      Parent::getNotifier(ANode()).clear();

      Parent::getNotifier(BNode()).clear();

      construct(n, m);

      Parent::getNotifier(ANode()).build();

      Parent::getNotifier(BNode()).build();

      Parent::getNotifier(Node()).build();

      Parent::getNotifier(UEdge()).build();

      Parent::getNotifier(Edge()).build();

    }

  };

} //namespace lemon

#endif //LEMON_FULL_GRAPH_H