src/include/fst/util.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // FST utility inline definitions.
   5
   6 #ifndef FST_UTIL_H_
   7 #define FST_UTIL_H_
   8
   9 #include <iostream>
  10 #include <iterator>
  11 #include <list>
  12 #include <map>
  13 #include <set>
  14 #include <sstream>
  15 #include <string>
  16 #include <type_traits>
  17 #include <unordered_map>
  18 #include <unordered_set>
  19 #include <utility>
  20 #include <vector>
  21
  22 #include <fst/compat.h>
  23 #include <fst/types.h>
  24 #include <fst/log.h>
  25 #include <fstream>
  26
  27 #include <fst/flags.h>
  28
  29
  30 // Utility for error handling.
  31
  32 DECLARE_bool(fst_error_fatal);
  33
  34 #define FSTERROR() \
  35   (FLAGS_fst_error_fatal ? LOG(FATAL) : LOG(ERROR))
  36
  37 namespace fst {
  38
  39 // Utility for type I/O.
  40
  41 // Reads types from an input stream.
  42
  43 // Generic case.
  44 template <class T,
  45     typename std::enable_if<std::is_class<T>::value, T>::type* = nullptr>
  46 inline std::istream &ReadType(std::istream &strm, T *t) {
  47   return t->Read(strm);
  48 }
  49
  50 // Numeric (boolean, integral, floating-point) case.
  51 template <class T,
  52     typename std::enable_if<std::is_arithmetic<T>::value, T>::type* = nullptr>
  53 inline std::istream &ReadType(std::istream &strm, T *t) {
  54   return strm.read(reinterpret_cast<char *>(t), sizeof(T)); \
  55 }
  56
  57 // String case.
  58 inline std::istream &ReadType(std::istream &strm, string *s) {  // NOLINT
  59   s->clear();
  60   int32 ns = 0;
  61   strm.read(reinterpret_cast<char *>(&ns), sizeof(ns));
  62   for (int32 i = 0; i < ns; ++i) {
  63     char c;
  64     strm.read(&c, 1);
  65     *s += c;
  66   }
  67   return strm;
  68 }
  69
  70 // Declares types that can be read from an input stream.
  71 template <class... T>
  72 std::istream &ReadType(std::istream &strm, std::vector<T...> *c);
  73 template <class... T>
  74 std::istream &ReadType(std::istream &strm, std::list<T...> *c);
  75 template <class... T>
  76 std::istream &ReadType(std::istream &strm, std::set<T...> *c);
  77 template <class... T>
  78 std::istream &ReadType(std::istream &strm, std::map<T...> *c);
  79 template <class... T>
  80 std::istream &ReadType(std::istream &strm, std::unordered_map<T...> *c);
  81 template <class... T>
  82 std::istream &ReadType(std::istream &strm, std::unordered_set<T...> *c);
  83
  84 // Pair case.
  85 template <typename S, typename T>
  86 inline std::istream &ReadType(std::istream &strm, std::pair<S, T> *p) {
  87   ReadType(strm, &p->first);
  88   ReadType(strm, &p->second);
  89   return strm;
  90 }
  91
  92 template <typename S, typename T>
  93 inline std::istream &ReadType(std::istream &strm, std::pair<const S, T> *p) {
  94   ReadType(strm, const_cast<S *>(&p->first));
  95   ReadType(strm, &p->second);
  96   return strm;
  97 }
  98
  99 namespace internal {
 100 template <class C, class ReserveFn>
 101 std::istream &ReadContainerType(std::istream &strm, C *c, ReserveFn reserve) {
 102   c->clear();
 103   int64 n = 0;
 104   ReadType(strm, &n);
 105   reserve(c, n);
 106   auto insert = std::inserter(*c, c->begin());
 107   for (int64 i = 0; i < n; ++i) {
 108     typename C::value_type value;
 109     ReadType(strm, &value);
 110     *insert = value;
 111   }
 112   return strm;
 113 }
 114 }  // namespace internal
 115
 116 template <class... T>
 117 std::istream &ReadType(std::istream &strm, std::vector<T...> *c) {
 118   return internal::ReadContainerType(
 119       strm, c, [](decltype(c) v, int n) { v->reserve(n); });
 120 }
 121
 122 template <class... T>
 123 std::istream &ReadType(std::istream &strm, std::list<T...> *c) {
 124   return internal::ReadContainerType(strm, c, [](decltype(c) v, int n) {});
 125 }
 126
 127 template <class... T>
 128 std::istream &ReadType(std::istream &strm, std::set<T...> *c) {
 129   return internal::ReadContainerType(strm, c, [](decltype(c) v, int n) {});
 130 }
 131
 132 template <class... T>
 133 std::istream &ReadType(std::istream &strm, std::map<T...> *c) {
 134   return internal::ReadContainerType(strm, c, [](decltype(c) v, int n) {});
 135 }
 136
 137 template <class... T>
 138 std::istream &ReadType(std::istream &strm, std::unordered_set<T...> *c) {
 139   return internal::ReadContainerType(
 140       strm, c, [](decltype(c) v, int n) { v->reserve(n); });
 141 }
 142
 143 template <class... T>
 144 std::istream &ReadType(std::istream &strm, std::unordered_map<T...> *c) {
 145   return internal::ReadContainerType(
 146       strm, c, [](decltype(c) v, int n) { v->reserve(n); });
 147 }
 148
 149 // Writes types to an output stream.
 150
 151 // Generic case.
 152 template <class T,
 153     typename std::enable_if<std::is_class<T>::value, T>::type* = nullptr>
 154 inline std::ostream &WriteType(std::ostream &strm, const T t) {
 155   t.Write(strm);
 156   return strm;
 157 }
 158
 159 // Numeric (boolean, integral, floating-point) case.
 160 template <class T,
 161     typename std::enable_if<std::is_arithmetic<T>::value, T>::type* = nullptr>
 162 inline std::ostream &WriteType(std::ostream &strm, const T t) {
 163   return strm.write(reinterpret_cast<const char *>(&t), sizeof(T));
 164 }
 165
 166 // String case.
 167 inline std::ostream &WriteType(std::ostream &strm, const string &s) {  // NOLINT
 168   int32 ns = s.size();
 169   strm.write(reinterpret_cast<const char *>(&ns), sizeof(ns));
 170   return strm.write(s.data(), ns);
 171 }
 172
 173 // Declares types that can be written to an output stream.
 174
 175 template <typename... T>
 176 std::ostream &WriteType(std::ostream &strm, const std::vector<T...> &c);
 177 template <typename... T>
 178 std::ostream &WriteType(std::ostream &strm, const std::list<T...> &c);
 179 template <typename... T>
 180 std::ostream &WriteType(std::ostream &strm, const std::set<T...> &c);
 181 template <typename... T>
 182 std::ostream &WriteType(std::ostream &strm, const std::map<T...> &c);
 183 template <typename... T>
 184 std::ostream &WriteType(std::ostream &strm, const std::unordered_map<T...> &c);
 185 template <typename... T>
 186 std::ostream &WriteType(std::ostream &strm, const std::unordered_set<T...> &c);
 187
 188 // Pair case.
 189 template <typename S, typename T>
 190 inline std::ostream &WriteType(std::ostream &strm,
 191                                const std::pair<S, T> &p) {  // NOLINT
 192   WriteType(strm, p.first);
 193   WriteType(strm, p.second);
 194   return strm;
 195 }
 196
 197 namespace internal {
 198 template <class C>
 199 std::ostream &WriteContainer(std::ostream &strm, const C &c) {
 200   const int64 n = c.size();
 201   WriteType(strm, n);
 202   for (const auto &e : c) {
 203     WriteType(strm, e);
 204   }
 205   return strm;
 206 }
 207 }  // namespace internal
 208
 209 template <typename... T>
 210 std::ostream &WriteType(std::ostream &strm, const std::vector<T...> &c) {
 211   return internal::WriteContainer(strm, c);
 212 }
 213
 214 template <typename... T>
 215 std::ostream &WriteType(std::ostream &strm, const std::list<T...> &c) {
 216   return internal::WriteContainer(strm, c);
 217 }
 218
 219 template <typename... T>
 220 std::ostream &WriteType(std::ostream &strm, const std::set<T...> &c) {
 221   return internal::WriteContainer(strm, c);
 222 }
 223
 224 template <typename... T>
 225 std::ostream &WriteType(std::ostream &strm, const std::map<T...> &c) {
 226   return internal::WriteContainer(strm, c);
 227 }
 228
 229 template <typename... T>
 230 std::ostream &WriteType(std::ostream &strm, const std::unordered_map<T...> &c) {
 231   return internal::WriteContainer(strm, c);
 232 }
 233
 234 template <typename... T>
 235 std::ostream &WriteType(std::ostream &strm, const std::unordered_set<T...> &c) {
 236   return internal::WriteContainer(strm, c);
 237 }
 238
 239 // Utilities for converting between int64 or Weight and string.
 240
 241 int64 StrToInt64(const string &s, const string &src, size_t nline,
 242                  bool allow_negative, bool *error = nullptr);
 243
 244 template <typename Weight>
 245 Weight StrToWeight(const string &s, const string &src, size_t nline) {
 246   Weight w;
 247   std::istringstream strm(s);
 248   strm >> w;
 249   if (!strm) {
 250     FSTERROR() << "StrToWeight: Bad weight = \"" << s << "\", source = " << src
 251                << ", line = " << nline;
 252     return Weight::NoWeight();
 253   }
 254   return w;
 255 }
 256
 257 template <typename Weight>
 258 void WeightToStr(Weight w, string *s) {
 259   std::ostringstream strm;
 260   strm.precision(9);
 261   strm << w;
 262   s->append(strm.str().data(), strm.str().size());
 263 }
 264
 265 // Utilities for reading/writing integer pairs (typically labels)
 266
 267 // Modifies line using a vector of pointers to a buffer beginning with line.
 268 void SplitToVector(char *line, const char *delim, std::vector<char *> *vec,
 269                    bool omit_empty_strings);
 270
 271 template <typename I>
 272 bool ReadIntPairs(const string &filename, std::vector<std::pair<I, I>> *pairs,
 273                   bool allow_negative = false) {
 274   std::ifstream strm(filename, std::ios_base::in);
 275   if (!strm) {
 276     LOG(ERROR) << "ReadIntPairs: Can't open file: " << filename;
 277     return false;
 278   }
 279   const int kLineLen = 8096;
 280   char line[kLineLen];
 281   size_t nline = 0;
 282   pairs->clear();
 283   while (strm.getline(line, kLineLen)) {
 284     ++nline;
 285     std::vector<char *> col;
 286     SplitToVector(line, "\n\t ", &col, true);
 287     // empty line or comment?
 288     if (col.empty() || col[0][0] == '\0' || col[0][0] == '#') continue;
 289     if (col.size() != 2) {
 290       LOG(ERROR) << "ReadIntPairs: Bad number of columns, "
 291                  << "file = " << filename << ", line = " << nline;
 292       return false;
 293     }
 294     bool err;
 295     I i1 = StrToInt64(col[0], filename, nline, allow_negative, &err);
 296     if (err) return false;
 297     I i2 = StrToInt64(col[1], filename, nline, allow_negative, &err);
 298     if (err) return false;
 299     pairs->push_back(std::make_pair(i1, i2));
 300   }
 301   return true;
 302 }
 303
 304 template <typename I>
 305 bool WriteIntPairs(const string &filename,
 306                    const std::vector<std::pair<I, I>> &pairs) {
 307   std::ostream *strm = &std::cout;
 308   if (!filename.empty()) {
 309     strm = new std::ofstream(filename);
 310     if (!*strm) {
 311       LOG(ERROR) << "WriteIntPairs: Can't open file: " << filename;
 312       return false;
 313     }
 314   }
 315   for (ssize_t n = 0; n < pairs.size(); ++n) {
 316     *strm << pairs[n].first << "\t" << pairs[n].second << "\n";
 317   }
 318   if (!*strm) {
 319     LOG(ERROR) << "WriteIntPairs: Write failed: "
 320                << (filename.empty() ? "standard output" : filename);
 321     return false;
 322   }
 323   if (strm != &std::cout) delete strm;
 324   return true;
 325 }
 326
 327 // Utilities for reading/writing label pairs.
 328
 329 template <typename Label>
 330 bool ReadLabelPairs(const string &filename,
 331                     std::vector<std::pair<Label, Label>> *pairs,
 332                     bool allow_negative = false) {
 333   return ReadIntPairs(filename, pairs, allow_negative);
 334 }
 335
 336 template <typename Label>
 337 bool WriteLabelPairs(const string &filename,
 338                      const std::vector<std::pair<Label, Label>> &pairs) {
 339   return WriteIntPairs(filename, pairs);
 340 }
 341
 342 // Utilities for converting a type name to a legal C symbol.
 343
 344 void ConvertToLegalCSymbol(string *s);
 345
 346 // Utilities for stream I/O.
 347
 348 bool AlignInput(std::istream &strm);
 349 bool AlignOutput(std::ostream &strm);
 350
 351 // An associative container for which testing membership is faster than an STL
 352 // set if members are restricted to an interval that excludes most non-members.
 353 // A Key must have ==, !=, and < operators defined. Element NoKey should be a
 354 // key that marks an uninitialized key and is otherwise unused. Find() returns
 355 // an STL const_iterator to the match found, otherwise it equals End().
 356 template <class Key, Key NoKey>
 357 class CompactSet {
 358  public:
 359   using const_iterator = typename std::set<Key>::const_iterator;
 360
 361   CompactSet() : min_key_(NoKey), max_key_(NoKey) {}
 362
 363   CompactSet(const CompactSet<Key, NoKey> &compact_set)
 364       : set_(compact_set.set_),
 365         min_key_(compact_set.min_key_),
 366         max_key_(compact_set.max_key_) {}
 367
 368   void Insert(Key key) {
 369     set_.insert(key);
 370     if (min_key_ == NoKey || key < min_key_) min_key_ = key;
 371     if (max_key_ == NoKey || max_key_ < key) max_key_ = key;
 372   }
 373
 374   void Erase(Key key) {
 375     set_.erase(key);
 376     if (set_.empty()) {
 377       min_key_ = max_key_ = NoKey;
 378     } else if (key == min_key_) {
 379       ++min_key_;
 380     } else if (key == max_key_) {
 381       --max_key_;
 382     }
 383   }
 384
 385   void Clear() {
 386     set_.clear();
 387     min_key_ = max_key_ = NoKey;
 388   }
 389
 390   const_iterator Find(Key key) const {
 391     if (min_key_ == NoKey || key < min_key_ || max_key_ < key) {
 392       return set_.end();
 393     } else {
 394       return set_.find(key);
 395     }
 396   }
 397
 398   bool Member(Key key) const {
 399     if (min_key_ == NoKey || key < min_key_ || max_key_ < key) {
 400       return false;  // out of range
 401     } else if (min_key_ != NoKey && max_key_ + 1 == min_key_ + set_.size()) {
 402       return true;  // dense range
 403     } else {
 404       return set_.count(key);
 405     }
 406   }
 407
 408   const_iterator Begin() const { return set_.begin(); }
 409
 410   const_iterator End() const { return set_.end(); }
 411
 412   // All stored keys are greater than or equal to this value.
 413   Key LowerBound() const { return min_key_; }
 414
 415   // All stored keys are less than or equal to this value.
 416   Key UpperBound() const { return max_key_; }
 417
 418  private:
 419   std::set<Key> set_;
 420   Key min_key_;
 421   Key max_key_;
 422
 423   void operator=(const CompactSet &) = delete;
 424 };
 425
 426 }  // namespace fst
 427
 428 #endif  // FST_UTIL_H_