/* -*- C++ -*-
 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 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.
 *
 */

#include <vector>
#include <limits>

///\ingroup maps
///\file
///\brief Maps that makes it possible to iterate through the keys having
///a certain value
///
///


namespace lemon {
  
  ///\todo This is only a static map!
  ///\param BaseMap is an interger map.
  template<class BaseMap>
  class IterableBoolMap
  {
  public:
  
    typedef typename BaseMap::Key Key;
    typedef bool Value;
  
    friend class RefType;
    friend class FalseIt;
    friend class TrueIt;

  private:
    BaseMap &cref;
    std::vector<Key> vals;
    int sep;           //map[e] is true <=> cref[e]>=sep
  
    bool isTrue(Key k) {return cref[k]>=sep;}
    void swap(Key k, int s) 
    {
      int ti=cref[k];
      Key tk=vals[s];
      cref[k]=s; vals[s]=k;
      cref[tk]=ti; vals[ti]=tk;
    }  

    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
  
  public:
    ///\e
    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}

    ///\e
    class FalseIt
    {
      const IterableBoolMap &M;
      int i;
    public:
      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
      FalseIt(Invalid)
	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
      FalseIt &operator++() { ++i; return *this;}
      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
      bool operator !=(Invalid) const { return i<M.sep; }
      bool operator ==(Invalid) const { return i>=M.sep; }
    };
    ///\e
    class TrueIt
    {
      const IterableBoolMap &M;
      int i;
    public:
      explicit TrueIt(const IterableBoolMap &_M)
	: M(_M), i(M.vals.size()-1) { }
      TrueIt(Invalid)
	: M(*((IterableBoolMap*)(0))), i(-1) { }
      TrueIt &operator++() { --i; return *this;}
      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
      bool operator !=(Invalid) const { return i>=M.sep; }
      bool operator ==(Invalid) const { return i<M.sep; }
    };
  
    ///\e
    class RefType
    {
      IterableBoolMap &M;
      Key k;
    public:
      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
    
      operator Value() const 
      {
	return M.isTrue(k);
      }
      Value operator = (Value v) const { M.set(k,v); return v; }
    };
  
  public:
    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
    {
      sep=0;
      for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
	  i!=cref.mapSet().end();
	  ++i) {
	i->second=sep;
	vals.push_back(i->first);
	sep++;
      }
      if(init) sep=0;
    }
    RefType operator[] (Key k) { return RefType(*this,k);}  
    Value operator[] (Key k) const { return isTrue(k);}  
  };




  /// \addtogroup graph_maps
  /// @{

  /// Iterable bool NodeMap

  /// This map can be used in the same way
  /// as the standard NodeMap<bool> of the
  /// given graph \c Graph. 
  /// In addition, this class provides two iterators called \ref TrueIt
  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
  template <class Graph>
  class IterableBoolNodeMap
  {
    typename Graph::template NodeMap<int> cmap;
  
  public:
  
    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
    BimType imap;


    typedef typename BimType::RefType RefType;
    typedef typename Graph::Node Key;
    typedef bool Value;
  
    friend class FalseIt;
    friend class TrueIt;
  
    ///\e
    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:
    ///\e
    void set(Key k, bool v) { imap.set(k,v);}
#ifdef DOXYGEN
    ///\e
    bool &operator[](Key k) { return imap[k];}  
    ///\e
    const bool &operator[](Key k) const { return imap[k];}  
#else
    Value operator[](Key k) const { return imap[k];}  
    RefType operator[](Key k) { return imap[k];}  
#endif
    ///Iterator for the "false" nodes
    class FalseIt : public BimType::FalseIt
    {
    public:
      explicit FalseIt(const IterableBoolNodeMap &m)
	: BimType::FalseIt(m.imap) { }
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
    };
    ///Iterator for the "true" nodes
    class TrueIt : public BimType::TrueIt
    {
    public:
      explicit TrueIt(const IterableBoolNodeMap &m)
	: BimType::TrueIt(m.imap) { }
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
    };  
  };

  /// Iterable bool EdgeMap

  /// This map can be used in the same way
  /// as the standard EdgeMap<bool> of the
  /// given graph \c Graph. 
  /// In addition, this class provides two iterators called \ref TrueIt
  /// and \ref FalseIt to iterate through the "true" and "false" edges.
  template <class Graph>
  class IterableBoolEdgeMap
  {
    typename Graph::template EdgeMap<int> cmap;
  
  public:
  
    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
    BimType imap;


    typedef typename BimType::RefType RefType;
    typedef typename Graph::Edge Key;
    typedef bool Value;
  
    friend class FalseIt;
    friend class TrueIt;
  
    ///\e
    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:
    ///\e
    void set(Key k, bool v) { imap.set(k,v);}
#ifdef DOXYGEN
    ///\e
    bool &operator[](Key k) { return imap[k];}  
    ///\e
    const bool &operator[](Key k) const { return imap[k];}  
#else
    Value operator[](Key k) const { return imap[k];}  
    RefType operator[](Key k) { return imap[k];}  
#endif
    ///Iterator for the "false" edges
    class FalseIt : public BimType::FalseIt
    {
    public:
      explicit FalseIt(const IterableBoolEdgeMap &m)
	: BimType::FalseIt(m.imap) { }
      FalseIt(Invalid i) : BimType::FalseIt(i) { }
    };
    ///Iterator for the "true" edges
    class TrueIt : public BimType::TrueIt
    {
    public:
      explicit TrueIt(const IterableBoolEdgeMap &m)
	: BimType::TrueIt(m.imap) { }
      TrueIt(Invalid i) : BimType::TrueIt(i) { }
    };  
  };

  /// @}
}