0
4
0
1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 | 2 |
* |
3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
4 | 4 |
* |
5 | 5 |
* Copyright (C) 2003-2008 |
6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 | 8 |
* |
9 | 9 |
* Permission to use, modify and distribute this software is granted |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef LEMON_BFS_H |
20 | 20 |
#define LEMON_BFS_H |
21 | 21 |
|
22 | 22 |
///\ingroup search |
23 | 23 |
///\file |
24 | 24 |
///\brief BFS algorithm. |
25 | 25 |
|
26 | 26 |
#include <lemon/list_graph.h> |
27 | 27 |
#include <lemon/bits/path_dump.h> |
28 | 28 |
#include <lemon/core.h> |
29 | 29 |
#include <lemon/error.h> |
30 | 30 |
#include <lemon/maps.h> |
31 | 31 |
#include <lemon/path.h> |
32 | 32 |
|
33 | 33 |
namespace lemon { |
34 | 34 |
|
35 | 35 |
///Default traits class of Bfs class. |
36 | 36 |
|
37 | 37 |
///Default traits class of Bfs class. |
38 | 38 |
///\tparam GR Digraph type. |
39 | 39 |
template<class GR> |
40 | 40 |
struct BfsDefaultTraits |
41 | 41 |
{ |
42 | 42 |
///The type of the digraph the algorithm runs on. |
43 | 43 |
typedef GR Digraph; |
44 | 44 |
|
45 | 45 |
///\brief The type of the map that stores the predecessor |
46 | 46 |
///arcs of the shortest paths. |
47 | 47 |
/// |
48 | 48 |
///The type of the map that stores the predecessor |
49 | 49 |
///arcs of the shortest paths. |
50 | 50 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
51 | 51 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
52 | 52 |
///Instantiates a PredMap. |
53 | 53 |
|
54 |
///This function instantiates a PredMap. |
|
54 |
///This function instantiates a PredMap. |
|
55 | 55 |
///\param g is the digraph, to which we would like to define the |
56 | 56 |
///PredMap. |
57 | 57 |
static PredMap *createPredMap(const Digraph &g) |
58 | 58 |
{ |
59 | 59 |
return new PredMap(g); |
60 | 60 |
} |
61 | 61 |
|
62 | 62 |
///The type of the map that indicates which nodes are processed. |
63 | 63 |
|
64 | 64 |
///The type of the map that indicates which nodes are processed. |
65 | 65 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
66 | 66 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 | 67 |
///Instantiates a ProcessedMap. |
68 | 68 |
|
69 | 69 |
///This function instantiates a ProcessedMap. |
70 | 70 |
///\param g is the digraph, to which |
71 | 71 |
///we would like to define the ProcessedMap |
72 | 72 |
#ifdef DOXYGEN |
73 | 73 |
static ProcessedMap *createProcessedMap(const Digraph &g) |
74 | 74 |
#else |
75 | 75 |
static ProcessedMap *createProcessedMap(const Digraph &) |
76 | 76 |
#endif |
77 | 77 |
{ |
78 | 78 |
return new ProcessedMap(); |
79 | 79 |
} |
80 | 80 |
|
81 | 81 |
///The type of the map that indicates which nodes are reached. |
82 | 82 |
|
83 |
///The type of the map that indicates which nodes are reached. |
|
84 |
///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
83 |
///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
85 | 84 |
typedef typename Digraph::template NodeMap<bool> ReachedMap; |
86 | 85 |
///Instantiates a ReachedMap. |
87 | 86 |
|
88 | 87 |
///This function instantiates a ReachedMap. |
89 | 88 |
///\param g is the digraph, to which |
90 | 89 |
///we would like to define the ReachedMap. |
91 | 90 |
static ReachedMap *createReachedMap(const Digraph &g) |
92 | 91 |
{ |
93 | 92 |
return new ReachedMap(g); |
94 | 93 |
} |
95 | 94 |
|
96 | 95 |
///The type of the map that stores the distances of the nodes. |
97 | 96 |
|
98 | 97 |
///The type of the map that stores the distances of the nodes. |
99 | 98 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
100 | 99 |
typedef typename Digraph::template NodeMap<int> DistMap; |
101 | 100 |
///Instantiates a DistMap. |
102 | 101 |
|
103 | 102 |
///This function instantiates a DistMap. |
104 | 103 |
///\param g is the digraph, to which we would like to define the |
105 | 104 |
///DistMap. |
106 | 105 |
static DistMap *createDistMap(const Digraph &g) |
107 | 106 |
{ |
108 | 107 |
return new DistMap(g); |
109 | 108 |
} |
110 | 109 |
}; |
111 | 110 |
|
112 | 111 |
///%BFS algorithm class. |
113 | 112 |
|
114 | 113 |
///\ingroup search |
115 | 114 |
///This class provides an efficient implementation of the %BFS algorithm. |
116 | 115 |
/// |
117 | 116 |
///There is also a \ref bfs() "function-type interface" for the BFS |
118 | 117 |
///algorithm, which is convenient in the simplier cases and it can be |
119 | 118 |
///used easier. |
120 | 119 |
/// |
121 | 120 |
///\tparam GR The type of the digraph the algorithm runs on. |
122 | 121 |
///The default value is \ref ListDigraph. The value of GR is not used |
123 | 122 |
///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. |
124 | 123 |
///\tparam TR Traits class to set various data types used by the algorithm. |
125 | 124 |
///The default traits class is |
126 | 125 |
///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". |
127 | 126 |
///See \ref BfsDefaultTraits for the documentation of |
128 | 127 |
///a Bfs traits class. |
129 | 128 |
#ifdef DOXYGEN |
130 | 129 |
template <typename GR, |
131 | 130 |
typename TR> |
132 | 131 |
#else |
133 | 132 |
template <typename GR=ListDigraph, |
134 | 133 |
typename TR=BfsDefaultTraits<GR> > |
135 | 134 |
#endif |
136 | 135 |
class Bfs { |
137 | 136 |
public: |
138 | 137 |
|
139 | 138 |
///The type of the digraph the algorithm runs on. |
140 | 139 |
typedef typename TR::Digraph Digraph; |
141 | 140 |
|
142 | 141 |
///\brief The type of the map that stores the predecessor arcs of the |
143 | 142 |
///shortest paths. |
144 | 143 |
typedef typename TR::PredMap PredMap; |
145 | 144 |
///The type of the map that stores the distances of the nodes. |
146 | 145 |
typedef typename TR::DistMap DistMap; |
147 | 146 |
///The type of the map that indicates which nodes are reached. |
148 | 147 |
typedef typename TR::ReachedMap ReachedMap; |
... | ... |
@@ -779,130 +779,130 @@ |
779 | 779 |
int prev, next; |
780 | 780 |
}; |
781 | 781 |
|
782 | 782 |
struct ArcT { |
783 | 783 |
int target; |
784 | 784 |
int prev_out, next_out; |
785 | 785 |
}; |
786 | 786 |
|
787 | 787 |
std::vector<NodeT> nodes; |
788 | 788 |
|
789 | 789 |
int first_node; |
790 | 790 |
|
791 | 791 |
int first_free_node; |
792 | 792 |
|
793 | 793 |
std::vector<ArcT> arcs; |
794 | 794 |
|
795 | 795 |
int first_free_arc; |
796 | 796 |
|
797 | 797 |
public: |
798 | 798 |
|
799 | 799 |
typedef ListGraphBase Digraph; |
800 | 800 |
|
801 | 801 |
class Node; |
802 | 802 |
class Arc; |
803 | 803 |
class Edge; |
804 | 804 |
|
805 | 805 |
class Node { |
806 | 806 |
friend class ListGraphBase; |
807 | 807 |
protected: |
808 | 808 |
|
809 | 809 |
int id; |
810 | 810 |
explicit Node(int pid) { id = pid;} |
811 | 811 |
|
812 | 812 |
public: |
813 | 813 |
Node() {} |
814 | 814 |
Node (Invalid) { id = -1; } |
815 | 815 |
bool operator==(const Node& node) const {return id == node.id;} |
816 | 816 |
bool operator!=(const Node& node) const {return id != node.id;} |
817 | 817 |
bool operator<(const Node& node) const {return id < node.id;} |
818 | 818 |
}; |
819 | 819 |
|
820 | 820 |
class Edge { |
821 | 821 |
friend class ListGraphBase; |
822 | 822 |
protected: |
823 | 823 |
|
824 | 824 |
int id; |
825 | 825 |
explicit Edge(int pid) { id = pid;} |
826 | 826 |
|
827 | 827 |
public: |
828 | 828 |
Edge() {} |
829 | 829 |
Edge (Invalid) { id = -1; } |
830 | 830 |
bool operator==(const Edge& edge) const {return id == edge.id;} |
831 | 831 |
bool operator!=(const Edge& edge) const {return id != edge.id;} |
832 | 832 |
bool operator<(const Edge& edge) const {return id < edge.id;} |
833 | 833 |
}; |
834 | 834 |
|
835 | 835 |
class Arc { |
836 | 836 |
friend class ListGraphBase; |
837 | 837 |
protected: |
838 | 838 |
|
839 | 839 |
int id; |
840 | 840 |
explicit Arc(int pid) { id = pid;} |
841 | 841 |
|
842 | 842 |
public: |
843 |
operator Edge() const { |
|
844 |
return id != -1 ? edgeFromId(id / 2) : INVALID; |
|
843 |
operator Edge() const { |
|
844 |
return id != -1 ? edgeFromId(id / 2) : INVALID; |
|
845 | 845 |
} |
846 | 846 |
|
847 | 847 |
Arc() {} |
848 | 848 |
Arc (Invalid) { id = -1; } |
849 | 849 |
bool operator==(const Arc& arc) const {return id == arc.id;} |
850 | 850 |
bool operator!=(const Arc& arc) const {return id != arc.id;} |
851 | 851 |
bool operator<(const Arc& arc) const {return id < arc.id;} |
852 | 852 |
}; |
853 | 853 |
|
854 | 854 |
|
855 | 855 |
|
856 | 856 |
ListGraphBase() |
857 | 857 |
: nodes(), first_node(-1), |
858 | 858 |
first_free_node(-1), arcs(), first_free_arc(-1) {} |
859 | 859 |
|
860 | 860 |
|
861 | 861 |
int maxNodeId() const { return nodes.size()-1; } |
862 | 862 |
int maxEdgeId() const { return arcs.size() / 2 - 1; } |
863 | 863 |
int maxArcId() const { return arcs.size()-1; } |
864 | 864 |
|
865 | 865 |
Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } |
866 | 866 |
Node target(Arc e) const { return Node(arcs[e.id].target); } |
867 | 867 |
|
868 | 868 |
Node u(Edge e) const { return Node(arcs[2 * e.id].target); } |
869 | 869 |
Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } |
870 | 870 |
|
871 | 871 |
static bool direction(Arc e) { |
872 | 872 |
return (e.id & 1) == 1; |
873 | 873 |
} |
874 | 874 |
|
875 | 875 |
static Arc direct(Edge e, bool d) { |
876 | 876 |
return Arc(e.id * 2 + (d ? 1 : 0)); |
877 | 877 |
} |
878 | 878 |
|
879 | 879 |
void first(Node& node) const { |
880 | 880 |
node.id = first_node; |
881 | 881 |
} |
882 | 882 |
|
883 | 883 |
void next(Node& node) const { |
884 | 884 |
node.id = nodes[node.id].next; |
885 | 885 |
} |
886 | 886 |
|
887 | 887 |
void first(Arc& e) const { |
888 | 888 |
int n = first_node; |
889 | 889 |
while (n != -1 && nodes[n].first_out == -1) { |
890 | 890 |
n = nodes[n].next; |
891 | 891 |
} |
892 | 892 |
e.id = (n == -1) ? -1 : nodes[n].first_out; |
893 | 893 |
} |
894 | 894 |
|
895 | 895 |
void next(Arc& e) const { |
896 | 896 |
if (arcs[e.id].next_out != -1) { |
897 | 897 |
e.id = arcs[e.id].next_out; |
898 | 898 |
} else { |
899 | 899 |
int n = nodes[arcs[e.id ^ 1].target].next; |
900 | 900 |
while(n != -1 && nodes[n].first_out == -1) { |
901 | 901 |
n = nodes[n].next; |
902 | 902 |
} |
903 | 903 |
e.id = (n == -1) ? -1 : nodes[n].first_out; |
904 | 904 |
} |
905 | 905 |
} |
906 | 906 |
|
907 | 907 |
void first(Edge& e) const { |
908 | 908 |
int n = first_node; |
... | ... |
@@ -403,130 +403,130 @@ |
403 | 403 |
class SmartGraphBase { |
404 | 404 |
|
405 | 405 |
protected: |
406 | 406 |
|
407 | 407 |
struct NodeT { |
408 | 408 |
int first_out; |
409 | 409 |
}; |
410 | 410 |
|
411 | 411 |
struct ArcT { |
412 | 412 |
int target; |
413 | 413 |
int next_out; |
414 | 414 |
}; |
415 | 415 |
|
416 | 416 |
std::vector<NodeT> nodes; |
417 | 417 |
std::vector<ArcT> arcs; |
418 | 418 |
|
419 | 419 |
int first_free_arc; |
420 | 420 |
|
421 | 421 |
public: |
422 | 422 |
|
423 | 423 |
typedef SmartGraphBase Digraph; |
424 | 424 |
|
425 | 425 |
class Node; |
426 | 426 |
class Arc; |
427 | 427 |
class Edge; |
428 | 428 |
|
429 | 429 |
class Node { |
430 | 430 |
friend class SmartGraphBase; |
431 | 431 |
protected: |
432 | 432 |
|
433 | 433 |
int _id; |
434 | 434 |
explicit Node(int id) { _id = id;} |
435 | 435 |
|
436 | 436 |
public: |
437 | 437 |
Node() {} |
438 | 438 |
Node (Invalid) { _id = -1; } |
439 | 439 |
bool operator==(const Node& node) const {return _id == node._id;} |
440 | 440 |
bool operator!=(const Node& node) const {return _id != node._id;} |
441 | 441 |
bool operator<(const Node& node) const {return _id < node._id;} |
442 | 442 |
}; |
443 | 443 |
|
444 | 444 |
class Edge { |
445 | 445 |
friend class SmartGraphBase; |
446 | 446 |
protected: |
447 | 447 |
|
448 | 448 |
int _id; |
449 | 449 |
explicit Edge(int id) { _id = id;} |
450 | 450 |
|
451 | 451 |
public: |
452 | 452 |
Edge() {} |
453 | 453 |
Edge (Invalid) { _id = -1; } |
454 | 454 |
bool operator==(const Edge& arc) const {return _id == arc._id;} |
455 | 455 |
bool operator!=(const Edge& arc) const {return _id != arc._id;} |
456 | 456 |
bool operator<(const Edge& arc) const {return _id < arc._id;} |
457 | 457 |
}; |
458 | 458 |
|
459 | 459 |
class Arc { |
460 | 460 |
friend class SmartGraphBase; |
461 | 461 |
protected: |
462 | 462 |
|
463 | 463 |
int _id; |
464 | 464 |
explicit Arc(int id) { _id = id;} |
465 | 465 |
|
466 | 466 |
public: |
467 |
operator Edge() const { |
|
468 |
return _id != -1 ? edgeFromId(_id / 2) : INVALID; |
|
467 |
operator Edge() const { |
|
468 |
return _id != -1 ? edgeFromId(_id / 2) : INVALID; |
|
469 | 469 |
} |
470 | 470 |
|
471 | 471 |
Arc() {} |
472 | 472 |
Arc (Invalid) { _id = -1; } |
473 | 473 |
bool operator==(const Arc& arc) const {return _id == arc._id;} |
474 | 474 |
bool operator!=(const Arc& arc) const {return _id != arc._id;} |
475 | 475 |
bool operator<(const Arc& arc) const {return _id < arc._id;} |
476 | 476 |
}; |
477 | 477 |
|
478 | 478 |
|
479 | 479 |
|
480 | 480 |
SmartGraphBase() |
481 | 481 |
: nodes(), arcs() {} |
482 | 482 |
|
483 | 483 |
|
484 | 484 |
int maxNodeId() const { return nodes.size()-1; } |
485 | 485 |
int maxEdgeId() const { return arcs.size() / 2 - 1; } |
486 | 486 |
int maxArcId() const { return arcs.size()-1; } |
487 | 487 |
|
488 | 488 |
Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); } |
489 | 489 |
Node target(Arc e) const { return Node(arcs[e._id].target); } |
490 | 490 |
|
491 | 491 |
Node u(Edge e) const { return Node(arcs[2 * e._id].target); } |
492 | 492 |
Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); } |
493 | 493 |
|
494 | 494 |
static bool direction(Arc e) { |
495 | 495 |
return (e._id & 1) == 1; |
496 | 496 |
} |
497 | 497 |
|
498 | 498 |
static Arc direct(Edge e, bool d) { |
499 | 499 |
return Arc(e._id * 2 + (d ? 1 : 0)); |
500 | 500 |
} |
501 | 501 |
|
502 | 502 |
void first(Node& node) const { |
503 | 503 |
node._id = nodes.size() - 1; |
504 | 504 |
} |
505 | 505 |
|
506 | 506 |
void next(Node& node) const { |
507 | 507 |
--node._id; |
508 | 508 |
} |
509 | 509 |
|
510 | 510 |
void first(Arc& arc) const { |
511 | 511 |
arc._id = arcs.size() - 1; |
512 | 512 |
} |
513 | 513 |
|
514 | 514 |
void next(Arc& arc) const { |
515 | 515 |
--arc._id; |
516 | 516 |
} |
517 | 517 |
|
518 | 518 |
void first(Edge& arc) const { |
519 | 519 |
arc._id = arcs.size() / 2 - 1; |
520 | 520 |
} |
521 | 521 |
|
522 | 522 |
void next(Edge& arc) const { |
523 | 523 |
--arc._id; |
524 | 524 |
} |
525 | 525 |
|
526 | 526 |
void firstOut(Arc &arc, const Node& v) const { |
527 | 527 |
arc._id = nodes[v._id].first_out; |
528 | 528 |
} |
529 | 529 |
void nextOut(Arc &arc) const { |
530 | 530 |
arc._id = arcs[arc._id].next_out; |
531 | 531 |
} |
532 | 532 |
... | ... |
@@ -27,310 +27,321 @@ |
27 | 27 |
then |
28 | 28 |
hg status --rev $HG_PARENT2:$HG_NODE -a -m |
29 | 29 |
fi |
30 | 30 |
} | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | |
31 | 31 |
sort | uniq | |
32 | 32 |
while read file; do echo $HGROOT/$file; done |
33 | 33 |
} |
34 | 34 |
|
35 | 35 |
function given_files() { |
36 | 36 |
for file in $GIVEN_FILES |
37 | 37 |
do |
38 | 38 |
echo $file |
39 | 39 |
done |
40 | 40 |
} |
41 | 41 |
|
42 | 42 |
# actions |
43 | 43 |
|
44 | 44 |
function update_action() { |
45 | 45 |
if ! diff -q $1 $2 >/dev/null |
46 | 46 |
then |
47 | 47 |
echo -n " [$3 updated]" |
48 | 48 |
rm $2 |
49 | 49 |
mv $1 $2 |
50 | 50 |
CHANGED=YES |
51 | 51 |
fi |
52 | 52 |
} |
53 | 53 |
|
54 | 54 |
function update_warning() { |
55 | 55 |
echo -n " [$2 warning]" |
56 | 56 |
WARNED=YES |
57 | 57 |
} |
58 | 58 |
|
59 | 59 |
function update_init() { |
60 | 60 |
echo Update source files... |
61 | 61 |
TOTAL_FILES=0 |
62 | 62 |
CHANGED_FILES=0 |
63 | 63 |
WARNED_FILES=0 |
64 | 64 |
} |
65 | 65 |
|
66 | 66 |
function update_done() { |
67 | 67 |
echo $CHANGED_FILES out of $TOTAL_FILES files has been changed. |
68 | 68 |
echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. |
69 | 69 |
} |
70 | 70 |
|
71 | 71 |
function update_begin() { |
72 | 72 |
((TOTAL_FILES++)) |
73 | 73 |
CHANGED=NO |
74 | 74 |
WARNED=NO |
75 | 75 |
} |
76 | 76 |
|
77 | 77 |
function update_end() { |
78 | 78 |
if [ $CHANGED == YES ] |
79 | 79 |
then |
80 | 80 |
((++CHANGED_FILES)) |
81 | 81 |
fi |
82 | 82 |
if [ $WARNED == YES ] |
83 | 83 |
then |
84 | 84 |
((++WARNED_FILES)) |
85 | 85 |
fi |
86 | 86 |
} |
87 | 87 |
|
88 | 88 |
function check_action() { |
89 | 89 |
if ! diff -q $1 $2 >/dev/null |
90 | 90 |
then |
91 |
echo |
|
91 |
echo |
|
92 |
echo -n " $3 failed at line(s): " |
|
93 |
echo -n $(diff $1 $2 | grep '^[0-9]' | sed "s/^\(.*\)c.*$/ \1/g" | |
|
94 |
sed "s/,/-/g" | paste -s -d',') |
|
92 | 95 |
FAILED=YES |
93 | 96 |
fi |
94 | 97 |
} |
95 | 98 |
|
96 | 99 |
function check_warning() { |
97 |
echo |
|
100 |
echo |
|
101 |
if [ "$2" == 'long lines' ] |
|
102 |
then |
|
103 |
echo -n " $2 warning at line(s): " |
|
104 |
echo -n $(grep -n -E '.{81,}' $1 | sed "s/^\([0-9]*\)/ \1\t/g" | |
|
105 |
cut -f 1 | paste -s -d',') |
|
106 |
else |
|
107 |
echo -n " $2 warning" |
|
108 |
fi |
|
98 | 109 |
WARNED=YES |
99 | 110 |
} |
100 | 111 |
|
101 | 112 |
function check_init() { |
102 | 113 |
echo Check source files... |
103 | 114 |
FAILED_FILES=0 |
104 | 115 |
WARNED_FILES=0 |
105 | 116 |
TOTAL_FILES=0 |
106 | 117 |
} |
107 | 118 |
|
108 | 119 |
function check_done() { |
109 | 120 |
echo $FAILED_FILES out of $TOTAL_FILES files has been failed. |
110 | 121 |
echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. |
111 | 122 |
|
112 | 123 |
if [ $FAILED_FILES -gt 0 ] |
113 | 124 |
then |
114 | 125 |
return 1 |
115 | 126 |
elif [ $WARNED_FILES -gt 0 ] |
116 | 127 |
then |
117 | 128 |
if [ "$WARNING" == 'INTERACTIVE' ] |
118 | 129 |
then |
119 | 130 |
echo -n "Are the files with warnings acceptable? (yes/no) " |
120 | 131 |
while read answer |
121 | 132 |
do |
122 | 133 |
if [ "$answer" == 'yes' ] |
123 | 134 |
then |
124 | 135 |
return 0 |
125 | 136 |
elif [ "$answer" == 'no' ] |
126 | 137 |
then |
127 | 138 |
return 1 |
128 | 139 |
fi |
129 | 140 |
echo -n "Are the files with warnings acceptable? (yes/no) " |
130 | 141 |
done |
131 | 142 |
elif [ "$WARNING" == 'WERROR' ] |
132 | 143 |
then |
133 | 144 |
return 1 |
134 | 145 |
fi |
135 | 146 |
fi |
136 | 147 |
} |
137 | 148 |
|
138 | 149 |
function check_begin() { |
139 | 150 |
((TOTAL_FILES++)) |
140 | 151 |
FAILED=NO |
141 | 152 |
WARNED=NO |
142 | 153 |
} |
143 | 154 |
|
144 | 155 |
function check_end() { |
145 | 156 |
if [ $FAILED == YES ] |
146 | 157 |
then |
147 | 158 |
((++FAILED_FILES)) |
148 | 159 |
fi |
149 | 160 |
if [ $WARNED == YES ] |
150 | 161 |
then |
151 | 162 |
((++WARNED_FILES)) |
152 | 163 |
fi |
153 | 164 |
} |
154 | 165 |
|
155 | 166 |
|
156 | 167 |
|
157 | 168 |
# checks |
158 | 169 |
|
159 | 170 |
function header_check() { |
160 | 171 |
if echo $1 | grep -q -E 'Makefile\.am$' |
161 | 172 |
then |
162 | 173 |
return |
163 | 174 |
fi |
164 | 175 |
|
165 | 176 |
TMP_FILE=`mktemp` |
166 | 177 |
|
167 | 178 |
(echo "/* -*- mode: C++; indent-tabs-mode: nil; -*- |
168 | 179 |
* |
169 | 180 |
* This file is a part of LEMON, a generic C++ optimization library. |
170 | 181 |
* |
171 | 182 |
* Copyright (C) "$YEAR" |
172 | 183 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
173 | 184 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
174 | 185 |
* |
175 | 186 |
* Permission to use, modify and distribute this software is granted |
176 | 187 |
* provided that this copyright notice appears in all copies. For |
177 | 188 |
* precise terms see the accompanying LICENSE file. |
178 | 189 |
* |
179 | 190 |
* This software is provided \"AS IS\" with no warranty of any kind, |
180 | 191 |
* express or implied, and with no claim as to its suitability for any |
181 | 192 |
* purpose. |
182 | 193 |
* |
183 | 194 |
*/ |
184 | 195 |
" |
185 | 196 |
awk 'BEGIN { pm=0; } |
186 | 197 |
pm==3 { print } |
187 | 198 |
/\/\* / && pm==0 { pm=1;} |
188 | 199 |
/[^:blank:]/ && (pm==0 || pm==2) { pm=3; print;} |
189 | 200 |
/\*\// && pm==1 { pm=2;} |
190 | 201 |
' $1 |
191 | 202 |
) >$TMP_FILE |
192 | 203 |
|
193 | 204 |
"$ACTION"_action "$TMP_FILE" "$1" header |
194 | 205 |
} |
195 | 206 |
|
196 | 207 |
function tabs_check() { |
197 | 208 |
if echo $1 | grep -q -v -E 'Makefile\.am$' |
198 | 209 |
then |
199 | 210 |
OLD_PATTERN=$(echo -e '\t') |
200 | 211 |
NEW_PATTERN=' ' |
201 | 212 |
else |
202 | 213 |
OLD_PATTERN=' ' |
203 | 214 |
NEW_PATTERN=$(echo -e '\t') |
204 | 215 |
fi |
205 | 216 |
TMP_FILE=`mktemp` |
206 | 217 |
cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE |
207 | 218 |
|
208 | 219 |
"$ACTION"_action "$TMP_FILE" "$1" 'tabs' |
209 | 220 |
} |
210 | 221 |
|
211 | 222 |
function spaces_check() { |
212 | 223 |
TMP_FILE=`mktemp` |
213 | 224 |
cat $1 | sed -e 's/ \+$//g' >$TMP_FILE |
214 | 225 |
|
215 |
"$ACTION"_action "$TMP_FILE" "$1" 'spaces' |
|
226 |
"$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces' |
|
216 | 227 |
} |
217 | 228 |
|
218 | 229 |
function long_lines_check() { |
219 | 230 |
if cat $1 | grep -q -E '.{81,}' |
220 | 231 |
then |
221 | 232 |
"$ACTION"_warning $1 'long lines' |
222 | 233 |
fi |
223 | 234 |
} |
224 | 235 |
|
225 | 236 |
# process the file |
226 | 237 |
|
227 | 238 |
function process_file() { |
228 |
echo -n " $ACTION |
|
239 |
echo -n " $ACTION $1..." |
|
229 | 240 |
|
230 | 241 |
CHECKING="header tabs spaces long_lines" |
231 | 242 |
|
232 | 243 |
"$ACTION"_begin $1 |
233 | 244 |
for check in $CHECKING |
234 | 245 |
do |
235 | 246 |
"$check"_check $1 |
236 | 247 |
done |
237 | 248 |
"$ACTION"_end $1 |
238 | 249 |
echo |
239 | 250 |
} |
240 | 251 |
|
241 | 252 |
function process_all { |
242 | 253 |
"$ACTION"_init |
243 | 254 |
while read file |
244 | 255 |
do |
245 | 256 |
process_file $file |
246 | 257 |
done < <($FILES) |
247 | 258 |
"$ACTION"_done |
248 | 259 |
} |
249 | 260 |
|
250 | 261 |
while [ $# -gt 0 ] |
251 | 262 |
do |
252 | 263 |
|
253 | 264 |
if [ "$1" == '--help' ] || [ "$1" == '-h' ] |
254 | 265 |
then |
255 | 266 |
echo -n \ |
256 | 267 |
"Usage: |
257 | 268 |
$0 [OPTIONS] [files] |
258 | 269 |
Options: |
259 | 270 |
--dry-run|-n |
260 | 271 |
Check the files, but do not modify them. |
261 | 272 |
--interactive|-i |
262 | 273 |
If --dry-run is specified and the checker emits warnings, |
263 | 274 |
then the user is asked if the warnings should be considered |
264 | 275 |
errors. |
265 | 276 |
--werror|-w |
266 | 277 |
Make all warnings into errors. |
267 | 278 |
--all|-a |
268 |
|
|
279 |
Check all source files in the repository. |
|
269 | 280 |
--modified|-m |
270 | 281 |
Check only the modified (and new) source files. This option is |
271 | 282 |
useful to check the modification before making a commit. |
272 | 283 |
--changed|-c |
273 | 284 |
Check only the changed source files compared to the parent(s) of |
274 | 285 |
the current hg node. This option is useful as hg hook script. |
275 | 286 |
To automatically check all your changes before making a commit, |
276 | 287 |
add the following section to the appropriate .hg/hgrc file. |
277 | 288 |
|
278 | 289 |
[hooks] |
279 | 290 |
pretxncommit.checksources = scripts/unify-sources.sh -c -n -i |
280 | 291 |
|
281 | 292 |
--help|-h |
282 | 293 |
Print this help message. |
283 | 294 |
files |
284 |
The files to check/unify. If no file names are given, the |
|
285 |
modified source will be checked/unified |
|
286 |
|
|
295 |
The files to check/unify. If no file names are given, the modified |
|
296 |
source files will be checked/unified (just like using the |
|
297 |
--modified|-m option). |
|
287 | 298 |
" |
288 | 299 |
exit 0 |
289 | 300 |
elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ] |
290 | 301 |
then |
291 |
[ -n "$ACTION" ] && echo " |
|
302 |
[ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1 |
|
292 | 303 |
ACTION=check |
293 | 304 |
elif [ "$1" == "--all" ] || [ "$1" == '-a' ] |
294 | 305 |
then |
295 |
[ -n "$FILES" ] && echo " |
|
306 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
|
296 | 307 |
FILES=all_files |
297 | 308 |
elif [ "$1" == "--changed" ] || [ "$1" == '-c' ] |
298 | 309 |
then |
299 |
[ -n "$FILES" ] && echo " |
|
310 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
|
300 | 311 |
FILES=changed_files |
301 | 312 |
elif [ "$1" == "--modified" ] || [ "$1" == '-m' ] |
302 | 313 |
then |
303 |
[ -n "$FILES" ] && echo " |
|
314 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
|
304 | 315 |
FILES=modified_files |
305 | 316 |
elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ] |
306 | 317 |
then |
307 |
[ -n "$WARNING" ] && echo " |
|
318 |
[ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 |
|
308 | 319 |
WARNING='INTERACTIVE' |
309 | 320 |
elif [ "$1" == "--werror" ] || [ "$1" == "-w" ] |
310 | 321 |
then |
311 |
[ -n "$WARNING" ] && echo " |
|
322 |
[ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 |
|
312 | 323 |
WARNING='WERROR' |
313 |
elif [ $(echo $1 | cut -c |
|
324 |
elif [ $(echo x$1 | cut -c 2) == '-' ] |
|
314 | 325 |
then |
315 | 326 |
echo "Invalid option $1" >&2 && exit 1 |
316 | 327 |
else |
317 | 328 |
[ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1 |
318 | 329 |
GIVEN_FILES=$@ |
319 | 330 |
FILES=given_files |
320 | 331 |
break |
321 | 332 |
fi |
322 | 333 |
|
323 | 334 |
shift |
324 | 335 |
done |
325 | 336 |
|
326 | 337 |
if [ -z $FILES ] |
327 | 338 |
then |
328 | 339 |
FILES=modified_files |
329 | 340 |
fi |
330 | 341 |
|
331 | 342 |
if [ -z $ACTION ] |
332 | 343 |
then |
333 | 344 |
ACTION=update |
334 | 345 |
fi |
335 | 346 |
|
336 | 347 |
process_all |
0 comments (0 inline)