Changeset 4071


Ignore:
Timestamp:
Aug 18, 2021, 4:31:29 AM (4 months ago)
Author:
Peter
Message:

Add variables height_ and size_ in NodeBase?, which describes the longest distance to its leaves and the size of the subtree in which it is the root, respectively. Use these variables to calculate the ranking, which means the ranking now scales like the height rather than the number of nodes. refs #710

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

Legend:

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

    r4070 r4071  
    234234    bool empty(void) const
    235235    {
    236       return size()==0;
     236      return root_node() == nullptr;
    237237    }
    238238
     
    346346    size_t ranking(const_iterator it) const
    347347    {
    348       // FIXME
    349       return std::distance(cbegin(), it);
     348      return impl_.ranking(it.node_);
    350349    }
    351350
     
    356355    size_t size(void) const
    357356    {
    358       return impl_.node_count_;
     357      return root_node() ? root_node()->size_ : 0;
    359358    }
    360359
     
    363362    ranking::Impl impl_;
    364363
    365     void print(const ranking::NodeBase* p) const
     364    void print(const ranking::NodeBase* p, std::ostream& os) const
    366365    {
    367366      if (p) {
    368367        if (p->is_head_node()==false) {
    369           print(p->right_);
    370         }
    371         std::cerr << std::string(p->generation()*4, ' ');
     368          print(p->right_, os);
     369        }
     370        os << std::string(p->generation()*4, ' ');
    372371        if (!p->is_head_node())
    373           std::cerr << static_cast<const ranking::NodeValue<T>*>(p)->value();
     372          os << value(p);
    374373        else
    375           std::cerr << "H";
    376         std::cerr << ":   "
     374          os << "H";
     375        os << ":   "
    377376                  << p->parent_ << " "
    378377                  << p << " "
     
    380379                  << p->right_ << "\n";
    381380        if (p->is_head_node()==false) {
    382           print(p->left_);
     381          print(p->left_, os);
    383382        }
    384383        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
    385           std::cerr << "print error: " << p << "\n";
     384          os << "print error: " << p << "\n";
    386385          exit(1);
    387386        }
     
    495494        root_node() = element.release();
    496495        root_node()->right_ = &impl_.head_;
     496        root_node()->height_ = 1;
     497        root_node()->size_ = 1;
    497498        impl_.head_.left_ = root_node();
    498         ++impl_.node_count_;
     499
    499500        YAT_ASSERT(root_node()->validate());
    500501        YAT_ASSERT(impl_.head_.validate());
     
    508509
    509510      // element right of root
    510       if (!compare_(element->value(),
    511                     static_cast<ranking::NodeValue<T>*>(x)->value())) {
     511      if (!compare_(element->value(), value(x))) {
    512512        // make new root parent of head
    513513        impl_.head_.parent_ = element.release();
     
    518518        impl_.head_.parent_->left_ = x;
    519519        x->parent_ = impl_.head_.parent_;
    520 
    521         ++impl_.node_count_;
     520        YAT_ASSERT(x->size_ > 0);
     521
     522        impl_.head_.parent_->size_ = x->size_ + 1;
     523        impl_.head_.parent_->height_ = x->height_ + 1;
     524
    522525        YAT_ASSERT(x->validate());
    523526        YAT_ASSERT(impl_.head_.parent_);
     
    533536      while (true) {
    534537        parent = x;
    535         if (compare_(element->value(),
    536                      static_cast<ranking::NodeValue<T>*>(x)->value())) {
     538        if (compare_(element->value(), value(x))) {
    537539          x = x->left_;
    538540          if (x == nullptr) {
    539541            element->parent_ = parent;
    540542            parent->left_ = element.release();
     543            parent->increment_size();
     544            parent->update_height();
    541545            if (impl_.head_.left_ == parent)
    542546              impl_.head_.left_ = parent->left_;
    543             ++impl_.node_count_;
    544547            YAT_ASSERT(validate());
    545548            return result;
     
    551554            element->parent_ = parent;
    552555            parent->right_ = element.release();
    553             ++impl_.node_count_;
     556            parent->increment_size();
     557            parent->update_height();
    554558            YAT_ASSERT(validate());
    555559            return result;
     
    667671
    668672
     673    const T& value(const ranking::NodeBase* p) const
     674    {
     675      YAT_ASSERT(p);
     676      YAT_ASSERT(!p->is_head_node());
     677      return static_cast<const ranking::NodeValue<T>*>(p)->value();
     678    }
     679
     680
    669681    bool validate(void) const
    670682    {
    671683#ifdef YAT_DEBUG_RANKING
    672       return impl_.validate();
     684      if (!impl_.validate())
     685        return false;
     686      bool ok = true;
     687      size_t rank = 0;
     688      for (auto it = cbegin(); it!=cend(); ++it) {
     689        size_t r = ranking(it);
     690        if (r != rank) {
     691          std::cerr << "ranking: " << r << "; expected: " << rank << "\n";
     692          std::cerr << "size: " << it.node_->size_ << "\n";
     693          std::cerr << it.node_->parent_ << " "
     694                    << it.node_->is_left_node() << " "
     695                    << it.node_->is_right_node() << "\n---\n";
     696          ok = false;
     697        }
     698        ++rank;
     699      }
     700      return ok;
    673701#else
    674702      return true;
     
    733761    last_node()->left_ = root->left_most();
    734762    last_node()->parent_ = root;
    735     impl_.node_count_ = other.size();
    736763    YAT_ASSERT(validate());
    737764    return root;
     
    745772    YAT_ASSERT(x);
    746773    ranking::NodeValue<T>* root = clone_node(x);
     774    root->height_ = x->height_;
     775    root->size_ = x->size_;
    747776    YAT_ASSERT(root);
    748777    root->parent_ = parent;
     
    758787      while (x) {
    759788        ranking::NodeValue<T>* y = clone_node(x);
     789        y->height_ = x->height_;
     790        y->size_ = x->size_;
    760791        parent->left_ = y;
    761792        y->parent_ = parent;
     
    795826    YAT_ASSERT(p != end());
    796827    const ranking::NodeBase* node = p.node_;
     828    //    std::cerr << "erase_node: " << node << "\n";
    797829    YAT_ASSERT(node);
    798830
    799831    // two children
    800832    if (node->left_ && node->right_) {
     833      // When node has two branches, we take the most leftmost node in
     834      // the right branch and place in nodes place.
    801835      ranking::NodeBase* leftmost = node->right_->left_most();
    802836      YAT_ASSERT(leftmost->left_ == nullptr);
    803       if (leftmost->parent_ != node)
     837
     838      // If the leftmost node has a kid, we need to relink the kid
     839      // with its grand parent
     840      if (leftmost->parent_ != node) {
    804841        impl_.relink(leftmost, leftmost->right_);
     842      }
    805843      impl_.relink(node, leftmost);
     844      YAT_ASSERT(leftmost->left_ == node->left_);
     845      YAT_ASSERT(!leftmost->left_ || leftmost->left_->parent_==leftmost);
     846      leftmost->update_height();
     847      leftmost->size_ =
     848        1 + ranking::size(leftmost->left_) + ranking::size(leftmost->right_);
     849      leftmost->parent_->decrement_size();
     850      YAT_ASSERT(validate());
    806851    }
    807852    else {
    808853      // single child node is simple, the child takes the node's place
    809854      impl_.relink(node, node->left_ ? node->left_ : node->right_);
     855      node->parent_->decrement_size();
     856      node->parent_->update_height();
     857      YAT_ASSERT(validate());
    810858    }
    811859    // FIXME we need to delete the node, but be careful to not delete
    812860    // any of ots children; perhaps const_cast first?
    813861
    814     --impl_.node_count_;
    815     YAT_ASSERT(validate());
    816862  }
    817863
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4070 r4071  
    6363    assert(head_.right_ == &head_);
    6464    head_.parent_->right_ = &head_;
    65     node_count_ = from.node_count_;
     65    head_.height_ = from.head_.height_;
     66    head_.size_ = from.head_.size_;
    6667    from.reset();
    6768    assert(validate());
     
    9091        assert(!child->left_);
    9192        child->left_ = node->left_;
     93        if (node->left_)
     94          node->left_->parent_ = child;
    9295      }
    9396      if (node->right_ && node->right_!=child) {
    9497        assert(!child->right_);
    9598        child->right_ = node->right_;
     99        if (node->right_)
     100          node->right_->parent_ = child;
    96101      }
    97102    }
     
    105110
    106111
     112  size_t Impl::ranking(const NodeBase* node) const
     113  {
     114    if (node->is_head_node())
     115      return size(node->parent_);
     116
     117    // root node
     118    if (node->parent_ == nullptr)
     119      return size(node->left_);
     120
     121    // The rank of the parent is the sum of the rank of the
     122    // left->child, the child itself, and the size of the child's
     123    // right branch.
     124    if (node->is_left_node())
     125      return ranking(node->parent_) - (1 + size(node->right_));
     126
     127    // right node
     128    return ranking(node->parent_) + 1 + size(node->left_);
     129  }
     130
     131
    107132  void Impl::reset(void)
    108133  {
     
    111136    head_.left_ = &head_;
    112137    head_.right_ = &head_;
    113     node_count_ = 0;
     138    // we don't count the head node
     139    head_.height_ = 0;
     140    head_.size_ = 0;
    114141    assert(validate());
    115142  }
     
    118145  bool Impl::validate(void) const
    119146  {
    120     if (node_count_ == 0) {
    121       assert(head_.parent_ == nullptr);
     147    if (head_.parent_ == nullptr) {
    122148      assert(head_.left_ == &head_);
    123149      assert(head_.right_ == &head_);
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4070 r4071  
    5252      // corresponds to begin()
    5353      NodeBase head_;
    54       size_t node_count_;
    5554      // typically only called with assert, YAT_ASSERT or similar
    5655      bool validate(void) const;
     56      // return number of nodes left of node, i.e., number of nodes
     57      // with value less than node->value.
     58      size_t ranking(const NodeBase* node) const;
    5759      void reset(void);
    5860      /*
  • branches/kendall-score/yat/utility/ranking/NodeBase.h

    r4070 r4071  
    2525// This is a private file used by yat/utility/Ranking.h
    2626
     27#include <cstddef>
     28
    2729namespace theplu {
    2830namespace yat {
     
    4244      NodeBase* left_;
    4345      NodeBase* right_;
     46      unsigned int height_; // max distance to leaf (plus 1)
     47      // number of total offsprings including myself
     48      size_t size_;
    4449
    4550      // return 0 for root, 1 for its children, etc
    4651      int generation(void) const;
     52
     53      // increase size of node and parent node, recursively.
     54      void increment_size(void);
     55      // decrease size of node and parent node, recursively.
     56      void decrement_size(void);
     57
     58      void update_height(void);
    4759
    4860      // return true if head node
     
    6678      bool recursive_validate(void) const;
    6779    };
     80
     81    size_t height(const NodeBase* node);
     82    size_t size(const NodeBase* node);
     83
    6884  } // end of namespace ranking
    6985
Note: See TracChangeset for help on using the changeset viewer.