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

#define LEMON_LIST_BPUGRAPH_H

///\ingroup graphs

///\file

///\brief ListBpUGraph classes.

#include <lemon/bits/bpugraph_extender.h>

#include <lemon/error.h>

#include <vector>

#include <list>

namespace lemon {

  class ListBpUGraphBase {

  public:

    class NodeSetError : public LogicError {

      virtual const char* exceptionName() const { 

	return "lemon::ListBpUGraph::NodeSetError";

      }

    };

  protected:

    struct NodeT {

      int first_edge, prev, next;

    };

    struct UEdgeT {

      int aNode, prev_out, next_out;

      int bNode, prev_in, next_in;

    };

    std::vector<NodeT> aNodes;

    std::vector<NodeT> bNodes;

    std::vector<UEdgeT> edges;

    int first_anode;

    int first_free_anode;

    int first_bnode;

    int first_free_bnode;

    int first_free_edge;

  public:

    class Node {

      friend class ListBpUGraphBase;

    protected:

      int id;

      explicit 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 ListBpUGraphBase;

    protected:

      int id;

      explicit 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;}

    };

    ListBpUGraphBase()

      : first_anode(-1), first_free_anode(-1),

        first_bnode(-1), first_free_bnode(-1),

        first_free_edge(-1) {}

    void firstANode(Node& node) const {

      node.id = first_anode != -1 ? (first_anode << 1) : -1;

    }

    void nextANode(Node& node) const {

      node.id = aNodes[node.id >> 1].next;

    }

    void firstBNode(Node& node) const {

      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;

    }

    void nextBNode(Node& node) const {

      node.id = bNodes[node.id >> 1].next;

    }

    void first(Node& node) const {

      if (first_anode != -1) {

        node.id = (first_anode << 1);

      } else if (first_bnode != -1) {

        node.id = (first_bnode << 1) + 1;

      } else {

        node.id = -1;

      }

    }

    void next(Node& node) const {

      if (aNode(node)) {

        node.id = aNodes[node.id >> 1].next;

        if (node.id == -1) {

          if (first_bnode != -1) {

            node.id = (first_bnode << 1) + 1;

          }

        }

      } else {

        node.id = bNodes[node.id >> 1].next;

      }

    }

    void first(UEdge& edge) const {

      int aNodeId = first_anode;

      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {

        aNodeId = aNodes[aNodeId].next != -1 ? 

          aNodes[aNodeId].next >> 1 : -1;

      }

      if (aNodeId != -1) {

        edge.id = aNodes[aNodeId].first_edge;

      } else {

        edge.id = -1;

      }

    }

    void next(UEdge& edge) const {

      int aNodeId = edges[edge.id].aNode >> 1;

      edge.id = edges[edge.id].next_out;

      if (edge.id == -1) {

        aNodeId = aNodes[aNodeId].next != -1 ? 

          aNodes[aNodeId].next >> 1 : -1;

        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {

          aNodeId = aNodes[aNodeId].next != -1 ? 

          aNodes[aNodeId].next >> 1 : -1;

        }

        if (aNodeId != -1) {

          edge.id = aNodes[aNodeId].first_edge;

        } else {

          edge.id = -1;

        }

      }

    }

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

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

