Changeset 4070


Ignore:
Timestamp:
Aug 9, 2021, 8:32:59 AM (4 months ago)
Author:
Peter
Message:

refs #710; add erase functions

Location:
branches/kendall-score
Files:
6 edited

Legend:

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

    r4069 r4070  
    226226
    227227
     228void test_erase(test::Suite& suite)
     229{
     230  suite.out() << YAT_TEST_PROLOGUE;
     231
     232  utility::Ranking<double> ranking;
     233  ranking.insert(1);
     234  ranking.insert(2);
     235  ranking.insert(3);
     236  auto it = ranking.find(2);
     237  suite.out() << "test erase(iterator)\n";
     238  ranking.erase(it);
     239  int n = ranking.size();
     240  if (n != 2) {
     241    suite.add(false);
     242    suite.err() << "error: size() = " << n << "; expected 2\n";
     243  }
     244  n = std::distance(ranking.begin(), ranking.end());
     245  if (n != 2) {
     246    suite.add(false);
     247    suite.err() << "error: distance = " << n << "; expected 2\n";
     248  }
     249
     250  suite.out() << "test erase(value)\n";
     251  ranking.insert(2);
     252  ranking.erase(2);
     253  n = ranking.size();
     254  if (n != 2) {
     255    suite.add(false);
     256    suite.err() << "error: size() = " << n << "; expected 2\n";
     257  }
     258  n = std::distance(ranking.begin(), ranking.end());
     259  if (n != 2) {
     260    suite.add(false);
     261    suite.err() << "error: distance = " << n << "; expected 2\n";
     262  }
     263
     264  suite.out() << "test erase(iterator, iterator)\n";
     265  ranking.insert(2);
     266  ranking.insert(4);
     267  ranking.insert(0);
     268  auto lower = ranking.lower_bound(1);
     269  auto upper = ranking.find(3);
     270  // erase { 1, 2}
     271  ranking.erase(lower, upper);
     272  n = ranking.size();
     273  if (n != 3) {
     274    suite.add(false);
     275    suite.err() << "error: size() = " << n << "; expected 3\n";
     276  }
     277  n = std::distance(ranking.begin(), ranking.end());
     278  if (n != 3) {
     279    suite.add(false);
     280    suite.err() << "error: distance = " << n << "; expected 3\n";
     281  }
     282}
     283
     284
    228285int main(int argc, char* argv[])
    229286{
     
    233290    test2(suite);
    234291    test_copy(suite);
     292    test_erase(suite);
    235293  }
    236294  catch (std::exception& e) {
  • branches/kendall-score/yat/utility/Ranking.h

    r4069 r4070  
    4242     Class is a binary tree with the special extension that it allow
    4343     fast access to the rank of an element in the tree.
     44
     45     \since New in yat 0.19
    4446   */
    4547  template<typename T, class Compare = std::less<T> >
     
    206208
    207209    /**
     210       Remove all nodes
     211     */
     212    void clear(void)
     213    {
     214      if (size()) {
     215        YAT_ASSERT(first_node() != &impl_.head_);
     216        erase(first_node());
     217      }
     218      impl_.reset();
     219    }
     220
     221
     222    /**
    208223       access comparison function which is used to sort elements
    209224     */
     
    222237    }
    223238
     239
     240    /**
     241       Remove element pointed to by \c position.
     242
     243       \return An iterator pointing to the element that follows the
     244       last element removed.
     245     */
     246    iterator erase(const_iterator position);
     247
     248    /**
     249       Erase all elements that are equivalent with \c value
     250       \return number of elements removed
     251     */
     252    size_type erase(const T& value);
     253
     254    /**
     255       Remove elements in range [first, last).
     256
     257       \return An iterator pointing to the element that follows the
     258       last element removed.
     259     */
     260    iterator erase(const_iterator first, const_iterator last);
    224261
    225262    /**
     
    326363    ranking::Impl impl_;
    327364
    328     void clear(void)
    329     {
    330       if (size()) {
    331         YAT_ASSERT(first_node() != &impl_.head_);
    332         erase(first_node());
    333       }
    334       impl_.reset();
     365    void print(const ranking::NodeBase* p) const
     366    {
     367      if (p) {
     368        if (p->is_head_node()==false) {
     369          print(p->right_);
     370        }
     371        std::cerr << std::string(p->generation()*4, ' ');
     372        if (!p->is_head_node())
     373          std::cerr << static_cast<const ranking::NodeValue<T>*>(p)->value();
     374        else
     375          std::cerr << "H";
     376        std::cerr << ":   "
     377                  << p->parent_ << " "
     378                  << p << " "
     379                  << p->left_ << " "
     380                  << p->right_ << "\n";
     381        if (p->is_head_node()==false) {
     382          print(p->left_);
     383        }
     384        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
     385          std::cerr << "print error: " << p << "\n";
     386          exit(1);
     387        }
     388      }
    335389    }
    336390
     
    353407    copy(const ranking::NodeValue<T>* root, ranking::NodeBase* h) const;
    354408
     409    /**
     410       Remove node position is pointing to
     411     */
     412    void erase_node(const_iterator position);
    355413
    356414    // return the root node
     
    619677  };
    620678
     679  // avoid doxygen reading code below as it has problems to to match
     680  // declarations and implementations unless matching perfectly.
     681
     682  /// \cond IGNORE_DOXYGEN
    621683
    622684  // implementations
    623   template<typename T, typename Compare>
    624   Ranking<T,Compare>::Ranking(const Ranking& other)
     685  template<typename T, typename C>
     686  Ranking<T,C>::Ranking(const Ranking& other)
    625687    : compare_(other.compare())
    626688  {
     
    631693
    632694
    633   template<typename T, typename Compare>
    634   Ranking<T,Compare>::Ranking(Ranking&& other)
     695  template<typename T, typename C>
     696  Ranking<T,C>::Ranking(Ranking&& other)
    635697    : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
    636698  {
     
    639701
    640702
    641   template<typename T, typename Compare>
    642   Ranking<T, Compare>&
    643   Ranking<T, Compare>::operator=(const Ranking& other)
     703  template<typename T, typename C>
     704  Ranking<T, C>& Ranking<T, C>::operator=(const Ranking& other)
    644705  {
    645706    if (this != &other) {
     
    651712
    652713
    653   template<typename T, typename Compare>
    654   Ranking<T, Compare>&
    655   Ranking<T, Compare>::operator=(Ranking&& other)
     714  template<typename T, typename C>
     715  Ranking<T, C>& Ranking<T, C>::operator=(Ranking&& other)
    656716  {
    657717    clear();
     
    662722
    663723
    664   template<typename T, typename Compare>
    665   ranking::NodeValue<T>* Ranking<T,Compare>::copy(const Ranking& other)
     724  template<typename T, typename C>
     725  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
    666726  {
    667727    YAT_ASSERT(validate());
     
    679739
    680740
    681   template<typename T, typename Compare>
    682   ranking::NodeValue<T>*
    683   Ranking<T,Compare>::copy(const ranking::NodeValue<T>* x,
    684                            ranking::NodeBase* parent) const
     741  template<typename T, typename C>
     742  ranking::NodeValue<T>* Ranking<T,C>::copy(const ranking::NodeValue<T>* x,
     743                                            ranking::NodeBase* parent) const
    685744  {
    686745    YAT_ASSERT(x);
     
    718777
    719778
    720   template<typename T, typename Compare>
     779  template<typename T, typename C>
    721780  ranking::NodeValue<T>*
    722   Ranking<T,Compare>::clone_node(const ranking::NodeValue<T>* x) const
     781  Ranking<T,C>::clone_node(const ranking::NodeValue<T>* x) const
    723782  {
    724783    YAT_ASSERT(x);
     
    730789  }
    731790
     791
     792  template<typename T, typename C>
     793  void Ranking<T, C>::erase_node(typename Ranking<T, C>::const_iterator p)
     794  {
     795    YAT_ASSERT(p != end());
     796    const ranking::NodeBase* node = p.node_;
     797    YAT_ASSERT(node);
     798
     799    // two children
     800    if (node->left_ && node->right_) {
     801      ranking::NodeBase* leftmost = node->right_->left_most();
     802      YAT_ASSERT(leftmost->left_ == nullptr);
     803      if (leftmost->parent_ != node)
     804        impl_.relink(leftmost, leftmost->right_);
     805      impl_.relink(node, leftmost);
     806    }
     807    else {
     808      // single child node is simple, the child takes the node's place
     809      impl_.relink(node, node->left_ ? node->left_ : node->right_);
     810    }
     811    // FIXME we need to delete the node, but be careful to not delete
     812    // any of ots children; perhaps const_cast first?
     813
     814    --impl_.node_count_;
     815    YAT_ASSERT(validate());
     816  }
     817
     818
     819  template<typename T, typename C>
     820  typename Ranking<T, C>::iterator
     821  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator p)
     822  {
     823    YAT_ASSERT(p != end());
     824    const_iterator res = p;
     825    ++res;
     826    erase_node(p);
     827    // iterator and const_iterator are same at the moment
     828    return res;
     829  }
     830
     831
     832  template<typename T, typename C>
     833  typename Ranking<T, C>::size_type Ranking<T, C>::erase(const T& value)
     834  {
     835    auto it = lower_bound(value);
     836    typename Ranking<T, C>::size_type n = 0;
     837    while (it!=end() && !compare_(value, *it)) {
     838      erase_node(it++);
     839      ++n;
     840    }
     841    return n;
     842  }
     843
     844
     845  template<typename T, typename C>
     846  typename Ranking<T, C>::iterator
     847  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator first,
     848                       typename Ranking<T, C>::const_iterator last)
     849  {
     850    if (first == cbegin() && last == cend())
     851      clear();
     852    else
     853      while (first != last) {
     854        erase_node(first++);
     855      }
     856    return last;
     857  }
     858
     859
     860  template<typename T, typename C>
     861  typename Ranking<T, C>::const_iterator Ranking<T, C>::find(const T& x) const
     862  {
     863    auto it = lower_bound(x);
     864    if (it != cend() && compare_(x, *it))
     865      it = cend();
     866    return it;
     867  }
     868
     869  /// \endcond
     870
    732871}}} // of namespace utility, yat, and theplu
    733872#endif
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4069 r4070  
    6969
    7070
     71  void Impl::relink(const NodeBase* node, NodeBase* child)
     72  {
     73    assert(node->parent_);
     74    assert(node != &head_);
     75    assert(child != &head_);
     76
     77    // make child the child of node's parent
     78    if (node->is_left_node())
     79      node->parent_->left_ = child;
     80    else if (node->is_right_node())
     81      node->parent_->right_ = child;
     82
     83    // make node's parent the parent of child
     84    if (child)
     85      child->parent_ = node->parent_;
     86
     87    // inherit the kids
     88    if (child) {
     89      if (node->left_ && node->left_!=child) {
     90        assert(!child->left_);
     91        child->left_ = node->left_;
     92      }
     93      if (node->right_ && node->right_!=child) {
     94        assert(!child->right_);
     95        child->right_ = node->right_;
     96      }
     97    }
     98
     99    // update pointer to left_most node
     100    if (head_.left_ == node) {
     101      head_.left_ = child ? child : node->parent_;
     102    }
     103    assert(child==nullptr || child->is_left_node() || child->is_right_node());
     104  }
     105
     106
    71107  void Impl::reset(void)
    72108  {
     
    92128      assert(head_.left_);
    93129      if (head_.parent_->right_ != &head_) {
    94         std::cerr << "head.parent->right != head\n";
    95130        return false;
    96131      }
     
    98133
    99134    if (head_.parent_) {
     135      if (head_.parent_->left_most() != head_.left_) {
     136        std::cerr << "head_.left incorrect\n";
     137        return false;
     138      }
    100139      if (!head_.parent_->recursive_validate())
    101140        return false;
     
    103142    else if (!head_.validate())
    104143      return false;
     144
    105145    return true;
    106146  }
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4069 r4070  
    4646      Impl& operator=(const Impl& rhs) = delete;
    4747      Impl& operator=(Impl&& rhs);
     48
    4849      // Head is the only node with no value. Its parent is the root
    4950      // node and the rest of the tree is in the left branch from the
     
    5556      bool validate(void) const;
    5657      void reset(void);
     58      /*
     59        \brief replace node with child
     60
     61       Function assumes that child can replace node without collision
     62       or destrying the order in the tree, which means
     63       if there is a node->left its value is <= child->value
     64       if there is a node->right its value is <= child->value
     65       if there is a node->left (ecl child) there is no child->left
     66       if there is a node->right (excl child) there is no child->right
     67      */
     68      void relink(const NodeBase* node, NodeBase* child);
    5769    private:
    5870      void move_data(Impl&&);
  • branches/kendall-score/yat/utility/ranking/Iterator.h

    r4069 r4070  
    5252    public:
    5353      explicit Iterator(const NodeBase* node = nullptr);
     54      const NodeBase* node_;
    5455    private:
    55       const NodeBase* node_;
    5656      friend class boost::iterator_core_access;
    5757      const T& dereference(void) const;
     
    7373    {
    7474      YAT_ASSERT(node_);
     75      YAT_ASSERT(node_->is_head_node()==false);
    7576      // All nodes are NodeValue except head which is pointee of end
    7677      // iterator and not dereferencable
     
    9596        return;
    9697      }
     98      // since node_ is not root, it must have a parent and be either
     99      // left or right.
     100      YAT_ASSERT(node_->parent_);
     101      YAT_ASSERT(node_->is_left_node() || node_->is_right_node());
    97102
    98103      // If we have a right branch, go to the leftmost leaf in it.
     
    106111      const NodeBase* child = node_;
    107112      YAT_ASSERT(child->parent_);
     113      YAT_ASSERT(child->is_left_node() || child->is_right_node());
    108114      while (child->is_right_node()) {
    109115        YAT_ASSERT(!child->is_left_node());
  • branches/kendall-score/yat/utility/ranking/NodeBase.h

    r4067 r4070  
    4343      NodeBase* right_;
    4444
     45      // return 0 for root, 1 for its children, etc
     46      int generation(void) const;
     47
    4548      // return true if head node
    4649      bool is_head_node(void) const;
Note: See TracChangeset for help on using the changeset viewer.