text:
namespace fst {

template <class A> class VectorFst;

// States and arcs implemented by STL vectors, templated on the
// State definition. This does not manage the Fst properties.
template <class State>
class VectorFstBaseImpl : public FstImpl<typename State::Arc> {
 public:
  typedef typename State::Arc Arc;
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;

  VectorFstBaseImpl() : start_(kNoStateId) {}

  ~VectorFstBaseImpl() {
    for (StateId s = 0; s < (StateId)states_.size(); ++s)
      delete states_[s];
  }

  StateId Start() const { return start_; }

  Weight Final(StateId s) const { return states_[s]->final; }

  StateId NumStates() const { return states_.size(); }

  size_t NumArcs(StateId s) const { return states_[s]->arcs.size(); }

  void SetStart(StateId s) { start_ = s; }

  void SetFinal(StateId s, Weight w) { states_[s]->final = w; }

  StateId AddState() {
    states_.push_back(new State);
    return states_.size() - 1;
  }

  StateId AddState(State *state) {
    states_.push_back(state);
    return states_.size() - 1;
  }

  void AddArc(StateId s, const Arc &arc) {
    states_[s]->arcs.push_back(arc);
  }

  void DeleteStates(const vector<StateId>& dstates) {
    vector<StateId> newid(states_.size(), 0);
    for (size_t i = 0; i < dstates.size(); ++i)
      newid[dstates[i]] = kNoStateId;
    StateId nstates = 0;
    for (StateId s = 0; s < (StateId)states_.size(); ++s) {
      if (newid[s] != kNoStateId) {
        newid[s] = nstates;
        if (s != nstates)
          states_[nstates] = states_[s];
        ++nstates;
      } else {
        delete states_[s];
      }
    }
    states_.resize(nstates);
    for (StateId s = 0; s < (StateId)states_.size(); ++s) {
      vector<Arc> &arcs = states_[s]->arcs;
      size_t narcs = 0;
      for (size_t i = 0; i < arcs.size(); ++i) {
        StateId t = newid[arcs[i].nextstate];
        if (t != kNoStateId) {
          arcs[i].nextstate = t;
          if (i != narcs)
            arcs[narcs] = arcs[i];
          ++narcs;
        } else {
          if (arcs[i].ilabel == 0)
            --states_[s]->niepsilons;
          if (arcs[i].olabel == 0)
            --states_[s]->noepsilons;
        }
      }
      arcs.resize(narcs);
    }
    if (Start() != kNoStateId)
      SetStart(newid[Start()]);
  }

  void DeleteStates() {
    for (StateId s = 0; s < (StateId)states_.size(); ++s)
      delete states_[s];
    states_.clear();
    SetStart(kNoStateId);
  }

  void DeleteArcs(StateId s, size_t n) {
    states_[s]->arcs.resize(states_[s]->arcs.size() - n);
  }

  void DeleteArcs(StateId s) { states_[s]->arcs.clear(); }

  State *GetState(StateId s) { return states_[s]; }

  const State *GetState(StateId s) const { return states_[s]; }

  void SetState(StateId s, State *state) { states_[s] = state; }

  void ReserveStates(StateId n) { states_.reserve(n); }

  void ReserveArcs(StateId s, size_t n) { states_[s]->arcs.reserve(n); }

  // Provide information needed for generic state iterator
  void InitStateIterator(StateIteratorData<Arc> *data) const {
    data->base = 0;
    data->nstates = states_.size();
  }

  // Provide information needed for generic arc iterator
  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const {
    data->base = 0;
    data->narcs = states_[s]->arcs.size();
    data->arcs = data->narcs > 0 ? &states_[s]->arcs[0] : 0;
    data->ref_count = 0;
  }

 private:
  vector<State *> states_;      // States represenation.
  StateId start_;               // initial state

  DISALLOW_EVIL_CONSTRUCTORS(VectorFstBaseImpl);
};

// Arcs implemented by an STL vector per state.
template <class A>
struct VectorState {
  typedef A Arc;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;

  VectorState() : final(Weight::Zero()), niepsilons(0), noepsilons(0) {}

  Weight final;              // Final weight
  vector<A> arcs;            // Arcs represenation
  size_t niepsilons;         // # of input epsilons
  size_t noepsilons;         // # of output epsilons
};

// This is a VectorFstBaseImpl container that holds VectorState's.  It
// manages Fst properties and the # of input and output epsilons.
template <class A>
class VectorFstImpl : public VectorFstBaseImpl< VectorState<A> > {
 public:
  using FstImpl<A>::SetType;
  using FstImpl<A>::SetProperties;
  using FstImpl<A>::Properties;
  using FstImpl<A>::WriteHeaderAndSymbols;

  using VectorFstBaseImpl<VectorState<A> >::Start;
  using VectorFstBaseImpl<VectorState<A> >::NumStates;

  friend class MutableArcIterator< VectorFst<A> >;

  typedef VectorFstBaseImpl< VectorState<A> > BaseImpl;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;

  VectorFstImpl() {
    SetType("vector");
    SetProperties(kNullProperties | kStaticProperties);
  }
  explicit VectorFstImpl(const Fst<A> &fst);

  static VectorFstImpl<A> *Read(istream &strm, const FstReadOptions &opts);

  size_t NumInputEpsilons(StateId s) const { return this->GetState(s)->niepsilons; }

  size_t NumOutputEpsilons(StateId s) const { return this->GetState(s)->noepsilons; }

  bool Write(ostream &strm, const FstWriteOptions &opts) const;

  void SetStart(StateId s) {
    BaseImpl::SetStart(s);
    SetProperties(Properties() & kSetStartProperties);
    if (Properties() & kAcyclic)
      SetProperties(Properties() | kInitialAcyclic);
  }

  void SetFinal(StateId s, Weight w) {
    Weight ow = this->Final(s);
    if (ow != Weight::Zero() && ow != Weight::One())
      SetProperties(Properties() & ~kWeighted);
    BaseImpl::SetFinal(s, w);
    if (w != Weight::Zero() && w != Weight::One()) {
      SetProperties(Properties() | kWeighted);
      SetProperties(Properties() & ~kUnweighted);
    }
    SetProperties(Properties() &
                  (kSetFinalProperties | kWeighted | kUnweighted));
  }

  StateId AddState() {
    StateId s = BaseImpl::AddState();
    SetProperties(Properties() & kAddStateProperties);
    return s;
  }

  void AddArc(StateId s, const A &arc) {
    VectorState<A> *state = this->GetState(s);
    if (arc.ilabel != arc.olabel) {
      SetProperties(Properties() | kNotAcceptor);
      SetProperties(Properties() & ~kAcceptor);
    }
    if (arc.ilabel == 0) {
      ++state->niepsilons;
      SetProperties(Properties() | kIEpsilons);
      SetProperties(Properties() & ~kNoIEpsilons);
      if (arc.olabel == 0) {
        SetProperties(Properties() | kEpsilons);
        SetProperties(Properties() & ~kNoEpsilons);
      }
    }
    if (arc.olabel == 0) {
      ++state->noepsilons;
      SetProperties(Properties() | kOEpsilons);
      SetProperties(Properties() & ~kNoOEpsilons);
    }
    if (!state->arcs.empty()) {
      A &parc = state->arcs.back();
      if (parc.ilabel > arc.ilabel) {
        SetProperties(Properties() | kNotILabelSorted);
        SetProperties(Properties() & ~kILabelSorted);
      }
      if (parc.olabel > arc.olabel) {
        SetProperties(Properties() | kNotOLabelSorted);
        SetProperties(Properties() & ~kOLabelSorted);
      }
    }
    if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) {
      SetProperties(Properties() | kWeighted);
      SetProperties(Properties() & ~kUnweighted);
    }
    if (arc.nextstate <= s) {
      SetProperties(Properties() | kNotTopSorted);
      SetProperties(Properties() & ~kTopSorted);
    }
    SetProperties(Properties() &
                  (kAddArcProperties | kAcceptor |
                   kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
                   kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted));
    if (Properties() & kTopSorted)
      SetProperties(Properties() | kAcyclic | kInitialAcyclic);
    BaseImpl::AddArc(s, arc);
  }

  void DeleteStates(const vector<StateId> &dstates) {
    BaseImpl::DeleteStates(dstates);
    SetProperties(Properties() & kDeleteStatesProperties);
  }

  void DeleteStates() {
    BaseImpl::DeleteStates();
    SetProperties(kNullProperties | kStaticProperties);
  }

  void DeleteArcs(StateId s, size_t n) {
    const vector<A> &arcs = this->GetState(s)->arcs;
    for (size_t i = 0; i < n; ++i) {
      size_t j = arcs.size() - i - 1;
      if (arcs[j].ilabel == 0)
        --this->GetState(s)->niepsilons;
      if (arcs[j].olabel == 0)
        --this->GetState(s)->noepsilons;
    }
    BaseImpl::DeleteArcs(s, n);
    SetProperties(Properties() & kDeleteArcsProperties);
  }

  void DeleteArcs(StateId s) {
    this->GetState(s)->niepsilons = 0;
    this->GetState(s)->noepsilons = 0;
    BaseImpl::DeleteArcs(s);
    SetProperties(Properties() & kDeleteArcsProperties);
  }

 private:
  // Properties always true of this Fst class
  static const uint64 kStaticProperties = kExpanded | kMutable;
  // Current file format version
  static const int kFileVersion = 2;
  // Minimum file format version supported
  static const int kMinFileVersion = 2;

  DISALLOW_EVIL_CONSTRUCTORS(VectorFstImpl);
};

template <class A>
VectorFstImpl<A>::VectorFstImpl(const Fst<A> &fst) {
  SetType("vector");
  SetProperties(fst.Properties(kCopyProperties, false) | kStaticProperties);
  this->SetInputSymbols(fst.InputSymbols());
  this->SetOutputSymbols(fst.OutputSymbols());
  BaseImpl::SetStart(fst.Start());

  for (StateIterator< Fst<A> > siter(fst);
       !siter.Done();
       siter.Next()) {
    StateId s = siter.Value();
    BaseImpl::AddState();
    BaseImpl::SetFinal(s, fst.Final(s));
    this->ReserveArcs(s, fst.NumArcs(s));
    for (ArcIterator< Fst<A> > aiter(fst, s);
         !aiter.Done();
         aiter.Next()) {
      const A &arc = aiter.Value();
      BaseImpl::AddArc(s, arc);
      if (arc.ilabel == 0)
        ++this->GetState(s)->niepsilons;
      if (arc.olabel == 0)
        ++this->GetState(s)->noepsilons;
    }
  }
}

template <class A>
VectorFstImpl<A> *VectorFstImpl<A>::Read(istream &strm,
                                         const FstReadOptions &opts) {
  VectorFstImpl<A> *impl = new VectorFstImpl;
  FstHeader hdr;
  if (!impl->ReadHeaderAndSymbols(strm, opts, kMinFileVersion, &hdr))
    return 0;
  impl->BaseImpl::SetStart(hdr.Start());
  impl->ReserveStates(hdr.NumStates());

  for (StateId s = 0; s < hdr.NumStates(); ++s) {
    impl->BaseImpl::AddState();
    VectorState<A> *state = impl->GetState(s);
    state->final.Read(strm);
    int64 narcs;
    ReadType(strm, &narcs);
    if (!strm) {
      LOG(ERROR) << "VectorFst::Read: read failed: " << opts.source;
      return 0;
    }
    impl->ReserveArcs(s, narcs);
    for (size_t j = 0; j < narcs; ++j) {
      A arc;
      ReadType(strm, &arc.ilabel);
      ReadType(strm, &arc.olabel);
      arc.weight.Read(strm);
      ReadType(strm, &arc.nextstate);
      if (!strm) {
        LOG(ERROR) << "VectorFst::Read: read failed: " << opts.source;
        return 0;
      }
      impl->BaseImpl::AddArc(s, arc);
      if (arc.ilabel == 0)
        ++state->niepsilons;
      if (arc.olabel == 0)
        ++state->noepsilons;
    }
  }
  return impl;
}

// Converts a string into a weight.
template <class W> class WeightFromString {
 public:
  W operator()(const string &s);
};

// Generic case fails.
template <class W> inline
W WeightFromString<W>::operator()(const string &s) {
  LOG(FATAL) << "VectorFst::Read: Obsolete file format";
  return W();
}

// TropicalWeight version.
template <> inline
TropicalWeight WeightFromString<TropicalWeight>::operator()(const string &s) {
  float f;
  memcpy(&f, s.data(), sizeof(f));
  return TropicalWeight(f);
}

// LogWeight version.
template <> inline
LogWeight WeightFromString<LogWeight>::operator()(const string &s) {
  float f;
  memcpy(&f, s.data(), sizeof(f));
  return LogWeight(f);
}

