git.sesse.net Git - casparcg/blob - dependencies64/boost/boost/graph/reverse_graph.hpp

   1 //  (C) Copyright David Abrahams 2000.
   2 // Distributed under the Boost Software License, Version 1.0. (See
   3 // accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef REVERSE_GRAPH_DWA092300_H_
   7 # define REVERSE_GRAPH_DWA092300_H_
   8
   9 #include <boost/graph/adjacency_iterator.hpp>
  10 #include <boost/graph/properties.hpp>
  11 #include <boost/iterator/transform_iterator.hpp>
  12 #include <boost/tuple/tuple.hpp>
  13 #include <boost/type_traits.hpp>
  14 #include <boost/mpl/if.hpp>
  15
  16 namespace boost {
  17
  18 struct reverse_graph_tag { };
  19
  20   namespace detail {
  21
  22     template <typename EdgeDesc>
  23     class reverse_graph_edge_descriptor {
  24       public:
  25       EdgeDesc underlying_descx; // Odd name is because this needs to be public but shouldn't be exposed to users anymore
  26
  27       private:
  28       typedef EdgeDesc base_descriptor_type;
  29
  30       public:
  31       explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_descx = EdgeDesc())
  32         : underlying_descx(underlying_descx) {}
  33
  34       friend bool operator==(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  35         return a.underlying_descx == b.underlying_descx;
  36       }
  37       friend bool operator!=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  38         return a.underlying_descx != b.underlying_descx;
  39       }
  40       friend bool operator<(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  41         return a.underlying_descx < b.underlying_descx;
  42       }
  43       friend bool operator>(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  44         return a.underlying_descx > b.underlying_descx;
  45       }
  46       friend bool operator<=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  47         return a.underlying_descx <= b.underlying_descx;
  48       }
  49       friend bool operator>=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
  50         return a.underlying_descx >= b.underlying_descx;
  51       }
  52     };
  53
  54     template <typename EdgeDesc>
  55     struct reverse_graph_edge_descriptor_maker {
  56       typedef reverse_graph_edge_descriptor<EdgeDesc> result_type;
  57
  58       reverse_graph_edge_descriptor<EdgeDesc> operator()(const EdgeDesc& ed) const {
  59         return reverse_graph_edge_descriptor<EdgeDesc>(ed);
  60       }
  61     };
  62
  63     template <typename EdgeDesc, typename Iter>
  64     std::pair<transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter>,
  65               transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter> >
  66     reverse_edge_iter_pair(const std::pair<Iter, Iter>& ip) {
  67       return std::make_pair(make_transform_iterator(ip.first, reverse_graph_edge_descriptor_maker<EdgeDesc>()),
  68                             make_transform_iterator(ip.second, reverse_graph_edge_descriptor_maker<EdgeDesc>()));
  69     }
  70
  71     // Get the underlying descriptor from a vertex or edge descriptor
  72     template <typename Desc>
  73     struct get_underlying_descriptor_from_reverse_descriptor {
  74       typedef Desc type;
  75       static Desc convert(const Desc& d) {return d;}
  76     };
  77     template <typename Desc>
  78     struct get_underlying_descriptor_from_reverse_descriptor<reverse_graph_edge_descriptor<Desc> > {
  79       typedef Desc type;
  80       static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {return d.underlying_descx;}
  81     };
  82
  83     template <bool isEdgeList> struct choose_rev_edge_iter { };
  84     template <> struct choose_rev_edge_iter<true> {
  85       template <class G> struct bind_ {
  86         typedef transform_iterator<reverse_graph_edge_descriptor_maker<typename graph_traits<G>::edge_descriptor>, typename graph_traits<G>::edge_iterator> type;
  87       };
  88     };
  89     template <> struct choose_rev_edge_iter<false> {
  90       template <class G> struct bind_ {
  91         typedef void type;
  92       };
  93     };
  94
  95   } // namespace detail
  96
  97 template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
  98 class reverse_graph {
  99     typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
 100     typedef graph_traits<BidirectionalGraph> Traits;
 101  public:
 102     typedef BidirectionalGraph base_type;
 103     typedef GraphRef base_ref_type;
 104
 105     // Constructor
 106     reverse_graph(GraphRef g) : m_g(g) {}
 107     // Conversion from reverse_graph on non-const reference to one on const reference
 108     reverse_graph(const reverse_graph<BidirectionalGraph, BidirectionalGraph&>& o): m_g(o.m_g) {}
 109
 110     // Graph requirements
 111     typedef typename Traits::vertex_descriptor vertex_descriptor;
 112     typedef detail::reverse_graph_edge_descriptor<typename Traits::edge_descriptor> edge_descriptor;
 113     typedef typename Traits::directed_category directed_category;
 114     typedef typename Traits::edge_parallel_category edge_parallel_category;
 115     typedef typename Traits::traversal_category traversal_category;
 116
 117     // IncidenceGraph requirements
 118     typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::in_edge_iterator> out_edge_iterator;
 119     typedef typename Traits::degree_size_type degree_size_type;
 120
 121     // BidirectionalGraph requirements
 122     typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::out_edge_iterator> in_edge_iterator;
 123
 124     // AdjacencyGraph requirements
 125     typedef typename adjacency_iterator_generator<Self, vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
 126
 127     // VertexListGraph requirements
 128     typedef typename Traits::vertex_iterator vertex_iterator;
 129
 130     // EdgeListGraph requirements
 131     enum { is_edge_list = is_convertible<traversal_category,
 132            edge_list_graph_tag>::value };
 133     typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
 134     typedef typename ChooseEdgeIter::
 135       template bind_<BidirectionalGraph>::type   edge_iterator;
 136     typedef typename Traits::vertices_size_type vertices_size_type;
 137     typedef typename Traits::edges_size_type edges_size_type;
 138
 139     typedef reverse_graph_tag graph_tag;
 140
 141 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 142     // Bundled properties support
 143     template<typename Descriptor>
 144     typename graph::detail::bundled_result<
 145                BidirectionalGraph,
 146                typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type
 147              >::type&
 148     operator[](Descriptor x)
 149     { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; }
 150
 151     template<typename Descriptor>
 152     typename graph::detail::bundled_result<
 153                BidirectionalGraph,
 154                typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type
 155              >::type const&
 156     operator[](Descriptor x) const
 157     { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; }
 158 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 159
 160     static vertex_descriptor null_vertex()
 161     { return Traits::null_vertex(); }
 162
 163     // would be private, but template friends aren't portable enough.
 164  // private:
 165     GraphRef m_g;
 166 };
 167
 168
 169 // These are separate so they are not instantiated unless used (see bug 1021)
 170 template <class BidirectionalGraph, class GraphRef>
 171 struct vertex_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
 172   typedef typename boost::vertex_property_type<BidirectionalGraph>::type type;
 173 };
 174
 175 template <class BidirectionalGraph, class GraphRef>
 176 struct edge_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
 177   typedef typename boost::edge_property_type<BidirectionalGraph>::type type;
 178 };
 179
 180 template <class BidirectionalGraph, class GraphRef>
 181 struct graph_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
 182   typedef typename boost::graph_property_type<BidirectionalGraph>::type type;
 183 };
 184
 185 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 186   template<typename Graph, typename GraphRef>
 187   struct vertex_bundle_type<reverse_graph<Graph, GraphRef> >
 188     : vertex_bundle_type<Graph> { };
 189
 190   template<typename Graph, typename GraphRef>
 191   struct edge_bundle_type<reverse_graph<Graph, GraphRef> >
 192     : edge_bundle_type<Graph> { };
 193
 194   template<typename Graph, typename GraphRef>
 195   struct graph_bundle_type<reverse_graph<Graph, GraphRef> >
 196     : graph_bundle_type<Graph> { };
 197 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 198
 199 template <class BidirectionalGraph>
 200 inline reverse_graph<BidirectionalGraph>
 201 make_reverse_graph(const BidirectionalGraph& g)
 202 {
 203     return reverse_graph<BidirectionalGraph>(g);
 204 }
 205
 206 template <class BidirectionalGraph>
 207 inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
 208 make_reverse_graph(BidirectionalGraph& g)
 209 {
 210     return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
 211 }
 212
 213 template <class BidirectionalGraph, class GRef>
 214 std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
 215           typename reverse_graph<BidirectionalGraph>::vertex_iterator>
 216 vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
 217 {
 218     return vertices(g.m_g);
 219 }
 220
 221 template <class BidirectionalGraph, class GRef>
 222 std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
 223           typename reverse_graph<BidirectionalGraph>::edge_iterator>
 224 edges(const reverse_graph<BidirectionalGraph,GRef>& g)
 225 {
 226     return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(edges(g.m_g));
 227 }
 228
 229 template <class BidirectionalGraph, class GRef>
 230 inline std::pair<typename reverse_graph<BidirectionalGraph>::out_edge_iterator,
 231                  typename reverse_graph<BidirectionalGraph>::out_edge_iterator>
 232 out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 233           const reverse_graph<BidirectionalGraph,GRef>& g)
 234 {
 235     return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(in_edges(u, g.m_g));
 236 }
 237
 238 template <class BidirectionalGraph, class GRef>
 239 inline typename graph_traits<BidirectionalGraph>::vertices_size_type
 240 num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
 241 {
 242     return num_vertices(g.m_g);
 243 }
 244
 245 template <class BidirectionalGraph, class GRef>
 246 inline typename reverse_graph<BidirectionalGraph>::edges_size_type
 247 num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
 248 {
 249     return num_edges(g.m_g);
 250 }
 251
 252 template <class BidirectionalGraph, class GRef>
 253 inline typename graph_traits<BidirectionalGraph>::degree_size_type
 254 out_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 255            const reverse_graph<BidirectionalGraph,GRef>& g)
 256 {
 257     return in_degree(u, g.m_g);
 258 }
 259
 260 template <class BidirectionalGraph, class GRef>
 261 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
 262 vertex(const typename graph_traits<BidirectionalGraph>::vertices_size_type v,
 263        const reverse_graph<BidirectionalGraph,GRef>& g)
 264 {
 265     return vertex(v, g.m_g);
 266 }
 267
 268 template <class BidirectionalGraph, class GRef>
 269 inline std::pair< typename graph_traits<reverse_graph<BidirectionalGraph,GRef> >::edge_descriptor,
 270                   bool>
 271 edge(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 272      const typename graph_traits<BidirectionalGraph>::vertex_descriptor v,
 273      const reverse_graph<BidirectionalGraph,GRef>& g)
 274 {
 275     typedef typename graph_traits<BidirectionalGraph>::edge_descriptor underlying_edge_descriptor;
 276     std::pair<underlying_edge_descriptor, bool> e = edge(v, u, g.m_g);
 277     return std::make_pair(detail::reverse_graph_edge_descriptor<underlying_edge_descriptor>(e.first), e.second);
 278 }
 279
 280 template <class BidirectionalGraph, class GRef>
 281 inline std::pair<typename reverse_graph<BidirectionalGraph>::in_edge_iterator,
 282                  typename reverse_graph<BidirectionalGraph>::in_edge_iterator>
 283 in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 284          const reverse_graph<BidirectionalGraph,GRef>& g)
 285 {
 286     return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(out_edges(u, g.m_g));
 287 }
 288
 289 template <class BidirectionalGraph, class GRef>
 290 inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
 291     typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
 292 adjacent_vertices(typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 293                   const reverse_graph<BidirectionalGraph,GRef>& g)
 294 {
 295     typedef reverse_graph<BidirectionalGraph,GRef> Graph;
 296     typename graph_traits<Graph>::out_edge_iterator first, last;
 297     boost::tie(first, last) = out_edges(u, g);
 298     typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
 299     return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
 300                           adjacency_iterator(last, const_cast<Graph*>(&g)));
 301 }
 302
 303 template <class BidirectionalGraph, class GRef>
 304 inline typename graph_traits<BidirectionalGraph>::degree_size_type
 305 in_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 306           const reverse_graph<BidirectionalGraph,GRef>& g)
 307 {
 308     return out_degree(u, g.m_g);
 309 }
 310
 311 template <class Edge, class BidirectionalGraph, class GRef>
 312 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
 313 source(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
 314 {
 315     return target(e.underlying_descx, g.m_g);
 316 }
 317
 318 template <class Edge, class BidirectionalGraph, class GRef>
 319 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
 320 target(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
 321 {
 322     return source(e.underlying_descx, g.m_g);
 323 }
 324
 325
 326 namespace detail {
 327
 328   template <typename PM>
 329   struct reverse_graph_edge_property_map {
 330     private:
 331     PM underlying_pm;
 332
 333     public:
 334     typedef reverse_graph_edge_descriptor<typename property_traits<PM>::key_type> key_type;
 335     typedef typename property_traits<PM>::value_type value_type;
 336     typedef typename property_traits<PM>::reference reference;
 337     typedef typename property_traits<PM>::category category;
 338
 339     explicit reverse_graph_edge_property_map(const PM& pm): underlying_pm(pm) {}
 340
 341     friend reference
 342     get(const reverse_graph_edge_property_map& m,
 343         const key_type& e) {
 344       return get(m.underlying_pm, e.underlying_descx);
 345     }
 346
 347     friend void
 348     put(const reverse_graph_edge_property_map& m,
 349         const key_type& e,
 350         const value_type& v) {
 351       put(m.underlying_pm, e.underlying_descx, v);
 352     }
 353
 354     reference operator[](const key_type& k) const {
 355       return (this->underlying_pm)[k.underlying_descx];
 356     }
 357   };
 358
 359 } // namespace detail
 360
 361 template <class BidirGraph, class GRef, class Property>
 362 struct property_map<reverse_graph<BidirGraph, GRef>, Property> {
 363   typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop;
 364   typedef boost::is_const<typename boost::remove_reference<GRef>::type> is_ref_const;
 365   typedef typename boost::mpl::if_<
 366                      is_ref_const,
 367                      typename property_map<BidirGraph, Property>::const_type,
 368                      typename property_map<BidirGraph, Property>::type>::type
 369     orig_type;
 370   typedef typename property_map<BidirGraph, Property>::const_type orig_const_type;
 371   typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type type;
 372   typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type;
 373 };
 374
 375 template <class BidirGraph, class GRef, class Property>
 376 struct property_map<const reverse_graph<BidirGraph, GRef>, Property> {
 377   typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop;
 378   typedef typename property_map<BidirGraph, Property>::const_type orig_const_type;
 379   typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type;
 380   typedef const_type type;
 381 };
 382
 383 template <class BidirGraph, class GRef, class Property>
 384 typename disable_if<
 385   is_same<Property, edge_underlying_t>,
 386   typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type>::type
 387 get(Property p, reverse_graph<BidirGraph,GRef>& g)
 388 {
 389   return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g));
 390 }
 391
 392 template <class BidirGraph, class GRef, class Property>
 393 typename disable_if<
 394   is_same<Property, edge_underlying_t>,
 395   typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type>::type
 396 get(Property p, const reverse_graph<BidirGraph,GRef>& g)
 397 {
 398   const BidirGraph& gref = g.m_g; // in case GRef is non-const
 399   return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type(get(p, gref));
 400 }
 401
 402 template <class BidirectionalGraph, class GRef, class Property, class Key>
 403 typename disable_if<
 404   is_same<Property, edge_underlying_t>,
 405   typename property_traits<
 406     typename property_map<reverse_graph<BidirectionalGraph, GRef>, Property>::const_type
 407   >::value_type>::type
 408 get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
 409 {
 410   return get(get(p, g), k);
 411 }
 412
 413 template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
 414 void
 415 put(Property p, reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
 416     const Value& val)
 417 {
 418   put(get(p, g), k, val);
 419 }
 420
 421 // Get the underlying descriptor from a reverse_graph's wrapped edge descriptor
 422
 423 namespace detail {
 424   template <class E>
 425   struct underlying_edge_desc_map_type {
 426     E operator[](const reverse_graph_edge_descriptor<E>& k) const {
 427       return k.underlying_descx;
 428     }
 429   };
 430
 431   template <class E>
 432   E
 433   get(underlying_edge_desc_map_type<E> m,
 434       const reverse_graph_edge_descriptor<E>& k)
 435   {
 436     return m[k];
 437   }
 438 }
 439
 440 template <class E>
 441 struct property_traits<detail::underlying_edge_desc_map_type<E> > {
 442   typedef detail::reverse_graph_edge_descriptor<E> key_type;
 443   typedef E value_type;
 444   typedef const E& reference;
 445   typedef readable_property_map_tag category;
 446 };
 447
 448 template <class Graph, class GRef>
 449 struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> {
 450   private:
 451   typedef typename graph_traits<Graph>::edge_descriptor ed;
 452
 453   public:
 454   typedef detail::underlying_edge_desc_map_type<ed> type;
 455   typedef detail::underlying_edge_desc_map_type<ed> const_type;
 456 };
 457
 458 template <typename T> struct is_reverse_graph: boost::mpl::false_ {};
 459 template <typename G, typename R> struct is_reverse_graph<reverse_graph<G, R> >: boost::mpl::true_ {};
 460
 461 template <class G>
 462 typename enable_if<is_reverse_graph<G>,
 463   detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type
 464 get(edge_underlying_t,
 465     G&)
 466 {
 467   return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>();
 468 }
 469
 470 template <class G>
 471 typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type
 472 get(edge_underlying_t,
 473     G&,
 474     const typename graph_traits<G>::edge_descriptor& k)
 475 {
 476   return k.underlying_descx;
 477 }
 478
 479 template <class G>
 480 typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type
 481 get(edge_underlying_t,
 482     const G&)
 483 {
 484   return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>();
 485 }
 486
 487 template <class G>
 488 typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type
 489 get(edge_underlying_t,
 490     const G&,
 491     const typename graph_traits<G>::edge_descriptor& k)
 492 {
 493   return k.underlying_descx;
 494 }
 495
 496 // Access to wrapped graph's graph properties
 497
 498 template<typename BidirectionalGraph, typename GRef, typename Tag,
 499          typename Value>
 500 inline void
 501 set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
 502              const Value& value)
 503 {
 504   set_property(g.m_g, tag, value);
 505 }
 506
 507 template<typename BidirectionalGraph, typename GRef, typename Tag>
 508 inline
 509 typename boost::mpl::if_<
 510            boost::is_const<typename boost::remove_reference<GRef>::type>,
 511            const typename graph_property<BidirectionalGraph, Tag>::type&,
 512            typename graph_property<BidirectionalGraph, Tag>::type& >::type
 513 get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
 514 {
 515   return get_property(g.m_g, tag);
 516 }
 517
 518 } // namespace boost
 519
 520 #endif