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

  *

  */

 ///\ingroup paths

 ///\file

 ///\brief Classes for representing paths in graphs.

 ///

 #ifndef LEMON_PATH_UTILS_H

 #define LEMON_PATH_UTILS_H

 #include <lemon/concepts/path.h>

 namespace lemon {

   namespace _path_bits {

     template <typename Path, typename Enable = void>

     struct RevTagIndicator {

       static const bool value = false;

     };

     template <typename Graph>

     struct RevTagIndicator<

       Graph, 

       typename enable_if<typename Graph::RevTag, void>::type

     > {

       static const bool value = true;

     };

     template <typename Target, typename Source,

               typename BuildEnable = void, typename RevEnable = void>

     struct PathCopySelector {

       static void copy(Target& target, const Source& source) {

         source.clear();

         for (typename Source::EdgeIt it(source); it != INVALID; ++it) {

           target.addBack(it);

         }

       }

     };

     template <typename Target, typename Source, typename BuildEnable>

     struct PathCopySelector<

       Target, Source, BuildEnable, 

       typename enable_if<typename Source::RevPathTag, void>::type> {

       static void copy(Target& target, const Source& source) {

         source.clear();

         for (typename Source::RevIt it(source); it != INVALID; ++it) {

           target.addFront(it);

         }

       }

     };

     template <typename Target, typename Source, typename RevEnable>

     struct PathCopySelector<

       Target, Source, 

       typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {

       static void copy(Target& target, const Source& source) {

         target.clear();

         target.build(source);

       }

     };

     template <typename Target, typename Source>

     struct PathCopySelector<

       Target, Source, 

       typename enable_if<typename Target::BuildTag, void>::type,

       typename enable_if<typename Source::RevPathTag, void>::type> {

       static void copy(Target& target, const Source& source) {

         target.clear();

         target.buildRev(source);

       }

     };

   }

   /// \brief Make of copy of a path.

   ///

   ///  Make of copy of a path.

   template <typename Target, typename Source>

   void copyPath(Target& target, const Source& source) {

     checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();

     _path_bits::PathCopySelector<Target, Source>::copy(target, source);

   }

   /// \brief Checks the path's consistency.

   ///

   /// Checks that each edge's target is the next's source. 

   /// \Checks the path's consistency.

   ///

   /// Checks that each edge's target is the next's source. 

   template <typename Graph, typename Path>

   bool checkPath(const Graph& graph, const Path& path) {

     typename Path::EdgeIt it(path);

     if (it == INVALID) return true;

     typename Graph::Node node = graph.target(it);

     ++it;

     while (it != INVALID) {

       if (graph.source(it) != node) return false;

       node = graph.target(it);

       ++it;

     }

     return true;

   }

   /// \brief Gives back the source of the path

   ///

   /// Gives back the source of the path.

   template <typename Graph, typename Path>

   typename Graph::Node pathSource(const Graph& graph, const Path& path) {

     return graph.source(path.front());

   }

   /// \brief Gives back the target of the path

   ///

   /// Gives back the target of the path.

   template <typename Graph, typename Path>

   typename Graph::Node pathTarget(const Graph& graph, const Path& path) {

     return graph.target(path.back());

   }

 }

 #endif