template <class A>
bool VectorFstImpl<A>::Write(ostream &strm,
                             const FstWriteOptions &opts) const {
  FstHeader hdr;
  hdr.SetStart(Start());
  hdr.SetNumStates(NumStates());
  WriteHeaderAndSymbols(strm, opts, kFileVersion, &hdr);
  if (!strm)
    return false;

  for (StateId s = 0; s < NumStates(); ++s) {
    const VectorState<A> *state = this->GetState(s);
    state->final.Write(strm);
    int64 narcs = state->arcs.size();
    WriteType(strm, narcs);
    for (size_t a = 0; a < narcs; ++a) {
      const A &arc = state->arcs[a];
      WriteType(strm, arc.ilabel);
      WriteType(strm, arc.olabel);
      arc.weight.Write(strm);
      WriteType(strm, arc.nextstate);
    }
  }
  strm.flush();
  if (!strm)
    LOG(ERROR) << "VectorFst::Write: write failed: " << opts.source;
  return strm;
}

// Simple concrete, mutable FST. Supports additional operations:
// ReserveStates and ReserveArcs (cf. STL vectors). This class
// attaches interface to implementation and handles reference
// counting.
template <class A>
class VectorFst : public MutableFst<A> {
 public:
  friend class StateIterator< VectorFst<A> >;
  friend class ArcIterator< VectorFst<A> >;
  friend class MutableArcIterator< VectorFst<A> >;

  typedef A Arc;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;

  VectorFst() : impl_(new VectorFstImpl<A>) {}

  VectorFst(const VectorFst<A> &fst) : MutableFst<A>(fst), impl_(fst.impl_) {
    impl_->IncrRefCount();
  }
  explicit VectorFst(const Fst<A> &fst) : impl_(new VectorFstImpl<A>(fst)) {}

  virtual ~VectorFst() { if (!impl_->DecrRefCount()) delete impl_; }

  VectorFst<A> &operator=(const VectorFst<A> &fst) {
    if (this != &fst) {
      if (!impl_->DecrRefCount()) delete impl_;
      fst.impl_->IncrRefCount();
      impl_ = fst.impl_;
    }
    return *this;
  }

  virtual VectorFst<A> &operator=(const Fst<A> &fst) {
    if (this != &fst) {
      if (!impl_->DecrRefCount()) delete impl_;
      impl_ = new VectorFstImpl<A>(fst);
    }
    return *this;
  }

  virtual StateId Start() const { return impl_->Start(); }

  virtual Weight Final(StateId s) const { return impl_->Final(s); }

  virtual StateId NumStates() const { return impl_->NumStates(); }

  virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }

  virtual size_t NumInputEpsilons(StateId s) const {
    return impl_->NumInputEpsilons(s);
  }

  virtual size_t NumOutputEpsilons(StateId s) const {
    return impl_->NumOutputEpsilons(s);
  }

  virtual uint64 Properties(uint64 mask, bool test) const {
    if (test) {
      uint64 known, test = TestProperties(*this, mask, &known);
      impl_->SetProperties(test, known);
      return test & mask;
    } else {
      return impl_->Properties(mask);
    }
  }

  virtual const string& Type() const { return impl_->Type(); }

  // Get a copy of this VectorFst
  virtual VectorFst<A> *Copy() const {
    impl_->IncrRefCount();
    return new VectorFst<A>(impl_);
  }

  // Read a VectorFst from an input stream; return NULL on error
  static VectorFst<A> *Read(istream &strm, const FstReadOptions &opts) {
    VectorFstImpl<A>* impl = VectorFstImpl<A>::Read(strm, opts);
    return impl ? new VectorFst<A>(impl) : 0;
  }

  // Read a VectorFst from a file; return NULL on error
  static VectorFst<A> *Read(const string &filename) {
    ifstream strm(filename.c_str());
    if (!strm) {
      LOG(ERROR) << "VectorFst::Read: Can't open file: " << filename;
      return 0;
    }
    return Read(strm, FstReadOptions(filename));
  }

  // Write a VectorFst to an output stream; return false on error
  virtual bool Write(ostream &strm, const FstWriteOptions &opts) const {
    return impl_->Write(strm, opts);
  }

  // Write a VectorFst to a file; return false on error
  virtual bool Write(const string &filename) const {
    if (!filename.empty()) {
      ofstream strm(filename.c_str());
      if (!strm) {
        LOG(ERROR) << "VectorFst::Write: Can't open file: " << filename;
        return false;
      }
      return Write(strm, FstWriteOptions(filename));
    } else {
      return Write(std::cout, FstWriteOptions("standard output"));
    }
  }

  virtual SymbolTable* InputSymbols() {
    return impl_->InputSymbols();
  }

  virtual SymbolTable* OutputSymbols() {
    return impl_->OutputSymbols();
  }

  virtual const SymbolTable* InputSymbols() const {
    return impl_->InputSymbols();
  }

  virtual const SymbolTable* OutputSymbols() const {
    return impl_->OutputSymbols();
  }

  virtual void SetStart(StateId s) {
    MutateCheck();
    impl_->SetStart(s);
  }

  virtual void SetFinal(StateId s, Weight w) {
    MutateCheck();
    impl_->SetFinal(s, w);
  }

  virtual void SetProperties(uint64 props, uint64 mask) {
    impl_->SetProperties(props, mask);
  }

  virtual StateId AddState() {
    MutateCheck();
    return impl_->AddState();
  }

  virtual void AddArc(StateId s, const A &arc) {
    MutateCheck();
    impl_->AddArc(s, arc);
  }

  virtual void DeleteStates(const vector<StateId> &dstates) {
    MutateCheck();
    impl_->DeleteStates(dstates);
  }

  virtual void DeleteStates() {
    MutateCheck();
    impl_->DeleteStates();
  }

  virtual void DeleteArcs(StateId s, size_t n) {
    MutateCheck();
    impl_->DeleteArcs(s, n);
  }

  virtual void DeleteArcs(StateId s) {
    MutateCheck();
    impl_->DeleteArcs(s);
  }

  virtual void SetInputSymbols(const SymbolTable* isyms) {
    MutateCheck();
    impl_->SetInputSymbols(isyms);
  }

  virtual void SetOutputSymbols(const SymbolTable* osyms) {
    MutateCheck();
    impl_->SetOutputSymbols(osyms);
  }

  void ReserveStates(StateId n) {
    MutateCheck();
    impl_->ReserveStates(n);
  }

  void ReserveArcs(StateId s, size_t n) {
    MutateCheck();
    impl_->ReserveArcs(s, n);
  }

  virtual void InitStateIterator(StateIteratorData<A> *data) const {
    impl_->InitStateIterator(data);
  }

  virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
    impl_->InitArcIterator(s, data);
  }

  virtual inline
  void InitMutableArcIterator(StateId s, MutableArcIteratorData<A> *);

 private:
  explicit VectorFst(VectorFstImpl<A> *impl) : impl_(impl) {}

  void MutateCheck() {
    // Copy on write
    if (impl_->RefCount() > 1) {
      impl_->DecrRefCount();
      impl_ = new VectorFstImpl<A>(*this);
    }
  }

  VectorFstImpl<A> *impl_;  // FST's impl
};

// Specialization for VectorFst; see generic version in fst.h
// for sample usage (but use the VectorFst type!). This version
// should inline.
template <class A>
class StateIterator< VectorFst<A> > {
 public:
  typedef typename A::StateId StateId;

  explicit StateIterator(const VectorFst<A> &fst)
    : nstates_(fst.impl_->NumStates()), s_(0) {}

  bool Done() const { return s_ >= nstates_; }

  StateId Value() const { return s_; }

  void Next() { ++s_; }

  void Reset() { s_ = 0; }

 private:
  StateId nstates_;
  StateId s_;

  DISALLOW_EVIL_CONSTRUCTORS(StateIterator);
};

// Specialization for VectorFst; see generic version in fst.h
// for sample usage (but use the VectorFst type!). This version
// should inline.
template <class A>
class ArcIterator< VectorFst<A> > {
 public:
  typedef typename A::StateId StateId;

  ArcIterator(const VectorFst<A> &fst, StateId s)
    : arcs_(fst.impl_->GetState(s)->arcs), i_(0) {}

  bool Done() const { return i_ >= arcs_.size(); }

  const A& Value() const { return arcs_[i_]; }

  void Next() { ++i_; }

  void Reset() { i_ = 0; }

  void Seek(size_t a) { i_ = a; }

 private:
  const vector<A>& arcs_;
  size_t i_;

  DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
};

// Specialization for VectorFst; see generic version in fst.h
// for sample usage (but use the VectorFst type!). This version
// should inline.
template <class A>
class MutableArcIterator< VectorFst<A> >
  : public MutableArcIteratorBase<A> {
 public:
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  MutableArcIterator(VectorFst<A> *fst, StateId s) : i_(0) {
    fst->MutateCheck();
    state_ = fst->impl_->GetState(s);
    properties_ = &fst->impl_->properties_;
  }

  virtual bool Done() const { return i_ >= state_->arcs.size(); }

  virtual const A& Value() const { return state_->arcs[i_]; }

  virtual void Next() { ++i_; }

  virtual void Reset() { i_ = 0; }

  virtual void Seek(size_t a) { i_ = a; }

  virtual void SetValue(const A &arc) {
    A& oarc = state_->arcs[i_];
    if (oarc.ilabel != oarc.olabel)
      *properties_ &= ~kNotAcceptor;
    if (oarc.ilabel == 0) {
      --state_->niepsilons;
      *properties_ &= ~kIEpsilons;
      if (oarc.olabel == 0)
        *properties_ &= ~kEpsilons;
    }
    if (oarc.olabel == 0) {
      --state_->noepsilons;
      *properties_ &= ~kOEpsilons;
    }
    if (oarc.weight != Weight::Zero() && oarc.weight != Weight::One())
      *properties_ &= ~kWeighted;
    oarc = arc;
    if (arc.ilabel != arc.olabel)
      *properties_ |= kNotAcceptor;
    if (arc.ilabel == 0) {
      ++state_->niepsilons;
      *properties_ |= kIEpsilons;
      if (arc.olabel == 0)
        *properties_ |= kEpsilons;
    }
    if (arc.olabel == 0) {
      ++state_->noepsilons;
      *properties_ |= kOEpsilons;
    }
    if (arc.weight != Weight::Zero() && arc.weight != Weight::One())
      *properties_ |= kWeighted;
    *properties_ &= kSetArcProperties | kNotAcceptor |
                    kEpsilons | kIEpsilons | kOEpsilons | kWeighted;
  }

 private:
  struct VectorState<A> *state_;
  uint64 *properties_;
  size_t i_;

  DISALLOW_EVIL_CONSTRUCTORS(MutableArcIterator);
};

// Provide information needed for the generic mutable arc iterator
template <class A> inline
void VectorFst<A>::InitMutableArcIterator(
    StateId s, MutableArcIteratorData<A> *data) {
  data->base = new MutableArcIterator< VectorFst<A> >(this, s);
}

// A useful alias when using StdArc.
typedef VectorFst<StdArc> StdVectorFst;

}  // namespace fst

#endif  // FST_LIB_VECTOR_FST_H__


text:
namespace Ped {

	/// Class that defines a Tobstacle object. An obstacle is, for now, always a wall with start and end coordinate.
	/// \author  chgloor
	/// \date    2012-01-17
	class LIBEXPORT Tobstacle {
	public:
		Tobstacle();
		Tobstacle(double ax, double ay, double bx, double by);
		Tobstacle(const Tvector& startIn, const Tvector& endIn);
		virtual ~Tobstacle();

		int getid() const { return id; };
		int gettype() const { return type; };
		double getax() const { return ax; };
		double getay() const { return ay; };
		double getbx() const { return bx; };
		double getby() const { return by; };
		Tvector getStartPoint() const;
		Tvector getEndPoint() const;

		virtual void setPosition(double ax, double ay, double bx, double by);
		virtual void setPosition(const Tvector& startIn, const Tvector& endIn);
		virtual void setStartPoint(const Tvector& startIn);
		virtual void setEndPoint(const Tvector& endIn);
		virtual void setType(int t) { type = t; };

		virtual Tvector closestPoint(double p1, double p2) const;
		virtual Tvector closestPoint(const Tvector& pointIn) const;
		virtual void rotate(const Tvector& rotationCenterIn, const Ped::Tangle& angleIn);

	protected:
		static int staticid;
		int id;									///< Obstacle number
		double ax;								///< Position of the obstacle
		double ay;								///< Position of the obstacle
		double bx;								///< Position of the obstacle
		double by;								///< Position of the obstacle
		int type;
	};
}

#endif

redpajama_set_name: RedPajamaGithub


text:
package org.knowm.xchange.examples.quoine.account;

import java.io.IOException;
import java.util.Arrays;

import org.knowm.xchange.Exchange;
import org.knowm.xchange.dto.account.AccountInfo;
import org.knowm.xchange.examples.quoine.QuoineExamplesUtils;
import org.knowm.xchange.quoine.dto.account.FiatAccount;
import org.knowm.xchange.quoine.service.QuoineAccountServiceRaw;
import org.knowm.xchange.service.account.AccountService;

