r144:4e626dbbe408
Tue, 22 Apr 2008 13:50:52
[Not Reviewed]
0 comments (0 inline)
0
1
0
25
18
| ... | ... |
@@ -858,146 +858,153 @@ |
| 858 | 858 |
|
| 859 | 859 |
/// \brief The first arc of the path. |
| 860 | 860 |
const Arc& front() const {
|
| 861 | 861 |
return arcs[0]; |
| 862 | 862 |
} |
| 863 | 863 |
|
| 864 | 864 |
/// \brief The last arc of the path. |
| 865 | 865 |
const Arc& back() const {
|
| 866 | 866 |
return arcs[len - 1]; |
| 867 | 867 |
} |
| 868 | 868 |
|
| 869 | 869 |
|
| 870 | 870 |
typedef True BuildTag; |
| 871 | 871 |
|
| 872 | 872 |
template <typename CPath> |
| 873 | 873 |
void build(const CPath& path) {
|
| 874 | 874 |
len = path.length(); |
| 875 | 875 |
arcs = new Arc[len]; |
| 876 | 876 |
int index = 0; |
| 877 | 877 |
for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
|
| 878 | 878 |
arcs[index] = it; |
| 879 | 879 |
++index; |
| 880 | 880 |
} |
| 881 | 881 |
} |
| 882 | 882 |
|
| 883 | 883 |
template <typename CPath> |
| 884 | 884 |
void buildRev(const CPath& path) {
|
| 885 | 885 |
len = path.length(); |
| 886 | 886 |
arcs = new Arc[len]; |
| 887 | 887 |
int index = len; |
| 888 | 888 |
for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
|
| 889 | 889 |
--index; |
| 890 | 890 |
arcs[index] = it; |
| 891 | 891 |
} |
| 892 | 892 |
} |
| 893 | 893 |
|
| 894 | 894 |
private: |
| 895 | 895 |
int len; |
| 896 | 896 |
Arc* arcs; |
| 897 | 897 |
}; |
| 898 | 898 |
|
| 899 | 899 |
/////////////////////////////////////////////////////////////////////// |
| 900 | 900 |
// Additional utilities |
| 901 | 901 |
/////////////////////////////////////////////////////////////////////// |
| 902 | 902 |
|
| 903 | 903 |
namespace _path_bits {
|
| 904 | 904 |
|
| 905 | 905 |
template <typename Path, typename Enable = void> |
| 906 |
struct |
|
| 906 |
struct RevPathTagIndicator {
|
|
| 907 | 907 |
static const bool value = false; |
| 908 | 908 |
}; |
| 909 | 909 |
|
| 910 |
template <typename Digraph> |
|
| 911 |
struct RevTagIndicator< |
|
| 912 |
Digraph, |
|
| 913 |
typename enable_if<typename Digraph::RevTag, void>::type |
|
| 910 |
template <typename Path> |
|
| 911 |
struct RevPathTagIndicator< |
|
| 912 |
Path, |
|
| 913 |
typename enable_if<typename Path::RevPathTag, void>::type |
|
| 914 |
> {
|
|
| 915 |
static const bool value = true; |
|
| 916 |
}; |
|
| 917 |
|
|
| 918 |
template <typename Path, typename Enable = void> |
|
| 919 |
struct BuildTagIndicator {
|
|
| 920 |
static const bool value = false; |
|
| 921 |
}; |
|
| 922 |
|
|
| 923 |
template <typename Path> |
|
| 924 |
struct BuildTagIndicator< |
|
| 925 |
Path, |
|
| 926 |
typename enable_if<typename Path::BuildTag, void>::type |
|
| 914 | 927 |
> {
|
| 915 | 928 |
static const bool value = true; |
| 916 | 929 |
}; |
| 917 | 930 |
|
| 918 | 931 |
template <typename Target, typename Source, |
| 919 |
|
|
| 932 |
bool buildEnable = BuildTagIndicator<Target>::value, |
|
| 933 |
bool revEnable = RevPathTagIndicator<Source>::value> |
|
| 920 | 934 |
struct PathCopySelector {
|
| 921 | 935 |
static void copy(Target& target, const Source& source) {
|
| 922 | 936 |
target.clear(); |
| 923 | 937 |
for (typename Source::ArcIt it(source); it != INVALID; ++it) {
|
| 924 | 938 |
target.addBack(it); |
| 925 | 939 |
} |
| 926 | 940 |
} |
| 927 | 941 |
}; |
| 928 | 942 |
|
| 929 |
template <typename Target, typename Source, typename BuildEnable> |
|
| 930 |
struct PathCopySelector< |
|
| 931 |
Target, Source, BuildEnable, |
|
| 932 |
typename enable_if<typename Source::RevPathTag, void>::type> {
|
|
| 943 |
template <typename Target, typename Source> |
|
| 944 |
struct PathCopySelector<Target, Source, false, true> {
|
|
| 933 | 945 |
static void copy(Target& target, const Source& source) {
|
| 934 | 946 |
target.clear(); |
| 935 | 947 |
for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
|
| 936 | 948 |
target.addFront(it); |
| 937 | 949 |
} |
| 938 | 950 |
} |
| 939 | 951 |
}; |
| 940 | 952 |
|
| 941 |
template <typename Target, typename Source, typename RevEnable> |
|
| 942 |
struct PathCopySelector< |
|
| 943 |
Target, Source, |
|
| 944 |
typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
|
|
| 953 |
template <typename Target, typename Source> |
|
| 954 |
struct PathCopySelector<Target, Source, true, false> {
|
|
| 945 | 955 |
static void copy(Target& target, const Source& source) {
|
| 946 | 956 |
target.clear(); |
| 947 | 957 |
target.build(source); |
| 948 | 958 |
} |
| 949 | 959 |
}; |
| 950 | 960 |
|
| 951 | 961 |
template <typename Target, typename Source> |
| 952 |
struct PathCopySelector< |
|
| 953 |
Target, Source, |
|
| 954 |
typename enable_if<typename Target::BuildTag, void>::type, |
|
| 955 |
typename enable_if<typename Source::RevPathTag, void>::type> {
|
|
| 962 |
struct PathCopySelector<Target, Source, true, true> {
|
|
| 956 | 963 |
static void copy(Target& target, const Source& source) {
|
| 957 | 964 |
target.clear(); |
| 958 | 965 |
target.buildRev(source); |
| 959 | 966 |
} |
| 960 | 967 |
}; |
| 961 | 968 |
|
| 962 | 969 |
} |
| 963 | 970 |
|
| 964 | 971 |
|
| 965 | 972 |
/// \brief Make a copy of a path. |
| 966 | 973 |
/// |
| 967 | 974 |
/// This function makes a copy of a path. |
| 968 | 975 |
template <typename Target, typename Source> |
| 969 | 976 |
void copyPath(Target& target, const Source& source) {
|
| 970 | 977 |
checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>(); |
| 971 | 978 |
_path_bits::PathCopySelector<Target, Source>::copy(target, source); |
| 972 | 979 |
} |
| 973 | 980 |
|
| 974 | 981 |
/// \brief Check the consistency of a path. |
| 975 | 982 |
/// |
| 976 | 983 |
/// This function checks that the target of each arc is the same |
| 977 | 984 |
/// as the source of the next one. |
| 978 | 985 |
/// |
| 979 | 986 |
template <typename Digraph, typename Path> |
| 980 | 987 |
bool checkPath(const Digraph& digraph, const Path& path) {
|
| 981 | 988 |
typename Path::ArcIt it(path); |
| 982 | 989 |
if (it == INVALID) return true; |
| 983 | 990 |
typename Digraph::Node node = digraph.target(it); |
| 984 | 991 |
++it; |
| 985 | 992 |
while (it != INVALID) {
|
| 986 | 993 |
if (digraph.source(it) != node) return false; |
| 987 | 994 |
node = digraph.target(it); |
| 988 | 995 |
++it; |
| 989 | 996 |
} |
| 990 | 997 |
return true; |
| 991 | 998 |
} |
| 992 | 999 |
|
| 993 | 1000 |
/// \brief The source of a path |
| 994 | 1001 |
/// |
| 995 | 1002 |
/// This function returns the source of the given path. |
| 996 | 1003 |
template <typename Digraph, typename Path> |
| 997 | 1004 |
typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
|
| 998 | 1005 |
return digraph.source(path.front()); |
| 999 | 1006 |
} |
| 1000 | 1007 |
|
| 1001 | 1008 |
/// \brief The target of a path |
| 1002 | 1009 |
/// |
| 1003 | 1010 |
/// This function returns the target of the given path. |
0 comments (0 inline)