text: // sparse-power-weight.h
  
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //     http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  //
  // Copyright 2005-2010 Google, Inc.
  // Author: krr@google.com (Kasturi Rangan Raghavan)
  // Inspiration: allauzen@google.com (Cyril Allauzen)
  //
  // \file
  // Cartesian power weight semiring operation definitions.
  // Uses SparseTupleWeight as underlying representation.
  
  #ifndef FST_LIB_SPARSE_POWER_WEIGHT_H__
  #define FST_LIB_SPARSE_POWER_WEIGHT_H__
  
  #include<string>
  
  #include <fst/sparse-tuple-weight.h>
  #include <fst/weight.h>
  
  
  namespace fst {
  
  // Below SparseTupleWeight*Mapper are used in conjunction with
  // SparseTupleWeightMap to compute the respective semiring operations
  template<class W, class K>
  struct SparseTupleWeightPlusMapper {
    W Map(const K& k, const W& v1, const W& v2) const {
      return Plus(v1, v2);
    }
  };
  
  template<class W, class K>
  struct SparseTupleWeightTimesMapper {
    W Map(const K& k, const W& v1, const W& v2) const {
      return Times(v1, v2);
    }
  };
  
  template<class W, class K>
  struct SparseTupleWeightDivideMapper {
    SparseTupleWeightDivideMapper(DivideType divide_type) {
      divide_type_ = divide_type;
    }
    W Map(const K& k, const W& v1, const W& v2) const {
      return Divide(v1, v2, divide_type_);
    }
    DivideType divide_type_;
  };
  
  template<class W, class K>
  struct SparseTupleWeightApproxMapper {
    SparseTupleWeightApproxMapper(float delta) { delta_ = delta; }
    W Map(const K& k, const W& v1, const W& v2) const {
      return ApproxEqual(v1, v2, delta_) ? W::One() : W::Zero();
    }
    float delta_;
  };
  
  // Sparse cartesian power semiring: W ^ n
  // Forms:
  //  - a left semimodule when W is a left semiring,
  //  - a right semimodule when W is a right semiring,
  //  - a bisemimodule when W is a semiring,
  //    the free semimodule of rank n over W
  // The Times operation is overloaded to provide the
  // left and right scalar products.
  // K is the key value type. kNoKey(-1) is reserved for internal use
  template <class W, class K = int>
  class SparsePowerWeight : public SparseTupleWeight<W, K> {
   public:
    using SparseTupleWeight<W, K>::Zero;
    using SparseTupleWeight<W, K>::One;
    using SparseTupleWeight<W, K>::Quantize;
    using SparseTupleWeight<W, K>::Reverse;
  
    typedef SparsePowerWeight<typename W::ReverseWeight, K> ReverseWeight;
  
    SparsePowerWeight() {}
  
    SparsePowerWeight(const SparseTupleWeight<W, K> &w) :
      SparseTupleWeight<W, K>(w) { }
  
    template <class Iterator>
    SparsePowerWeight(Iterator begin, Iterator end) :
      SparseTupleWeight<W, K>(begin, end) { }
  
    SparsePowerWeight(const K &key, const W &w) :
      SparseTupleWeight<W, K>(key, w) { }
  
    static const SparsePowerWeight<W, K> &Zero() {
      static const SparsePowerWeight<W, K> zero(SparseTupleWeight<W, K>::Zero());
      return zero;
    }
  
    static const SparsePowerWeight<W, K> &One() {
      static const SparsePowerWeight<W, K> one(SparseTupleWeight<W, K>::One());
      return one;
    }
  
    // Overide this: Overwrite the Type method to reflect the key type
    // if using non-default key type.
    static const string &Type() {
      static string type;
      if(type.empty()) {
        type = W::Type() + "_^n";
        if(sizeof(K) != sizeof(uint32)) {
          string size;
          Int64ToStr(8 * sizeof(K), &size);
          type += "_" + size;
        }
      }
      return type;
    }
  
    static uint64 Properties() {
      uint64 props = W::Properties();
      return props & (kLeftSemiring | kRightSemiring |
                      kCommutative | kIdempotent);
    }
  
    SparsePowerWeight<W, K> Quantize(float delta = kDelta) const {
      return SparseTupleWeight<W, K>::Quantize(delta);
    }
  
    ReverseWeight Reverse() const {
      return SparseTupleWeight<W, K>::Reverse();
    }
  };
  
  // Semimodule plus operation
  template <class W, class K>
  inline SparsePowerWeight<W, K> Plus(const SparsePowerWeight<W, K> &w1,
                                      const SparsePowerWeight<W, K> &w2) {
    SparsePowerWeight<W, K> ret;
    SparseTupleWeightPlusMapper<W, K> operator_mapper;
    SparseTupleWeightMap(&ret, w1, w2, operator_mapper);
    return ret;
  }
  
  // Semimodule times operation
  template <class W, class K>
  inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1,
                                       const SparsePowerWeight<W, K> &w2) {
    SparsePowerWeight<W, K> ret;
    SparseTupleWeightTimesMapper<W, K> operator_mapper;
    SparseTupleWeightMap(&ret, w1, w2, operator_mapper);
    return ret;
  }
  
  // Semimodule divide operation
  template <class W, class K>
  inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1,
                                        const SparsePowerWeight<W, K> &w2,
                                        DivideType type = DIVIDE_ANY) {
    SparsePowerWeight<W, K> ret;
    SparseTupleWeightDivideMapper<W, K> operator_mapper(type);
    SparseTupleWeightMap(&ret, w1, w2, operator_mapper);
    return ret;
  }
  
  // Semimodule dot product
  template <class W, class K>
  inline const W& DotProduct(const SparsePowerWeight<W, K> &w1,
                      const SparsePowerWeight<W, K> &w2) {
    const SparsePowerWeight<W, K>& product = Times(w1, w2);
    W ret(W::Zero());
    for (SparseTupleWeightIterator<W, K> it(product); !it.Done(); it.Next()) {
      ret = Plus(ret, it.Value().second);
    }
    return ret;
  }
  
  template <class W, class K>
  inline bool ApproxEqual(const SparsePowerWeight<W, K> &w1,
                          const SparsePowerWeight<W, K> &w2,
                          float delta = kDelta) {
    SparseTupleWeight<W, K> ret;
    SparseTupleWeightApproxMapper<W, K> operator_mapper(kDelta);
    SparseTupleWeightMap(&ret, w1, w2, operator_mapper);
    return ret == SparsePowerWeight<W, K>::One();
  }
  
  template <class W, class K>
  inline SparsePowerWeight<W, K> Times(const W &k,
                                       const SparsePowerWeight<W, K> &w2) {
    SparsePowerWeight<W, K> w1(k);
    return Times(w1, w2);
  }
  
  template <class W, class K>
  inline SparsePowerWeight<W, K> Times(const SparsePowerWeight<W, K> &w1,
                                       const W &k) {
    SparsePowerWeight<W, K> w2(k);
    return Times(w1, w2);
  }
  
  template <class W, class K>
  inline SparsePowerWeight<W, K> Divide(const SparsePowerWeight<W, K> &w1,
                                        const W &k,
                                        DivideType divide_type = DIVIDE_ANY) {
    SparsePowerWeight<W, K> w2(k);
    return Divide(w1, w2, divide_type);
  }
  
  }  // namespace fst
  
  #endif  // FST_LIB_SPARSE_POWER_WEIGHT_H__
  