folly/sorted_vector_types.h

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * This header defines two classes that very nearly model
  19  * AssociativeContainer (but not quite).  These implement set-like and
  20  * map-like behavior on top of a sorted vector, instead of using
  21  * rb-trees like std::set and std::map.
  22  *
  23  * This is potentially useful in cases where the number of elements in
  24  * the set or map is small, or when you want to avoid using more
  25  * memory than necessary and insertions/deletions are much more rare
  26  * than lookups (these classes have O(N) insertions/deletions).
  27  *
  28  * In the interest of using these in conditions where the goal is to
  29  * minimize memory usage, they support a GrowthPolicy parameter, which
  30  * is a class defining a single function called increase_capacity,
  31  * which will be called whenever we are about to insert something: you
  32  * can then decide to call reserve() based on the current capacity()
  33  * and size() of the passed in vector-esque Container type.  An
  34  * example growth policy that grows one element at a time:
  35  *
  36  *    struct OneAtATimePolicy {
  37  *      template<class Container>
  38  *      void increase_capacity(Container& c) {
  39  *        if (c.size() == c.capacity()) {
  40  *          c.reserve(c.size() + 1);
  41  *        }
  42  *      }
  43  *    };
  44  *
  45  *    typedef sorted_vector_set<int,
  46  *                              std::less<int>,
  47  *                              std::allocator<int>,
  48  *                              OneAtATimePolicy>
  49  *            OneAtATimeIntSet;
  50  *
  51  * Important differences from std::set and std::map:
  52  *   - insert() and erase() invalidate iterators and references
  53  *   - insert() and erase() are O(N)
  54  *   - our iterators model RandomAccessIterator
  55  *   - sorted_vector_map::value_type is pair<K,V>, not pair<const K,V>.
  56  *     (This is basically because we want to store the value_type in
  57  *     std::vector<>, which requires it to be Assignable.)
  58  */
  59
  60 #pragma once
  61
  62 #include <algorithm>
  63 #include <initializer_list>
  64 #include <iterator>
  65 #include <stdexcept>
  66 #include <type_traits>
  67 #include <utility>
  68 #include <vector>
  69
  70 #include <boost/operators.hpp>
  71
  72 namespace folly {
  73
  74 //////////////////////////////////////////////////////////////////////
  75
  76 namespace detail {
  77
  78   // This wrapper goes around a GrowthPolicy and provides iterator
  79   // preservation semantics, but only if the growth policy is not the
  80   // default (i.e. nothing).
  81   template<class Policy>
  82   struct growth_policy_wrapper : private Policy {
  83     template<class Container, class Iterator>
  84     Iterator increase_capacity(Container& c, Iterator desired_insertion)
  85     {
  86       typedef typename Container::difference_type diff_t;
  87       diff_t d = desired_insertion - c.begin();
  88       Policy::increase_capacity(c);
  89       return c.begin() + d;
  90     }
  91   };
  92   template<>
  93   struct growth_policy_wrapper<void> {
  94     template<class Container, class Iterator>
  95     Iterator increase_capacity(Container&, Iterator it) {
  96       return it;
  97     }
  98   };
  99
 100   /*
 101    * This helper returns the distance between two iterators if it is
 102    * possible to figure it out without messing up the range
 103    * (i.e. unless they are InputIterators).  Otherwise this returns
 104    * -1.
 105    */
 106   template<class Iterator>
 107   int distance_if_multipass(Iterator first, Iterator last) {
 108     typedef typename std::iterator_traits<Iterator>::iterator_category categ;
 109     if (std::is_same<categ,std::input_iterator_tag>::value)
 110       return -1;
 111     return std::distance(first, last);
 112   }
 113
 114   template<class OurContainer, class Vector, class GrowthPolicy>
 115   typename OurContainer::iterator
 116   insert_with_hint(OurContainer& sorted,
 117                    Vector& cont,
 118                    typename OurContainer::iterator hint,
 119                    typename OurContainer::value_type&& value,
 120                    GrowthPolicy& po)
 121   {
 122     const typename OurContainer::value_compare& cmp(sorted.value_comp());
 123     if (hint == cont.end() || cmp(value, *hint)) {
 124       if (hint == cont.begin()) {
 125         po.increase_capacity(cont, cont.begin());
 126         return cont.insert(cont.begin(), std::move(value));
 127       }
 128       if (cmp(*(hint - 1), value)) {
 129         hint = po.increase_capacity(cont, hint);
 130         return cont.insert(hint, std::move(value));
 131       }
 132       return sorted.insert(std::move(value)).first;
 133     }
 134
 135     if (cmp(*hint, value)) {
 136       if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
 137         typename OurContainer::iterator it =
 138           po.increase_capacity(cont, hint + 1);
 139         return cont.insert(it, std::move(value));
 140       }
 141     }
 142
 143     // Value and *hint did not compare, so they are equal keys.
 144     return hint;
 145   }
 146
 147 }
 148
 149 //////////////////////////////////////////////////////////////////////
 150
 151 /**
 152  * A sorted_vector_set is a container similar to std::set<>, but
 153  * implemented as as a sorted array with std::vector<>.
 154  *
 155  * @param class T               Data type to store
 156  * @param class Compare         Comparison function that imposes a
 157  *                              strict weak ordering over instances of T
 158  * @param class Allocator       allocation policy
 159  * @param class GrowthPolicy    policy object to control growth
 160  *
 161  * @author Aditya Agarwal <aditya@fb.com>
 162  * @author Akhil Wable    <akhil@fb.com>
 163  * @author Jordan DeLong  <delong.j@fb.com>
 164  */
 165 template<class T,
 166          class Compare      = std::less<T>,
 167          class Allocator    = std::allocator<T>,
 168          class GrowthPolicy = void>
 169 class sorted_vector_set
 170   : boost::totally_ordered1<
 171       sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
 172     , detail::growth_policy_wrapper<GrowthPolicy> >
 173 {
 174   typedef std::vector<T,Allocator> ContainerT;
 175
 176   detail::growth_policy_wrapper<GrowthPolicy>&
 177   get_growth_policy() { return *this; }
 178
 179 public:
 180   typedef T       value_type;
 181   typedef T       key_type;
 182   typedef Compare key_compare;
 183   typedef Compare value_compare;
 184
 185   typedef typename ContainerT::pointer                pointer;
 186   typedef typename ContainerT::reference              reference;
 187   typedef typename ContainerT::const_reference        const_reference;
 188   /*
 189    * XXX: Our normal iterator ought to also be a constant iterator
 190    * (cf. Defect Report 103 for std::set), but this is a bit more of a
 191    * pain.
 192    */
 193   typedef typename ContainerT::iterator               iterator;
 194   typedef typename ContainerT::const_iterator         const_iterator;
 195   typedef typename ContainerT::difference_type        difference_type;
 196   typedef typename ContainerT::size_type              size_type;
 197   typedef typename ContainerT::reverse_iterator       reverse_iterator;
 198   typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
 199
 200   explicit sorted_vector_set(const Compare& comp = Compare(),
 201                              const Allocator& alloc = Allocator())
 202     : m_(comp, alloc)
 203   {}
 204
 205   template<class InputIterator>
 206   explicit sorted_vector_set(
 207       InputIterator first,
 208       InputIterator last,
 209       const Compare& comp = Compare(),
 210       const Allocator& alloc = Allocator())
 211     : m_(comp, alloc)
 212   {
 213     // This is linear if [first, last) is already sorted (and if we
 214     // can figure out the distance between the two iterators).
 215     insert(first, last);
 216   }
 217
 218   explicit sorted_vector_set(
 219       std::initializer_list<value_type> list,
 220       const Compare& comp = Compare(),
 221       const Allocator& alloc = Allocator())
 222     : m_(comp, alloc)
 223   {
 224     insert(list.begin(), list.end());
 225   }
 226
 227   key_compare key_comp() const { return m_; }
 228   value_compare value_comp() const { return m_; }
 229
 230   iterator begin()                      { return m_.cont_.begin();  }
 231   iterator end()                        { return m_.cont_.end();    }
 232   const_iterator cbegin() const         { return m_.cont_.cbegin(); }
 233   const_iterator begin() const          { return m_.cont_.begin();  }
 234   const_iterator cend() const           { return m_.cont_.cend();   }
 235   const_iterator end() const            { return m_.cont_.end();    }
 236   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
 237   reverse_iterator rend()               { return m_.cont_.rend();   }
 238   const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
 239   const_reverse_iterator rend() const   { return m_.cont_.rend();   }
 240
 241   void clear()                  { return m_.cont_.clear();    }
 242   size_type size() const        { return m_.cont_.size();     }
 243   size_type max_size() const    { return m_.cont_.max_size(); }
 244   bool empty() const            { return m_.cont_.empty();    }
 245   void reserve(size_type s)     { return m_.cont_.reserve(s); }
 246   void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
 247   size_type capacity() const    { return m_.cont_.capacity(); }
 248
 249   std::pair<iterator,bool> insert(const value_type& value) {
 250     return insert(std::move(value_type(value)));
 251   }
 252
 253   std::pair<iterator,bool> insert(value_type&& value) {
 254     iterator it = lower_bound(value);
 255     if (it == end() || value_comp()(value, *it)) {
 256       it = get_growth_policy().increase_capacity(m_.cont_, it);
 257       return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
 258     }
 259     return std::make_pair(it, false);
 260   }
 261
 262   iterator insert(iterator hint, const value_type& value) {
 263     return insert(hint, std::move(value_type(value)));
 264   }
 265
 266   iterator insert(iterator hint, value_type&& value) {
 267     return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
 268       get_growth_policy());
 269   }
 270
 271   template<class InputIterator>
 272   void insert(InputIterator first, InputIterator last) {
 273     int d = detail::distance_if_multipass(first, last);
 274     if (d != -1) {
 275       m_.cont_.reserve(m_.cont_.size() + d);
 276     }
 277     for (; first != last; ++first) {
 278       insert(end(), *first);
 279     }
 280   }
 281
 282   size_type erase(const key_type& key) {
 283     iterator it = lower_bound(key);
 284     if (it == end()) {
 285       return 0;
 286     }
 287     m_.cont_.erase(it);
 288     return 1;
 289   }
 290
 291   void erase(iterator it) {
 292     m_.cont_.erase(it);
 293   }
 294
 295   void erase(iterator first, iterator last) {
 296     m_.cont_.erase(first, last);
 297   }
 298
 299   iterator find(const key_type& key) {
 300     iterator it = lower_bound(key);
 301     if (it == end() || !key_comp()(key, *it))
 302       return it;
 303     return end();
 304   }
 305
 306   const_iterator find(const key_type& key) const {
 307     const_iterator it = lower_bound(key);
 308     if (it == end() || !key_comp()(key, *it))
 309       return it;
 310     return end();
 311   }
 312
 313   size_type count(const key_type& key) const {
 314     return find(key) == end() ? 0 : 1;
 315   }
 316
 317   iterator lower_bound(const key_type& key) {
 318     return std::lower_bound(begin(), end(), key, key_comp());
 319   }
 320
 321   const_iterator lower_bound(const key_type& key) const {
 322     return std::lower_bound(begin(), end(), key, key_comp());
 323   }
 324
 325   iterator upper_bound(const key_type& key) {
 326     return std::upper_bound(begin(), end(), key, key_comp());
 327   }
 328
 329   const_iterator upper_bound(const key_type& key) const {
 330     return std::upper_bound(begin(), end(), key, key_comp());
 331   }
 332
 333   std::pair<iterator,iterator> equal_range(const key_type& key) {
 334     return std::equal_range(begin(), end(), key, key_comp());
 335   }
 336
 337   std::pair<const_iterator,const_iterator>
 338   equal_range(const key_type& key) const {
 339     return std::equal_range(begin(), end(), key, key_comp());
 340   }
 341
 342   // Nothrow as long as swap() on the Compare type is nothrow.
 343   void swap(sorted_vector_set& o) {
 344     using std::swap;  // Allow ADL for swap(); fall back to std::swap().
 345     Compare& a = m_;
 346     Compare& b = o.m_;
 347     swap(a, b);
 348     m_.cont_.swap(o.m_.cont_);
 349   }
 350
 351   bool operator==(const sorted_vector_set& other) const {
 352     return other.m_.cont_ == m_.cont_;
 353   }
 354
 355   bool operator<(const sorted_vector_set& other) const {
 356     return m_.cont_ < other.m_.cont_;
 357   }
 358
 359 private:
 360   /*
 361    * This structure derives from the comparison object in order to
 362    * make use of the empty base class optimization if our comparison
 363    * functor is an empty class (usual case).
 364    *
 365    * Wrapping up this member like this is better than deriving from
 366    * the Compare object ourselves (there are some perverse edge cases
 367    * involving virtual functions).
 368    *
 369    * More info:  http://www.cantrip.org/emptyopt.html
 370    */
 371   struct EBO : Compare {
 372     explicit EBO(const Compare& c, const Allocator& alloc)
 373       : Compare(c)
 374       , cont_(alloc)
 375     {}
 376     ContainerT cont_;
 377   } m_;
 378 };
 379
 380 // Swap function that can be found using ADL.
 381 template<class T, class C, class A, class G>
 382 inline void swap(sorted_vector_set<T,C,A,G>& a,
 383                  sorted_vector_set<T,C,A,G>& b) {
 384   return a.swap(b);
 385 }
 386
 387 //////////////////////////////////////////////////////////////////////
 388
 389 /**
 390  * A sorted_vector_map is similar to a sorted_vector_set but stores
 391  * <key,value> pairs instead of single elements.
 392  *
 393  * @param class Key           Key type
 394  * @param class Value         Value type
 395  * @param class Compare       Function that can compare key types and impose
 396  *                            a strict weak ordering over them.
 397  * @param class Allocator     allocation policy
 398  * @param class GrowthPolicy  policy object to control growth
 399  *
 400  * @author Aditya Agarwal <aditya@fb.com>
 401  * @author Akhil Wable    <akhil@fb.com>
 402  * @author Jordan DeLong  <delong.j@fb.com>
 403  */
 404 template<class Key,
 405          class Value,
 406          class Compare        = std::less<Key>,
 407          class Allocator      = std::allocator<std::pair<Key,Value> >,
 408          class GrowthPolicy   = void>
 409 class sorted_vector_map
 410   : boost::totally_ordered1<
 411       sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
 412     , detail::growth_policy_wrapper<GrowthPolicy> >
 413 {
 414   typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
 415
 416   detail::growth_policy_wrapper<GrowthPolicy>&
 417   get_growth_policy() { return *this; }
 418
 419 public:
 420   typedef Key                                       key_type;
 421   typedef Value                                     mapped_type;
 422   typedef std::pair<key_type,mapped_type>           value_type;
 423   typedef Compare                                   key_compare;
 424
 425   struct value_compare : private Compare {
 426     bool operator()(const value_type& a, const value_type& b) const {
 427       return Compare::operator()(a.first, b.first);
 428     }
 429
 430   protected:
 431     friend class sorted_vector_map;
 432     explicit value_compare(const Compare& c) : Compare(c) {}
 433   };
 434
 435   typedef typename ContainerT::pointer                pointer;
 436   typedef typename ContainerT::reference              reference;
 437   typedef typename ContainerT::const_reference        const_reference;
 438   typedef typename ContainerT::iterator               iterator;
 439   typedef typename ContainerT::const_iterator         const_iterator;
 440   typedef typename ContainerT::difference_type        difference_type;
 441   typedef typename ContainerT::size_type              size_type;
 442   typedef typename ContainerT::reverse_iterator       reverse_iterator;
 443   typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
 444
 445   explicit sorted_vector_map(const Compare& comp = Compare(),
 446                              const Allocator& alloc = Allocator())
 447     : m_(value_compare(comp), alloc)
 448   {}
 449
 450   template<class InputIterator>
 451   explicit sorted_vector_map(
 452       InputIterator first,
 453       InputIterator last,
 454       const Compare& comp = Compare(),
 455       const Allocator& alloc = Allocator())
 456     : m_(value_compare(comp), alloc)
 457   {
 458     insert(first, last);
 459   }
 460
 461   explicit sorted_vector_map(
 462       std::initializer_list<value_type> list,
 463       const Compare& comp = Compare(),
 464       const Allocator& alloc = Allocator())
 465     : m_(value_compare(comp), alloc)
 466   {
 467     insert(list.begin(), list.end());
 468   }
 469
 470   key_compare key_comp() const { return m_; }
 471   value_compare value_comp() const { return m_; }
 472
 473   iterator begin()                      { return m_.cont_.begin();  }
 474   iterator end()                        { return m_.cont_.end();    }
 475   const_iterator cbegin() const         { return m_.cont_.cbegin(); }
 476   const_iterator begin() const          { return m_.cont_.begin();  }
 477   const_iterator cend() const           { return m_.cont_.cend();   }
 478   const_iterator end() const            { return m_.cont_.end();    }
 479   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
 480   reverse_iterator rend()               { return m_.cont_.rend();   }
 481   const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
 482   const_reverse_iterator rend() const   { return m_.cont_.rend();   }
 483
 484   void clear()                  { return m_.cont_.clear();    }
 485   size_type size() const        { return m_.cont_.size();     }
 486   size_type max_size() const    { return m_.cont_.max_size(); }
 487   bool empty() const            { return m_.cont_.empty();    }
 488   void reserve(size_type s)     { return m_.cont_.reserve(s); }
 489   void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
 490   size_type capacity() const    { return m_.cont_.capacity(); }
 491
 492   std::pair<iterator,bool> insert(const value_type& value) {
 493     return insert(std::move(value_type(value)));
 494   }
 495
 496   std::pair<iterator,bool> insert(value_type&& value) {
 497     iterator it = lower_bound(value.first);
 498     if (it == end() || value_comp()(value, *it)) {
 499       it = get_growth_policy().increase_capacity(m_.cont_, it);
 500       return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
 501     }
 502     return std::make_pair(it, false);
 503   }
 504
 505   iterator insert(iterator hint, const value_type& value) {
 506     return insert(hint, std::move(value_type(value)));
 507   }
 508
 509   iterator insert(iterator hint, value_type&& value) {
 510     return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
 511       get_growth_policy());
 512   }
 513
 514   template<class InputIterator>
 515   void insert(InputIterator first, InputIterator last) {
 516     int d = detail::distance_if_multipass(first, last);
 517     if (d != -1) {
 518       m_.cont_.reserve(m_.cont_.size() + d);
 519     }
 520     for (; first != last; ++first) {
 521       insert(end(), *first);
 522     }
 523   }
 524
 525   size_type erase(const key_type& key) {
 526     iterator it = find(key);
 527     if (it == end()) {
 528       return 0;
 529     }
 530     m_.cont_.erase(it);
 531     return 1;
 532   }
 533
 534   void erase(iterator it) {
 535     m_.cont_.erase(it);
 536   }
 537
 538   void erase(iterator first, iterator last) {
 539     m_.cont_.erase(first, last);
 540   }
 541
 542   iterator find(const key_type& key) {
 543     iterator it = lower_bound(key);
 544     if (it == end() || !key_comp()(key, it->first))
 545       return it;
 546     return end();
 547   }
 548
 549   const_iterator find(const key_type& key) const {
 550     const_iterator it = lower_bound(key);
 551     if (it == end() || !key_comp()(key, it->first))
 552       return it;
 553     return end();
 554   }
 555
 556   mapped_type& at(const key_type& key) {
 557     iterator it = find(key);
 558     if (it != end()) {
 559       return it->second;
 560     }
 561     throw std::out_of_range("sorted_vector_map::at");
 562   }
 563
 564   const mapped_type& at(const key_type& key) const {
 565     const_iterator it = find(key);
 566     if (it != end()) {
 567       return it->second;
 568     }
 569     throw std::out_of_range("sorted_vector_map::at");
 570   }
 571
 572   size_type count(const key_type& key) const {
 573     return find(key) == end() ? 0 : 1;
 574   }
 575
 576   iterator lower_bound(const key_type& key) {
 577     auto c = key_comp();
 578     auto f = [&](const value_type& a, const key_type& b) {
 579       return c(a.first, b);
 580     };
 581     return std::lower_bound(begin(), end(), key, f);
 582   }
 583
 584   const_iterator lower_bound(const key_type& key) const {
 585     auto c = key_comp();
 586     auto f = [&](const value_type& a, const key_type& b) {
 587       return c(a.first, b);
 588     };
 589     return std::lower_bound(begin(), end(), key, f);
 590   }
 591
 592   iterator upper_bound(const key_type& key) {
 593     auto c = key_comp();
 594     auto f = [&](const key_type& a, const value_type& b) {
 595       return c(a, b.first);
 596     };
 597     return std::upper_bound(begin(), end(), key, f);
 598   }
 599
 600   const_iterator upper_bound(const key_type& key) const {
 601     auto c = key_comp();
 602     auto f = [&](const key_type& a, const value_type& b) {
 603       return c(a, b.first);
 604     };
 605     return std::upper_bound(begin(), end(), key, f);
 606   }
 607
 608   std::pair<iterator,iterator> equal_range(const key_type& key) {
 609     // Note: std::equal_range can't be passed a functor that takes
 610     // argument types different from the iterator value_type, so we
 611     // have to do this.
 612     iterator low = lower_bound(key);
 613     auto c = key_comp();
 614     auto f = [&](const key_type& a, const value_type& b) {
 615       return c(a, b.first);
 616     };
 617     iterator high = std::upper_bound(low, end(), key, f);
 618     return std::make_pair(low, high);
 619   }
 620
 621   std::pair<const_iterator,const_iterator>
 622   equal_range(const key_type& key) const {
 623     return const_cast<sorted_vector_map*>(this)->equal_range(key);
 624   }
 625
 626   // Nothrow as long as swap() on the Compare type is nothrow.
 627   void swap(sorted_vector_map& o) {
 628     using std::swap; // Allow ADL for swap(); fall back to std::swap().
 629     Compare& a = m_;
 630     Compare& b = o.m_;
 631     swap(a, b);
 632     m_.cont_.swap(o.m_.cont_);
 633   }
 634
 635   mapped_type& operator[](const key_type& key) {
 636     iterator it = lower_bound(key);
 637     if (it == end() || key_comp()(key, it->first)) {
 638       return insert(it, value_type(key, mapped_type()))->second;
 639     }
 640     return it->second;
 641   }
 642
 643   bool operator==(const sorted_vector_map& other) const {
 644     return m_.cont_ == other.m_.cont_;
 645   }
 646
 647   bool operator<(const sorted_vector_map& other) const {
 648     return m_.cont_ < other.m_.cont_;
 649   }
 650
 651 private:
 652   // This is to get the empty base optimization; see the comment in
 653   // sorted_vector_set.
 654   struct EBO : value_compare {
 655     explicit EBO(const value_compare& c, const Allocator& alloc)
 656       : value_compare(c)
 657       , cont_(alloc)
 658     {}
 659     ContainerT cont_;
 660   } m_;
 661 };
 662
 663 // Swap function that can be found using ADL.
 664 template<class K, class V, class C, class A, class G>
 665 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
 666                  sorted_vector_map<K,V,C,A,G>& b) {
 667   return a.swap(b);
 668 }
 669
 670 //////////////////////////////////////////////////////////////////////
 671
 672 }