/**
 * Demo requesting account info at Quoine
 */
public class AccountInfoDemo {

  public static void main(String[] args) throws IOException {

    Exchange exchange = QuoineExamplesUtils.createExchange();

    // Interested in the private account functionality (authentication)
    AccountService accountService = exchange.getAccountService();

    generic(accountService);
    raw((QuoineAccountServiceRaw) accountService);
  }

  private static void generic(AccountService accountService) throws IOException {

    AccountInfo accountInfo = accountService.getAccountInfo();

    System.out.println(accountInfo.toString());
  }

  private static void raw(QuoineAccountServiceRaw quoineAccountServiceRaw) throws IOException {

    final FiatAccount[] quoineFiatAccountInfo = quoineAccountServiceRaw.getQuoineFiatAccountInfo();

    System.out.println(Arrays.toString(quoineFiatAccountInfo));
  }

}


text:
if (!String.prototype.format) {
    String.prototype.format = function () {
        var args = arguments;
        return this.replace(/{(\d+)}/g, function (match, number) {
            return typeof args[number] != 'undefined'
                ? args[number]
                : match
                ;
        });
    };
}

toggle_button_loading_text = function($element){

    var btnText = $element.data('loading-text');
    $element
        .data('loading-text', $element.text())
        .text(btnText)
    ;
};

$(function() {
    $('#sidebar-wrapper').slimscroll({
        height: '100%',
        width: '500px',
        position: 'right',
        alwaysVisible: true,
        color: '#73715e'
    });

    $('[data-toggle="tooltip"]').tooltip();

    if (/Android|webOS|iPhone|iPad|iPod|BlackBerry|IEMobile|Opera Mini/i.test(navigator.userAgent)) {
        $('select') .select2({
            placeholder: "Select a state",
            allowClear: true,
            width: '170px',
            minimumResultsForSearch: Infinity
        });
    } else {
        $('select').select2({
            placeholder: "Select a state",
            allowClear: true,
            width: '170px'
        });
    }

    $('select').change(function (e) {
            var $target = $(e.target);
            var $img = $target.parents('.row:first').find('img');

            $img.attr('src', $target.children('option:selected').data('photo'));
        });

    $('.event-list>li').click(function(e){
        var $target = $(this);

        $('.background-image').css('background-image', "url('" + $target.data('background') + "')");
        $('#race-title').html($target.data('title'));
        $('input[name="stage"]').val($target.data('slug'));
    });

    $('*[data-event="ajaxRequest"]').click(function(e){
        e.preventDefault();

        var $target = $(e.target);
        var $container = $($target.data('container'));
        var $resultContainer = $($target.data('result-container'));
        var $form = $($target).parents('form:first');

        $.ajax({
            async: true,
            type: $form.attr('method'),
            url: decodeURI($form.attr('action')).format($('input[name="stage"]').val()),
            data: $form.serialize(),
            beforeSend: function(){
                toggle_button_loading_text($target);
            },
            success: function(data){
                if (data.status === "ok") {
                    $container.show();
                    $resultContainer.html(data.view);
                }
                toggle_button_loading_text($target);
            }
        });
    });
});


text:
import java.util.Iterator;
import net.runelite.mapping.ObfuscatedName;
import net.runelite.mapping.ObfuscatedSignature;

@ObfuscatedName("hg")
public class class211 implements Iterator {
   @ObfuscatedName("o")
   @ObfuscatedSignature(
      signature = "Lhm;"
   )
   CombatInfoList field2632;
   @ObfuscatedName("k")
   @ObfuscatedSignature(
      signature = "Lhj;"
   )
   Node field2633;
   @ObfuscatedName("t")
   @ObfuscatedSignature(
      signature = "Lhj;"
   )
   Node field2634;

   @ObfuscatedSignature(
      signature = "(Lhm;)V"
   )
   class211(CombatInfoList var1) {
      this.field2634 = null;
      this.field2632 = var1;
      this.field2633 = this.field2632.node.next;
      this.field2634 = null;
   }

   public Object next() {
      Node var1 = this.field2633;
      if(var1 == this.field2632.node) {
         var1 = null;
         this.field2633 = null;
      } else {
         this.field2633 = var1.next;
      }

      this.field2634 = var1;
      return var1;
   }

   public boolean hasNext() {
      return this.field2632.node != this.field2633;
   }

   public void remove() {
      if(this.field2634 == null) {
         throw new IllegalStateException();
      } else {
         this.field2634.unlink();
         this.field2634 = null;
      }
   }
}


text:
package hr;

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 *
 * @author harish.sharma
 *
 */
public class P1 {
    public static Long solve(final Integer n, final Long m, final Queue<Integer> heap) {
        if (n == 0 || m == 0) return 0l;
        Long tempM = m;
        Long totalProfit = 0l;
        while (tempM > 0) {
            Integer max = heap.remove();
            Integer currTop = heap.peek();
            if (currTop != null) {
                while (max >= currTop && tempM > 0) {
                    totalProfit += max;
                    tempM--;
                    max--;
                }
            }
            if (max != 1) heap.add(max);
        }
        return totalProfit;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long m = in.nextLong();
        Queue<Integer> heap = new PriorityQueue<>(n, Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            heap.add(in.nextInt());
        }
        System.out.println(solve(n, m, heap));
        in.close();
    }
}


text:
package org.unitime.timetable.authenticate.jaas;

import java.io.Serializable;
import java.security.Principal;

/**
 * Represents an authenticated and authorized timetable user
 *
 * @author Tomas Muller
 */
final public class AuthenticatedUser implements Principal, Serializable, HasExternalId {
	private static final long serialVersionUID = 11L;

	String iName, iExternalId;

	public AuthenticatedUser(String name, String externalId) {
		iName = name;
		iExternalId = externalId;
	}

	public boolean equals(Object obj) {
		return getName().equals(((Principal)obj).getName());
	}

	public int hashCode() {
		return getName().hashCode();
	}

	public String toString() {
		return getName();
	}

	public String getName() {
		return iName;
	}

	@Override
	public String getExternalId() {
		return iExternalId;
	}
}


text:
UIKIT_EXTERN NSString const *kUIControlDoraemonMCSerializerWrapperKey ;

NS_ASSUME_NONNULL_BEGIN

@interface UIControl (DoraemonMCSerializer)

/// 当前对象的信息转为字典
- (NSDictionary *)do_mc_serialize_dictionary;
/// 将字典中的值同步到当前对象的属性参数
- (void)do_mc_serialize_syncInfoWithDictionary:(NSDictionary *)dictionary;

@end

NS_ASSUME_NONNULL_END


text:
package io.cattle.platform.object.util;

import javax.annotation.PostConstruct;

import org.apache.commons.beanutils.BeanUtilsBean;
import org.apache.commons.beanutils.ConvertUtilsBean;
import org.apache.commons.beanutils.converters.IntegerConverter;
import org.apache.commons.beanutils.converters.LongConverter;

public class CommonsConverterStartup {

    @PostConstruct
    public void init() {
        ConvertUtilsBean service = BeanUtilsBean.getInstance().getConvertUtils();
        service.register(new LongConverter(null), Long.class);
        service.register(new IntegerConverter(null), Integer.class);
    }

}


text:
function New-RsWebServiceProxy
{
    <#
        .SYNOPSIS
            This script creates a web service proxy object to the Reporting Services SOAP endpoint.

        .DESCRIPTION
            This script creates a web service proxy object to the Reporting Services SOAP endpoint associated to the Report Server URI specified by the user.

            By default, this function uses the connection values set by Connect-RsReportingServer.
            The defaults without ever calling Connect-RsReportingServer are:
            - ReportServerUri: http://localhost/reportserver/
            - Credential: Current User

        .PARAMETER ReportServerUri
            Specify the Report Server URL to your SQL Server Reporting Services Instance.
            By Default, this parameter uses the uri specified by the Connect-RsReportingServer function.

        .PARAMETER Credential
            Specify the Credential to use when connecting to your SQL Server Reporting Services Instance.
            By Default, this parameter uses the credentials (if any) specified by the Connect-RsReportingServer function.

        .PARAMETER ApiVersion
            The version of the API to use, 2010 by default. Specify '2005' or '2006' if you need
            to query a Sql Server Reporting Service Instance running a version prior to
            SQL Server 2008 R2 to access those respective APIs.

        .PARAMETER CustomAuthentication
            If the server implements a custom authentication schema such as 'Forms' instead of standard Basic/NTLM.

        .EXAMPLE
            New-RsWebServiceProxy
            Description
            -----------
            This command will create and return a web service proxy to the default server using default credentials.

        .EXAMPLE
            New-RsWebServiceProxy -ReportServerUri http://myserver/reportserver_sql2012
            Description
            -----------
            This command will create and return a web service proxy to the Report Server located at http://myserver/reportserver_sql2012 using current user's credentials.

        .EXAMPLE
            New-RsWebServiceProxy -Credential 'CaptainAwesome'
            Description
            -----------
            This command will create and return a web service proxy to the Report Server located at http://localhost/reportserver using CaptainAwesome's credentials.
    #>

    [cmdletbinding()]
    param
    (
        [string]
        $ReportServerUri = ([Microsoft.ReportingServicesTools.ConnectionHost]::ReportServerUri),

        [Alias('Credentials')]
        [AllowNull()]
        [System.Management.Automation.PSCredential]
        $Credential = ([Microsoft.ReportingServicesTools.ConnectionHost]::Credential),

        [ValidateSet('2005','2006','2010')]
        [string]
        $ApiVersion = '2010',

        [switch]
        $CustomAuthentication
    )

    #region If we did not specify a connection parameter, use a default connection
    if (-not ($PSBoundParameters.ContainsKey("ReportServerUri") -or $PSBoundParameters.ContainsKey("Credential")))
    {
        if ([Microsoft.ReportingServicesTools.ConnectionHost]::Proxy)
        {
            return ([Microsoft.ReportingServicesTools.ConnectionHost]::Proxy)
        }
        else
        {
            try
            {
                $proxy = New-RsWebServiceProxy -ReportServerUri ([Microsoft.ReportingServicesTools.ConnectionHost]::ReportServerUri) -Credential ([Microsoft.ReportingServicesTools.ConnectionHost]::Credential) -ErrorAction Stop
                [Microsoft.ReportingServicesTools.ConnectionHost]::Proxy = $proxy
                return $proxy
            }
            catch
            {
                throw (New-Object System.Exception("Failed to establish proxy connection to $([Microsoft.ReportingServicesTools.ConnectionHost]::ReportServerUri) : $($_.Exception.Message)", $_.Exception))
            }
        }
    }
    #endregion If we did not specify a connection parameter, use a default connection

    #region Build explicitly required proxy object
    # forming the full URL to the SOAP Proxy of ReportServerUri
    if ($ReportServerUri -notlike '*/')
    {
        $ReportServerUri = $ReportServerUri + '/'
    }
    $reportServerUriObject = New-Object System.Uri($ReportServerUri)
    $soapEndpointUriObject = New-Object System.Uri($reportServerUriObject, "ReportService$ApiVersion.asmx")
    $ReportServerUri = $soapEndPointUriObject.ToString()

    # creating proxy either using specified credentials or default credentials
    try
    {
        Write-Verbose "Establishing proxy connection to $ReportServerUri..."
        if ($Credential)
        {
            $proxy = New-WebServiceProxy -Uri $ReportServerUri -Credential $Credential -ErrorAction Stop
        }
        else
        {
            $proxy = New-WebServiceProxy -Uri $ReportServerUri -UseDefaultCredential -ErrorAction Stop
        }

        if ($CustomAuthentication)
        {
            if (!$Credential)
            {
                $Credential = Get-Credential
            }
            $NetworkCredential = $Credential.GetNetworkCredential()

            $proxy.CookieContainer = New-Object System.Net.CookieContainer
            $proxy.LogonUser($NetworkCredential.UserName, $NetworkCredential.Password, "Forms")

            Write-Verbose "Authenticated!"
        }

        return $proxy
    }
    catch
    {
        throw (New-Object System.Exception("Failed to establish proxy connection to $ReportServerUri : $($_.Exception.Message)", $_.Exception))
    }
    #endregion Build explicitly required proxy object
}


text:
#ifndef ADIOS2_CORE_ADIOS_H_
#define ADIOS2_CORE_ADIOS_H_

/// \cond EXCLUDE_FROM_DOXYGEN
#include <functional> //std::function
#include <memory>     //std::shared_ptr
#include <string>
#include <unordered_map>
#include <vector>
/// \endcond

#include "adios2/common/ADIOSConfig.h"
#include "adios2/common/ADIOSTypes.h"
#include "adios2/core/CoreTypes.h"
#include "adios2/core/Operator.h"
#include "adios2/core/VariableStruct.h"
#include "adios2/helper/adiosComm.h"

