Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / graph_archetypes.hpp
1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #ifndef BOOST_GRAPH_ARCHETYPES_HPP
11 #define BOOST_GRAPH_ARCHETYPES_HPP
12
13 #include <boost/property_map.hpp>
14 #include <boost/concept_archetype.hpp>
15
16 namespace boost { // should use a different namespace for this
17
18   namespace detail {
19     struct null_graph_archetype : public null_archetype<> {
20       struct traversal_category { }; 
21     };
22   }
23   
24   //===========================================================================
25   template <typename Vertex, typename Directed, typename ParallelCategory,
26     typename Base = detail::null_graph_archetype >
27   struct incidence_graph_archetype : public Base
28   {
29     typedef typename Base::traversal_category base_trav_cat;
30     struct traversal_category
31       : public incidence_graph_tag, public base_trav_cat { };
32 #if 0
33     typedef immutable_graph_tag mutability_category;
34 #endif
35     typedef Vertex vertex_descriptor;
36     typedef unsigned int degree_size_type;
37     typedef unsigned int vertices_size_type;
38     typedef unsigned int edges_size_type;
39     struct edge_descriptor {
40       edge_descriptor() { }
41       edge_descriptor(const detail::dummy_constructor&) { }
42       bool operator==(const edge_descriptor&) const { return false; }
43       bool operator!=(const edge_descriptor&) const { return false; }
44     };
45     typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
46
47     typedef Directed directed_category;
48     typedef ParallelCategory edge_parallel_category;
49
50     typedef void adjacency_iterator;
51     typedef void in_edge_iterator;
52     typedef void vertex_iterator;
53     typedef void edge_iterator;
54   };
55   template <typename V, typename D, typename P, typename B>
56   V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
57            const incidence_graph_archetype<V,D,P,B>& )
58   {
59     return V(static_object<detail::dummy_constructor>::get());
60   }
61   template <typename V, typename D, typename P, typename B>
62   V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
63            const incidence_graph_archetype<V,D,P,B>& )
64   {
65     return V(static_object<detail::dummy_constructor>::get());
66   }
67   
68   template <typename V, typename D, typename P, typename B>
69   std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
70             typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
71   out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
72   {
73     typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
74     return std::make_pair(Iter(), Iter());
75   }
76   
77   template <typename V, typename D, typename P, typename B>
78   typename incidence_graph_archetype<V,D,P,B>::degree_size_type
79   out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
80   {
81     return 0;
82   }
83
84   //===========================================================================
85   template <typename Vertex, typename Directed, typename ParallelCategory,
86     typename Base = detail::null_graph_archetype >
87   struct adjacency_graph_archetype : public Base
88   {
89     typedef typename Base::traversal_category base_trav_cat;
90     struct traversal_category
91       : public adjacency_graph_tag, public base_trav_cat { };
92     typedef Vertex vertex_descriptor;
93     typedef unsigned int degree_size_type;
94     typedef unsigned int vertices_size_type;
95     typedef unsigned int edges_size_type;
96     typedef void edge_descriptor;
97     typedef input_iterator_archetype<Vertex> adjacency_iterator;
98
99     typedef Directed directed_category;
100     typedef ParallelCategory edge_parallel_category;
101
102     typedef void in_edge_iterator;
103     typedef void out_edge_iterator;
104     typedef void vertex_iterator;
105     typedef void edge_iterator;
106   };
107   
108   template <typename V, typename D, typename P, typename B>
109   std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
110             typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
111   adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
112   {
113     typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
114     return std::make_pair(Iter(), Iter());
115   }
116
117   template <typename V, typename D, typename P, typename B>
118   typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
119   out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
120   {
121     return 0;
122   }
123
124   //===========================================================================
125   template <typename Vertex, typename Directed, typename ParallelCategory,
126     typename Base = detail::null_graph_archetype >
127   struct vertex_list_graph_archetype : public Base
128   {
129     typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory> 
130       Incidence;
131     typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory> 
132       Adjacency;
133
134     typedef typename Base::traversal_category base_trav_cat;
135     struct traversal_category
136       : public vertex_list_graph_tag, public base_trav_cat { };
137 #if 0
138     typedef immutable_graph_tag mutability_category;
139 #endif
140     typedef Vertex vertex_descriptor;
141     typedef unsigned int degree_size_type;
142     typedef typename Incidence::edge_descriptor edge_descriptor;
143     typedef typename Incidence::out_edge_iterator out_edge_iterator;
144     typedef typename Adjacency::adjacency_iterator adjacency_iterator;
145
146     typedef input_iterator_archetype<Vertex> vertex_iterator;
147     typedef unsigned int vertices_size_type;
148     typedef unsigned int edges_size_type;
149
150     typedef Directed directed_category;
151     typedef ParallelCategory edge_parallel_category;
152
153     typedef void in_edge_iterator;
154     typedef void edge_iterator;
155   };
156   
157   template <typename V, typename D, typename P, typename B>
158   std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
159             typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
160   vertices(const vertex_list_graph_archetype<V,D,P,B>& )
161   {
162     typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
163     return std::make_pair(Iter(), Iter());
164   }
165
166   template <typename V, typename D, typename P, typename B>
167   typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
168   num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
169   {
170     return 0;
171   }
172
173   // ambiguously inherited from incidence graph and adjacency graph
174   template <typename V, typename D, typename P, typename B>
175   typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
176   out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
177   {
178     return 0;
179   }
180
181   //===========================================================================
182
183   struct property_graph_archetype_tag { };
184
185   template <typename GraphArchetype, typename Property, typename ValueArch>
186   struct property_graph_archetype : public GraphArchetype
187   {
188     typedef property_graph_archetype_tag graph_tag;
189     typedef ValueArch vertex_property_type;
190     typedef ValueArch edge_property_type;
191   };
192
193   struct choose_edge_property_map_archetype {
194     template <typename Graph, typename Property, typename Tag>
195     struct bind_ {
196       typedef mutable_lvalue_property_map_archetype
197         <typename Graph::edge_descriptor, Property> type;
198       typedef lvalue_property_map_archetype
199         <typename Graph::edge_descriptor, Property> const_type;
200     };
201   };
202   template <>
203   struct edge_property_selector<property_graph_archetype_tag> {
204     typedef choose_edge_property_map_archetype type;
205   };
206   
207   struct choose_vertex_property_map_archetype {
208     template <typename Graph, typename Property, typename Tag>
209     struct bind_ {
210       typedef mutable_lvalue_property_map_archetype
211         <typename Graph::vertex_descriptor, Property> type;
212       typedef lvalue_property_map_archetype
213         <typename Graph::vertex_descriptor, Property> const_type;
214     };
215   };
216
217   template <>
218   struct vertex_property_selector<property_graph_archetype_tag> {
219     typedef choose_vertex_property_map_archetype type;
220   };
221   
222   template <typename G, typename P, typename V>
223   typename property_map<property_graph_archetype<G, P, V>, P>::type
224   get(P, property_graph_archetype<G, P, V>&) {
225     typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
226     return pmap;
227   }
228
229   template <typename G, typename P, typename V>
230   typename property_map<property_graph_archetype<G, P, V>, P>::const_type
231   get(P, const property_graph_archetype<G, P, V>&) {
232     typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
233     return pmap;
234   }
235
236   template <typename G, typename P, typename K, typename V>
237   typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
238   get(P p, const property_graph_archetype<G, P, V>& g, K k) {
239     return get( get(p, g), k);
240   }
241
242   template <typename G, typename P, typename V, typename Key>
243   void
244   put(P p, property_graph_archetype<G, P, V>& g, 
245       const Key& key, const V& value)
246   {
247     typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
248     Map pmap = get(p, g);
249     put(pmap, key, value);
250   }
251
252   struct color_value_archetype {
253     color_value_archetype() { }
254     color_value_archetype(detail::dummy_constructor) { }
255     bool operator==(const color_value_archetype& ) const { return true; }
256     bool operator!=(const color_value_archetype& ) const { return true; }
257   };
258   template <>
259   struct color_traits<color_value_archetype> {
260     static color_value_archetype white()
261     { 
262       return color_value_archetype
263         (static_object<detail::dummy_constructor>::get()); 
264     }
265     static color_value_archetype gray()
266     {
267       return color_value_archetype
268         (static_object<detail::dummy_constructor>::get()); 
269     }
270     static color_value_archetype black()
271     {
272       return color_value_archetype
273         (static_object<detail::dummy_constructor>::get()); 
274     }
275   };
276
277   template <typename T>
278   class buffer_archetype {
279   public:
280     void push(const T&) {}
281     void pop() {}
282     T& top() { return static_object<T>::get(); }
283     const T& top() const { return static_object<T>::get(); }
284     bool empty() const { return true; }
285   };
286   
287 } // namespace boost
288
289
290 #endif // BOOST_GRAPH_ARCHETYPES_HPP