1 # ifndef CPPAD_LOCAL_SUBGRAPH_INFO_HPP
2 # define CPPAD_LOCAL_SUBGRAPH_INFO_HPP
3 /* --------------------------------------------------------------------------
4 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell
5 
6 CppAD is distributed under multiple licenses. This distribution is under
7 the terms of the
8                     Eclipse Public License Version 1.0.
9 
10 A copy of this license is included in the COPYING file of this distribution.
11 Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
12 -------------------------------------------------------------------------- */
13 
14 # include <cppad/local/pod_vector.hpp>
15 # include <cppad/local/subgraph/arg_variable.hpp>
16 
17 // BEGIN_CPPAD_LOCAL_SUBGRAPH_NAMESPACE
18 namespace CppAD { namespace local { namespace subgraph {
19 /*!
20 \file info.hpp
21 subgraph information attached to a operation sequence
22 */
23 
24 /// class for maintaining subgraph information attached to on ADFun object.
25 class subgraph_info {
26 private:
27 	// -----------------------------------------------------------------------
28 	// private member data set by constructor, resize, and assign
29 	// -----------------------------------------------------------------------
30 	/// number of independent variables for this function
31 	size_t  n_ind_;
32 
33 	/// number of dependent variables for this function
34 	size_t  n_dep_;
35 
36 	/// number of operatros in operation sequence
37 	size_t  n_op_;
38 
39 	/// number of variables in operation sequence
40 	size_t n_var_;
41 
42 	/// the entire operation sequence as a subgraph (size n_op_).
43 	pod_vector<addr_t> entire_graph_;
44 
45 	// -----------------------------------------------------------------------
46 	// private member data set by set_map_user_op
47 	// -----------------------------------------------------------------------
48 
49 	/// Mapping atomic call operators to UserOp that begins call sequence,
50 	/// other operators are not changed by the map.
51 	/// (size zero after construtor or resize)
52 	pod_vector<addr_t> map_user_op_;
53 
54 	// -----------------------------------------------------------------------
55 	// other private member data
56 	// -----------------------------------------------------------------------
57 
58 	/// flags which operatiors are in subgraph
59 	/// (size zero or n_op_).
60 	pod_vector<addr_t> in_subgraph_;
61 
62 	/// flags which dependent variables are selected
63 	pod_vector<bool> select_domain_;
64 
65 	/// flags which dependent variables have been processed since
66 	/// the previous init_rev
67 	pod_vector<bool> process_range_;
68 
69 public:
70 	// -----------------------------------------------------------------------
71 	// const public functions
72 	// -----------------------------------------------------------------------
73 	/// number of independent variables
n_ind(void) const74 	size_t n_ind(void) const
75 	{	return n_ind_; }
76 
77 	/// number of dependent variables
n_dep(void) const78 	size_t n_dep(void) const
79 	{	return n_dep_; }
80 
81 	/// number of operators
n_op(void) const82 	size_t n_op(void) const
83 	{	return n_op_; }
84 
85 	// number of variables
n_var(void) const86 	size_t n_var(void) const
87 	{	return n_var_; }
88 
89 	/// entire graph represented as a sorted subgraph
entire_graph(void) const90 	const pod_vector<addr_t>& entire_graph(void) const
91 	{	return entire_graph_; }
92 
93 	/// map user atomic function calls to first operator in the call
map_user_op(void) const94 	const pod_vector<addr_t>& map_user_op(void) const
95 	{	return map_user_op_; }
96 
97 	/// previous select_domain argument to init_rev
select_domain(void) const98 	const pod_vector<bool>& select_domain(void) const
99 	{	return select_domain_; }
100 
101 	/// dependent variables that have been processed since previous init_rev
process_range(void) const102 	const pod_vector<bool>& process_range(void) const
103 	{	return process_range_; }
104 
105 
106 	/// amount of memory corresonding to this object
memory(void) const107 	size_t memory(void) const
108 	{	CPPAD_ASSERT_UNKNOWN( entire_graph_.size() == n_op_ );
109 		size_t sum = entire_graph_.size() * sizeof(addr_t);
110 		sum       += map_user_op_.size()  * sizeof(addr_t);
111 		sum       += in_subgraph_.size()  * sizeof(addr_t);
112 		return sum;
113 	}
114 	// -----------------------------------------------------------------------
115 	/*!
116 	check that the value of map_user_op is OK for this operation sequence
117 
118 	\param play
119 	is the player for this operation sequence.
120 
121 	\return
122 	is true, if map_user_op has the correct value for this operation sequence
123 	(is the same as it would be after a set_map_user_op).
124 	*/
125 	template <typename Base>
check_map_user_op(const player<Base> * play) const126 	bool check_map_user_op(const player<Base>* play) const
127 	{	if( map_user_op_.size() != n_op_ )
128 			return false;
129 		bool   ok   = true;
130 		size_t i_op = 0;
131 		while( i_op < n_op_ )
132 		{	OpCode op = play->GetOp(i_op);
133 			ok       &= map_user_op_[i_op] == addr_t( i_op );
134 			if( op == UserOp )
135 			{	addr_t begin = addr_t( i_op );
136 				op           = play->GetOp(++i_op);
137 				while( op != UserOp )
138 				{	CPPAD_ASSERT_UNKNOWN(
139 					op==UsrapOp || op==UsravOp || op==UsrrpOp || op==UsrrvOp
140 					);
141 					ok  &= map_user_op_[i_op] == begin;
142 					op   = play->GetOp(++i_op);
143 				}
144 				ok  &= map_user_op_[i_op] == begin;
145 			}
146 			++i_op;
147 		}
148 		return ok;
149 	}
150 	// -----------------------------------------------------------------------
151 	// non const public functions
152 	// -----------------------------------------------------------------------
153 
154 	/// flag which operators that are in the subgraph
in_subgraph(void)155 	pod_vector<addr_t>& in_subgraph(void)
156 	{	return in_subgraph_; }
157 
158 
159 	/// default constructor (all sizes are zero)
subgraph_info(void)160 	subgraph_info(void)
161 	: n_ind_(0), n_dep_(0), n_op_(0), n_var_(0)
162 	{	CPPAD_ASSERT_UNKNOWN( entire_graph_.size()  == 0 );
163 		CPPAD_ASSERT_UNKNOWN( map_user_op_.size()   == 0 );
164 		CPPAD_ASSERT_UNKNOWN( in_subgraph_.size()   == 0 );
165 	}
166 	// -----------------------------------------------------------------------
167 	/// assignment operator
operator =(const subgraph_info & info)168 	void operator=(const subgraph_info& info)
169 	{	n_ind_            = info.n_ind_;
170 		n_dep_            = info.n_dep_;
171 		n_op_             = info.n_op_;
172 		entire_graph_     = info.entire_graph_;
173 		map_user_op_      = info.map_user_op_;
174 		in_subgraph_      = info.in_subgraph_;
175 		return;
176 	}
177 	// -----------------------------------------------------------------------
178 	/*!
179 	set sizes for this object (the default sizes are zero)
180 
181 	\param n_ind
182 	number of indepent variables.
183 
184 	\param n_dep
185 	number of dependent variables.
186 
187 	\param n_op
188 	number of operators.
189 
190 	\param n_var
191 	number of variables.
192 
193 	\par entire_graph_
194 	This member funcition is set the sorted subgraph corresponding to the
195 	entire operation sequence; i.e., entire_graph_[i_op] == i_op for
196 	i_op = 0 , ... , n_op -1.
197 
198 	\par map_user_op_
199 	is resized to zero.
200 
201 	\par in_subgraph_
202 	is resized to zero.
203 	*/
resize(size_t n_ind,size_t n_dep,size_t n_op,size_t n_var)204 	void resize(size_t n_ind, size_t n_dep, size_t n_op, size_t n_var)
205 	{	CPPAD_ASSERT_UNKNOWN(
206 			n_op <= size_t( std::numeric_limits<addr_t>::max() )
207 		);
208 		// n_ind_
209 		n_ind_ = n_ind;
210 		// n_dep_
211 		n_dep_ = n_dep;
212 		// n_op_
213 		n_op_  = n_op;
214 		// n_var_
215 		n_var_ = n_var;
216 
217 		//
218 		// entire_graph_
219 		size_t old_size = entire_graph_.size();
220 		size_t old_cap  = entire_graph_.capacity();
221 		entire_graph_.resize(n_op);
222 		if( old_cap < n_op )
223 		{	for(size_t i_op = 0; i_op < n_op; ++i_op)
224 				entire_graph_[i_op] = addr_t( i_op );
225 		}
226 		else if( old_size < n_op )
227 		{	for(size_t i_op = old_size; i_op < n_op; ++i_op)
228 				entire_graph_[i_op] = addr_t( i_op );
229 		}
230 		//
231 		// map_user_op_
232 		map_user_op_.resize(0);
233 		//
234 		// in_subgraph_
235 		in_subgraph_.resize(0);
236 		//
237 		return;
238 	}
239 	// -----------------------------------------------------------------------
240 	/*!
241 	set the value of map_user_op for this operation sequence
242 
243 	\param play
244 	is the player for this operation sequence. It must same number of
245 	operators and variables as this subgraph_info object.
246 
247 	\par map_user_op_
248 	This size of map_user_op_ must be zero when this function is called
249 	(which is true after a resize operation).
250 	This function sets its size to the number of operations in play.
251 	We use the term user OpCocde for the any one of the following:
252 	UserOp, UsrapOp, UsravOp, UsrrpOp, or UsrrvOp. Suppose
253 	\code
254 		OpCodce op_i = play->GetOp(i_op);
255 		size_t  j_op = map_user_op[i_op];
256 		OpCode  op_j = play->GetOP(j_op);
257 	\endcode
258 	If op is a user OpCode, j_op is the index of the first operator
259 	in the corresponding atomic function call and op_j == UserOp.
260 	Otherwise j_op == i_op;
261 
262 	*/
263 	template <typename Base>
set_map_user_op(const player<Base> * play)264 	void set_map_user_op(const player<Base>* play)
265 	{	CPPAD_ASSERT_UNKNOWN( map_user_op_.size()   == 0 );
266 		//
267 		CPPAD_ASSERT_UNKNOWN( n_op_  == play->num_op_rec() );
268 		CPPAD_ASSERT_UNKNOWN( n_var_ == play->num_var_rec() );
269 		//
270 		// resize map_user_op_
271 		map_user_op_.resize(n_op_);
272 		//
273 		// set map_user_op for each operator
274 		for(size_t i_op = 0; i_op < n_op_; ++i_op)
275 		{	// this operator
276 			OpCode op = play->GetOp(i_op);
277 			//
278 			// value of map_user_op when op is not in atomic function call)
279 			map_user_op_[i_op] = addr_t( i_op );
280 			//
281 			if( op == UserOp )
282 			{	// first UserOp in an atomic function call sequence
283 				//
284 				// All operators in this atomic call sequence will be
285 				// mapped to the UserOp that begins this call.
286 				addr_t begin = addr_t( i_op );
287 				op           = play->GetOp(++i_op);
288 				while( op != UserOp )
289 				{	CPPAD_ASSERT_UNKNOWN(
290 					op==UsrapOp || op==UsravOp || op==UsrrpOp || op==UsrrvOp
291 					);
292 					// map this operator to the beginning of the call
293 					map_user_op_[i_op] = begin;
294 					op                 = play->GetOp(++i_op);
295 				}
296 				// map the second UserOp to the beginning of the call
297 				map_user_op_[i_op] = begin;
298 			}
299 		}
300 		return;
301 	}
302 	// -----------------------------------------------------------------------
303 	// see init_rev.hpp
304 	template <typename Base, typename BoolVector>
305 	void init_rev(
306 		const player<Base>*  play                ,
307 		const BoolVector&    select_domain
308 	);
309 	// -----------------------------------------------------------------------
310 	// see get_rev.hpp
311 	template <typename Base>
312 	void get_rev(
313 		const player<Base>*       play         ,
314 		const vector<size_t>&     dep_taddr    ,
315 		addr_t                    i_dep        ,
316 		pod_vector<addr_t>&       subgraph
317 	);
318 };
319 
320 } } } // END_CPPAD_LOCAL_SUBGRAPH_NAMESPACE
321 
322 // routines that operate on in_subgraph
323 # include <cppad/local/subgraph/init_rev.hpp>
324 # include <cppad/local/subgraph/get_rev.hpp>
325 
326 # endif
327