namespace adios2
{
namespace core
{
class IO;

/** @brief Point of entry class for an application.
 *         Serves as factory of IO class objects and Transforms */
class ADIOS
{
public:
    /** Get the communicator passed to constructor for parallel case.  */
    helper::Comm const &GetComm() const { return m_Comm; }

    /** Changed by language bindings in constructor */
    const std::string m_HostLanguage = "C++";

    /**
     * @brief Constructor for MPI applications WITH a XML config file
     * @param configFile XML format (maybe support different formats in the
     * future (json)?)
     * @param mpiComm MPI communicator from application, make sure is valid
     * through the scope of adios2 calls
     */
    ADIOS(const std::string configFile, helper::Comm comm,
          const std::string hostLanguage);

    /**
     * @brief Constructor for non-MPI applications WITH a XML config file (it
     * must end with extension .xml)
     * @param configFile XML format (maybe support different formats in the
     * future (json)?)
     */
    ADIOS(const std::string configFile, const std::string hostLanguage);

    /**
     * @brief Constructor for MPI apps WITHOUT a XML config file
     * @param mpiComm MPI communicator from application
     */
    ADIOS(helper::Comm comm, const std::string hostLanguage);

    /**
     *  @brief ADIOS no-MPI default empty constructor
     */
    ADIOS(const std::string hostLanguage);

    /**
     * Delete copy constructor explicitly. Objects shouldn't be allowed to be
     * redefined. Use smart pointers if this is absolutely necessary.
     * @param adios reference to another adios object
     */
    ADIOS(const ADIOS &adios) = delete;

    ~ADIOS();

    /**
     * Declares a new IO class object and returns a reference to that object.
     * @param ioName must be unique
     * @return reference to newly created IO object inside current ADIOS object
     * @exception std::invalid_argument if IO with unique name is already
     * declared
     */
    IO &DeclareIO(const std::string name,
                  const ArrayOrdering ArrayOrder = ArrayOrdering::Auto);

    /**
     * Retrieve a reference to an existing IO object created with DeclareIO.
     * Follow the C++11 STL containers at function.
     * @param name of IO to look for
     * @return if IO exists returns a reference to existing IO object inside
     * ADIOS
     * @exception std::invalid_argument if IO was not created with DeclareIO
     */
    IO &AtIO(const std::string name);

    /**
     * Flushes all engines in all IOs created with the current ADIOS object
     * using DeclareIO and IO.Open.
     * If no IO or engine is created it does nothing.
     * @exception std::runtime_error if any engine Flush fails
     */
    void FlushAll();

    /**
     * Declares a derived class of the Operator abstract class. If object is
     * defined in the user
     * config file, by name, it will be already created during the processing of
     * the config file. So this function returns a reference to that object.
     * @param name must be unique for each operator created with DefineOperator
     * @param type from derived class
     * @param parameters optional parameters
     * @return reference to Operator object
     * @exception std::invalid_argument if Operator with unique name is already
     * defined
     */
    std::pair<std::string, Params> &
    DefineOperator(const std::string &name, const std::string type,
                   const Params &parameters = Params());
    /**
     * Retrieve a reference pointer to an existing Operator object
     * created with DefineOperator.
     * @return if IO exists returns a reference to existing IO object inside
     * ADIOS, otherwise a nullptr
     */
    std::pair<std::string, Params> *
    InquireOperator(const std::string &name) noexcept;

    StructDefinition &DefineStruct(const std::string &name, const size_t size);
    StructDefinition *InquireStruct(const std::string &name);

    /**
     * DANGER ZONE: removes a particular IO. This will effectively eliminate any
     * parameter from the config.xml file
     * @param name io input name
     * @return true: IO was found and removed, false: IO not found and not
     * removed
     */
    bool RemoveIO(const std::string name);

    /**
     * DANGER ZONE: removes all IOs created with DeclareIO. This will
     * effectively eliminate any parameter from the config.xml file
     */
    void RemoveAllIOs() noexcept;

    /** Inform ADIOS about entering communication-free computation block
     * in main thread. Useful when using Async IO */
    void EnterComputationBlock() noexcept;

    /** Inform ADIOS about exiting communication-free computation block
     * in main thread. Useful when using Async IO */
    void ExitComputationBlock() noexcept;

private:
    /** Communicator given to parallel constructor. */
    helper::Comm m_Comm;

    /** XML File to be read containing configuration information */
    const std::string m_ConfigFile;

    /**
     * @brief List of IO class objects defined from either ADIOS
     * configuration file (XML) or the DeclareIO function explicitly.
     * Using map (binary tree) to preserve references returned by DeclareIO.
     * <pre>
     *     Key: unique method name
     *     Value: IO class object
     * </pre>
     */
    std::map<std::string, IO> m_IOs;

    /** operators created with DefineOperator */
    std::unordered_map<std::string, std::pair<std::string, Params>> m_Operators;

    std::unordered_map<std::string, StructDefinition> m_StructDefinitions;

    /** Flag for Enter/ExitComputationBlock */
    bool enteredComputationBlock = false;

    void CheckOperator(const std::string name) const;

    void XMLInit(const std::string &configFileXML);

    void YAMLInit(const std::string &configFileYAML);
};

} // end namespace core
} // end namespace adios2

#endif /* ADIOS2_ADIOS_H_ */


text:
namespace llvm {

class raw_ostream;

class PDBSymbolTypeVTableShape : public PDBSymbol {
public:
  PDBSymbolTypeVTableShape(const IPDBSession &PDBSession,
                           std::unique_ptr<IPDBRawSymbol> VtblShapeSymbol);

  DECLARE_PDB_SYMBOL_CONCRETE_TYPE(PDB_SymType::VTableShape)

  void dump(PDBSymDumper &Dumper) const override;

  FORWARD_SYMBOL_METHOD(isConstType)
  FORWARD_SYMBOL_METHOD(getCount)
  FORWARD_SYMBOL_METHOD(getLexicalParentId)
  FORWARD_SYMBOL_METHOD(getSymIndexId)
  FORWARD_SYMBOL_METHOD(isUnalignedType)
  FORWARD_SYMBOL_METHOD(isVolatileType)
};

} // namespace llvm

#endif // LLVM_DEBUGINFO_PDB_PDBSYMBOLTYPEVTABLESHAPE_H


text:
/**
 * @Title:  BZParamsDaoTest.java
 * @Package com.sva.test.dao
 * @Description:    BZParamsDao测试类
 * @author: LabelCS
 * @date:   2016年9月3日 下午9:20:39
 * @version V1.0
 */
package com.sva.test.dao;

import java.math.BigDecimal;
import java.util.Date;
import java.util.List;
import java.util.Map;

import javax.annotation.Resource;
import org.junit.Test;

import com.sva.dao.BZParamsDao;
import com.sva.model.BZPramesModel;
import com.sva.model.BZPramesModel1;
import org.junit.Assert;

/**
 * @ClassName:  BZParamsDaoTest
 * @Description:BZParamsDao测试类
 * @author: LabelCS
 * @date:   2016年9月3日 下午9:20:39
 *
 */
public class BZParamsDaoTest extends BasicDaoTest {

    @Resource
    BZParamsDao bZParamsDao;

