Changeset 4079


Ignore:
Timestamp:
Aug 26, 2021, 10:38:04 AM (3 months ago)
Author:
Peter
Message:

store the right_most node, so it can be accessed in constant time (rather than logarithmic); refs #710

Location:
branches/kendall-score/yat/utility
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/kendall-score/yat/utility/Ranking.h

    r4077 r4079  
    523523        impl_.head_.left_ = impl_.root_node();
    524524        impl_.head_.right_ = impl_.root_node();
     525        impl_.right_most() = impl_.root_node();
    525526        impl_.head_.update_height();
    526527        impl_.head_.update_size();
     
    806807    head_node()->update_height();
    807808    head_node()->update_size();
     809    if (root_node())
     810      impl_.right_most() = root_node()->right_most();
     811    else
     812      impl_.right_most() = head_node();
    808813    YAT_ASSERT(validate());
    809814    return root;
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4077 r4079  
    7777      head_.left_->parent_ = &head_;
    7878      head_.right_ = from.head_.right_;
    79     }
    80     else
     79      right_most_ = root_node()->right_most();
     80    }
     81    else {
    8182      head_.right_ = &head_;
     83      right_most() = &head_;
     84    }
    8285    head_.height_ = from.head_.height_;
    8386    head_.size_ = from.head_.size_;
     
    120123
    121124    // update pointer to left_most node
    122     if (head_.left_ == node) {
    123       head_.left_ = child ? child : node->parent_;
    124     }
     125    if (left_most() == node)
     126      left_most() = child ? child : node->parent_;
     127    if (right_most() == node)
     128      right_most() = child ? child : node->parent_;
    125129    assert(child==nullptr || child->is_left_node() || child->is_right_node());
    126130  }
     
    150154    head_.left_ = nullptr;
    151155    head_.right_ = &head_; // most left node
     156    right_most_ = &head_;
    152157    head_.update_height();
    153158    head_.update_size();
     
    201206      parent.right_ = element.release();
    202207      child = parent.right_;
     208      if (&parent == right_most())
     209        right_most() = child;
    203210    }
    204211
     
    426433    }
    427434
     435    if (root_node()) {
     436      if (left_most() != root_node()->left_most()) {
     437        std::cerr << "leftmost incorrect\n";
     438        return false;
     439      }
     440      if (right_most() != root_node()->right_most()) {
     441        std::cerr << "rightmost incorrect\n";
     442        return false;
     443      }
     444    }
     445
    428446
    429447    /*
     
    467485
    468486
    469   NodeBase* Impl::right_most(void)
    470   {
    471     // FIXME this scaled logN, make it constant time
    472     return root_node()->right_most();
     487  NodeBase*& Impl::right_most(void)
     488  {
     489    return right_most_;
    473490  }
    474491
     
    476493  const NodeBase* Impl::right_most(void) const
    477494  {
    478     // FIXME this scaled logN, make it constant time
    479     return root_node()->right_most();
     495    return right_most_;
    480496  }
    481497
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4077 r4079  
    6262      NodeBase*& left_most(void);
    6363      const NodeBase* left_most(void) const;
    64       NodeBase* right_most(void);
     64      NodeBase*& right_most(void);
    6565      const NodeBase* right_most(void) const;
    6666
     
    126126      NodeBase* right_rotate(NodeBase* y);
    127127    private:
     128      NodeBase* right_most_;
    128129      void move_data(Impl&&);
    129130      void erase_rebalance(NodeBase* node);
Note: See TracChangeset for help on using the changeset viewer.