address.hpp
Go to the documentation of this file.
1 
26 #ifndef MLPACK_CORE_TREE_ADDRESS_HPP
27 #define MLPACK_CORE_TREE_ADDRESS_HPP
28 
29 namespace mlpack {
30 namespace bound {
31 namespace addr {
32 
56 template<typename AddressType, typename VecType>
57 void PointToAddress(AddressType& address, const VecType& point)
58 {
59  typedef typename VecType::elem_type VecElemType;
60  // Check that the arguments are compatible.
61  typedef typename std::conditional<sizeof(VecElemType) * CHAR_BIT <= 32,
62  uint32_t,
63  uint64_t>::type AddressElemType;
64 
65  static_assert(std::is_same<typename AddressType::elem_type,
66  AddressElemType>::value == true, "The vector element type does not "
67  "correspond to the address element type.");
68  arma::Col<AddressElemType> result(point.n_elem);
69 
70  constexpr size_t order = sizeof(AddressElemType) * CHAR_BIT;
71  // Calculate the number of bits for the exponent.
72  const int numExpBits = std::ceil(std::log2(
73  std::numeric_limits<VecElemType>::max_exponent -
74  std::numeric_limits<VecElemType>::min_exponent + 1.0));
75 
76  // Calculate the number of bits for the mantissa.
77  const int numMantBits = order - numExpBits - 1;
78 
79  assert(point.n_elem == address.n_elem);
80  assert(address.n_elem > 0);
81 
82  for (size_t i = 0; i < point.n_elem; i++)
83  {
84  int e;
85  VecElemType normalizedVal = std::frexp(point(i), &e);
86  bool sgn = std::signbit(normalizedVal);
87 
88  if (point(i) == 0)
89  e = std::numeric_limits<VecElemType>::min_exponent;
90 
91  if (sgn)
92  normalizedVal = -normalizedVal;
93 
94  if (e < std::numeric_limits<VecElemType>::min_exponent)
95  {
96  AddressElemType tmp = (AddressElemType) 1 <<
97  (std::numeric_limits<VecElemType>::min_exponent - e);
98 
99  e = std::numeric_limits<VecElemType>::min_exponent;
100  normalizedVal /= tmp;
101  }
102 
103  // Extract the mantissa.
104  AddressElemType tmp = (AddressElemType) 1 << numMantBits;
105  result(i) = std::floor(normalizedVal * tmp);
106 
107  // Add the exponent.
108  assert(result(i) < ((AddressElemType) 1 << numMantBits));
109  result(i) |= ((AddressElemType)
110  (e - std::numeric_limits<VecElemType>::min_exponent)) << numMantBits;
111 
112  assert(result(i) < ((AddressElemType) 1 << (order - 1)) - 1);
113 
114  // Negative values should be inverted.
115  if (sgn)
116  {
117  result(i) = ((AddressElemType) 1 << (order - 1)) - 1 - result(i);
118  assert((result(i) >> (order - 1)) == 0);
119  }
120  else
121  {
122  result(i) |= (AddressElemType) 1 << (order - 1);
123  assert((result(i) >> (order - 1)) == 1);
124  }
125  }
126 
127  address.zeros(point.n_elem);
128 
129  // Interleave the bits of the new representation across all the elements
130  // in the address vector.
131  for (size_t i = 0; i < order; i++)
132  for (size_t j = 0; j < point.n_elem; j++)
133  {
134  size_t bit = (i * point.n_elem + j) % order;
135  size_t row = (i * point.n_elem + j) / order;
136 
137  address(row) |= (((result(j) >> (order - 1 - i)) & 1) <<
138  (order - 1 - bit));
139  }
140 }
141 
152 template<typename AddressType, typename VecType>
153 void AddressToPoint(VecType& point, const AddressType& address)
154 {
155  typedef typename VecType::elem_type VecElemType;
156  // Check that the arguments are compatible.
157  typedef typename std::conditional<sizeof(VecElemType) * CHAR_BIT <= 32,
158  uint32_t,
159  uint64_t>::type AddressElemType;
160 
161  static_assert(std::is_same<typename AddressType::elem_type,
162  AddressElemType>::value == true, "The vector element type does not "
163  "correspond to the address element type.");
164 
165  constexpr size_t order = sizeof(AddressElemType) * CHAR_BIT;
166  // Calculate the number of bits for the exponent.
167  const int numExpBits = std::ceil(std::log2(
168  std::numeric_limits<VecElemType>::max_exponent -
169  std::numeric_limits<VecElemType>::min_exponent + 1.0));
170 
171  assert(point.n_elem == address.n_elem);
172  assert(address.n_elem > 0);
173 
174  arma::Col<AddressElemType> rearrangedAddress(address.n_elem,
175  arma::fill::zeros);
176  // Calculate the number of bits for the mantissa.
177  const int numMantBits = order - numExpBits - 1;
178 
179  for (size_t i = 0; i < order; i++)
180  for (size_t j = 0; j < address.n_elem; j++)
181  {
182  size_t bit = (i * address.n_elem + j) % order;
183  size_t row = (i * address.n_elem + j) / order;
184 
185  rearrangedAddress(j) |= (((address(row) >> (order - 1 - bit)) & 1) <<
186  (order - 1 - i));
187  }
188 
189  for (size_t i = 0; i < rearrangedAddress.n_elem; i++)
190  {
191  bool sgn = rearrangedAddress(i) & ((AddressElemType) 1 << (order - 1));
192 
193  if (!sgn)
194  {
195  rearrangedAddress(i) = ((AddressElemType) 1 << (order - 1)) - 1 -
196  rearrangedAddress(i);
197  }
198 
199  // Extract the mantissa.
200  AddressElemType tmp = (AddressElemType) 1 << numMantBits;
201  AddressElemType mantissa = rearrangedAddress(i) & (tmp - 1);
202  if (mantissa == 0)
203  mantissa = 1;
204 
205  VecElemType normalizedVal = (VecElemType) mantissa / tmp;
206 
207  if (!sgn)
208  normalizedVal = -normalizedVal;
209 
210  // Extract the exponent
211  tmp = (AddressElemType) 1 << numExpBits;
212  AddressElemType e = (rearrangedAddress(i) >> numMantBits) & (tmp - 1);
213 
214  e += std::numeric_limits<VecElemType>::min_exponent;
215 
216  point(i) = std::ldexp(normalizedVal, e);
217  if (std::isinf(point(i)))
218  {
219  if (point(i) > 0)
220  point(i) = std::numeric_limits<VecElemType>::max();
221  else
222  point(i) = std::numeric_limits<VecElemType>::lowest();
223  }
224  }
225 }
226 
232 template<typename AddressType1, typename AddressType2>
233 int CompareAddresses(const AddressType1& addr1, const AddressType2& addr2)
234 {
235  static_assert(std::is_same<typename AddressType1::elem_type,
236  typename AddressType2::elem_type>::value == true, "Can't compare "
237  "addresses of distinct types");
238 
239  assert(addr1.n_elem == addr2.n_elem);
240 
241  for (size_t i = 0; i < addr1.n_elem; i++)
242  {
243  if (addr1[i] < addr2[i])
244  return -1;
245  else if (addr2[i] < addr1[i])
246  return 1;
247  }
248 
249  return 0;
250 }
251 
255 template<typename AddressType1, typename AddressType2, typename AddressType3>
256 bool Contains(const AddressType1& address, const AddressType2& loBound,
257  const AddressType3& hiBound)
258 {
259  return ((CompareAddresses(loBound, address) <= 0) &&
260  (CompareAddresses(hiBound, address) >= 0));
261 }
262 
263 } // namespace addr
264 } // namespace bound
265 } // namespace mlpack
266 
267 #endif // MLPACK_CORE_TREE_ADDRESS_HPP
.hpp
Definition: add_to_po.hpp:21
void AddressToPoint(VecType &point, const AddressType &address)
Translate the address to the point.
Definition: address.hpp:153
void PointToAddress(AddressType &address, const VecType &point)
Calculate the address of a point.
Definition: address.hpp:57
bool Contains(const AddressType1 &address, const AddressType2 &loBound, const AddressType3 &hiBound)
Returns true if an address is contained between two other addresses.
Definition: address.hpp:256
int CompareAddresses(const AddressType1 &addr1, const AddressType2 &addr2)
Compare two addresses.
Definition: address.hpp:233