1// queue.h
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Author: allauzen@cs.nyu.edu (Cyril Allauzen)
16//
17// \file
18// Functions and classes for various Fst state queues with
19// a unified interface.
20
21#ifndef FST_LIB_QUEUE_H__
22#define FST_LIB_QUEUE_H__
23
24#include <deque>
25#include <vector>
26
27#include "fst/lib/arcfilter.h"
28#include "fst/lib/connect.h"
29#include "fst/lib/heap.h"
30#include "fst/lib/topsort.h"
31
32namespace fst {
33
34// template <class S>
35// class Queue {
36//  public:
37//   typedef typename S StateId;
38//
39//   // Ctr: may need args (e.g., Fst, comparator) for some queues
40//   Queue(...);
41//   // Returns the head of the queue
42//   StateId Head() const;
43//   // Inserts a state
44//   void Enqueue(StateId s);
45//   // Removes the head of the queue
46//   void Dequeue();
47//   // Updates ordering of state s when weight changes, if necessary
48//   void Update(StateId s);
49//   // Does the queue contain no elements?
50//   bool Empty() const;
51//   // Remove all states from queue
52//   void Clear();
53// };
54
55// State queue types.
56enum QueueType {
57  TRIVIAL_QUEUE = 0,         // Single state queue
58  FIFO_QUEUE = 1,            // First-in, first-out queue
59  LIFO_QUEUE = 2,            // Last-in, first-out queue
60  SHORTEST_FIRST_QUEUE = 3,  // Shortest-first queue
61  TOP_ORDER_QUEUE = 4,       // Topologically-ordered queue
62  STATE_ORDER_QUEUE = 5,     // State-ID ordered queue
63  SCC_QUEUE = 6,             // Component graph top-ordered meta-queue
64  AUTO_QUEUE = 7,            // Auto-selected queue
65  OTHER_QUEUE = 8
66 };
67
68
69// QueueBase, templated on the StateId, is the base class shared by the
70// queues considered by AutoQueue.
71template <class S>
72class QueueBase {
73 public:
74  typedef S StateId;
75
76  QueueBase(QueueType type) : queue_type_(type) {}
77  virtual ~QueueBase() {}
78  StateId Head() const { return Head_(); }
79  void Enqueue(StateId s) { Enqueue_(s); }
80  void Dequeue() { Dequeue_(); }
81  void Update(StateId s) { Update_(s); }
82  bool Empty() const { return Empty_(); }
83  void Clear() { Clear_(); }
84  QueueType Type() { return queue_type_; }
85
86 private:
87  virtual StateId Head_() const = 0;
88  virtual void Enqueue_(StateId s) = 0;
89  virtual void Dequeue_() = 0;
90  virtual void Update_(StateId s) = 0;
91  virtual bool Empty_() const = 0;
92  virtual void Clear_() = 0;
93
94  QueueType queue_type_;
95};
96
97
98// Trivial queue discipline, templated on the StateId. You may enqueue
99// at most one state at a time. It is used for strongly connected components
100// with only one state and no self loops.
101template <class S>
102class TrivialQueue : public QueueBase<S> {
103public:
104  typedef S StateId;
105
106  TrivialQueue() : QueueBase<S>(TRIVIAL_QUEUE), front_(kNoStateId) {}
107  StateId Head() const { return front_; }
108  void Enqueue(StateId s) { front_ = s; }
109  void Dequeue() { front_ = kNoStateId; }
110  void Update(StateId s) {}
111  bool Empty() const { return front_ == kNoStateId; }
112  void Clear() { front_ = kNoStateId; }
113
114
115private:
116  virtual StateId Head_() const { return Head(); }
117  virtual void Enqueue_(StateId s) { Enqueue(s); }
118  virtual void Dequeue_() { Dequeue(); }
119  virtual void Update_(StateId s) { Update(s); }
120  virtual bool Empty_() const { return Empty(); }
121  virtual void Clear_() { return Clear(); }
122
123  StateId front_;
124};
125
126
127// First-in, first-out queue discipline, templated on the StateId.
128template <class S>
129class FifoQueue : public QueueBase<S>, public deque<S> {
130 public:
131  using deque<S>::back;
132  using deque<S>::push_front;
133  using deque<S>::pop_back;
134  using deque<S>::empty;
135  using deque<S>::clear;
136
137  typedef S StateId;
138
139  FifoQueue() : QueueBase<S>(FIFO_QUEUE) {}
140  StateId Head() const { return back(); }
141  void Enqueue(StateId s) { push_front(s); }
142  void Dequeue() { pop_back(); }
143  void Update(StateId s) {}
144  bool Empty() const { return empty(); }
145  void Clear() { clear(); }
146
147 private:
148  virtual StateId Head_() const { return Head(); }
149  virtual void Enqueue_(StateId s) { Enqueue(s); }
150  virtual void Dequeue_() { Dequeue(); }
151  virtual void Update_(StateId s) { Update(s); }
152  virtual bool Empty_() const { return Empty(); }
153  virtual void Clear_() { return Clear(); }
154};
155
156
157// Last-in, first-out queue discipline, templated on the StateId.
158template <class S>
159class LifoQueue : public QueueBase<S>, public deque<S> {
160 public:
161  using deque<S>::front;
162  using deque<S>::push_front;
163  using deque<S>::pop_front;
164  using deque<S>::empty;
165  using deque<S>::clear;
166
167  typedef S StateId;
168
169  LifoQueue() : QueueBase<S>(LIFO_QUEUE) {}
170  StateId Head() const { return front(); }
171  void Enqueue(StateId s) { push_front(s); }
172  void Dequeue() { pop_front(); }
173  void Update(StateId s) {}
174  bool Empty() const { return empty(); }
175  void Clear() { clear(); }
176
177 private:
178  virtual StateId Head_() const { return Head(); }
179  virtual void Enqueue_(StateId s) { Enqueue(s); }
180  virtual void Dequeue_() { Dequeue(); }
181  virtual void Update_(StateId s) { Update(s); }
182  virtual bool Empty_() const { return Empty(); }
183  virtual void Clear_() { return Clear(); }
184};
185
186
187// Shortest-first queue discipline, templated on the StateId and
188// comparison function object.  Comparison function object COMP is
189// used to compare two StateIds. If a (single) state's order changes,
190// it can be reordered in the queue with a call to Update().
191template <typename S, typename C>
192class ShortestFirstQueue : public QueueBase<S> {
193 public:
194  typedef S StateId;
195  typedef C Compare;
196
197  ShortestFirstQueue(C comp)
198      : QueueBase<S>(SHORTEST_FIRST_QUEUE), heap_(comp) {}
199
200  StateId Head() const { return heap_.Top(); }
201
202  void Enqueue(StateId s) {
203    for (StateId i = key_.size(); i <= s; ++i)
204      key_.push_back(kNoKey);
205    key_[s] = heap_.Insert(s);
206  }
207
208  void Dequeue() {
209    key_[heap_.Pop()] = kNoKey;
210  }
211
212  void Update(StateId s) {
213    if (s >= (StateId)key_.size() || key_[s] == kNoKey) {
214      Enqueue(s);
215    } else {
216      heap_.Update(key_[s], s);
217    }
218  }
219
220  bool Empty() const { return heap_.Empty(); }
221
222  void Clear() {
223    heap_.Clear();
224    key_.clear();
225  }
226
227 private:
228  Heap<S, C> heap_;
229  vector<ssize_t> key_;
230
231  virtual StateId Head_() const { return Head(); }
232  virtual void Enqueue_(StateId s) { Enqueue(s); }
233  virtual void Dequeue_() { Dequeue(); }
234  virtual void Update_(StateId s) { Update(s); }
235  virtual bool Empty_() const { return Empty(); }
236  virtual void Clear_() { return Clear(); }
237};
238
239
240// Given a vector that maps from states to weights and a Less
241// comparison function object between weights, this class defines a
242// comparison function object between states.
243template <typename S, typename L>
244class StateWeightCompare {
245 public:
246  typedef L Less;
247  typedef typename L::Weight Weight;
248  typedef S StateId;
249
250  StateWeightCompare(const vector<Weight>* weights, const L &less)
251      : weights_(weights), less_(less) {}
252
253  bool operator()(const S x, const S y) const {
254    return less_((*weights_)[x], (*weights_)[y]);
255  }
256
257 private:
258  const vector<Weight>* weights_;
259  L less_;
260};
261
262
263// Shortest-first queue discipline, templated on the StateId and Weight is
264// specialized to use the weight's natural order for the comparion function.
265template <typename S, typename W>
266class NaturalShortestFirstQueue :
267      public ShortestFirstQueue<S, StateWeightCompare<S, NaturalLess<W> > > {
268 public:
269  typedef StateWeightCompare<S, NaturalLess<W> > C;
270
271  NaturalShortestFirstQueue(vector<W> *distance) :
272      ShortestFirstQueue<S, C>(C(distance, less_)) {}
273
274 private:
275  NaturalLess<W> less_;
276};
277
278
279// Topological-order queue discipline, templated on the StateId.
280// States are ordered in the queue topologically. The FST must be acyclic.
281template <class S>
282class TopOrderQueue : public QueueBase<S> {
283 public:
284  typedef S StateId;
285
286  // This constructor computes the top. order. It accepts an arc filter
287  // to limit the transitions considered in that computation (e.g., only
288  // the epsilon graph).
289  template <class Arc, class ArcFilter>
290
291  TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter)
292      : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId),
293        order_(0), state_(0) {
294    bool acyclic;
295    TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic);
296    DfsVisit(fst, &top_order_visitor, filter);
297    if (!acyclic)
298      LOG(FATAL) << "TopOrderQueue: fst is not acyclic.";
299    state_.resize(order_.size(), kNoStateId);
300  }
301
302  // This constructor is passed the top. order, useful when we know it
303  // beforehand.
304  TopOrderQueue(const vector<StateId> &order)
305      : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId),
306        order_(order), state_(order.size(), kNoStateId) {}
307
308  StateId Head() const { return state_[front_]; }
309
310  void Enqueue(StateId s) {
311    if (front_ > back_) front_ = back_ = order_[s];
312    else if (order_[s] > back_) back_ = order_[s];
313    else if (order_[s] < front_) front_ = order_[s];
314    state_[order_[s]] = s;
315  }
316
317  void Dequeue() {
318    state_[front_] = kNoStateId;
319    while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_;
320  }
321
322  void Update(StateId s) {}
323
324  bool Empty() const { return front_ > back_; }
325
326  void Clear() {
327    for (StateId i = front_; i <= back_; ++i) state_[i] = kNoStateId;
328    back_ = kNoStateId;
329    front_ = 0;
330  }
331
332 private:
333  StateId front_;
334  StateId back_;
335  vector<StateId> order_;
336  vector<StateId> state_;
337
338  virtual StateId Head_() const { return Head(); }
339  virtual void Enqueue_(StateId s) { Enqueue(s); }
340  virtual void Dequeue_() { Dequeue(); }
341  virtual void Update_(StateId s) { Update(s); }
342  virtual bool Empty_() const { return Empty(); }
343  virtual void Clear_() { return Clear(); }
344
345};
346
347
348// State order queue discipline, templated on the StateId.
349// States are ordered in the queue by state Id.
350template <class S>
351class StateOrderQueue : public QueueBase<S> {
352public:
353  typedef S StateId;
354
355  StateOrderQueue()
356      : QueueBase<S>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {}
357
358  StateId Head() const { return front_; }
359
360  void Enqueue(StateId s) {
361    if (front_ > back_) front_ = back_ = s;
362    else if (s > back_) back_ = s;
363    else if (s < front_) front_ = s;
364    while ((StateId)enqueued_.size() <= s) enqueued_.push_back(false);
365    enqueued_[s] = true;
366  }
367
368  void Dequeue() {
369    enqueued_[front_] = false;
370    while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_;
371  }
372
373  void Update(StateId s) {}
374
375  bool Empty() const { return front_ > back_; }
376
377  void Clear() {
378        for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false;
379        front_ = 0;
380        back_ = kNoStateId;
381  }
382
383private:
384  StateId front_;
385  StateId back_;
386  vector<bool> enqueued_;
387
388  virtual StateId Head_() const { return Head(); }
389  virtual void Enqueue_(StateId s) { Enqueue(s); }
390  virtual void Dequeue_() { Dequeue(); }
391  virtual void Update_(StateId s) { Update(s); }
392  virtual bool Empty_() const { return Empty(); }
393  virtual void Clear_() { return Clear(); }
394
395};
396
397
398// SCC topological-order meta-queue discipline, templated on the StateId S
399// and a queue Q, which is used inside each SCC.  It visits the SCC's
400// of an FST in topological order. Its constructor is passed the queues to
401// to use within an SCC.
402template <class S, class Q>
403class SccQueue : public QueueBase<S> {
404 public:
405  typedef S StateId;
406  typedef Q Queue;
407
408  // Constructor takes a vector specifying the SCC number per state
409  // and a vector giving the queue to use per SCC number.
410  SccQueue(const vector<StateId> &scc, vector<Queue*> *queue)
411    : QueueBase<S>(SCC_QUEUE), queue_(queue), scc_(scc), front_(0),
412      back_(kNoStateId) {}
413
414  StateId Head() const {
415    while ((front_ <= back_) &&
416           (((*queue_)[front_] && (*queue_)[front_]->Empty())
417            || (((*queue_)[front_] == 0) &&
418                ((front_ > (StateId)trivial_queue_.size())
419                 || (trivial_queue_[front_] == kNoStateId)))))
420      ++front_;
421    if (front_ > back_)
422      LOG(FATAL) << "SccQueue: head of empty queue";
423    if ((*queue_)[front_])
424      return (*queue_)[front_]->Head();
425    else
426      return trivial_queue_[front_];
427  }
428
429  void Enqueue(StateId s) {
430    if (front_ > back_) front_ = back_ = scc_[s];
431    else if (scc_[s] > back_) back_ = scc_[s];
432    else if (scc_[s] < front_) front_ = scc_[s];
433    if ((*queue_)[scc_[s]]) {
434      (*queue_)[scc_[s]]->Enqueue(s);
435    } else {
436      while ( (StateId)trivial_queue_.size() <= scc_[s])
437        trivial_queue_.push_back(kNoStateId);
438      trivial_queue_[scc_[s]] = s;
439    }
440  }
441
442  void Dequeue() {
443    if (front_ > back_)
444      LOG(FATAL) << "SccQueue: dequeue of empty queue";
445    if ((*queue_)[front_])
446      (*queue_)[front_]->Dequeue();
447    else if (front_ < (StateId)trivial_queue_.size())
448      trivial_queue_[front_] = kNoStateId;
449  }
450
451  void Update(StateId s) {
452    if ((*queue_)[scc_[s]])
453      (*queue_)[scc_[s]]->Update(s);
454  }
455
456  bool Empty() const {
457    if (front_ < back_)   // Queue scc # back_ not empty unless back_==front_
458      return false;
459    else if (front_ > back_)
460      return true;
461    else if ((*queue_)[front_])
462      return (*queue_)[front_]->Empty();
463    else
464      return (front_ > (StateId)trivial_queue_.size())
465        || (trivial_queue_[front_] == kNoStateId);
466  }
467
468  void Clear() {
469    for (StateId i = front_; i <= back_; ++i)
470      if ((*queue_)[i])
471        (*queue_)[i]->Clear();
472      else if (i < (StateId)trivial_queue_.size())
473        trivial_queue_[i] = kNoStateId;
474    front_ = 0;
475    back_ = kNoStateId;
476  }
477
478private:
479  vector<Queue*> *queue_;
480  const vector<StateId> &scc_;
481  mutable StateId front_;
482  StateId back_;
483  vector<StateId> trivial_queue_;
484
485  virtual StateId Head_() const { return Head(); }
486  virtual void Enqueue_(StateId s) { Enqueue(s); }
487  virtual void Dequeue_() { Dequeue(); }
488  virtual void Update_(StateId s) { Update(s); }
489  virtual bool Empty_() const { return Empty(); }
490  virtual void Clear_() { return Clear(); }
491};
492
493
494// Automatic queue discipline, templated on the StateId. It selects a
495// queue discipline for a given FST based on its properties.
496template <class S>
497class AutoQueue : public QueueBase<S> {
498public:
499  typedef S StateId;
500
501  // This constructor takes a state distance vector that, if non-null and if
502  // the Weight type has the path property, will entertain the
503  // shortest-first queue using the natural order w.r.t to the distance.
504  template <class Arc, class ArcFilter>
505  AutoQueue(const Fst<Arc> &fst, const vector<typename Arc::Weight> *distance,
506            ArcFilter filter) : QueueBase<S>(AUTO_QUEUE) {
507    typedef typename Arc::Weight Weight;
508    typedef StateWeightCompare< StateId, NaturalLess<Weight> > Compare;
509
510    //  First check if the FST is known to have these properties.
511    uint64 props = fst.Properties(kAcyclic | kCyclic |
512                                  kTopSorted | kUnweighted, false);
513    if ((props & kTopSorted) || fst.Start() == kNoStateId) {
514      queue_ = new StateOrderQueue<StateId>();
515      VLOG(2) << "AutoQueue: using state-order discipline";
516    } else if (props & kAcyclic) {
517      queue_ = new TopOrderQueue<StateId>(fst, filter);
518      VLOG(2) << "AutoQueue: using top-order discipline";
519    } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) {
520      queue_ = new LifoQueue<StateId>();
521      VLOG(2) << "AutoQueue: using LIFO discipline";
522    } else {
523      uint64 props;
524      // Decompose into strongly-connected components.
525      SccVisitor<Arc> scc_visitor(&scc_, 0, 0, &props);
526      DfsVisit(fst, &scc_visitor, filter);
527      StateId nscc = *max_element(scc_.begin(), scc_.end()) + 1;
528      vector<QueueType> queue_types(nscc);
529      NaturalLess<Weight> *less = 0;
530      Compare *comp = 0;
531      if (distance && (Weight::Properties() & kPath)) {
532        less = new NaturalLess<Weight>;
533        comp = new Compare(distance, *less);
534      }
535      // Find the queue type to use per SCC.
536      bool unweighted;
537      bool all_trivial;
538      SccQueueType(fst, scc_, &queue_types, filter, less, &all_trivial,
539                                      &unweighted);
540      // If unweighted and semiring is idempotent, use lifo queue.
541      if (unweighted) {
542          queue_ = new LifoQueue<StateId>();
543          VLOG(2) << "AutoQueue: using LIFO discipline";
544          delete comp;
545          delete less;
546          return;
547      }
548      // If all the scc are trivial, FST is acyclic and the scc# gives
549      // the topological order.
550      if (all_trivial) {
551          queue_ = new TopOrderQueue<StateId>(scc_);
552          VLOG(2) << "AutoQueue: using top-order discipline";
553          delete comp;
554          delete less;
555          return;
556      }
557      VLOG(2) << "AutoQueue: using SCC meta-discipline";
558      queues_.resize(nscc);
559      for (StateId i = 0; i < nscc; ++i) {
560        switch(queue_types[i]) {
561          case TRIVIAL_QUEUE:
562            queues_[i] = 0;
563            VLOG(3) << "AutoQueue: SCC #" << i
564                    << ": using trivial discipline";
565            break;
566          case SHORTEST_FIRST_QUEUE:
567            CHECK(comp);
568            queues_[i] = new ShortestFirstQueue<StateId, Compare>(*comp);
569            VLOG(3) << "AutoQueue: SCC #" << i <<
570              ": using shortest-first discipline";
571            break;
572          case LIFO_QUEUE:
573            queues_[i] = new LifoQueue<StateId>();
574            VLOG(3) << "AutoQueue: SCC #" << i
575                    << ": using LIFO disciplle";
576            break;
577          case FIFO_QUEUE:
578          default:
579            queues_[i] = new FifoQueue<StateId>();
580            VLOG(3) << "AutoQueue: SCC #" << i
581                    << ": using FIFO disciplle";
582            break;
583        }
584      }
585      queue_ = new SccQueue< StateId, QueueBase<StateId> >(scc_, &queues_);
586      delete comp;
587      delete less;
588    }
589  }
590
591  ~AutoQueue() {
592    for (StateId i = 0; i < (StateId)queues_.size(); ++i) /*naucen-edit*/
593      delete queues_[i];
594    delete queue_;
595  }
596
597  StateId Head() const { return queue_->Head(); }
598
599  void Enqueue(StateId s) { queue_->Enqueue(s); }
600
601  void Dequeue() { queue_->Dequeue(); }
602
603  void Update(StateId s) { queue_->Update(s); }
604
605  bool Empty() const { return queue_->Empty(); }
606
607  void Clear() { queue_->Clear(); }
608
609
610 private:
611  QueueBase<StateId> *queue_;
612  vector< QueueBase<StateId>* > queues_;
613  vector<StateId> scc_;
614
615  template <class Arc, class ArcFilter, class Less>
616  static void SccQueueType(const Fst<Arc> &fst,
617                           const vector<StateId> &scc,
618                           vector<QueueType> *queue_types,
619                           ArcFilter filter, Less *less,
620                           bool *all_trivial, bool *unweighted);
621
622  virtual StateId Head_() const { return Head(); }
623
624  virtual void Enqueue_(StateId s) { Enqueue(s); }
625
626  virtual void Dequeue_() { Dequeue(); }
627
628  virtual void Update_(StateId s) { Update(s); }
629
630  virtual bool Empty_() const { return Empty(); }
631
632  virtual void Clear_() { return Clear(); }
633};
634
635
636// Examines the states in an Fst's strongly connected components and
637// determines which type of queue to use per SCC. Stores result in
638// vector QUEUE_TYPES, which is assumed to have length equal to the
639// number of SCCs. An arc filter is used to limit the transitions
640// considered (e.g., only the epsilon graph).  ALL_TRIVIAL is set
641// to true if every queue is the trivial queue. UNWEIGHTED is set to
642// true if the semiring is idempotent and all the arc weights are equal to
643// Zero() or One().
644template <class StateId>
645template <class A, class ArcFilter, class Less>
646void AutoQueue<StateId>::SccQueueType(const Fst<A> &fst,
647                                      const vector<StateId> &scc,
648                                      vector<QueueType> *queue_type,
649                                      ArcFilter filter, Less *less,
650                                      bool *all_trivial, bool *unweighted) {
651  typedef A Arc;
652  typedef typename A::StateId StateId;
653  typedef typename A::Weight Weight;
654
655  *all_trivial = true;
656  *unweighted = true;
657
658  for (StateId i = 0; i < (StateId)queue_type->size(); ++i)
659    (*queue_type)[i] = TRIVIAL_QUEUE;
660
661  for (StateIterator< Fst<Arc> > sit(fst); !sit.Done(); sit.Next()) {
662    StateId state = sit.Value();
663    for (ArcIterator< Fst<Arc> > ait(fst, state);
664	 !ait.Done();
665	 ait.Next()) {
666      const Arc &arc = ait.Value();
667      if (!filter(arc)) continue;
668      if (scc[state] == scc[arc.nextstate]) {
669        QueueType &type = (*queue_type)[scc[state]];
670        if (!less || ((*less)(arc.weight, Weight::One())))
671          type = FIFO_QUEUE;
672        else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) {
673          if (!(Weight::Properties() & kIdempotent) ||
674              (arc.weight != Weight::Zero() && arc.weight != Weight::One()))
675            type = SHORTEST_FIRST_QUEUE;
676          else
677            type = LIFO_QUEUE;
678        }
679        if (type != TRIVIAL_QUEUE) *all_trivial = false;
680      }
681      if (!(Weight::Properties() & kIdempotent) ||
682          (arc.weight != Weight::Zero() && arc.weight != Weight::One()))
683        *unweighted = false;
684    }
685  }
686}
687
688}  // namespace fst
689
690#endif
691