RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

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

#define LEMON_BFS_H

///\ingroup search

///\file

///\brief BFS algorithm.

#include <lemon/list_graph.h>

#include <lemon/bits/path_dump.h>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/path.h>

namespace lemon {

  ///Default traits class of Bfs class.

  ///Default traits class of Bfs class.

  ///\tparam GR Digraph type.

  template<class GR>

  struct BfsDefaultTraits

  {

    ///The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    ///\brief The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that indicates which nodes are reached.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

    ///\param g is the digraph, to which we would like to define the

    ///DistMap.

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default value is \ref ListDigraph. The value of GR is not used

  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.

  ///\tparam TR Traits class to set various data types used by the algorithm.

  ///The default traits class is

  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".

  ///See \ref BfsDefaultTraits for the documentation of

  ///a Bfs traits class.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    ///The type of the digraph the algorithm runs on.

    typedef typename TR::Digraph Digraph;

    ///\brief The type of the map that stores the predecessor arcs of the

    ///shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    ///The type of the map that indicates which nodes are reached.

    typedef typename TR::ReachedMap ReachedMap;

    ///The type of the map that indicates which nodes are processed.

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///The traits class.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the map of predecessor arcs.

    PredMap *_pred;

    //Indicates if _pred is locally allocated (true) or not.

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

    //Indicates if _dist is locally allocated (true) or not.

    bool local_dist;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    //Pointer to the map of processed status of the nodes.

    ProcessedMap *_processed;

    //Indicates if _processed is locally allocated (true) or not.

    bool local_processed;

    std::vector<typename Digraph::Node> _queue;

    int _queue_head,_queue_tail,_queue_next_dist;

    int _curr_dist;

    //Creates the maps if necessary.

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

