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