Changeset 4077


Ignore:
Timestamp:
Aug 26, 2021, 6:07:09 AM (3 months ago)
Author:
Peter
Message:

implement insert with hint; refs #710

Location:
branches/kendall-score
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/kendall-score/test/ranking.cc

    r4072 r4077  
    283283
    284284
     285void test_insert_hint(test::Suite& suite)
     286{
     287  suite.out() << YAT_TEST_PROLOGUE;
     288
     289  utility::Ranking<double> ranking;
     290  ranking.insert(1);
     291  ranking.insert(2);
     292  ranking.insert(3);
     293
     294  auto hint = ranking.lower_bound(2);
     295  ranking.insert(hint, 2);
     296  ranking.insert(hint, 1);
     297  ranking.insert(hint, 0);
     298  ranking.insert(hint, 3);
     299  ranking.insert(hint, 4);
     300  hint = ranking.lower_bound(4);
     301  ranking.insert(hint, 5);
     302
     303  hint = ranking.lower_bound(4);
     304  ranking.insert(hint, 4.1);
     305}
     306
     307
    285308int main(int argc, char* argv[])
    286309{
     
    291314    test_copy(suite);
    292315    test_erase(suite);
     316    test_insert_hint(suite);
    293317  }
    294318  catch (std::exception& e) {
  • branches/kendall-score/yat/utility/Ranking.h

    r4074 r4077  
    3232#include <cstddef>
    3333#include <functional>
     34#include <iostream>
     35#include <iterator>
    3436#include <memory>
    3537
    36 #include <iostream> // debug
    3738namespace theplu {
    3839namespace yat {
     
    109110
    110111    /**
     112       \return iterator pointing to the first element, i.e., the
     113       node with the smallest value.
     114     */
     115    iterator begin(void)
     116    {
     117      return iterator(impl_.left_most());
     118    }
     119
     120
     121    /**
    111122       \return iterator pointing to the first element
    112123     */
    113     iterator begin(void)
    114     {
    115       return iterator(impl_.left_most());
     124    const_iterator begin(void) const
     125    {
     126      return cbegin();
    116127    }
    117128
     
    120131       \return iterator pointing to the first element
    121132     */
    122     const_iterator begin(void) const
    123     {
    124       return cbegin();
    125     }
    126 
    127 
    128     /**
    129        \return iterator pointing to the first element
    130      */
    131133    const_iterator cbegin(void) const
    132134    {
     
    163165
    164166    /**
    165        \return reverse iterator pointing to first element
     167       \return reverse iterator pointing to first element, i.e., the
     168       node with the largest value.
    166169     */
    167170    reverse_iterator rbegin(void)
     
    247250
    248251    /**
    249        Remove element pointed to by \c position.
     252       Remove node pointed to by \c position.
    250253
    251254       \return An iterator pointing to the element that follows the
     
    298301    /**
    299302       \brief insert with hint
     303
     304       If \c hint will follow the inserted element, the insertion is done
     305       in constant time. Otherwise, the usual insert function is
     306       called which takes logN.
    300307     */
    301308    iterator insert(const_iterator hint, const T& element)
    302309    {
    303       // FIXME use the hint
    304       return insert(element);
     310      std::unique_ptr<ranking::NodeValue<T>>
     311        newnode(new ranking::NodeValue<T>(element));
     312      return insert(hint, std::move(newnode));
    305313    }
    306314
     
    311319    iterator insert(const_iterator hint,  T&& element)
    312320    {
    313       // FIXME use the hint
    314       return insert(std::move(element));
     321      std::unique_ptr<ranking::NodeValue<T>>
     322        newnode(new ranking::NodeValue<T>(std::move(element)));
     323      return insert(hint, std::move(newnode));
    315324    }
    316325
     
    370379    Compare compare_;
    371380    ranking::Impl impl_;
     381
     382    iterator
     383    insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
     384                         ranking::NodeBase& parent, bool left)
     385    {
     386      iterator result(element.get());
     387      impl_.insert_and_rebalance(std::move(element), parent, left);
     388      YAT_ASSERT(validate());
     389      return result;
     390    }
     391
     392
    372393
    373394    void print(const ranking::NodeBase* p, std::ostream& os) const
     
    481502    {
    482503      while (x) {
    483         if (x->right_ && x->right_ !=  &impl_.head_)
     504        if (x->right_)
    484505          erase(right(x));
    485506        ranking::NodeValue<T>* tmp = left(x);
     
    496517    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
    497518    {
    498       iterator result(element.get());
    499519
    500520      if (empty()) {
     
    511531
    512532        YAT_ASSERT(validate());
    513         return result;
    514       }
    515 
    516       ranking::NodeBase* x = impl_.root_node();
     533        return iterator(root_node());
     534      }
     535
     536      return insert(impl_.root_node(), std::move(element));
     537    }
     538
     539
     540    // Insert \a element into the subtree in which x is the root.
     541    iterator insert(ranking::NodeBase* x,
     542                    std::unique_ptr<ranking::NodeValue<T>>&& element)
     543    {
    517544      YAT_ASSERT(x);
    518545      YAT_ASSERT(!x->is_head_node());
     
    522549        if (compare_(element->value(), value(x))) {
    523550          x = x->left_;
    524           if (x == nullptr) {
    525             impl_.insert_and_rebalance(std::move(element), *parent,
    526                                        parent->left_);
    527             if (impl_.left_most() == parent)
    528               impl_.left_most() = parent->left_;
    529             YAT_ASSERT(validate());
    530             return result;
    531           }
     551          if (x == nullptr)
     552            return insert_and_rebalance(std::move(element), *parent, true);
    532553        }
    533554        else {
    534555          x = x->right_;
    535           if (x == nullptr) {
    536             impl_.insert_and_rebalance(std::move(element), *parent,
    537                                        parent->right_);
    538             YAT_ASSERT(validate());
    539             return result;
    540           }
     556          if (x == nullptr)
     557            return insert_and_rebalance(std::move(element), *parent, false);
    541558        }
    542559      }
    543560      YAT_ASSERT(0 && "we can't reach here");
    544       return result;
     561      return iterator(element.get());
     562    }
     563
     564
     565    iterator insert(const_iterator hint,
     566                    std::unique_ptr<ranking::NodeValue<T>>&& element)
     567    {
     568      // special case when hint == end()
     569      if (hint.node_ == head_node()) {
     570        YAT_ASSERT(hint == cend());
     571        if (empty() || compare_(element->value(), value(impl_.right_most())))
     572          return insert(std::move(element));
     573        return insert_and_rebalance(std::move(element), *impl_.right_most(),
     574                                    false);
     575      }
     576
     577      YAT_ASSERT(hint != end());
     578
     579      // value <= hint i.e. !(hint<value)
     580      if (!compare_(*hint, element->value())) {
     581        // if hint == begin
     582        if (hint.node_ == impl_.left_most()) {
     583          YAT_ASSERT(hint == cbegin());
     584          return insert_and_rebalance(std::move(element),
     585                                      *impl_.left_most(),
     586                                      true);
     587        }
     588
     589        // prev <= value <= hint insert
     590        YAT_ASSERT(hint != cbegin());
     591        auto before = std::prev(hint);
     592        if (!compare_(element->value(), *before)) {
     593          return insert(const_cast<ranking::NodeBase*>(hint.node_),
     594                        std::move(element));
     595        }
     596        else {
     597          return insert(std::move(element));
     598        }
     599      }
     600      // else value > hint
     601      else {
     602        YAT_ASSERT(compare_(*hint, element->value()));
     603        // hint == rightmost
     604        if (hint.node_ == impl_.right_most()) {
     605          return insert_and_rebalance(std::move(element),
     606                                      *impl_.right_most(),
     607                                      false);
     608        }
     609        auto after = std::next(hint);
     610        YAT_ASSERT(after != cend());
     611        // hint < value <= after
     612        if (!compare_(*after, element->value())) {
     613          return insert(const_cast<ranking::NodeBase*>(after.node_),
     614                        std::move(element));
     615        }
     616      }
     617
     618      return insert(std::move(element));
    545619    }
    546620
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4075 r4077  
    189189
    190190  void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
    191                                   NodeBase& parent, NodeBase*& child)
    192   {
    193     assert(child == nullptr);
    194     child = element.release();
     191                                  NodeBase& parent, bool left)
     192  {
     193    NodeBase* child = nullptr;
     194    if (left) {
     195      parent.left_ = element.release();
     196      child = parent.left_;
     197      if (&parent == left_most())
     198        left_most() = child;
     199    }
     200    else {
     201      parent.right_ = element.release();
     202      child = parent.right_;
     203    }
     204
    195205    child->parent_ = &parent;
    196206    parent.increment_size();
    197207    parent.update_height_recursively();
    198 
    199208    insert_rebalance(&parent, child);
    200209  }
     
    458467
    459468
     469  NodeBase* Impl::right_most(void)
     470  {
     471    // FIXME this scaled logN, make it constant time
     472    return root_node()->right_most();
     473  }
     474
     475
     476  const NodeBase* Impl::right_most(void) const
     477  {
     478    // FIXME this scaled logN, make it constant time
     479    return root_node()->right_most();
     480  }
     481
     482
    460483  NodeBase*& Impl::root_node(void)
    461484  {
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4075 r4077  
    6262      NodeBase*& left_most(void);
    6363      const NodeBase* left_most(void) const;
     64      NodeBase* right_most(void);
     65      const NodeBase* right_most(void) const;
    6466
    6567      /*
     
    7072      */
    7173      void insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
    72                                 NodeBase& parent, NodeBase*& child);
     74                                NodeBase& parent, bool left);
    7375
    7476      /*
Note: See TracChangeset for help on using the changeset viewer.