137 |
138 |
138 private: |
139 private: |
139 const Path *path; |
140 const Path *path; |
140 int idx; |
141 int idx; |
141 }; |
142 }; |
|
143 |
|
144 /// \brief Gets the collection of the arcs of the path. |
|
145 /// |
|
146 /// This function can be used for iterating on the |
|
147 /// arcs of the path. It returns a wrapped |
|
148 /// ArcIt, which looks like an STL container |
|
149 /// (by having begin() and end()) which you can use in range-based |
|
150 /// for loops, STL algorithms, etc. |
|
151 /// For example you can write: |
|
152 ///\code |
|
153 /// for(auto a: p.arcs()) |
|
154 /// doSomething(a); |
|
155 ///\endcode |
|
156 LemonRangeWrapper1<ArcIt, Path> arcs() const { |
|
157 return LemonRangeWrapper1<ArcIt, Path>(*this); |
|
158 } |
|
159 |
142 |
160 |
143 /// \brief Length of the path. |
161 /// \brief Length of the path. |
144 int length() const { return head.size() + tail.size(); } |
162 int length() const { return head.size() + tail.size(); } |
145 /// \brief Return whether the path is empty. |
163 /// \brief Return whether the path is empty. |
146 bool empty() const { return head.empty() && tail.empty(); } |
164 bool empty() const { return head.empty() && tail.empty(); } |
343 private: |
361 private: |
344 const SimplePath *path; |
362 const SimplePath *path; |
345 int idx; |
363 int idx; |
346 }; |
364 }; |
347 |
365 |
|
366 /// \brief Gets the collection of the arcs of the path. |
|
367 /// |
|
368 /// This function can be used for iterating on the |
|
369 /// arcs of the path. It returns a wrapped |
|
370 /// ArcIt, which looks like an STL container |
|
371 /// (by having begin() and end()) which you can use in range-based |
|
372 /// for loops, STL algorithms, etc. |
|
373 /// For example you can write: |
|
374 ///\code |
|
375 /// for(auto a: p.arcs()) |
|
376 /// doSomething(a); |
|
377 ///\endcode |
|
378 LemonRangeWrapper1<ArcIt, SimplePath> arcs() const { |
|
379 return LemonRangeWrapper1<ArcIt, SimplePath>(*this); |
|
380 } |
|
381 |
|
382 |
348 /// \brief Length of the path. |
383 /// \brief Length of the path. |
349 int length() const { return data.size(); } |
384 int length() const { return data.size(); } |
350 /// \brief Return true if the path is empty. |
385 /// \brief Return true if the path is empty. |
351 bool empty() const { return data.empty(); } |
386 bool empty() const { return data.empty(); } |
352 |
387 |
540 |
575 |
541 private: |
576 private: |
542 const ListPath *path; |
577 const ListPath *path; |
543 Node *node; |
578 Node *node; |
544 }; |
579 }; |
|
580 |
|
581 /// \brief Gets the collection of the arcs of the path. |
|
582 /// |
|
583 /// This function can be used for iterating on the |
|
584 /// arcs of the path. It returns a wrapped |
|
585 /// ArcIt, which looks like an STL container |
|
586 /// (by having begin() and end()) which you can use in range-based |
|
587 /// for loops, STL algorithms, etc. |
|
588 /// For example you can write: |
|
589 ///\code |
|
590 /// for(auto a: p.arcs()) |
|
591 /// doSomething(a); |
|
592 ///\endcode |
|
593 LemonRangeWrapper1<ArcIt, ListPath> arcs() const { |
|
594 return LemonRangeWrapper1<ArcIt, ListPath>(*this); |
|
595 } |
|
596 |
545 |
597 |
546 /// \brief The n-th arc. |
598 /// \brief The n-th arc. |
547 /// |
599 /// |
548 /// This function looks for the n-th arc in O(n) time. |
600 /// This function looks for the n-th arc in O(n) time. |
549 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
601 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
793 typedef typename Digraph::Arc Arc; |
845 typedef typename Digraph::Arc Arc; |
794 |
846 |
795 /// \brief Default constructor |
847 /// \brief Default constructor |
796 /// |
848 /// |
797 /// Default constructor |
849 /// Default constructor |
798 StaticPath() : len(0), arcs(0) {} |
850 StaticPath() : len(0), _arcs(0) {} |
799 |
851 |
800 /// \brief Copy constructor |
852 /// \brief Copy constructor |
801 /// |
853 /// |
802 StaticPath(const StaticPath& cpath) : arcs(0) { |
854 StaticPath(const StaticPath& cpath) : _arcs(0) { |
803 pathCopy(cpath, *this); |
855 pathCopy(cpath, *this); |
804 } |
856 } |
805 |
857 |
806 /// \brief Template copy constructor |
858 /// \brief Template copy constructor |
807 /// |
859 /// |
808 /// This path can be initialized from any other path type. |
860 /// This path can be initialized from any other path type. |
809 template <typename CPath> |
861 template <typename CPath> |
810 StaticPath(const CPath& cpath) : arcs(0) { |
862 StaticPath(const CPath& cpath) : _arcs(0) { |
811 pathCopy(cpath, *this); |
863 pathCopy(cpath, *this); |
812 } |
864 } |
813 |
865 |
814 /// \brief Destructor of the path |
866 /// \brief Destructor of the path |
815 /// |
867 /// |
816 /// Destructor of the path |
868 /// Destructor of the path |
817 ~StaticPath() { |
869 ~StaticPath() { |
818 if (arcs) delete[] arcs; |
870 if (_arcs) delete[] _arcs; |
819 } |
871 } |
820 |
872 |
821 /// \brief Copy assignment |
873 /// \brief Copy assignment |
822 /// |
874 /// |
823 StaticPath& operator=(const StaticPath& cpath) { |
875 StaticPath& operator=(const StaticPath& cpath) { |
880 |
932 |
881 private: |
933 private: |
882 const StaticPath *path; |
934 const StaticPath *path; |
883 int idx; |
935 int idx; |
884 }; |
936 }; |
|
937 |
|
938 /// \brief Gets the collection of the arcs of the path. |
|
939 /// |
|
940 /// This function can be used for iterating on the |
|
941 /// arcs of the path. It returns a wrapped |
|
942 /// ArcIt, which looks like an STL container |
|
943 /// (by having begin() and end()) which you can use in range-based |
|
944 /// for loops, STL algorithms, etc. |
|
945 /// For example you can write: |
|
946 ///\code |
|
947 /// for(auto a: p.arcs()) |
|
948 /// doSomething(a); |
|
949 ///\endcode |
|
950 LemonRangeWrapper1<ArcIt, StaticPath> arcs() const { |
|
951 return LemonRangeWrapper1<ArcIt, StaticPath>(*this); |
|
952 } |
|
953 |
885 |
954 |
886 /// \brief The n-th arc. |
955 /// \brief The n-th arc. |
887 /// |
956 /// |
888 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
957 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
889 const Arc& nth(int n) const { |
958 const Arc& nth(int n) const { |
890 return arcs[n]; |
959 return _arcs[n]; |
891 } |
960 } |
892 |
961 |
893 /// \brief The arc iterator pointing to the n-th arc. |
962 /// \brief The arc iterator pointing to the n-th arc. |
894 ArcIt nthIt(int n) const { |
963 ArcIt nthIt(int n) const { |
895 return ArcIt(*this, n); |
964 return ArcIt(*this, n); |
902 int empty() const { return len == 0; } |
971 int empty() const { return len == 0; } |
903 |
972 |
904 /// \brief Erase all arcs in the digraph. |
973 /// \brief Erase all arcs in the digraph. |
905 void clear() { |
974 void clear() { |
906 len = 0; |
975 len = 0; |
907 if (arcs) delete[] arcs; |
976 if (_arcs) delete[] _arcs; |
908 arcs = 0; |
977 _arcs = 0; |
909 } |
978 } |
910 |
979 |
911 /// \brief The first arc of the path. |
980 /// \brief The first arc of the path. |
912 const Arc& front() const { |
981 const Arc& front() const { |
913 return arcs[0]; |
982 return _arcs[0]; |
914 } |
983 } |
915 |
984 |
916 /// \brief The last arc of the path. |
985 /// \brief The last arc of the path. |
917 const Arc& back() const { |
986 const Arc& back() const { |
918 return arcs[len - 1]; |
987 return _arcs[len - 1]; |
919 } |
988 } |
920 |
989 |
921 |
990 |
922 typedef True BuildTag; |
991 typedef True BuildTag; |
923 |
992 |
924 template <typename CPath> |
993 template <typename CPath> |
925 void build(const CPath& path) { |
994 void build(const CPath& path) { |
926 len = path.length(); |
995 len = path.length(); |
927 arcs = new Arc[len]; |
996 _arcs = new Arc[len]; |
928 int index = 0; |
997 int index = 0; |
929 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
998 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
930 arcs[index] = it; |
999 _arcs[index] = it; |
931 ++index; |
1000 ++index; |
932 } |
1001 } |
933 } |
1002 } |
934 |
1003 |
935 template <typename CPath> |
1004 template <typename CPath> |
936 void buildRev(const CPath& path) { |
1005 void buildRev(const CPath& path) { |
937 len = path.length(); |
1006 len = path.length(); |
938 arcs = new Arc[len]; |
1007 _arcs = new Arc[len]; |
939 int index = len; |
1008 int index = len; |
940 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
1009 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
941 --index; |
1010 --index; |
942 arcs[index] = it; |
1011 _arcs[index] = it; |
943 } |
1012 } |
944 } |
1013 } |
945 |
1014 |
946 private: |
1015 private: |
947 int len; |
1016 int len; |
948 Arc* arcs; |
1017 Arc* _arcs; |
949 }; |
1018 }; |
950 |
1019 |
951 /////////////////////////////////////////////////////////////////////// |
1020 /////////////////////////////////////////////////////////////////////// |
952 // Additional utilities |
1021 // Additional utilities |
953 /////////////////////////////////////////////////////////////////////// |
1022 /////////////////////////////////////////////////////////////////////// |
1155 return (_it < n._it && _nd != INVALID); |
1224 return (_it < n._it && _nd != INVALID); |
1156 } |
1225 } |
1157 |
1226 |
1158 }; |
1227 }; |
1159 |
1228 |
|
1229 /// \brief Gets the collection of the nodes of the path. |
|
1230 /// |
|
1231 /// This function can be used for iterating on the |
|
1232 /// nodes of the path. It returns a wrapped |
|
1233 /// PathNodeIt, which looks like an STL container |
|
1234 /// (by having begin() and end()) which you can use in range-based |
|
1235 /// for loops, STL algorithms, etc. |
|
1236 /// For example you can write: |
|
1237 ///\code |
|
1238 /// for(auto u: pathNodes(g,p)) |
|
1239 /// doSomething(u); |
|
1240 ///\endcode |
|
1241 template<typename Path> |
|
1242 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path> |
|
1243 pathNodes(const typename Path::Digraph &g, const Path &p) { |
|
1244 return |
|
1245 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>(g,p); |
|
1246 } |
|
1247 |
1160 ///@} |
1248 ///@} |
1161 |
1249 |
1162 } // namespace lemon |
1250 } // namespace lemon |
1163 |
1251 |
1164 #endif // LEMON_PATH_H |
1252 #endif // LEMON_PATH_H |