1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief the pattern used by all the partial instantiations of multidimensional
25  * tables
26  *
27  * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6)
28  */
29 
30 #include <agrum/tools/multidim/instantiation.h>
31 
32 // check if we allowed these patterns to be used
33 #ifndef GUM_PARTIAL_INSTANTIATION_PATTERN_ALLOWED
34 
35 // #warning To use partialIntantiationPattern, you must define
36 // GUM_PARTIAL_INSTANTIATION_PATTERN_ALLOWED
37 
38 #else
39 namespace gum {
40 
41   // a specialized function instantiating some variables of a table and returning
42   // the result
43 
44 #  ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_NAME
45 #    define GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE GUM_SCALAR
46   template < typename GUM_SCALAR >
GUM_MULTI_DIM_PARTIAL_INSTANTIATION_NAME(const MultiDimImplementation<GUM_SCALAR> * table,const HashTable<const DiscreteVariable *,Idx> & inst_vars)47   MultiDimImplementation< GUM_SCALAR >* GUM_MULTI_DIM_PARTIAL_INSTANTIATION_NAME(
48      const MultiDimImplementation< GUM_SCALAR >*      table,
49      const HashTable< const DiscreteVariable*, Idx >& inst_vars)
50 #  endif
51 
52   // clang-format off
53 
54 #ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER_NAME
55 #define GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE GUM_SCALAR *
56 #define GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
57   template <typename GUM_SCALAR>
58   MultiDimImplementation<GUM_SCALAR*>*
59   GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER_NAME(
60       const MultiDimImplementation<GUM_SCALAR*>* table,
61       const HashTable<const DiscreteVariable*, Idx>& inst_vars )
62 #endif
63 
64   // clang-format on
65 
66   {
67 
68     // get the variables of the uninstantiated table
69     const Sequence< const DiscreteVariable* >& table_vars = table->variablesSequence();
70 
71     // Compute the offset of the variables. In addition, get the offset in
72     // table induced by the instantiation inst_var
73     Idx                                       table_alone_offset = 0;
74     Idx                                       offset             = 1;
75     HashTable< const DiscreteVariable*, Idx > var1offset(table_vars.size());
76 
77     for (const auto var: table_vars) {
78       if (inst_vars.exists(var)) { table_alone_offset += inst_vars[var] * offset; }
79 
80       var1offset.insert(var, offset);
81       offset *= var->domainSize();
82     }
83 
84     // Compute the sequence of variables in the result table.  Compute as
85     // well the offsets and the domain size of the variables that belong to
86     // result. Finally, compute has_before_incr: this is a Boolean indicating
87     // whether the instantiated variables are the last variables in the
88     // variables sequence of table (true) or not (false). If this Boolean is
89     // true, then we can fill result by parsing both table and result using
90     // only 1-increments.
91     Sequence< const DiscreteVariable* > result_varSeq;
92     std::vector< Idx >                  table_and_result_offset;
93     std::vector< Idx >                  table_and_result_domain;
94     Idx                                 result_domain_size = 1;
95     bool                                has_before_incr    = true;
96     bool                                found_inst_var     = false;
97 
98     for (const auto var: table_vars) {
99       if (!inst_vars.exists(var)) {
100         table_and_result_domain.push_back(var->domainSize());
101         table_and_result_offset.push_back(var1offset[var]);
102         result_domain_size *= var->domainSize();
103         result_varSeq << var;
104 
105         if (found_inst_var) has_before_incr = false;
106       } else {
107         found_inst_var = true;
108       }
109     }
110 
111     // table_and_result_value is a vector indictating, for each
112     // uninstantiated variable, how many increments we can still perform on
113     // that variable before we must perform a "major" increment: for
114     // instance, let A and B be two variables of size 10. Then, if
115     // table_and_result_value[A] = 3 and table_and_result_value[B] = 2, this
116     // means that the offset they represent is 78 (10^2 - 32). If we still
117     // increment B twice, then the offset should be 80, which means that we
118     // shall increment A once and decrease B by 10.  The value by which
119     // variables shall be decreased is indicated in table_and_result_down
120     std::vector< Idx > table_and_result_value = table_and_result_domain;
121     std::vector< Idx > table_and_result_down  = table_and_result_offset;
122 
123     for (unsigned int i = 0; i < table_and_result_down.size(); ++i)
124       table_and_result_down[i] *= (table_and_result_domain[i] - 1);
125 
126     // create a table "result" containing only the variables that are not
127     // instantiated: the variables are stored in the order in which they
128     // appear in "table". Hence, ++ operations on an instantiation on table
129     // will more or less correspond to a ++ operation on an instantiation on
130     // result
131     MultiDimArray< GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE >* result
132        = new MultiDimArray< GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE >;
133     result->beginMultipleChanges();
134 
135     for (const auto var: result_varSeq)
136       *result << *var;
137 
138     result->endMultipleChanges();
139 
140 #  ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
141     // fill the matrix with any element
142     {
143       const Instantiation table_inst(table);
144       const GUM_SCALAR&   any_element = *(table->get(table_inst));
145 
146       for (Idx i = 0; i < result_domain_size; ++i) {
147         result->unsafeSet(i, new GUM_SCALAR(any_element));
148       }
149     }
150 #  endif /* GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER */
151 
152     // compute the result: it is now sufficient to loop over the variables
153     // that were not instantiated. ptable and presult are pointers on the
154     // arrays that are directly used for this loop
155     GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE* presult
156        = const_cast< GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE* >(&(result->unsafeGet(0)));
157     Instantiation table_inst(table);
158     table_inst += table_alone_offset;
159 
160     // but before doing so, check whether the instantiated variables are the
161     // last ones or not. If so, we can optimize the parsing of ptable and
162     // presult as both tables need be parsed using only 1-increments
163     if (has_before_incr) {
164       for (Idx i = 0; i < result_domain_size; ++i) {
165 #  ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
166         **presult = *(table->get(table_inst));
167 #  else
168         *presult = table->get(table_inst);
169 #  endif
170 
171         // update the offset of result and table
172         ++table_inst;
173         ++presult;
174       }
175     } else {
176       // here, some uninstantiated variables exist after the instantiated
177       // ones in the variables sequence of table. So, we must perform a more
178       // complicated parsing of ptable
179       for (Idx j = 0; j < result_domain_size; ++j) {
180 #  ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
181         **presult = *(table->get(table_inst));
182 #  else
183         *presult = table->get(table_inst);
184 #  endif
185 
186         // update the offset of table for the outer loop
187         for (unsigned int k = 0; k < table_and_result_value.size(); ++k) {
188           --table_and_result_value[k];
189 
190           if (table_and_result_value[k]) {
191             table_inst += table_and_result_offset[k];
192             break;
193           }
194 
195           table_and_result_value[k] = table_and_result_domain[k];
196           table_inst -= table_and_result_down[k];
197         }
198 
199         // update the offset of result for the outer loop
200         ++presult;
201       }
202     }
203 
204     return result;
205   }
206 
207 #  undef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_TYPE
208 
209 #  ifdef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
210 #    undef GUM_MULTI_DIM_PARTIAL_INSTANTIATION_POINTER
211 #  endif
212 
213 } /* End of namespace gum */
214 
215 #endif /* GUM_PARTIAL_INSTANTIATION_PATTERN_ALLOWED */
216