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