        _dist = Traits::createDistMap(*G);

      }

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*G);

      }

      if(!_processed) {

        local_processed = true;

        _processed = Traits::createProcessedMap(*G);

      }

    }

  protected:

    Bfs() {}

  public:

    typedef Bfs Create;

    ///\name Named template parameters

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &)

      {

        LEMON_ASSERT(false, "PredMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///PredMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///PredMap type.

    template <class T>

    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &)

      {

        LEMON_ASSERT(false, "DistMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///DistMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///DistMap type.

    template <class T>

    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &)

      {

        LEMON_ASSERT(false, "ReachedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///ReachedMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///ReachedMap type.

    template <class T>

    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

    };

#!/bin/bash

YEAR=`date +2003-%Y`

HGROOT=`hg root`

# file enumaration modes

function all_files() {

    hg status -a -m -c |

    cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |

    while read file; do echo $HGROOT/$file; done

}

function modified_files() {

    hg status -a -m |

    cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |

    while read file; do echo $HGROOT/$file; done

}

function changed_files() {

    {

        if [ -n "$HG_PARENT1" ]

        then

            hg status --rev $HG_PARENT1:$HG_NODE -a -m

        fi

        if [ -n "$HG_PARENT2" ]

        then

            hg status --rev $HG_PARENT2:$HG_NODE -a -m

        fi

    } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 

    sort | uniq |

    while read file; do echo $HGROOT/$file; done

}

function given_files() {

    for file in $GIVEN_FILES

    do

	echo $file

    done

}

# actions

function update_action() {

    if ! diff -q $1 $2 >/dev/null

    then

	echo -n " [$3 updated]"

	rm $2

	mv $1 $2

	CHANGED=YES

    fi

}

function update_warning() {

    echo -n " [$2 warning]"

    WARNED=YES

}

function update_init() {

    echo Update source files...

    TOTAL_FILES=0

    CHANGED_FILES=0

    WARNED_FILES=0

}

function update_done() {

    echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.

    echo $WARNED_FILES out of $TOTAL_FILES files has been warned.

}

function update_begin() {

    ((TOTAL_FILES++))

    CHANGED=NO

    WARNED=NO

}

function update_end() {

    if [ $CHANGED == YES ]

    then

	((++CHANGED_FILES))

    fi

    if [ $WARNED == YES ]

    then

	((++WARNED_FILES))

    fi

}

function check_action() {

    if ! diff -q $1 $2 >/dev/null

    then

	FAILED=YES

    fi

}

function check_warning() {

    WARNED=YES

}

function check_init() {

    echo Check source files...

    FAILED_FILES=0

    WARNED_FILES=0

    TOTAL_FILES=0

}

function check_done() {

    echo $FAILED_FILES out of $TOTAL_FILES files has been failed.

    echo $WARNED_FILES out of $TOTAL_FILES files has been warned.

    if [ $FAILED_FILES -gt 0 ]

    then

	return 1

    elif [ $WARNED_FILES -gt 0 ]

    then

	if [ "$WARNING" == 'INTERACTIVE' ]

	then

	    echo -n "Assume as normal behaviour? (yes/no) "

	    while read answer

	    do

		if [ "$answer" == 'yes' ]

		then

		    return 0

		elif [ "$answer" == 'no' ]

		then

		    return 1

		fi

		echo -n "Assume as normal behaviour? (yes/no) "		    

	    done

	elif [ "$WARNING" == 'WERROR' ]

	then

	    return 1

	fi

    fi

}

function check_begin() {

    ((TOTAL_FILES++))

    FAILED=NO

    WARNED=NO

}

function check_end() {

    if [ $FAILED == YES ]

    then

	((++FAILED_FILES))

    fi

    if [ $WARNED == YES ]

    then

	((++WARNED_FILES))

    fi

}

# checks

function header_check() {

    if echo $1 | grep -q -E 'Makefile\.am$'

    then

	return

    fi

    TMP_FILE=`mktemp`

    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) "$YEAR"

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

 *

 */

"

    awk 'BEGIN { pm=0; }

     pm==3 { print }

     /\/\* / && pm==0 { pm=1;}

     /[^:blank:]/ && (pm==0 || pm==2) { pm=3; print;}

     /\*\// && pm==1 { pm=2;}

    ' $1

    ) >$TMP_FILE

    "$ACTION"_action "$TMP_FILE" "$1" header

}

function tabs_check() {

    if echo $1 | grep -q -v -E 'Makefile\.am$'

    then

        OLD_PATTERN=$(echo -e '\t')

        NEW_PATTERN='        '

    else

        OLD_PATTERN='        '

        NEW_PATTERN=$(echo -e '\t')

    fi

    TMP_FILE=`mktemp`

    cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE

    "$ACTION"_action "$TMP_FILE" "$1" 'tabs'

}

function spaces_check() {

    TMP_FILE=`mktemp`

    cat $1 | sed -e 's/ \+$//g' >$TMP_FILE

    "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'

}

function long_lines_check() {

    if cat $1 | grep -q -E '.{81,}'

    then

	"$ACTION"_warning $1 'long lines'

    fi

}

# process the file

function process_file() {

    echo -n "    $ACTION $1..."

    CHECKING="header tabs spaces long_lines"

    "$ACTION"_begin $1

    for check in $CHECKING

    do

	"$check"_check $1

    done

    "$ACTION"_end $1

    echo

}

function process_all {

    "$ACTION"_init

    while read file

    do

	process_file $file

    done < <($FILES)

    "$ACTION"_done

}

while [ $# -gt 0 ]

do

    if [ "$1" == '--help' ] || [ "$1" == '-h' ]

    then

	echo -n \

"Usage:

  $0 [OPTIONS] [files]

Options:

  --dry-run|-n

     Check the given files, but do not modify them.

  --interactive|-i

     If --dry-run is specified and files are warned, then a message is

     prompted whether the warnings should be turned to errors.

  --werror|-w

     If --dry-run is specified, the warnings are turned to errors.

  --all|-a

     Check all source files in the repository.

  --modified|-m

     Check only the modified source files. This option is proper to

     use before a commit. E.g. all files which are modified or added

     into the repository will be updated.

  --changed|-c

     Check only the changed source files compared to the parent(s) of

     the current hg node.  This option is proper to use as hg hook

     script. E.g. to check all your commited source files with this

     script add the following section to the appropriate .hg/hgrc

     file.

       [hooks]

       pretxncommit.checksources = scripts/unify-sources.sh -c -n -i

  --help|-h

     Print this help message.

  files

     The files to check/unify. If no file names are given, the modified

     source files will be checked/unified (just like using the

     --modified|-m option).

"

        exit 0