common.h 17.7 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
#ifndef LIGHTGBM_UTILS_COMMON_FUN_H_
#define LIGHTGBM_UTILS_COMMON_FUN_H_

#include <LightGBM/utils/log.h>
5
#include <LightGBM/utils/openmp_wrapper.h>
Guolin Ke's avatar
Guolin Ke committed
6
7
8
9
10
11

#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <cstdint>
12
#include <algorithm>
13
#include <cmath>
Guolin Ke's avatar
Guolin Ke committed
14
#include <functional>
Guolin Ke's avatar
Guolin Ke committed
15
#include <memory>
16
#include <iterator>
Guolin Ke's avatar
Guolin Ke committed
17
#include <type_traits>
18
#include <iomanip>
Guolin Ke's avatar
Guolin Ke committed
19
20
21
22
23

namespace LightGBM {

namespace Common {

Guolin Ke's avatar
Guolin Ke committed
24
25
26
27
28
29
inline char tolower(char in) {
  if (in <= 'Z' && in >= 'A')
    return in - ('Z' - 'z');
  return in;
}

30
inline static std::string Trim(std::string str) {
Guolin Ke's avatar
Guolin Ke committed
31
  if (str.empty()) {
Guolin Ke's avatar
Guolin Ke committed
32
33
34
35
36
37
38
    return str;
  }
  str.erase(str.find_last_not_of(" \f\n\r\t\v") + 1);
  str.erase(0, str.find_first_not_of(" \f\n\r\t\v"));
  return str;
}

39
inline static std::string RemoveQuotationSymbol(std::string str) {
Guolin Ke's avatar
Guolin Ke committed
40
  if (str.empty()) {
41
42
43
44
45
46
    return str;
  }
  str.erase(str.find_last_not_of("'\"") + 1);
  str.erase(0, str.find_first_not_of("'\""));
  return str;
}
Guolin Ke's avatar
Guolin Ke committed
47

Guolin Ke's avatar
Guolin Ke committed
48
49
50
51
52
53
54
inline static bool StartsWith(const std::string& str, const std::string prefix) {
  if (str.substr(0, prefix.size()) == prefix) {
    return true;
  } else {
    return false;
  }
}
Guolin Ke's avatar
Guolin Ke committed
55

Guolin Ke's avatar
Guolin Ke committed
56
inline static std::vector<std::string> Split(const char* c_str, char delimiter) {
Guolin Ke's avatar
Guolin Ke committed
57
  std::vector<std::string> ret;
Guolin Ke's avatar
Guolin Ke committed
58
59
  std::string str(c_str);
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
  size_t pos = 0;
  while (pos < str.length()) {
    if (str[pos] == delimiter) {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      ++pos;
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
  }
  return ret;
}

inline static std::vector<std::string> SplitLines(const char* c_str) {
  std::vector<std::string> ret;
  std::string str(c_str);
  size_t i = 0;
  size_t pos = 0;
  while (pos < str.length()) {
    if (str[pos] == '\n' || str[pos] == '\r') {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      // skip the line endings
      while (str[pos] == '\n' || str[pos] == '\r') ++pos;
      // new begin
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
Guolin Ke's avatar
Guolin Ke committed
98
99
100
101
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
102
103
104
105
inline static std::vector<std::string> Split(const char* c_str, const char* delimiters) {
  std::vector<std::string> ret;
  std::string str(c_str);
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
  size_t pos = 0;
  while (pos < str.length()) {
    bool met_delimiters = false;
    for (int j = 0; delimiters[j] != '\0'; ++j) {
      if (str[pos] == delimiters[j]) {
        met_delimiters = true;
        break;
      }
    }
    if (met_delimiters) {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      ++pos;
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
Guolin Ke's avatar
Guolin Ke committed
127
128
129
130
  }
  return ret;
}

131
132
133
134
135
136
inline static std::string FindFromLines(const std::vector<std::string>& lines, const char* key_word) {
  for (auto& line : lines) {
    size_t find_pos = line.find(key_word);
    if (find_pos != std::string::npos) {
      return line;
    }
137
  }
138
  return "";
139
140
}

Guolin Ke's avatar
Guolin Ke committed
141
142
143
144
145
146
147
148
149
inline static const char* Atoi(const char* p, int* out) {
  int sign, value;
  while (*p == ' ') {
    ++p;
  }
  sign = 1;
  if (*p == '-') {
    sign = -1;
    ++p;
150
  } else if (*p == '+') {
Guolin Ke's avatar
Guolin Ke committed
151
152
153
154
155
156
157
158
159
160
161
162
    ++p;
  }
  for (value = 0; *p >= '0' && *p <= '9'; ++p) {
    value = value * 10 + (*p - '0');
  }
  *out = sign * value;
  while (*p == ' ') {
    ++p;
  }
  return p;
}

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
template<class T>
inline static double Pow(T base, int power) {
  if (power < 0) {
    return 1.0 / Pow(base, -power);
  } else if (power == 0) {
    return 1;
  } else if (power % 2 == 0) {
    return Pow(base*base, power / 2);
  } else if (power % 3 == 0) {
    return Pow(base*base*base, power / 3);
  } else {
    return base * Pow(base, power - 1);
  }
}

178
inline static const char* Atof(const char* p, double* out) {
Guolin Ke's avatar
Guolin Ke committed
179
  int frac;
180
  double sign, value, scale;
Guolin Ke's avatar
Guolin Ke committed
181
  *out = NAN;
Guolin Ke's avatar
Guolin Ke committed
182
183
184
185
186
  // Skip leading white space, if any.
  while (*p == ' ') {
    ++p;
  }
  // Get sign, if any.
187
  sign = 1.0;
Guolin Ke's avatar
Guolin Ke committed
188
  if (*p == '-') {
189
    sign = -1.0;
Guolin Ke's avatar
Guolin Ke committed
190
    ++p;
191
  } else if (*p == '+') {
Guolin Ke's avatar
Guolin Ke committed
192
193
194
    ++p;
  }

Guolin Ke's avatar
Guolin Ke committed
195
196
197
  // is a number
  if ((*p >= '0' && *p <= '9') || *p == '.' || *p == 'e' || *p == 'E') {
    // Get digits before decimal point or exponent, if any.
198
199
    for (value = 0.0; *p >= '0' && *p <= '9'; ++p) {
      value = value * 10.0 + (*p - '0');
Guolin Ke's avatar
Guolin Ke committed
200
    }
Guolin Ke's avatar
Guolin Ke committed
201

Guolin Ke's avatar
Guolin Ke committed
202
203
    // Get digits after decimal point, if any.
    if (*p == '.') {
204
205
      double right = 0.0;
      int nn = 0;
Guolin Ke's avatar
Guolin Ke committed
206
      ++p;
Guolin Ke's avatar
Guolin Ke committed
207
      while (*p >= '0' && *p <= '9') {
208
209
        right = (*p - '0') + right * 10.0;
        ++nn;
Guolin Ke's avatar
Guolin Ke committed
210
211
        ++p;
      }
212
      value += right / Pow(10.0, nn);
Guolin Ke's avatar
Guolin Ke committed
213
214
    }

Guolin Ke's avatar
Guolin Ke committed
215
216
    // Handle exponent, if any.
    frac = 0;
217
    scale = 1.0;
Guolin Ke's avatar
Guolin Ke committed
218
    if ((*p == 'e') || (*p == 'E')) {
Guolin Ke's avatar
Guolin Ke committed
219
      uint32_t expon;
Guolin Ke's avatar
Guolin Ke committed
220
      // Get sign of exponent, if any.
Guolin Ke's avatar
Guolin Ke committed
221
      ++p;
Guolin Ke's avatar
Guolin Ke committed
222
223
224
225
226
227
228
229
230
231
      if (*p == '-') {
        frac = 1;
        ++p;
      } else if (*p == '+') {
        ++p;
      }
      // Get digits of exponent, if any.
      for (expon = 0; *p >= '0' && *p <= '9'; ++p) {
        expon = expon * 10 + (*p - '0');
      }
232
233
234
      if (expon > 308) expon = 308;
      // Calculate scaling factor.
      while (expon >= 50) { scale *= 1E50; expon -= 50; }
Guolin Ke's avatar
Guolin Ke committed
235
      while (expon >= 8) { scale *= 1E8;  expon -= 8; }
236
      while (expon > 0) { scale *= 10.0; expon -= 1; }
Guolin Ke's avatar
Guolin Ke committed
237
    }
Guolin Ke's avatar
Guolin Ke committed
238
239
240
    // Return signed and scaled floating point result.
    *out = sign * (frac ? (value / scale) : (value * scale));
  } else {
241
    size_t cnt = 0;
242
    while (*(p + cnt) != '\0' && *(p + cnt) != ' '
243
244
245
           && *(p + cnt) != '\t' && *(p + cnt) != ','
           && *(p + cnt) != '\n' && *(p + cnt) != '\r'
           && *(p + cnt) != ':') {
246
247
      ++cnt;
    }
248
    if (cnt > 0) {
Guolin Ke's avatar
Guolin Ke committed
249
      std::string tmp_str(p, cnt);
Guolin Ke's avatar
Guolin Ke committed
250
      std::transform(tmp_str.begin(), tmp_str.end(), tmp_str.begin(), Common::tolower);
zhangjin's avatar
zhangjin committed
251
252
      if (tmp_str == std::string("na") || tmp_str == std::string("nan") ||
          tmp_str == std::string("null")) {
Guolin Ke's avatar
Guolin Ke committed
253
        *out = NAN;
254
      } else if (tmp_str == std::string("inf") || tmp_str == std::string("infinity")) {
255
        *out = sign * 1e308;
256
      } else {
257
        Log::Fatal("Unknown token %s in data file", tmp_str.c_str());
Guolin Ke's avatar
Guolin Ke committed
258
259
      }
      p += cnt;
260
    }
Guolin Ke's avatar
Guolin Ke committed
261
  }
Guolin Ke's avatar
Guolin Ke committed
262

Guolin Ke's avatar
Guolin Ke committed
263
264
265
  while (*p == ' ') {
    ++p;
  }
Guolin Ke's avatar
Guolin Ke committed
266

Guolin Ke's avatar
Guolin Ke committed
267
268
269
  return p;
}

270
271
272
273
274
275
276
277
inline bool AtoiAndCheck(const char* p, int* out) {
  const char* after = Atoi(p, out);
  if (*after != '\0') {
    return false;
  }
  return true;
}

278
inline bool AtofAndCheck(const char* p, double* out) {
279
280
281
282
283
284
285
  const char* after = Atof(p, out);
  if (*after != '\0') {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
286
287
288
289
290
291
292
293
294
295
296
297
298
299
inline static const char* SkipSpaceAndTab(const char* p) {
  while (*p == ' ' || *p == '\t') {
    ++p;
  }
  return p;
}

inline static const char* SkipReturn(const char* p) {
  while (*p == '\n' || *p == '\r' || *p == ' ') {
    ++p;
  }
  return p;
}

Guolin Ke's avatar
Guolin Ke committed
300
301
302
303
304
template<typename T, typename T2>
inline static std::vector<T2> ArrayCast(const std::vector<T>& arr) {
  std::vector<T2> ret;
  for (size_t i = 0; i < arr.size(); ++i) {
    ret.push_back(static_cast<T2>(arr[i]));
Guolin Ke's avatar
Guolin Ke committed
305
  }
Guolin Ke's avatar
Guolin Ke committed
306
  return ret;
Guolin Ke's avatar
Guolin Ke committed
307
308
}

309
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
310
inline static std::string ArrayToString(const std::vector<T>& arr, char delimiter) {
Guolin Ke's avatar
Guolin Ke committed
311
  if (arr.empty()) {
312
    return std::string("");
Guolin Ke's avatar
Guolin Ke committed
313
  }
314
  std::stringstream str_buf;
315
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
316
317
318
319
  str_buf << arr[0];
  for (size_t i = 1; i < arr.size(); ++i) {
    str_buf << delimiter;
    str_buf << arr[i];
Guolin Ke's avatar
Guolin Ke committed
320
  }
321
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
322
323
}

Guolin Ke's avatar
Guolin Ke committed
324
325
326
327
328
329
template<typename T>
inline static std::string ArrayToString(const std::vector<T>& arr, size_t n, char delimiter) {
  if (arr.empty() || n == 0) {
    return std::string("");
  }
  std::stringstream str_buf;
330
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
Guolin Ke's avatar
Guolin Ke committed
331
332
333
334
335
336
337
338
  str_buf << arr[0];
  for (size_t i = 1; i < std::min(n, arr.size()); ++i) {
    str_buf << delimiter;
    str_buf << arr[i];
  }
  return str_buf.str();
}

339
340
341
template<typename T, bool is_float>
struct __StringToTHelper {
  T operator()(const std::string& str) const {
Guolin Ke's avatar
Guolin Ke committed
342
    return static_cast<T>(std::stoll(str));
343
344
345
346
347
348
349
350
351
352
  }
};

template<typename T>
struct __StringToTHelper<T, true> {
  T operator()(const std::string& str) const {
    return static_cast<T>(std::stod(str));
  }
};

Guolin Ke's avatar
Guolin Ke committed
353
354
template<typename T>
inline static std::vector<T> StringToArray(const std::string& str, char delimiter, size_t n) {
Guolin Ke's avatar
Guolin Ke committed
355
356
357
  if (n == 0) {
    return std::vector<T>();
  }
Guolin Ke's avatar
Guolin Ke committed
358
359
  std::vector<std::string> strs = Split(str.c_str(), delimiter);
  if (strs.size() != n) {
Guolin Ke's avatar
Guolin Ke committed
360
    Log::Fatal("StringToArray error, size doesn't match.");
Guolin Ke's avatar
Guolin Ke committed
361
  }
Guolin Ke's avatar
Guolin Ke committed
362
  std::vector<T> ret(n);
363
364
365
  __StringToTHelper<T, std::is_floating_point<T>::value> helper;
  for (size_t i = 0; i < n; ++i) {
    ret[i] = helper(strs[i]);
Guolin Ke's avatar
Guolin Ke committed
366
367
368
369
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
370
371
template<typename T>
inline static std::vector<T> StringToArray(const std::string& str, char delimiter) {
Guolin Ke's avatar
Guolin Ke committed
372
  std::vector<std::string> strs = Split(str.c_str(), delimiter);
Guolin Ke's avatar
Guolin Ke committed
373
  std::vector<T> ret;
374
375
376
377
  ret.reserve(strs.size());
  __StringToTHelper<T, std::is_floating_point<T>::value> helper;
  for (const auto& s : strs) {
    ret.push_back(helper(s));
Guolin Ke's avatar
Guolin Ke committed
378
379
380
381
  }
  return ret;
}

382
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
383
inline static std::string Join(const std::vector<T>& strs, const char* delimiter) {
Guolin Ke's avatar
Guolin Ke committed
384
  if (strs.empty()) {
Guolin Ke's avatar
Guolin Ke committed
385
386
    return std::string("");
  }
387
  std::stringstream str_buf;
388
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
389
  str_buf << strs[0];
Guolin Ke's avatar
Guolin Ke committed
390
  for (size_t i = 1; i < strs.size(); ++i) {
391
392
    str_buf << delimiter;
    str_buf << strs[i];
Guolin Ke's avatar
Guolin Ke committed
393
  }
394
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
395
396
}

397
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
398
inline static std::string Join(const std::vector<T>& strs, size_t start, size_t end, const char* delimiter) {
Guolin Ke's avatar
Guolin Ke committed
399
400
401
  if (end - start <= 0) {
    return std::string("");
  }
Guolin Ke's avatar
Guolin Ke committed
402
403
  start = std::min(start, static_cast<size_t>(strs.size()) - 1);
  end = std::min(end, static_cast<size_t>(strs.size()));
404
  std::stringstream str_buf;
405
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
406
  str_buf << strs[start];
Guolin Ke's avatar
Guolin Ke committed
407
  for (size_t i = start + 1; i < end; ++i) {
408
409
    str_buf << delimiter;
    str_buf << strs[i];
Guolin Ke's avatar
Guolin Ke committed
410
  }
411
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
412
413
414
415
416
417
418
419
420
421
422
423
424
}

static inline int64_t Pow2RoundUp(int64_t x) {
  int64_t t = 1;
  for (int i = 0; i < 64; ++i) {
    if (t >= x) {
      return t;
    }
    t <<= 1;
  }
  return 0;
}

425
426
427
428
/*!
 * \brief Do inplace softmax transformaton on p_rec
 * \param p_rec The input/output vector of the values.
 */
429
430
431
inline void Softmax(std::vector<double>* p_rec) {
  std::vector<double> &rec = *p_rec;
  double wmax = rec[0];
432
433
434
  for (size_t i = 1; i < rec.size(); ++i) {
    wmax = std::max(rec[i], wmax);
  }
435
  double wsum = 0.0f;
436
437
438
439
440
  for (size_t i = 0; i < rec.size(); ++i) {
    rec[i] = std::exp(rec[i] - wmax);
    wsum += rec[i];
  }
  for (size_t i = 0; i < rec.size(); ++i) {
441
    rec[i] /= static_cast<double>(wsum);
442
443
444
  }
}

Guolin Ke's avatar
Guolin Ke committed
445
446
inline void Softmax(const double* input, double* output, int len) {
  double wmax = input[0];
447
  for (int i = 1; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
448
    wmax = std::max(input[i], wmax);
449
450
451
  }
  double wsum = 0.0f;
  for (int i = 0; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
452
453
    output[i] = std::exp(input[i] - wmax);
    wsum += output[i];
454
455
  }
  for (int i = 0; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
456
    output[i] /= static_cast<double>(wsum);
457
458
459
  }
}

Guolin Ke's avatar
Guolin Ke committed
460
461
462
463
464
template<typename T>
std::vector<const T*> ConstPtrInVectorWrapper(const std::vector<std::unique_ptr<T>>& input) {
  std::vector<const T*> ret;
  for (size_t i = 0; i < input.size(); ++i) {
    ret.push_back(input.at(i).get());
465
  }
Guolin Ke's avatar
Guolin Ke committed
466
  return ret;
467
468
}

Guolin Ke's avatar
Guolin Ke committed
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
template<typename T1, typename T2>
inline void SortForPair(std::vector<T1>& keys, std::vector<T2>& values, size_t start, bool is_reverse = false) {
  std::vector<std::pair<T1, T2>> arr;
  for (size_t i = start; i < keys.size(); ++i) {
    arr.emplace_back(keys[i], values[i]);
  }
  if (!is_reverse) {
    std::sort(arr.begin(), arr.end(), [](const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
      return a.first < b.first;
    });
  } else {
    std::sort(arr.begin(), arr.end(), [](const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
      return a.first > b.first;
    });
  }
  for (size_t i = start; i < arr.size(); ++i) {
    keys[i] = arr[i].first;
    values[i] = arr[i].second;
  }

}

491
492
493
494
495
/*
* approximate hessians of absolute loss with Gaussian function
* cf. https://en.wikipedia.org/wiki/Gaussian_function
*
* y is a prediction.
Tsukasa OMOTO's avatar
Tsukasa OMOTO committed
496
497
* t means true target.
* g means gradient.
498
* eta is a parameter to control the width of Gaussian function.
499
500
* w means weights.
*/
501
502
inline static double ApproximateHessianWithGaussian(const double y, const double t, const double g,
                                                    const double eta, const double w=1.0f) {
503
  const double diff = y - t;
Tsukasa OMOTO's avatar
Tsukasa OMOTO committed
504
505
506
  const double pi = 4.0 * std::atan(1.0);
  const double x = std::fabs(diff);
  const double a = 2.0 * std::fabs(g) * w;  // difference of two first derivatives, (zero to inf) and (zero to -inf).
507
  const double b = 0.0;
508
  const double c = std::max((std::fabs(y) + std::fabs(t)) * eta, 1.0e-10);
Tsukasa OMOTO's avatar
Tsukasa OMOTO committed
509
  return w * std::exp(-(x - b) * (x - b) / (2.0 * c * c)) * a / (c * std::sqrt(2 * pi));
510
511
}

512
template <typename T>
Guolin Ke's avatar
Guolin Ke committed
513
514
inline static std::vector<T*> Vector2Ptr(std::vector<std::vector<T>>& data) {
  std::vector<T*> ptr(data.size());
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
  for (size_t i = 0; i < data.size(); ++i) {
    ptr[i] = data[i].data();
  }
  return ptr;
}

template <typename T>
inline static std::vector<int> VectorSize(const std::vector<std::vector<T>>& data) {
  std::vector<int> ret(data.size());
  for (size_t i = 0; i < data.size(); ++i) {
    ret[i] = static_cast<int>(data[i].size());
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
530
inline static double AvoidInf(double x) {
Guolin Ke's avatar
Guolin Ke committed
531
532
533
534
  if (x >= 1e300) {
    return 1e300;
  } else if(x <= -1e300) {
    return -1e300;
Guolin Ke's avatar
Guolin Ke committed
535
536
537
538
539
  } else {
    return x;
  }
}

540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
template<class _Iter> inline
static typename std::iterator_traits<_Iter>::value_type* IteratorValType(_Iter) {
  return (0);
}

template<class _RanIt, class _Pr, class _VTRanIt> inline
static void ParallelSort(_RanIt _First, _RanIt _Last, _Pr _Pred, _VTRanIt*) {
  size_t len = _Last - _First;
  const size_t kMinInnerLen = 1024;
  int num_threads = 1;
  #pragma omp parallel
  #pragma omp master
  {
    num_threads = omp_get_num_threads();
  }
  if (len <= kMinInnerLen || num_threads <= 1) {
    std::sort(_First, _Last, _Pred);
    return;
  }
  size_t inner_size = (len + num_threads - 1) / num_threads;
  inner_size = std::max(inner_size, kMinInnerLen);
  num_threads = static_cast<int>((len + inner_size - 1) / inner_size);
  #pragma omp parallel for schedule(static,1)
  for (int i = 0; i < num_threads; ++i) {
    size_t left = inner_size*i;
    size_t right = left + inner_size;
    right = std::min(right, len);
    if (right > left) {
      std::sort(_First + left, _First + right, _Pred);
    }
  }
  // Buffer for merge.
  std::vector<_VTRanIt> temp_buf(len);
  _RanIt buf = temp_buf.begin();
574
  size_t s = inner_size;
575
576
577
578
579
580
581
582
583
  // Recursive merge
  while (s < len) {
    int loop_size = static_cast<int>((len + s * 2 - 1) / (s * 2));
    #pragma omp parallel for schedule(static,1)
    for (int i = 0; i < loop_size; ++i) {
      size_t left = i * 2 * s;
      size_t mid = left + s;
      size_t right = mid + s;
      right = std::min(len, right);
Guolin Ke's avatar
Guolin Ke committed
584
      if (mid >= right) { continue; }
585
586
587
588
589
590
591
592
593
594
595
596
      std::copy(_First + left, _First + mid, buf + left);
      std::merge(buf + left, buf + mid, _First + mid, _First + right, _First + left, _Pred);
    }
    s *= 2;
  }
}

template<class _RanIt, class _Pr> inline
static void ParallelSort(_RanIt _First, _RanIt _Last, _Pr _Pred) {
  return ParallelSort(_First, _Last, _Pred, IteratorValType(_First));
}

597
// Check that all y[] are in interval [ymin, ymax] (end points included); throws error if not
598
599
template <typename T>
inline void CheckElementsIntervalClosed(const T *y, T ymin, T ymax, int ny, const char *callername) {
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
  auto fatal_msg = [&y, &ymin, &ymax, &callername](int i) { 
    std::ostringstream os;
    os << "[%s]: does not tolerate element [#%i = " << y[i] << "] outside [" << ymin << ", " << ymax << "]";
    Log::Fatal(os.str().c_str(), callername, i);
  };
  for (int i = 1; i < ny; i += 2) {
    if (y[i - 1] < y[i]) {
      if (y[i - 1] < ymin) {
        fatal_msg(i - 1);
      } else if (y[i] > ymax) {
        fatal_msg(i);
      }
    } else {
      if (y[i - 1] > ymax) {
        fatal_msg(i - 1);
      } else if (y[i] < ymin) {
        fatal_msg(i);
      }
    }
  }
  if (ny & 1) { // odd
    if (y[ny - 1] < ymin || y[ny - 1] > ymax) {
      fatal_msg(ny - 1);
623
624
625
626
627
628
    }
  }
}

// One-pass scan over array w with nw elements: find min, max and sum of elements;
// this is useful for checking weight requirements.
629
630
template <typename T1, typename T2>
inline void ObtainMinMaxSum(const T1 *w, int nw, T1 *mi, T1 *ma, T2 *su) {
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
  T1 minw;
  T1 maxw;
  T1 sumw;
  int i;
  if (nw & 1) { // odd
    minw = w[0];
    maxw = w[0];
    sumw = w[0];
    i = 2;
  } else { // even
    if (w[0] < w[1]) {
      minw = w[0];
      maxw = w[1];
    } else {
      minw = w[1];
      maxw = w[0];
    }
    sumw = w[0] + w[1];
    i = 3;
  }
  for (; i < nw; i += 2) {
    if (w[i - 1] < w[i]) {
      minw = std::min(minw, w[i - 1]);
      maxw = std::max(maxw, w[i]);
    } else {
      minw = std::min(minw, w[i]);
      maxw = std::max(maxw, w[i - 1]);
    }
    sumw += w[i - 1] + w[i];
  }
  if (mi != nullptr) {
    *mi = minw;
  }
  if (ma != nullptr) {
    *ma = maxw;
  }
  if (su != nullptr) {
    *su = static_cast<T2>(sumw);
  }
670
671
}

672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
template<class T>
inline std::vector<uint32_t> ConstructBitset(const T* vals, int n) {
  std::vector<uint32_t> ret;
  for (int i = 0; i < n; ++i) {
    int i1 = vals[i] / 32;
    int i2 = vals[i] % 32;
    if (static_cast<int>(ret.size()) < i1 + 1) {
      ret.resize(i1 + 1, 0);
    }
    ret[i1] |= (1 << i2);
  }
  return ret;
}

template<class T>
inline bool FindInBitset(const uint32_t* bits, int n, T pos) {
  int i1 = pos / 32;
  if (i1 >= n) {
    return false;
  }
  int i2 = pos % 32;
  return (bits[i1] >> i2) & 1;
}

696
697
698
699
700
701
702
703
704
inline static bool CheckDoubleEqualOrdered(double a, double b) {
  double upper = std::nextafter(a, INFINITY);
  return b <= upper;
}

inline static double GetDoubleUpperBound(double a) {
  return std::nextafter(a, INFINITY);;
}

Guolin Ke's avatar
Guolin Ke committed
705
706
707
708
}  // namespace Common

}  // namespace LightGBM

Guolin Ke's avatar
Guolin Ke committed
709
#endif   // LightGBM_UTILS_COMMON_FUN_H_