    @Test
    public void doqueryTest(){
        List<BZPramesModel> result = bZParamsDao.doquery();
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void doquery3Test(){
        List<BZPramesModel> result = bZParamsDao.doquery3();
        Assert.assertNotEquals("结果不为0",0, result.size());
    }

    @Test
    public void doquery4Test(){
        List<BZPramesModel> result = bZParamsDao.doquery4();
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void doquery1Test(){
        List<BZPramesModel> result = bZParamsDao.doquery1();
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void updateBZInfoTest(){
        BZPramesModel mmm = new BZPramesModel();
        mmm.setDensitySel(1);
        mmm.setDensitySel1(1);
        mmm.setDensitySel2(1);
        mmm.setDensitySel3(1);
        mmm.setDensitySel4(1);
        mmm.setDensitySel5(1);
        mmm.setDensitySel6(1);
        mmm.setDensitySel7(1);
        mmm.setRadiusSel(1);
        mmm.setRadiusSel1(1);
        mmm.setRadiusSel2(1);
        mmm.setRadiusSel3(1);
        mmm.setRadiusSel4(1);
        mmm.setRadiusSel5(1);
        mmm.setRadiusSel6(1);
        mmm.setRadiusSel7(1);
        mmm.setFloorNo1(new BigDecimal(1));
        mmm.setFloorNo2(new BigDecimal(1));
        mmm.setFloorNo3(new BigDecimal(1));
        mmm.setFloorNo4(new BigDecimal(1));
        mmm.setFloorNo5(new BigDecimal(1));
        mmm.setFloorNo6(new BigDecimal(1));
        mmm.setFloorNo7(new BigDecimal(1));
        mmm.setFloorNo8(new BigDecimal(1));
        mmm.setCoefficient(1D);
        mmm.setPeriodSel(1);
        mmm.setStartTime(new Date());
        mmm.setId(1);
        int result = bZParamsDao.updateBZInfo(mmm);
        Assert.assertEquals("结果为1",1, result);
    }

    @Test
    public void updateSHInfoTest(){
        BZPramesModel mmm = new BZPramesModel();
        mmm.setDensitySel(1);
        mmm.setDensitySel1(1);
        mmm.setDensitySel2(1);
        mmm.setRadiusSel(1);
        mmm.setRadiusSel1(1);
        mmm.setRadiusSel2(1);
        mmm.setFloorNo1(new BigDecimal(1));
        mmm.setFloorNo2(new BigDecimal(1));
        mmm.setFloorNo3(new BigDecimal(1));
        mmm.setCoefficient(1D);
        mmm.setPeriodSel(1);
        mmm.setStartTime(new Date());
        mmm.setId(1);
        int result = bZParamsDao.updateSHInfo(mmm);
        Assert.assertNotEquals("结果不为0",0, result);
    }

    @Test
    public void updateSHInfoJingTest(){
        BZPramesModel mmm = new BZPramesModel();
        mmm.setDensitySel(1);
        mmm.setDensitySel1(1);
        mmm.setDensitySel2(1);
        mmm.setDensitySel3(1);
        mmm.setRadiusSel(1);
        mmm.setRadiusSel1(1);
        mmm.setRadiusSel2(1);
        mmm.setRadiusSel3(1);
        mmm.setFloorNo1(new BigDecimal(1));
        mmm.setFloorNo2(new BigDecimal(1));
        mmm.setFloorNo3(new BigDecimal(1));
        mmm.setFloorNo4(new BigDecimal(1));
        mmm.setCoefficient(1D);
        mmm.setPeriodSel(1);
        mmm.setStartTime(new Date());
        mmm.setId(1);
        int result = bZParamsDao.updateSHInfoJing(mmm);
        Assert.assertNotEquals("结果不为0",0, result);
    }

    @Test
    public void getBzDataTest(){
        String placeId = "1";
        List<Map<String, Object>> result = bZParamsDao.getBzData(placeId);
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void getBzAllDataTest(){
        String placeId = "1";
        List<Map<String, Object>> result = bZParamsDao.getBzAllData(placeId);
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void getAllFloorNoTest(){
        String id = "1";
        List<Map<String, Object>> result = bZParamsDao.getAllFloorNo(id);
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void getAllFloorNo2Test(){
        String id = "111";
        List<Map<String, Object>> result = bZParamsDao.getAllFloorNo2(id);
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void getAllFloorNoJingTest(){
        String id = "1";
        List<Map<String, Object>> result = bZParamsDao.getAllFloorNoJing(id);
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void doquery2Test(){
        List<BZPramesModel1> result = bZParamsDao.doquery2();
        Assert.assertEquals("结果为0",0, result.size());
    }

    @Test
    public void updateBZInfo1Test(){
        BZPramesModel1 mmm = new BZPramesModel1();
        mmm.setDensitySel(1);
        mmm.setDensitySel1(1);
        mmm.setDensitySel2(1);
        mmm.setRadiusSel(1);
        mmm.setRadiusSel1(1);
        mmm.setRadiusSel2(1);
        mmm.setPlaceId(1);
        mmm.setPlaceId2(2);
        mmm.setPlaceId2sp(2);
        mmm.setPlaceId3(3);
        mmm.setPlaceId3sp(3);
        mmm.setFloorNo(new BigDecimal(1));
        mmm.setFloorNo2(new BigDecimal(2));
        mmm.setFloorNo2sp(new BigDecimal(2));
        mmm.setFloorNo3(new BigDecimal(3));
        mmm.setFloorNo3sp(new BigDecimal(3));
        mmm.setCoefficient(1D);
        mmm.setPeriodSel(1);
        mmm.setStartTime(new Date());
        mmm.setId(1);
        int result = bZParamsDao.updateBZInfo1(mmm);
        Assert.assertNotEquals("结果不为0",0, result);
    }
}


text:
Kotlin with kotlin script gradle

	import org.jetbrains.kotlin.allopen.gradle.AllOpenExtension
	import org.jetbrains.kotlin.gradle.model.AllOpen
	import org.jetbrains.kotlin.gradle.tasks.KotlinCompile
	import org.jetbrains.kotlin.noarg.gradle.NoArgExtension

	plugins {
		kotlin("jvm") version Ver.kotlin
		id("org.jetbrains.kotlin.plugin.allopen") version Ver.kotlin
		id("org.jetbrains.kotlin.plugin.noarg") version Ver.kotlin
		id("org.jetbrains.kotlin.plugin...") version Ver.kotlin
	}

	tasks.withType<KotlinCompile> {
		kotlinOptions {
			apiVersion = "1.3"
			languageVersion = "1.3"
			//default suppressWarnings = false
			//default verbose = false
			jvmTarget = "1.8"
			noReflect = true
			noStdlib = true
		}
	}

	configure<AllOpenExtension> {
		annotation("javax.enterprise.context.ApplicationScoped")
	}

	configure<NoArgExtension> {
		annotation("javax.enterprise.context.ApplicationScoped")
		annotation("javax.xml.bind.annotation.XmlRootElement")
		annotation("javax.xml.bind.annotation.XmlAccessorType")
	}

	dependencies {
		compile(Deps.kt_stdlib_jdk8)

		// kotlin-reflect is (just) used by mockito_core-kotlin
		testImplementation(Deps.kt_reflect)
		testImplementation(Deps.mockito_core) {
			exclude(group = "org.hamcrest")
		}
	}


text:
package com.cattong.entity;

public enum StatusCatalog {
	Unknow(0),                 //0.未分类
	Hot_Retweet(1),          //1.热门转发
	Hot_Comment(2),          //2.热门评论
	News(10),                //10.新闻
	News_Technology(11),     //11.科技新闻
	News_IT(12),             //12.IT新闻
	News_Economy(13),        //13.经济新闻
	News_Entertainment(14),  //14.娱乐新闻
	Entertainment(20),       //20.娱乐
	Technology(30),          //30.科技
	IT(40),                  //40.IT
	Culture(50),             //50.人文艺术
	Philosophy(60),          //60.哲理类
	Joke(70),                //70.冷笑话
	Picture(80),             //80.图片:自拍,风景
	Picture_Mobile(81),      //81.素人(移动自拍)
	Picture_Person(82),      //82.人物
	Picture_Scenery(83),     //83.风景
	Picture_Cartoon(84),      //84.动漫
	Picture_Product(85),       //85.产品
	Picture_Reading(86),       //86.阅读
	Picture_Screenshot(87);    //87.截图

    private int catalogNo;
	private StatusCatalog(int catalogNo) {
		this.catalogNo = catalogNo;
	}

	public int getCatalogNo() {
		return catalogNo;
	}

	public static StatusCatalog getStatusCatalog(int catalogNo) {
		StatusCatalog sc = StatusCatalog.Unknow;

		switch (catalogNo) {
		case 0: sc = StatusCatalog.Unknow; break;
		case 1: sc = StatusCatalog.Hot_Retweet; break;
		case 2: sc = StatusCatalog.Hot_Comment; break;
		case 10: sc = StatusCatalog.News; break;
		case 11: sc = StatusCatalog.News_Technology; break;
		case 12: sc = StatusCatalog.News_IT; break;
		case 13: sc = StatusCatalog.News_Economy; break;
		case 14: sc = StatusCatalog.News_Entertainment; break;
		case 20: sc = StatusCatalog.Entertainment; break;
		case 30: sc = StatusCatalog.Technology; break;
		case 40: sc = StatusCatalog.IT; break;
		case 50: sc = StatusCatalog.Culture; break;
		case 60: sc = StatusCatalog.Philosophy; break;
		case 70: sc = StatusCatalog.Joke; break;
		case 80: sc = StatusCatalog.Picture; break;
		case 81: sc = StatusCatalog.Picture_Mobile; break;
		case 82: sc = StatusCatalog.Picture_Person; break;
		case 83: sc = StatusCatalog.Picture_Scenery; break;
		case 84: sc = StatusCatalog.Picture_Cartoon; break;
		case 85: sc = StatusCatalog.Picture_Product; break;
		case 86: sc = StatusCatalog.Picture_Reading; break;
		case 87: sc = StatusCatalog.Picture_Screenshot; break;
		default : sc = StatusCatalog.Unknow; break;
		}

		return sc;
	}
}


text:
"""
This script will upload a list of files to each of a user's active vessels.
"""

import os
import sys

# If this script resides outside of the directory that contains the seattlelib
# files and experimentlib.py, then you'll need to set that path here. If you
# downloaded an installer (even if you haven't installed seattle on the machine
# this script resides on), the path will be to the seattle_repy directory from
# the extracted installer.
#PATH_TO_SEATTLE_REPY = "/path/to/seattle_repy"
#sys.path.append(PATH_TO_SEATTLE_REPY)

import experimentlib

PUBLICKEY_FILENAME = "/path/to/user.publickey"
PRIVATEKEY_FILENAME = "/path/to/user.privatekey"

# The list of local files to upload. These can contain directory paths.
FILES_TO_UPLOAD = ['file1.txt', 'file2.txt']

def main():

  identity = experimentlib.create_identity_from_key_files(PUBLICKEY_FILENAME, PRIVATEKEY_FILENAME)

  nodelocation_list = experimentlib.lookup_node_locations_by_identity(identity)

  print("Number of advertising nodes: " + str(len(nodelocation_list)))

  vesselhandle_list = experimentlib.find_vessels_on_nodes(identity, nodelocation_list)

  print("Number of active vessels: " + str(len(vesselhandle_list)))

  # Note that we could use experimentlib.run_parallelized() to parallelize the
  # uploading of files and speed things up, but for simplicity we do each
  # upload sequentially.

  for vesselhandle in vesselhandle_list:
    try:
      nodeid, vesselname = experimentlib.get_nodeid_and_vesselname(vesselhandle)
      nodelocation = experimentlib.get_node_location(nodeid)

      for local_filename in FILES_TO_UPLOAD:
        experimentlib.upload_file_to_vessel(vesselhandle, identity, local_filename)
        print("Uploaded " + local_filename + " to " + nodelocation + " vessel " + vesselname)

    except experimentlib.SeattleExperimentError, e:
      print("Failure on vessel " + vesselhandle + ". Error was: " + str(e))

  print("Done.")

if __name__ == "__main__":
  main()


text:
GarageDoor::GPIO::Manager::Manager()
{
    Config = new GarageDoor::Config();
}

GarageDoor::GPIO::Manager::Manager(GarageDoor::Config * conf) : Config(conf) {}

void GarageDoor::GPIO::Manager::LoadPins()
{
    std::string path = "/sys/class/gpio_sw";
    std::vector<std::string> dirList = GarageDoor::Filesystem::ListDirectory(path);

    for ( auto & i : dirList)
    {
        if (i == "standby_led" || i == "normal_led")
        {
            continue;
        }

        // Create instance of PIN and pushback
        pin_ptr pin(new GarageDoor::GPIO::Pin(i));
        pinList.push_back(pin);
    }
}

void GarageDoor::GPIO::Manager::UnloadPins()
{
    if (pinList.size() < 1) { return; }

    std::cout << "Unloading pins..." << std::endl;

    for (pin_ptr & ptr : pinList)
    {
        if (!ptr->HasErrors())
        {
            ptr->Reset();
        }
    }

    pinList.clear();
}

int GarageDoor::GPIO::Manager::CountPins()
{
    return pinList.size();
}

pin_ptr GarageDoor::GPIO::Manager::GetPin(tstring pinName)
{
    if (pinList.size() < 1) { return nullptr; }

    for (auto & i : pinList)
    {
        if ( i->GetName() == pinName )
        {
            return i;
        }
    }

    return nullptr;
}

void GarageDoor::GPIO::Manager::LoadDoors()
{
    json settings = Config->GetJsonRaw();

    for (auto door : settings["pin_mapping"]["doors"])
    {
        GarageDoor::Door doorStruct;
        doorStruct.name = door["name"].dump();
        doorStruct.pin = door["relay_pin"].dump();
        doorStruct.sig_key = door["sig_key"].dump();
        doorStruct.mag_key = door["magnetic_key"].dump();

        pin_ptr pin(GetPin(doorStruct.pin));
        if (pin != nullptr)
        {
            doorStruct.value = GetPin(doorStruct.pin)->GetValue();
        }

        doorList.insert(std::pair<tstring, GarageDoor::Door>(doorStruct.name, doorStruct));
        std::cout << "Appending door: " << doorStruct.name << std::endl;
    }

    std::cout << doorList.size() << " Door(s) Loaded From Configuration" << std::endl;
}


text:
const test = require('ava');
const sanitizeHeaderLog = require('./');
const sinon = require('sinon');

test('initial test', () => {
  var spy = sinon.spy();
  sanitizeHeaderLog(spy);
});


text:
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#ifdef HAVE_VALGRIND
# include <valgrind/valgrind.h>
#endif

#include <gst/check/gstcheck.h>

#include <gst/check/gstharness.h>

GST_START_TEST (test_create_and_unref)
{
  GstElement *e;

  e = gst_element_factory_make ("dtlsenc", NULL);
  fail_unless (e != NULL);
  gst_element_set_state (e, GST_STATE_NULL);
  gst_object_unref (e);

  e = gst_element_factory_make ("dtlsdec", NULL);
  fail_unless (e != NULL);
  gst_element_set_state (e, GST_STATE_NULL);
  gst_object_unref (e);
}

GST_END_TEST;

static GMutex key_lock;
static GCond key_cond;
static int key_count;

static void
_on_key_received (GstElement * element, gpointer user_data)
{
  g_mutex_lock (&key_lock);
  key_count++;
  g_cond_broadcast (&key_cond);
  g_mutex_unlock (&key_lock);
}

static void
_wait_for_key_count_to_reach (int n)
{
  g_mutex_lock (&key_lock);
  while (key_count < n)
    g_cond_wait (&key_cond, &key_lock);
  g_mutex_unlock (&key_lock);
}

static gchar data[] = {
  0x00, 0x01, 0x02, 0x03,
};

GST_START_TEST (test_data_transfer)
{
  GstHarness *server, *client;
  GstElement *s_enc, *s_dec, *c_enc, *c_dec, *s_bin, *c_bin;
  GstPad *target, *ghost;
  GstBuffer *buffer, *buf2;

  /* setup a server and client for dtls negotiation */
  s_bin = gst_bin_new (NULL);
  c_bin = gst_bin_new (NULL);

  /* XXX: the element set states are needed to avoid a runtime warning:
   *
   *   'gst_dtls_connection_process: runtime check failed: (!priv->bio_buffer)'
   *
   * where the encoder needs to be started (and SSL initialized) before the
   * associated decoder receives any data and calls gst_dtls_connection_process().
   */
  s_dec = gst_element_factory_make ("dtlsdec", "server_dec");
  g_object_set (s_dec, "connection-id", "server", NULL);
  g_signal_connect (s_dec, "on-key-received", G_CALLBACK (_on_key_received),
      NULL);
  gst_element_set_state (s_dec, GST_STATE_PAUSED);
  gst_bin_add (GST_BIN (s_bin), s_dec);

  s_enc = gst_element_factory_make ("dtlsenc", "server_enc");
  g_object_set (s_enc, "connection-id", "server", NULL);
  g_signal_connect (s_enc, "on-key-received", G_CALLBACK (_on_key_received),
      NULL);
  gst_element_set_state (s_enc, GST_STATE_PAUSED);
  gst_bin_add (GST_BIN (c_bin), s_enc);

  c_dec = gst_element_factory_make ("dtlsdec", "client_dec");
  g_object_set (c_dec, "connection-id", "client", NULL);
  g_signal_connect (c_dec, "on-key-received", G_CALLBACK (_on_key_received),
      NULL);
  gst_element_set_state (c_dec, GST_STATE_PAUSED);
  gst_bin_add (GST_BIN (c_bin), c_dec);

  c_enc = gst_element_factory_make ("dtlsenc", "client_enc");
  g_object_set (c_enc, "connection-id", "client", "is-client", TRUE, NULL);
  g_signal_connect (c_enc, "on-key-received", G_CALLBACK (_on_key_received),
      NULL);
  gst_element_set_state (c_enc, GST_STATE_PAUSED);
  gst_bin_add (GST_BIN (s_bin), c_enc);

  gst_element_link_pads (s_enc, "src", c_dec, "sink");
  gst_element_link_pads (c_enc, "src", s_dec, "sink");

  target = gst_element_get_request_pad (c_dec, "src");
  ghost = gst_ghost_pad_new ("src", target);
  gst_element_add_pad (s_bin, ghost);
  gst_object_unref (target);

  target = gst_element_get_request_pad (s_enc, "sink");
  ghost = gst_ghost_pad_new ("sink", target);
  gst_element_add_pad (s_bin, ghost);
  gst_object_unref (target);

  target = gst_element_get_request_pad (s_dec, "src");
  ghost = gst_ghost_pad_new ("src", target);
  gst_element_add_pad (c_bin, ghost);
  gst_object_unref (target);

  target = gst_element_get_request_pad (c_enc, "sink");
  ghost = gst_ghost_pad_new ("sink", target);
  gst_element_add_pad (c_bin, ghost);
  gst_object_unref (target);

  server = gst_harness_new_with_element (s_bin, "sink", "src");
  client = gst_harness_new_with_element (c_bin, "sink", "src");

  gst_harness_set_src_caps_str (server, "application/data");
  gst_harness_set_src_caps_str (client, "application/data");

  _wait_for_key_count_to_reach (4);

  buffer = gst_buffer_new_wrapped_full (GST_MEMORY_FLAG_READONLY, data,
      G_N_ELEMENTS (data), 0, G_N_ELEMENTS (data), NULL, NULL);
  gst_harness_push (server, gst_buffer_ref (buffer));
  buf2 = gst_harness_pull (server);
  fail_unless_equals_int (0, gst_buffer_memcmp (buf2, 0, data,
          G_N_ELEMENTS (data)));
  gst_buffer_unref (buf2);

  gst_harness_play (client);
  gst_harness_push (client, gst_buffer_ref (buffer));
  buf2 = gst_harness_pull (client);
  fail_unless_equals_int (0, gst_buffer_memcmp (buf2, 0, data,
          G_N_ELEMENTS (data)));
  gst_buffer_unref (buf2);

  gst_object_unref (s_bin);
  gst_object_unref (c_bin);

  gst_buffer_unref (buffer);
  gst_harness_teardown (server);
  gst_harness_teardown (client);
}

GST_END_TEST;

static Suite *
dtls_suite (void)
{
  Suite *s = suite_create ("dtls");
  TCase *tc_chain = tcase_create ("general");

  suite_add_tcase (s, tc_chain);
  tcase_add_test (tc_chain, test_create_and_unref);
  tcase_add_test (tc_chain, test_data_transfer);

  return s;
}

GST_CHECK_MAIN (dtls);


text:
using System;

namespace Box.V2.Utility
{
    public class ExponentialBackoff : IRetryStrategy
    {
        public TimeSpan GetRetryTimeout(int numRetries)
        {
            var baseInterval = TimeSpan.FromSeconds(2.0);
            const double RETRY_RANDOMIZATION_FACTOR = 0.5;
            var minRandomization = 1 - RETRY_RANDOMIZATION_FACTOR;
            var maxRandomization = 1 + RETRY_RANDOMIZATION_FACTOR;
            var random = new Random();

            var randomization = random.NextDouble() * (maxRandomization - minRandomization) + minRandomization;
            var exponential = Math.Pow(2, numRetries - 1);
            var result = Math.Ceiling(exponential * baseInterval.TotalSeconds * randomization);
            return TimeSpan.FromSeconds(result);
        }
    }
}


text:
/*
 *  This header file abstracts the different card types. The goal is new card
 *  types can easily be added by simply changing this file and
 *  vcard_emul_type.c. It is currently not a requirement to dynamically add new
 *  card types.
 *
 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
 * See the COPYING.LIB file in the top-level directory.
 */

#ifndef VCARD_EMUL_TYPE_H
#define VCARD_EMUL_TYPE_H 1
#include "vcardt.h"
#include "vreadert.h"

/*
 * types
 */
typedef enum {
     VCARD_EMUL_NONE = 0,
     VCARD_EMUL_CAC,
     VCARD_EMUL_PASSTHRU
} VCardEmulType;

/* functions used by the rest of the emulator */
VCardStatus vcard_init(VReader *vreader, VCard *vcard, VCardEmulType type,
                       const char *params, unsigned char * const *cert,
                       int cert_len[], VCardKey *key[], int cert_count);
VCardEmulType vcard_emul_type_select(VReader *vreader);
VCardEmulType vcard_emul_type_from_string(const char *type_string);

#endif


text:
typedef NS_ENUM(NSInteger, SCDatePickerVieWStyle) {
    SCDatePickerViewStyleContinous,
    SCDatePickerViewStylePaginated,
    SCDatePickerViewStyleContinousWithRangeSelection
};

@class SCDatePickerView;

@protocol SCDatePickerViewDelegate <NSObject>

@optional

- (CGFloat)heightForMonthHeaderInDatePickerView:(SCDatePickerView *)datePickerView;

- (UIColor *)datePickerView:(SCDatePickerView *)datePickerView selectedDateColorForDate:(NSDate *)date;
- (UIColor *)datePickerView:(SCDatePickerView *)datePickerView enabledDateColorForDate:(NSDate *)date;
- (UIColor *)datePickerView:(SCDatePickerView *)datePickerView disabledDateColorForDate:(NSDate *)date;
- (UIColor *)datePickerView:(SCDatePickerView *)datePickerView invalidDateColorForDate:(NSDate *)date;

- (UIView *)datePickerView:(SCDatePickerView *)datePickerView selectedBackgroundViewForDate:(NSDate *)date withFrame:(CGRect)frame;

- (UIImage *)previousMonthImageForDatePickerView:(SCDatePickerView *)datePickerView;
- (UIImage *)nextMonthImageForDatePickerView:(SCDatePickerView *)datePickerView;

- (void)datePickerView:(SCDatePickerView *)datePickerView didSelectDate:(NSDate *)date;
- (void)datePickerView:(SCDatePickerView *)datePickerView didSelectDateRangeFrom:(NSDate *)fromDate to:(NSDate *)toDate;

@end

@interface SCDatePickerView : UIView<UICollectionViewDelegate, UICollectionViewDataSource, UICollectionViewDelegateFlowLayout>

@property (nonatomic, weak) IBOutlet id<SCDatePickerViewDelegate> delegate;

// customization properties
@property (nonatomic, strong) NSDate *startDate;
@property (nonatomic, strong) NSDate *endDate;
@property (nonatomic, strong) NSDate *selectedDate;
@property (nonatomic, strong) NSDate *selectedEndDate;
@property (nonatomic, assign) int currentMonthOffset;

// FIXME -- switch to use delegate methods
@property (nonatomic, strong) UIFont *headerFont;
@property (nonatomic, strong) UIFont *dayOfWeekFont;
@property (nonatomic, strong) UIFont *dateFont;
@property (nonatomic, strong) UIFont *selectedDateFont;
@property (nonatomic, strong) NSDateFormatter *dateFormatter;
@property (nonatomic, strong) NSDateFormatter *monthYearFormatter;

@property (nonatomic, assign) SCDatePickerVieWStyle style;

- (id)initWithFrame:(CGRect)frame style:(SCDatePickerVieWStyle)style;
//- (void)selectDate:(NSDate *)date;
//- (void)selectDateRangeFromDate:(NSDate *)fromDate toDate:(NSDate *)toDate;

@end


text:
/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
/* cairo - a vector graphics library with display and print output
 *
 * Copyright 2009 Andrea Canciani
 *
 * This library is free software; you can redistribute it and/or
 * modify it either under the terms of the GNU Lesser General Public
 * License version 2.1 as published by the Free Software Foundation
 * (the "LGPL") or, at your option, under the terms of the Mozilla
 * Public License Version 1.1 (the "MPL"). If you do not alter this
 * notice, a recipient may use your version of this file under either
 * the MPL or the LGPL.
 *
 * You should have received a copy of the LGPL along with this library
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
 * You should have received a copy of the MPL along with this library
 * in the file COPYING-MPL-1.1
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.1 (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.mozilla.org/MPL/
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
 * the specific language governing rights and limitations.
 *
 * The Original Code is the cairo graphics library.
 *
 * The Initial Developer of the Original Code is Andrea Canciani.
 *
 * Contributor(s):
 *	Andrea Canciani <ranma42@gmail.com>
 */

#include "cairoint.h"

#include "cairo-array-private.h"
#include "cairo-pattern-private.h"

/*
 * Rasterizer for mesh patterns.
 *
 * This implementation is based on techniques derived from several
 * papers (available from ACM):
 *
 * - Lien, Shantz and Pratt "Adaptive Forward Differencing for
 *   Rendering Curves and Surfaces" (discussion of the AFD technique,
 *   bound of 1/sqrt(2) on step length without proof)
 *
 * - Popescu and Rosen, "Forward rasterization" (description of
 *   forward rasterization, proof of the previous bound)
 *
 * - Klassen, "Integer Forward Differencing of Cubic Polynomials:
 *   Analysis and Algorithms"
 *
 * - Klassen, "Exact Integer Hybrid Subdivision and Forward
 *   Differencing of Cubics" (improving the bound on the minimum
 *   number of steps)
 *
 * - Chang, Shantz and Rocchetti, "Rendering Cubic Curves and Surfaces
 *   with Integer Adaptive Forward Differencing" (analysis of forward
 *   differencing applied to Bezier patches)
 *
 * Notes:
 * - Poor performance expected in degenerate cases
 *
 * - Patches mostly outside the drawing area are drawn completely (and
 *   clipped), wasting time
 *
 * - Both previous problems are greatly reduced by splitting until a
 *   reasonably small size and clipping the new tiles: execution time
 *   is quadratic in the convex-hull diameter instead than linear to
 *   the painted area. Splitting the tiles doesn't change the painted
 *   area but (usually) reduces the bounding box area (bbox area can
 *   remain the same after splitting, but cannot grow)
 *
 * - The initial implementation used adaptive forward differencing,
 *   but simple forward differencing scored better in benchmarks
 *
 * Idea:
 *
 * We do a sampling over the cubic patch with step du and dv (in the
 * two parameters) that guarantees that any point of our sampling will
 * be at most at 1/sqrt(2) from its adjacent points. In formulae
 * (assuming B is the patch):
 *
 *   |B(u,v) - B(u+du,v)| < 1/sqrt(2)
 *   |B(u,v) - B(u,v+dv)| < 1/sqrt(2)
 *
 * This means that every pixel covered by the patch will contain at
 * least one of the samples, thus forward rasterization can be
 * performed. Sketch of proof (from Popescu and Rosen):
 *
 * Let's take the P pixel we're interested into. If we assume it to be
 * square, its boundaries define 9 regions on the plane:
 *
 * 1|2|3
 * -+-+-
 * 8|P|4
 * -+-+-
 * 7|6|5
 *
 * Let's check that the pixel P will contain at least one point
 * assuming that it is covered by the patch.
 *
 * Since the pixel is covered by the patch, its center will belong to
 * (at least) one of the quads:
 *
 *   {(B(u,v), B(u+du,v), B(u,v+dv), B(u+du,v+dv)) for u,v in [0,1]}
 *
 * If P doesn't contain any of the corners of the quad:
 *
 * - if one of the corners is in 1,3,5 or 7, other two of them have to
 *   be in 2,4,6 or 8, thus if the last corner is not in P, the length
 *   of one of the edges will be > 1/sqrt(2)
 *
 * - if none of the corners is in 1,3,5 or 7, all of them are in 2,4,6
 *   and/or 8. If they are all in different regions, they can't
 *   satisfy the distance constraint. If two of them are in the same
 *   region (let's say 2), no point is in 6 and again it is impossible
 *   to have the center of P in the quad respecting the distance
 *   constraint (both these assertions can be checked by continuity
 *   considering the length of the edges of a quad with the vertices
 *   on the edges of P)
 *
 * Each of the cases led to a contradiction, so P contains at least
 * one of the corners of the quad.
 */

/*
 * Make sure that errors are less than 1 in fixed point math if you
 * change these values.
 *
 * The error is amplified by about steps^3/4 times.
 * The rasterizer always uses a number of steps that is a power of 2.
 *
 * 256 is the maximum allowed number of steps (to have error < 1)
 * using 8.24 for the differences.
 */
#define STEPS_MAX_V 256.0
#define STEPS_MAX_U 256.0

/*
 * If the patch/curve is only partially visible, split it to a finer
 * resolution to get higher chances to clip (part of) it.
 *
 * These values have not been computed, but simply obtained
 * empirically (by benchmarking some patches). They should never be
 * greater than STEPS_MAX_V (or STEPS_MAX_U), but they can be as small
 * as 1 (depending on how much you want to spend time in splitting the
 * patch/curve when trying to save some rasterization time).
 */
#define STEPS_CLIP_V 64.0
#define STEPS_CLIP_U 64.0

/* Utils */
static inline double
sqlen (cairo_point_double_t p0, cairo_point_double_t p1)
{
    cairo_point_double_t delta;

    delta.x = p0.x - p1.x;
    delta.y = p0.y - p1.y;

    return delta.x * delta.x + delta.y * delta.y;
}

static inline int16_t
_color_delta_to_shifted_short (int32_t from, int32_t to, int shift)
{
    int32_t delta = to - from;

    /* We need to round toward zero, because otherwise adding the
     * delta 2^shift times can overflow */
    if (delta >= 0)
	return delta >> shift;
    else
	return -((-delta) >> shift);
}

/*
 * Convert a number of steps to the equivalent shift.
 *
 * Input: the square of the minimum number of steps
 *
 * Output: the smallest integer x such that 2^x > steps
 */
static inline int
sqsteps2shift (double steps_sq)
{
    int r;
    frexp (MAX (1.0, steps_sq), &r);
    return (r + 1) >> 1;
}

/*
 * FD functions
 *
 * A Bezier curve is defined (with respect to a parameter t in
 * [0,1]) from its nodes (x,y,z,w) like this:
 *
 *   B(t) = x(1-t)^3 + 3yt(1-t)^2 + 3zt^2(1-t) + wt^3
 *
 * To efficiently evaluate a Bezier curve, the rasterizer uses forward
 * differences. Given x, y, z, w (the 4 nodes of the Bezier curve), it
 * is possible to convert them to forward differences form and walk
 * over the curve using fd_init (), fd_down () and fd_fwd ().
 *
 * f[0] is always the value of the Bezier curve for "current" t.
 */

/*
 * Initialize the coefficient for forward differences.
 *
 * Input: x,y,z,w are the 4 nodes of the Bezier curve
 *
 * Output: f[i] is the i-th difference of the curve
 *
 * f[0] is the value of the curve for t==0, i.e. f[0]==x.
 *
 * The initial step is 1; this means that each step increases t by 1
 * (so fd_init () immediately followed by fd_fwd (f) n times makes
 * f[0] be the value of the curve for t==n).
 */
static inline void
fd_init (double x, double y, double z, double w, double f[4])
{
    f[0] = x;
    f[1] = w - x;
    f[2] = 6. * (w - 2. * z + y);
    f[3] = 6. * (w - 3. * z + 3. * y - x);
}

/*
 * Halve the step of the coefficients for forward differences.
 *
 * Input: f[i] is the i-th difference of the curve
 *
 * Output: f[i] is the i-th difference of the curve with half the
 *         original step
 *
 * f[0] is not affected, so the current t is not changed.
 *
 * The other coefficients are changed so that the step is half the
 * original step. This means that doing fd_fwd (f) n times with the
 * input f results in the same f[0] as doing fd_fwd (f) 2n times with
 * the output f.
 */
static inline void
fd_down (double f[4])
{
    f[3] *= 0.125;
    f[2] = f[2] * 0.25 - f[3];
    f[1] = (f[1] - f[2]) * 0.5;
}

/*
 * Perform one step of forward differences along the curve.
 *
 * Input: f[i] is the i-th difference of the curve
 *
 * Output: f[i] is the i-th difference of the curve after one step
 */
static inline void
fd_fwd (double f[4])
{
    f[0] += f[1];
    f[1] += f[2];
    f[2] += f[3];
}

/*
 * Transform to integer forward differences.
 *
 * Input: d[n] is the n-th difference (in double precision)
 *
 * Output: i[n] is the n-th difference (in fixed point precision)
 *
 * i[0] is 9.23 fixed point, other differences are 4.28 fixed point.
 */
static inline void
fd_fixed (double d[4], int32_t i[4])
{
    i[0] = _cairo_fixed_16_16_from_double (256 *  2 * d[0]);
    i[1] = _cairo_fixed_16_16_from_double (256 * 16 * d[1]);
    i[2] = _cairo_fixed_16_16_from_double (256 * 16 * d[2]);
    i[3] = _cairo_fixed_16_16_from_double (256 * 16 * d[3]);
}

/*
 * Perform one step of integer forward differences along the curve.
 *
 * Input: f[n] is the n-th difference
 *
 * Output: f[n] is the n-th difference
 *
 * f[0] is 9.23 fixed point, other differences are 4.28 fixed point.
 */
static inline void
fd_fixed_fwd (int32_t f[4])
{
    f[0] += (f[1] >> 5) + ((f[1] >> 4) & 1);
    f[1] += f[2];
    f[2] += f[3];
}

/*
 * Compute the minimum number of steps that guarantee that walking
 * over a curve will leave no holes.
 *
 * Input: p[0..3] the nodes of the Bezier curve
 *
 * Returns: the square of the number of steps
 *
 * Idea:
 *
 * We want to make sure that at every step we move by less than
 * 1/sqrt(2).
 *
 * The derivative of the cubic Bezier with nodes (p0, p1, p2, p3) is
 * the quadratic Bezier with nodes (p1-p0, p2-p1, p3-p2) scaled by 3,
 * so (since a Bezier curve is always bounded by its convex hull), we
 * can say that:
 *
 *  max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p1|, |p3-p2|)
 *
 * We can improve this by noticing that a quadratic Bezier (a,b,c) is
 * bounded by the quad (a,lerp(a,b,t),lerp(b,c,t),c) for any t, so
 * (substituting the previous values, using t=0.5 and simplifying):
 *
 *  max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|)
 *
 * So, to guarantee a maximum step length of 1/sqrt(2) we must do:
 *
 *   3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|) sqrt(2) steps
 */
static inline double
bezier_steps_sq (cairo_point_double_t p[4])
{
    double tmp = sqlen (p[0], p[1]);
    tmp = MAX (tmp, sqlen (p[2], p[3]));
    tmp = MAX (tmp, sqlen (p[0], p[2]) * .25);
    tmp = MAX (tmp, sqlen (p[1], p[3]) * .25);
    return 18.0 * tmp;
}

/*
 * Split a 1D Bezier cubic using de Casteljau's algorithm.
 *
 * Input: x,y,z,w the nodes of the Bezier curve
 *
 * Output: x0,y0,z0,w0 and x1,y1,z1,w1 are respectively the nodes of
 *         the first half and of the second half of the curve
 *
 * The output control nodes have to be distinct.
 */
static inline void
split_bezier_1D (double  x,  double  y,  double  z,  double  w,
		 double *x0, double *y0, double *z0, double *w0,
		 double *x1, double *y1, double *z1, double *w1)
{
    double tmp;

    *x0 = x;
    *w1 = w;

    tmp = 0.5 * (y + z);
    *y0 = 0.5 * (x + y);
    *z1 = 0.5 * (z + w);

    *z0 = 0.5 * (*y0 + tmp);
    *y1 = 0.5 * (tmp + *z1);

    *w0 = *x1 = 0.5 * (*z0 + *y1);
}

/*
 * Split a Bezier curve using de Casteljau's algorithm.
 *
 * Input: p[0..3] the nodes of the Bezier curve
 *
 * Output: fst_half[0..3] and snd_half[0..3] are respectively the
 *         nodes of the first and of the second half of the curve
 *
 * fst_half and snd_half must be different, but they can be the same as
 * nodes.
 */
static void
split_bezier (cairo_point_double_t p[4],
	      cairo_point_double_t fst_half[4],
	      cairo_point_double_t snd_half[4])
{
    split_bezier_1D (p[0].x, p[1].x, p[2].x, p[3].x,
		     &fst_half[0].x, &fst_half[1].x, &fst_half[2].x, &fst_half[3].x,
		     &snd_half[0].x, &snd_half[1].x, &snd_half[2].x, &snd_half[3].x);

    split_bezier_1D (p[0].y, p[1].y, p[2].y, p[3].y,
		     &fst_half[0].y, &fst_half[1].y, &fst_half[2].y, &fst_half[3].y,
		     &snd_half[0].y, &snd_half[1].y, &snd_half[2].y, &snd_half[3].y);
}

typedef enum _intersection {
    INSIDE = -1, /* the interval is entirely contained in the reference interval */
    OUTSIDE = 0, /* the interval has no intersection with the reference interval */
    PARTIAL = 1  /* the interval intersects the reference interval (but is not fully inside it) */
} intersection_t;

/*
 * Check if an interval if inside another.
 *
 * Input: a,b are the extrema of the first interval
 *        c,d are the extrema of the second interval
 *
 * Returns: INSIDE  iff [a,b) intersection [c,d) = [a,b)
 *          OUTSIDE iff [a,b) intersection [c,d) = {}
 *          PARTIAL otherwise
 *
 * The function assumes a < b and c < d
 *
 * Note: Bitwise-anding the results along each component gives the
 *       expected result for [a,b) x [A,B) intersection [c,d) x [C,D).
 */
static inline int
intersect_interval (double a, double b, double c, double d)
{
    if (c <= a && b <= d)
	return INSIDE;
    else if (a >= d || b <= c)
	return OUTSIDE;
    else
	return PARTIAL;
}

/*
 * Set the color of a pixel.
 *
 * Input: data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *        x, y are the coordinates of the pixel to be colored
 *        r,g,b,a are the color components of the color to be set
 *
 * Output: the (x,y) pixel in data has the (r,g,b,a) color
 *
 * The input color components are not premultiplied, but the data
 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
 * premultiplied).
 *
 * If the pixel to be set is outside the image, this function does
 * nothing.
 */
static inline void
draw_pixel (unsigned char *data, int width, int height, int stride,
	    int x, int y, uint16_t r, uint16_t g, uint16_t b, uint16_t a)
{
    if (likely (0 <= x && 0 <= y && x < width && y < height)) {
	uint32_t tr, tg, tb, ta;

	/* Premultiply and round */
	ta = a;
	tr = r * ta + 0x8000;
	tg = g * ta + 0x8000;
	tb = b * ta + 0x8000;

	tr += tr >> 16;
	tg += tg >> 16;
	tb += tb >> 16;

	*((uint32_t*) (data + y*(ptrdiff_t)stride + 4*x)) = ((ta << 16) & 0xff000000) |
	    ((tr >> 8) & 0xff0000) | ((tg >> 16) & 0xff00) | (tb >> 24);
    }
}

/*
 * Forward-rasterize a cubic curve using forward differences.
 *
 * Input: data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *        ushift is log2(n) if n is the number of desired steps
 *        dxu[i], dyu[i] are the x,y forward differences of the curve
 *        r0,g0,b0,a0 are the color components of the start point
 *        r3,g3,b3,a3 are the color components of the end point
 *
 * Output: data will be changed to have the requested curve drawn in
 *         the specified colors
 *
 * The input color components are not premultiplied, but the data
 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
 * premultiplied).
 *
 * The function draws n+1 pixels, that is from the point at step 0 to
 * the point at step n, both included. This is the discrete equivalent
 * to drawing the curve for values of the interpolation parameter in
 * [0,1] (including both extremes).
 */
static inline void
rasterize_bezier_curve (unsigned char *data, int width, int height, int stride,
			int ushift, double dxu[4], double dyu[4],
			uint16_t r0, uint16_t g0, uint16_t b0, uint16_t a0,
			uint16_t r3, uint16_t g3, uint16_t b3, uint16_t a3)
{
    int32_t xu[4], yu[4];
    int x0, y0, u, usteps = 1 << ushift;

    uint16_t r = r0, g = g0, b = b0, a = a0;
    int16_t dr = _color_delta_to_shifted_short (r0, r3, ushift);
    int16_t dg = _color_delta_to_shifted_short (g0, g3, ushift);
    int16_t db = _color_delta_to_shifted_short (b0, b3, ushift);
    int16_t da = _color_delta_to_shifted_short (a0, a3, ushift);

    fd_fixed (dxu, xu);
    fd_fixed (dyu, yu);

    /*
     * Use (dxu[0],dyu[0]) as origin for the forward differences.
     *
     * This makes it possible to handle much larger coordinates (the
     * ones that can be represented as cairo_fixed_t)
     */
    x0 = _cairo_fixed_from_double (dxu[0]);
    y0 = _cairo_fixed_from_double (dyu[0]);
    xu[0] = 0;
    yu[0] = 0;

    for (u = 0; u <= usteps; ++u) {
	/*
	 * This rasterizer assumes that pixels are integer aligned
	 * squares, so a generic (x,y) point belongs to the pixel with
	 * top-left coordinates (floor(x), floor(y))
	 */

	int x = _cairo_fixed_integer_floor (x0 + (xu[0] >> 15) + ((xu[0] >> 14) & 1));
	int y = _cairo_fixed_integer_floor (y0 + (yu[0] >> 15) + ((yu[0] >> 14) & 1));

	draw_pixel (data, width, height, stride, x, y, r, g, b, a);

	fd_fixed_fwd (xu);
	fd_fixed_fwd (yu);
	r += dr;
	g += dg;
	b += db;
	a += da;
    }
}

/*
 * Clip, split and rasterize a Bezier curve.
 *
 * Input: data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *        p[i] is the i-th node of the Bezier curve
 *        c0[i] is the i-th color component at the start point
 *        c3[i] is the i-th color component at the end point
 *
 * Output: data will be changed to have the requested curve drawn in
 *         the specified colors
 *
 * The input color components are not premultiplied, but the data
 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
 * premultiplied).
 *
 * The color components are red, green, blue and alpha, in this order.
 *
 * The function guarantees that it will draw the curve with a step
 * small enough to never have a distance above 1/sqrt(2) between two
 * consecutive points (which is needed to ensure that no hole can
 * appear when using this function to rasterize a patch).
 */
static void
draw_bezier_curve (unsigned char *data, int width, int height, int stride,
		   cairo_point_double_t p[4], double c0[4], double c3[4])
{
    double top, bottom, left, right, steps_sq;
    int i, v;

    top = bottom = p[0].y;
    for (i = 1; i < 4; ++i) {
	top    = MIN (top,    p[i].y);
	bottom = MAX (bottom, p[i].y);
    }

    /* Check visibility */
    v = intersect_interval (top, bottom, 0, height);
    if (v == OUTSIDE)
	return;

    left = right = p[0].x;
    for (i = 1; i < 4; ++i) {
	left  = MIN (left,  p[i].x);
	right = MAX (right, p[i].x);
    }

    v &= intersect_interval (left, right, 0, width);
    if (v == OUTSIDE)
	return;

    steps_sq = bezier_steps_sq (p);
    if (steps_sq >= (v == INSIDE ? STEPS_MAX_U * STEPS_MAX_U : STEPS_CLIP_U * STEPS_CLIP_U)) {
	/*
	 * The number of steps is greater than the threshold. This
	 * means that either the error would become too big if we
	 * directly rasterized it or that we can probably save some
	 * time by splitting the curve and clipping part of it
	 */
	cairo_point_double_t first[4], second[4];
	double midc[4];
	split_bezier (p, first, second);
	midc[0] = (c0[0] + c3[0]) * 0.5;
	midc[1] = (c0[1] + c3[1]) * 0.5;
	midc[2] = (c0[2] + c3[2]) * 0.5;
	midc[3] = (c0[3] + c3[3]) * 0.5;
	draw_bezier_curve (data, width, height, stride, first, c0, midc);
	draw_bezier_curve (data, width, height, stride, second, midc, c3);
    } else {
	double xu[4], yu[4];
	int ushift = sqsteps2shift (steps_sq), k;

	fd_init (p[0].x, p[1].x, p[2].x, p[3].x, xu);
	fd_init (p[0].y, p[1].y, p[2].y, p[3].y, yu);

	for (k = 0; k < ushift; ++k) {
	    fd_down (xu);
	    fd_down (yu);
	}

	rasterize_bezier_curve (data, width, height, stride, ushift,
				xu, yu,
				_cairo_color_double_to_short (c0[0]),
				_cairo_color_double_to_short (c0[1]),
				_cairo_color_double_to_short (c0[2]),
				_cairo_color_double_to_short (c0[3]),
				_cairo_color_double_to_short (c3[0]),
				_cairo_color_double_to_short (c3[1]),
				_cairo_color_double_to_short (c3[2]),
				_cairo_color_double_to_short (c3[3]));

	/* Draw the end point, to make sure that we didn't leave it
	 * out because of rounding */
	draw_pixel (data, width, height, stride,
		    _cairo_fixed_integer_floor (_cairo_fixed_from_double (p[3].x)),
		    _cairo_fixed_integer_floor (_cairo_fixed_from_double (p[3].y)),
		    _cairo_color_double_to_short (c3[0]),
		    _cairo_color_double_to_short (c3[1]),
		    _cairo_color_double_to_short (c3[2]),
		    _cairo_color_double_to_short (c3[3]));
    }
}

/*
 * Forward-rasterize a cubic Bezier patch using forward differences.
 *
 * Input: data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *        vshift is log2(n) if n is the number of desired steps
 *        p[i][j], p[i][j] are the the nodes of the Bezier patch
 *        col[i][j] is the j-th color component of the i-th corner
 *
 * Output: data will be changed to have the requested patch drawn in
 *         the specified colors
 *
 * The nodes of the patch are as follows:
 *
 * u\v 0    - >    1
 * 0  p00 p01 p02 p03
 * |  p10 p11 p12 p13
 * v  p20 p21 p22 p23
 * 1  p30 p31 p32 p33
 *
 * i.e. u varies along the first component (rows), v varies along the
 * second one (columns).
 *
 * The color components are red, green, blue and alpha, in this order.
 * c[0..3] are the colors in p00, p30, p03, p33 respectively
 *
 * The input color components are not premultiplied, but the data
 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
 * premultiplied).
 *
 * If the patch folds over itself, the part with the highest v
 * parameter is considered above. If both have the same v, the one
 * with the highest u parameter is above.
 *
 * The function draws n+1 curves, that is from the curve at step 0 to
 * the curve at step n, both included. This is the discrete equivalent
 * to drawing the patch for values of the interpolation parameter in
 * [0,1] (including both extremes).
 */
static inline void
rasterize_bezier_patch (unsigned char *data, int width, int height, int stride, int vshift,
			cairo_point_double_t p[4][4], double col[4][4])
{
    double pv[4][2][4], cstart[4], cend[4], dcstart[4], dcend[4];
    int v, i, k;

    v = 1 << vshift;

    /*
     * pv[i][0] is the function (represented using forward
     * differences) mapping v to the x coordinate of the i-th node of
     * the Bezier curve with parameter u.
     * (Likewise p[i][0] gives the y coordinate).
     *
     * This means that (pv[0][0][0],pv[0][1][0]),
     * (pv[1][0][0],pv[1][1][0]), (pv[2][0][0],pv[2][1][0]) and
     * (pv[3][0][0],pv[3][1][0]) are the nodes of the Bezier curve for
     * the "current" v value (see the FD comments for more details).
     */
    for (i = 0; i < 4; ++i) {
	fd_init (p[i][0].x, p[i][1].x, p[i][2].x, p[i][3].x, pv[i][0]);
	fd_init (p[i][0].y, p[i][1].y, p[i][2].y, p[i][3].y, pv[i][1]);
	for (k = 0; k < vshift; ++k) {
	    fd_down (pv[i][0]);
	    fd_down (pv[i][1]);
	}
    }

    for (i = 0; i < 4; ++i) {
	cstart[i]  = col[0][i];
	cend[i]    = col[1][i];
	dcstart[i] = (col[2][i] - col[0][i]) / v;
	dcend[i]   = (col[3][i] - col[1][i]) / v;
    }

    v++;
    while (v--) {
	cairo_point_double_t nodes[4];
	for (i = 0; i < 4; ++i) {
	    nodes[i].x = pv[i][0][0];
	    nodes[i].y = pv[i][1][0];
	}

	draw_bezier_curve (data, width, height, stride, nodes, cstart, cend);

	for (i = 0; i < 4; ++i) {
	    fd_fwd (pv[i][0]);
	    fd_fwd (pv[i][1]);
	    cstart[i] += dcstart[i];
	    cend[i] += dcend[i];
	}
    }
}

/*
 * Clip, split and rasterize a Bezier cubic patch.
 *
 * Input: data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *        p[i][j], p[i][j] are the nodes of the patch
 *        col[i][j] is the j-th color component of the i-th corner
 *
 * Output: data will be changed to have the requested patch drawn in
 *         the specified colors
 *
 * The nodes of the patch are as follows:
 *
 * u\v 0    - >    1
 * 0  p00 p01 p02 p03
 * |  p10 p11 p12 p13
 * v  p20 p21 p22 p23
 * 1  p30 p31 p32 p33
 *
 * i.e. u varies along the first component (rows), v varies along the
 * second one (columns).
 *
 * The color components are red, green, blue and alpha, in this order.
 * c[0..3] are the colors in p00, p30, p03, p33 respectively
 *
 * The input color components are not premultiplied, but the data
 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
 * premultiplied).
 *
 * If the patch folds over itself, the part with the highest v
 * parameter is considered above. If both have the same v, the one
 * with the highest u parameter is above.
 *
 * The function guarantees that it will draw the patch with a step
 * small enough to never have a distance above 1/sqrt(2) between two
 * adjacent points (which guarantees that no hole can appear).
 *
 * This function can be used to rasterize a tile of PDF type 7
 * shadings (see http://www.adobe.com/devnet/pdf/pdf_reference.html).
 */
static void
draw_bezier_patch (unsigned char *data, int width, int height, int stride,
		     cairo_point_double_t p[4][4], double c[4][4])
{
    double top, bottom, left, right, steps_sq;
    int i, j, v;

    top = bottom = p[0][0].y;
    for (i = 0; i < 4; ++i) {
	for (j= 0; j < 4; ++j) {
	    top    = MIN (top,    p[i][j].y);
	    bottom = MAX (bottom, p[i][j].y);
	}
    }

    v = intersect_interval (top, bottom, 0, height);
    if (v == OUTSIDE)
	return;

    left = right = p[0][0].x;
    for (i = 0; i < 4; ++i) {
	for (j= 0; j < 4; ++j) {
	    left  = MIN (left,  p[i][j].x);
	    right = MAX (right, p[i][j].x);
	}
    }

    v &= intersect_interval (left, right, 0, width);
    if (v == OUTSIDE)
	return;

    steps_sq = 0;
    for (i = 0; i < 4; ++i)
	steps_sq = MAX (steps_sq, bezier_steps_sq (p[i]));

    if (steps_sq >= (v == INSIDE ? STEPS_MAX_V * STEPS_MAX_V : STEPS_CLIP_V * STEPS_CLIP_V)) {
	/* The number of steps is greater than the threshold. This
	 * means that either the error would become too big if we
	 * directly rasterized it or that we can probably save some
	 * time by splitting the curve and clipping part of it. The
	 * patch is only split in the v direction to guarantee that
	 * rasterizing each part will overwrite parts with low v with
	 * overlapping parts with higher v. */

	cairo_point_double_t first[4][4], second[4][4];
	double subc[4][4];

	for (i = 0; i < 4; ++i)
	    split_bezier (p[i], first[i], second[i]);

	for (i = 0; i < 4; ++i) {
	    subc[0][i] = c[0][i];
	    subc[1][i] = c[1][i];
	    subc[2][i] = 0.5 * (c[0][i] + c[2][i]);
	    subc[3][i] = 0.5 * (c[1][i] + c[3][i]);
	}

	draw_bezier_patch (data, width, height, stride, first, subc);

	for (i = 0; i < 4; ++i) {
	    subc[0][i] = subc[2][i];
	    subc[1][i] = subc[3][i];
	    subc[2][i] = c[2][i];
	    subc[3][i] = c[3][i];
	}
	draw_bezier_patch (data, width, height, stride, second, subc);
    } else {
	rasterize_bezier_patch (data, width, height, stride, sqsteps2shift (steps_sq), p, c);
    }
}

/*
 * Draw a tensor product shading pattern.
 *
 * Input: mesh is the mesh pattern
 *        data is the base pointer of the image
 *        width, height are the dimensions of the image
 *        stride is the stride in bytes between adjacent rows
 *
 * Output: data will be changed to have the pattern drawn on it
 *
 * data is assumed to be clear and its content is assumed to be in
 * CAIRO_FORMAT_ARGB32 (8 bpc, premultiplied).
 *
 * This function can be used to rasterize a PDF type 7 shading (see
 * http://www.adobe.com/devnet/pdf/pdf_reference.html).
 */
void
_cairo_mesh_pattern_rasterize (const cairo_mesh_pattern_t *mesh,
			       void                       *data,
			       int                         width,
			       int                         height,
			       int                         stride,
			       double                      x_offset,
			       double                      y_offset)
{
    cairo_point_double_t nodes[4][4];
    double colors[4][4];
    cairo_matrix_t p2u;
    unsigned int i, j, k, n;
    cairo_status_t status;
    const cairo_mesh_patch_t *patch;
    const cairo_color_t *c;

    assert (mesh->base.status == CAIRO_STATUS_SUCCESS);
    assert (mesh->current_patch == NULL);

    p2u = mesh->base.matrix;
    status = cairo_matrix_invert (&p2u);
    assert (status == CAIRO_STATUS_SUCCESS);

    n = _cairo_array_num_elements (&mesh->patches);
    patch = _cairo_array_index_const (&mesh->patches, 0);
    for (i = 0; i < n; i++) {
	for (j = 0; j < 4; j++) {
	    for (k = 0; k < 4; k++) {
		nodes[j][k] = patch->points[j][k];
		cairo_matrix_transform_point (&p2u, &nodes[j][k].x, &nodes[j][k].y);
		nodes[j][k].x += x_offset;
		nodes[j][k].y += y_offset;
	    }
	}

	c = &patch->colors[0];
	colors[0][0] = c->red;
	colors[0][1] = c->green;
	colors[0][2] = c->blue;
	colors[0][3] = c->alpha;

	c = &patch->colors[3];
	colors[1][0] = c->red;
	colors[1][1] = c->green;
	colors[1][2] = c->blue;
	colors[1][3] = c->alpha;

	c = &patch->colors[1];
	colors[2][0] = c->red;
	colors[2][1] = c->green;
	colors[2][2] = c->blue;
	colors[2][3] = c->alpha;

	c = &patch->colors[2];
	colors[3][0] = c->red;
	colors[3][1] = c->green;
	colors[3][2] = c->blue;
	colors[3][3] = c->alpha;

	draw_bezier_patch (data, width, height, stride, nodes, colors);
	patch++;
    }
}