Changeset 4075


Ignore:
Timestamp:
Aug 20, 2021, 8:54:37 AM (3 months ago)
Author:
Peter
Message:

fix some docs and get rid of function not used. refs #710

Location:
branches/kendall-score/yat/utility/ranking
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4072 r4075  
    7070  void Impl::move_data(Impl&& from)
    7171  {
    72     // FIXME we need to clean up before the move
     72    assert(empty());
    7373
    7474    head_.parent_ = from.head_.parent_;
     
    147147  void Impl::reset(void)
    148148  {
    149     // FIXME do we need to destruct parent and rest of tree?
    150149    head_.parent_ = nullptr;
    151150    head_.left_ = nullptr;
     
    355354
    356355
    357   NodeBase* Impl::rebalance_old_root(NodeBase* node)
    358   {
    359     if (node->balance() > 1) {
    360       // height(y) > height(T4) + 1
    361       // i.e. height(x) > height(T4)
    362 
    363       // left left case
    364       if (node->left_->balance() >= 0) {
    365         assert(height(node->left_) > height(node->right_) + 1);
    366         // height(x) > height(T4)
    367         assert(height(node->left_->left_) > height(node->right_));
    368         // y is balanced, so:
    369         //  height(T3) <= height(x) <= height(T3)+1
    370         assert(height(node->left_->left_) >= height(node->left_->right_));
    371         assert(height(node->left_->left_) <= height(node->left_->right_)+1);
    372         // x is balanced, so |height(T1)-height(T2)| <= 1
    373 
    374         node = right_rotate(node);
    375       }
    376       else { // left right case
    377         left_rotate(node->left_);
    378         node = right_rotate(node);
    379       }
    380       return rebalance_old_root(node);
    381     }
    382 
    383     if (node->balance() >= -1)
    384       return node;
    385 
    386     assert(0);
    387     return node;
    388   }
    389 
    390 
    391356  NodeBase* Impl::right_rotate(NodeBase* y)
    392357  {
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4072 r4075  
    4848      Impl& operator=(Impl&& rhs);
    4949
    50       // FIXME
    51       // Head is the only node with no value. Its parent is the root
    52       // node and the rest of the tree is in the left branch from the
    53       // root. Also, it holds a link to the leftmost node, which
    54       // corresponds to begin()
     50      // Head is the only node with no parent; it is also the node
     51      // with no value. All other nodes are NodeValue<T> pointers. Its
     52      // left child is the root node and it also holds a short cut to
     53      // the leftmost node to allow constant access and creating of
     54      // the begin() iterator.
    5555      NodeBase head_;
    5656
     
    6262      NodeBase*& left_most(void);
    6363      const NodeBase* left_most(void) const;
    64 
    65 
    66       /*
    67 
    68        */
    69       NodeBase* rebalance_old_root(NodeBase* node);
    7064
    7165      /*
Note: See TracChangeset for help on using the changeset viewer.