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

#define LEMON_EDGE_LOOKUP_H

#include<lemon/graph_utils.h>

#include<algorithm>

#include<vector>

namespace lemon {

  template<class G>

  class EdgeLookUp2

  {

  public:

    GRAPH_TYPEDEFS(typename G)

    typedef G Graph;

  private:

    const Graph &_g;

    typename Graph::template NodeMap<int> _start;

    typename Graph::template NodeMap<int> _end;

    std::vector<Edge> _edges;

    class EdgeLess {

      const Graph &g;

    public:

      EdgeLess(const Graph &_g) : g(_g) {}

      bool operator()(Edge a,Edge b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

  public:

    ///Refresh the data structure at a node.

    void refresh(Node n) 

    {

      const int bi = _start[n] = _edges.size();

      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

      const typename std::vector<Edge>::iterator ei=_edges.end();

      _end[n]=_edges.size();

      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    }

    ///Refresh the full data structure.

    void refresh() 

    {

      _edges.clear();

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an edge between two nodes.

    ///Find an edge between two nodes.

    ///\param s The source node

    ///\param t The target node

    ///\return An edge from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    Edge operator()(Node s, Node t) 

    {

      int a=_start[s];

      int b=_end[s];

      while(a<b) 

	{

	  int n=(a+b)/2;

	  Node tt = _g.target(_edges[n]);

	  if(tt==t) return _edges[n];

	  else if(tt<t) a=n+1;

	  else b=n;

	}

      return INVALID;

    }

    ///Find the next edge

      ///\warning This function is unimplemented.

    Edge operator()(Node s, Node t, Edge prev) 

    {

      return prev==INVALID?(*this)(s,t):INVALID;

    }

  };

  template<class G>

  class EdgeLookUp3

  {

  public:

    GRAPH_TYPEDEFS(typename G)

    typedef G Graph;

  private:

    const Graph &_g;

    typename Graph::template NodeMap<Edge*> _start;

    typename Graph::template NodeMap<Edge*> _end;

    std::vector<Edge> _edges;

    class EdgeLess {

      const Graph &g;

    public:

      EdgeLess(const Graph &_g) : g(_g) {}

      bool operator()(Edge a,Edge b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

  public:

    ///Refresh the data structure at a node.

    void refresh(Node n) 

    {

      const int bi = _start[n] = _edges.size();

      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

      const typename std::vector<Edge>::iterator ei=_edges.end();

      _end[n]=_edges.size();

      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    }

    ///Refresh the full data structure.

    void refresh() 

    {

      _edges.resize(countEdges(_g));

      int l=0;

      for(NodeIt n(_g);n!=INVALID;++n)

	{

	  int ls = l;

	  _start[n]=&(_edges[l]);	

	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

	  _end[n]=&(_edges[l]);

	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

	}

    }

    ///Find an edge between two nodes.

    ///Find an edge between two nodes.

    ///\param s The source node

    ///\param t The target node

    ///\return An edge from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    Edge operator()(Node s, Node t) 

    {

      Edge *a=_start[s];

      Edge *b=_end[s];

      while(a!=b) 

	{

 	  Edge *m=a+((b-a)/2);

	  Node tt = _g.target(*m);

	  if(tt==t) return *m;

	  else if(tt<t) a=m+1;

	  else b=m;

	}

      return INVALID;

    }

    ///Find the next edge

      ///\warning This function is unimplemented.

    Edge operator()(Node s, Node t, Edge prev) 

    {

      return prev==INVALID?(*this)(s,t):INVALID;

    }

  };

  template<class G>

  class EdgeLookUp4

  {

  public:

    GRAPH_TYPEDEFS(typename G)

    typedef G Graph;

  private:

    const Graph &_g;

    typename Graph::template NodeMap<Edge*> _start;

    typename Graph::template NodeMap<Edge*> _end;

    std::vector<Edge> _edges;

    class EdgeLess {

      const Graph &g;

    public:

      EdgeLess(const Graph &_g) : g(_g) {}

      bool operator()(Edge a,Edge b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

  public:

    ///Refresh the data structure at a node.

    void refresh(Node n) 

    {

      const int bi = _start[n] = _edges.size();

      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

      const typename std::vector<Edge>::iterator ei=_edges.end();

      _end[n]=_edges.size();

      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    }

    ///Refresh the full data structure.

    void refresh() 

    {

      _edges.resize(countEdges(_g));

      int l=0;

      for(NodeIt n(_g);n!=INVALID;++n)

	{

	  int ls = l;

	  _start[n]=&(_edges[l]);	

	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

	  _end[n]=&(_edges[l]);

	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

	}

    }

    ///Find an edge between two nodes.

    ///Find an edge between two nodes.

    ///\param s The source node

    ///\param t The target node

    ///\return An edge from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    Edge operator()(Node s, Node t) 

    {

      Edge *a=_start[s];

      Edge *b=_end[s];

      while(a!=b) 

	{

#ifdef X86

 	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);

#elif X86_64

	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);

#else

 	  Edge *m=a+((b-a)/2);

#endif

	  Node tt = _g.target(*m);

	  if(tt==t) return *m;

	  else if(tt<t) a=m+1;

	  else b=m;

	}

      return INVALID;

    }

    ///Find the next edge

      ///\warning This function is unimplemented.

    Edge operator()(Node s, Node t, Edge prev) 

    {

      return prev==INVALID?(*this)(s,t):INVALID;

    }

  };

}

#endif