      edge.id = aNodes[node.id >> 1].first_edge;

    }

    void nextFromANode(UEdge& edge) const {

      edge.id = edges[edge.id].next_out;

    }

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

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

      edge.id = bNodes[node.id >> 1].first_edge;

    }

    void nextFromBNode(UEdge& edge) const {

      edge.id = edges[edge.id].next_in;

    }

    static int id(const Node& node) {

      return node.id;

    }

    static Node nodeFromId(int id) {

      return Node(id);

    }

    int maxNodeId() const {

      return aNodes.size() > bNodes.size() ?

	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;

    }

    static int id(const UEdge& edge) {

      return edge.id;

    }

    static UEdge uEdgeFromId(int id) {

      return UEdge(id);

    }

    int maxUEdgeId() const {

      return edges.size();

    }

    static int aNodeId(const Node& node) {

      return node.id >> 1;

    }

    static Node fromANodeId(int id) {

      return Node(id << 1);

    }

    int maxANodeId() const {

      return aNodes.size();

    }

    static int bNodeId(const Node& node) {

      return node.id >> 1;

    }

    static Node fromBNodeId(int id) {

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

    }

    int maxBNodeId() const {

      return bNodes.size();

    }

    Node aNode(const UEdge& edge) const {

      return Node(edges[edge.id].aNode);

    }

    Node bNode(const UEdge& edge) const {

      return Node(edges[edge.id].bNode);

    }

    static bool aNode(const Node& node) {

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

    }

    static bool bNode(const Node& node) {

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

    }

    Node addANode() {

      int aNodeId;

      if (first_free_anode == -1) {

        aNodeId = aNodes.size();

        aNodes.push_back(NodeT());

      } else {

        aNodeId = first_free_anode;

        first_free_anode = aNodes[first_free_anode].next;

      }

      if (first_anode != -1) {

        aNodes[aNodeId].next = first_anode << 1;

        aNodes[first_anode].prev = aNodeId << 1;

      } else {

        aNodes[aNodeId].next = -1;

      }

      aNodes[aNodeId].prev = -1;

      first_anode = aNodeId;

      aNodes[aNodeId].first_edge = -1;

      return Node(aNodeId << 1);

    }

    Node addBNode() {

      int bNodeId;

      if (first_free_bnode == -1) {

        bNodeId = bNodes.size();

        bNodes.push_back(NodeT());

      } else {

        bNodeId = first_free_bnode;

        first_free_bnode = bNodes[first_free_bnode].next;

      }

      if (first_bnode != -1) {

        bNodes[bNodeId].next = (first_bnode << 1) + 1;

        bNodes[first_bnode].prev = (bNodeId << 1) + 1;

      } else {

        bNodes[bNodeId].next = -1;

      }

      first_bnode = bNodeId;

      bNodes[bNodeId].first_edge = -1;

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

    }

    UEdge addEdge(const Node& source, const Node& target) {

      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());

      int edgeId;

      if (first_free_edge != -1) {

        edgeId = first_free_edge;

        first_free_edge = edges[edgeId].next_out;

      } else {

        edgeId = edges.size();

        edges.push_back(UEdgeT());

      }

      if ((source.id & 1) == 0) {

	edges[edgeId].aNode = source.id;

	edges[edgeId].bNode = target.id;

      } else {

	edges[edgeId].aNode = target.id;

	edges[edgeId].bNode = source.id;

      }

      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;

      edges[edgeId].prev_out = -1;

      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {

        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;

      }

      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;

      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;

      edges[edgeId].prev_in = -1;

      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {

        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;

      }

      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;

      return UEdge(edgeId);

    }

    void erase(const Node& node) {

      if (aNode(node)) {

        int aNodeId = node.id >> 1;

        if (aNodes[aNodeId].prev != -1) {

          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;

        } else {

          first_anode = aNodes[aNodeId].next >> 1;

        }

        if (aNodes[aNodeId].next != -1) {

          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;

        }

        aNodes[aNodeId].next = first_free_anode;

        first_free_anode = aNodeId;

      } else {

        int bNodeId = node.id >> 1;

        if (bNodes[bNodeId].prev != -1) {

          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;

        } else {

          first_bnode = bNodes[bNodeId].next >> 1;

        }

        if (bNodes[bNodeId].next != -1) {

          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;

        }

        bNodes[bNodeId].next = first_free_bnode;

        first_free_bnode = bNodeId;

      }

    }

    void erase(const UEdge& edge) {

      if (edges[edge.id].prev_out != -1) {

        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;

      } else {

        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;

      }

      if (edges[edge.id].next_out != -1) {

        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;

      }

      if (edges[edge.id].prev_in != -1) {

        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;

      } else {

        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;

      }

      if (edges[edge.id].next_in != -1) {

        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;

      }

      edges[edge.id].next_out = first_free_edge;

      first_free_edge = edge.id;

    }

    void clear() {

      aNodes.clear();

      bNodes.clear();

      edges.clear();

      first_anode = -1;

      first_free_anode = -1;

      first_bnode = -1;

      first_free_bnode = -1;

      first_free_edge = -1;

    }

  };

  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;

  /// \ingroup graphs

  ///

  /// \brief A smart bipartite undirected graph class.

  ///

  /// This is a bipartite undirected graph implementation.

  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 

  /// concept.

  /// \sa concept::BpUGraph.

  ///

  class ListBpUGraph : public ExtendedListBpUGraphBase {};

  /// @}  

} //namespace lemon

#endif