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

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.