source: branches/kendall-score/yat/utility/Ranking.h @ 4079

Last change on this file since 4079 was 4079, checked in by Peter, 5 months ago

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

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 20.4 KB
Line 
1#ifndef theplu_yat_utility_ranking
2#define theplu_yat_utility_ranking
3
4// $Id: Ranking.h 4079 2021-08-26 08:38:04Z peter $
5
6/*
7  Copyright (C) 2021 Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25#include "ranking/Impl.h"
26#include "ranking/Iterator.h"
27#include "ranking/NodeBase.h"
28#include "ranking/NodeValue.h"
29
30#include "yat_assert.h"
31
32#include <cstddef>
33#include <functional>
34#include <iostream>
35#include <iterator>
36#include <memory>
37
38namespace theplu {
39namespace yat {
40namespace utility {
41
42  /**
43     Class is a binary tree with the special extension that it allow
44     fast access to the rank of an element in the tree.
45
46     \since New in yat 0.19
47   */
48  template<typename T, class Compare = std::less<T> >
49  class Ranking
50  {
51  public:
52    /// value type
53    typedef T value_type;
54    /// type used to compare elements
55    typedef Compare key_compare;
56    /// size type
57    typedef size_t size_type;
58    /// iterator
59    typedef ranking::Iterator<T> iterator;
60    /// iterator
61    typedef ranking::Iterator<T> const_iterator;
62    /// reverse iterator
63    typedef std::reverse_iterator<iterator> reverse_iterator;
64    /// reverse iterator
65    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
66
67    /**
68       \brief Default constructor
69     */
70    Ranking(void) = default;
71
72    /**
73       \brief Destructor
74     */
75    ~Ranking(void)
76    {
77      clear();
78    }
79
80    /**
81       Construct empty container with comparison function \c c.
82     */
83    Ranking(const Compare& c)
84      : compare_(c)
85    {
86      YAT_ASSERT(validate());
87    }
88
89
90    /**
91       \brief Copy constructor
92     */
93    Ranking(const Ranking& other);
94
95    /**
96       \brief move constructor
97     */
98    Ranking(Ranking&& other);
99
100    /**
101       \brief assignment operator
102     */
103    Ranking& operator=(const Ranking& other);
104
105    /**
106       \brief move assignment
107     */
108    Ranking& operator=(Ranking&& other);
109
110
111    /**
112       \return iterator pointing to the first element, i.e., the
113       node with the smallest value.
114     */
115    iterator begin(void)
116    {
117      return iterator(impl_.left_most());
118    }
119
120
121    /**
122       \return iterator pointing to the first element
123     */
124    const_iterator begin(void) const
125    {
126      return cbegin();
127    }
128
129
130    /**
131       \return iterator pointing to the first element
132     */
133    const_iterator cbegin(void) const
134    {
135      return const_iterator(impl_.left_most());
136    }
137
138
139    /**
140       \return iterator pointing to one-passed-last element
141     */
142    iterator end(void)
143    {
144      return iterator(&impl_.head_);
145    }
146
147
148    /**
149       \return iterator pointing to one-passed-last element
150     */
151    const_iterator end(void) const
152    {
153      return cend();
154    }
155
156
157    /**
158       \return iterator pointing to one-passed-last element
159     */
160    const_iterator cend(void) const
161    {
162      return const_iterator(&impl_.head_);
163    }
164
165
166    /**
167       \return reverse iterator pointing to first element, i.e., the
168       node with the largest value.
169     */
170    reverse_iterator rbegin(void)
171    {
172      return reverse_iterator(end());
173    }
174
175
176    /**
177       \return reverse iterator pointing to one-passed-last element
178     */
179    reverse_iterator rend(void)
180    {
181      return reverse_iterator(begin());
182    }
183
184
185    /**
186       \return reverse iterator pointing to one-passed-last element
187     */
188    const_reverse_iterator rend(void) const
189    {
190      return crend();
191    }
192
193
194    /**
195       \return reverse iterator pointing to first element
196     */
197    const_reverse_iterator rbegin(void) const
198    {
199      return crbegin();
200    }
201
202
203    /**
204       \return reverse iterator pointing to first element
205     */
206    const_reverse_iterator crbegin(void) const
207    {
208      return const_reverse_iterator(cend());
209    }
210
211    /**
212       \return reverse iterator pointing to the one-passed-last element
213     */
214    const_reverse_iterator crend(void) const
215    {
216      return const_reverse_iterator(cbegin());
217    }
218
219
220    /**
221       Remove all nodes
222     */
223    void clear(void)
224    {
225      if (size()) {
226        YAT_ASSERT(root_node() != head_node());
227        erase(root_node());
228      }
229      impl_.reset();
230    }
231
232
233    /**
234       access comparison function which is used to sort elements
235     */
236    const Compare& compare(void) const
237    {
238      return compare_;
239    }
240
241
242    /**
243       \return true if (and only if) container has zero elements
244     */
245    bool empty(void) const
246    {
247      return impl_.empty();
248    }
249
250
251    /**
252       Remove node pointed to by \c position.
253
254       \return An iterator pointing to the element that follows the
255       last element removed.
256     */
257    iterator erase(const_iterator position);
258
259    /**
260       Erase all elements that are equivalent with \c value
261       \return number of elements removed
262     */
263    size_type erase(const T& value);
264
265    /**
266       Remove elements in range [first, last).
267
268       \return An iterator pointing to the element that follows the
269       last element removed.
270     */
271    iterator erase(const_iterator first, const_iterator last);
272
273    /**
274       Find an element that is equivalent to x
275     */
276    const_iterator find(const T& x) const;
277
278
279    /**
280       \brief insert an element
281     */
282    iterator insert(const T& element)
283    {
284      std::unique_ptr<ranking::NodeValue<T>>
285        newnode(new ranking::NodeValue<T>(element));
286      return insert(std::move(newnode));
287    }
288
289
290    /**
291       \brief insert an element
292     */
293    iterator insert(T&& element)
294    {
295      std::unique_ptr<ranking::NodeValue<T>>
296        newnode(new ranking::NodeValue<T>(std::move(element)));
297      return insert(std::move(newnode));
298    }
299
300
301    /**
302       \brief insert with hint
303
304       If \c hint will follow the inserted element, the insertion is done
305       in constant time. Otherwise, the usual insert function is
306       called which takes logN.
307     */
308    iterator insert(const_iterator hint, const T& element)
309    {
310      std::unique_ptr<ranking::NodeValue<T>>
311        newnode(new ranking::NodeValue<T>(element));
312      return insert(hint, std::move(newnode));
313    }
314
315
316    /**
317       \brief insert with hint
318     */
319    iterator insert(const_iterator hint,  T&& element)
320    {
321      std::unique_ptr<ranking::NodeValue<T>>
322        newnode(new ranking::NodeValue<T>(std::move(element)));
323      return insert(hint, std::move(newnode));
324    }
325
326
327    /**
328       \brief insert range
329     */
330    template<typename InputIterator>
331    void insert(InputIterator first, InputIterator last)
332    {
333      for (; first!=last; ++first)
334        insert(end(), *first);
335    }
336
337
338    /**
339       \return the first element which is equal (or greater) to \c x
340     */
341    const_iterator lower_bound(const T& x) const
342    {
343      if (empty())
344        return cend();
345      return lower_bound(root_node(), head_node(), x);
346    }
347
348
349    /**
350       \return the first element which is greater than \c x
351     */
352    const_iterator upper_bound(const T& x) const
353    {
354      if (empty())
355        return cend();
356      return upper_bound(root_node(), head_node(), x);
357    }
358
359
360    /**
361       \return number of elements smaller than \c it
362     */
363    size_t ranking(const_iterator it) const
364    {
365      YAT_ASSERT(it.node_);
366      return impl_.ranking(it.node_);
367    }
368
369
370    /**
371       \return number of elements in container
372     */
373    size_t size(void) const
374    {
375      return impl_.size();
376    }
377
378  private:
379    Compare compare_;
380    ranking::Impl impl_;
381
382    iterator
383    insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
384                         ranking::NodeBase& parent, bool left)
385    {
386      iterator result(element.get());
387      impl_.insert_and_rebalance(std::move(element), parent, left);
388      YAT_ASSERT(validate());
389      return result;
390    }
391
392
393
394    void print(const ranking::NodeBase* p, std::ostream& os) const
395    {
396      if (p) {
397        if (p->is_head_node()==false) {
398          print(p->right_, os);
399        }
400        os << std::string(p->generation()*4, ' ');
401        if (!p->is_head_node())
402          os << value(p);
403        else
404          os << "H";
405        os << ", H=" << ranking::height(p) << ", S=" << ranking::size(p);
406        os << ":   "
407           << p->parent_ << " "
408           << p << " "
409           << p->left_ << " "
410           << p->right_ << "\n";
411        if (p->is_head_node()==false) {
412          print(p->left_, os);
413        }
414        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
415          os << "print error: " << p << "\n";
416          exit(1);
417        }
418      }
419    }
420
421    // return a copy of x but with children and parent set to nullptr.
422    ranking::NodeValue<T>*
423    clone_node(const ranking::NodeValue<T>* x) const;
424
425    /**
426       copy data in other.Impl_ into impl_
427
428       Basically copy constructor of Impl but nodes (except for head
429       node) are copied as NodeValue<T> and Impl is not aware of T.
430     */
431    ranking::NodeValue<T>* copy(const Ranking& other);
432
433    /**
434       Create a copy of root and return it
435     */
436    ranking::NodeValue<T>* copy(const ranking::NodeValue<T>* root) const;
437
438    /**
439       Remove node position is pointing to
440     */
441    void erase_node(const_iterator position);
442
443    // return the root node
444    const ranking::NodeValue<T>* root_node(void) const
445    {
446      return static_cast<const ranking::NodeValue<T>*>(impl_.root_node());
447    }
448
449
450    ranking::NodeValue<T>* root_node(void)
451    {
452      return static_cast<ranking::NodeValue<T>*>(impl_.root_node());
453    }
454
455
456    const ranking::NodeBase* head_node(void) const
457    {
458      return &impl_.head_;
459    }
460
461
462    ranking::NodeBase* head_node(void)
463    {
464      return &impl_.head_;
465    }
466
467
468    const ranking::NodeValue<T>*
469    left(const ranking::NodeBase* x) const
470    {
471      YAT_ASSERT(x->left_ != &impl_.head_);
472      return static_cast<const ranking::NodeValue<T>*>(x->left_);
473    }
474
475
476    ranking::NodeValue<T>*
477    left(ranking::NodeBase* x) const
478    {
479      YAT_ASSERT(x->left_ != &impl_.head_);
480      return static_cast<ranking::NodeValue<T>*>(x->left_);
481    }
482
483
484    const ranking::NodeValue<T>*
485    right(const ranking::NodeBase* x) const
486    {
487      YAT_ASSERT(x->right_ != &impl_.head_);
488      return static_cast<const ranking::NodeValue<T>*>(x->right_);
489    }
490
491
492    ranking::NodeValue<T>*
493    right(ranking::NodeBase* x) const
494    {
495      YAT_ASSERT(x->right_ != &impl_.head_);
496      return static_cast<ranking::NodeValue<T>*>(x->right_);
497    }
498
499
500    // delete x and its offsprings
501    void erase(ranking::NodeValue<T>* x) const
502    {
503      while (x) {
504        if (x->right_)
505          erase(right(x));
506        ranking::NodeValue<T>* tmp = left(x);
507        delete x;
508        x = tmp;
509      }
510    }
511
512
513    /**
514       traverse the tree and find a suitable leaf where we can insert
515       \c element and keep the tree sorted.
516     */
517    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
518    {
519
520      if (empty()) {
521        element->parent_ = &impl_.head_;
522        impl_.root_node() = element.release();
523        impl_.head_.left_ = impl_.root_node();
524        impl_.head_.right_ = impl_.root_node();
525        impl_.right_most() = impl_.root_node();
526        impl_.head_.update_height();
527        impl_.head_.update_size();
528
529        YAT_ASSERT(impl_.root_node()->parent_);
530        YAT_ASSERT(impl_.root_node()->parent_ == &impl_.head_);
531        YAT_ASSERT(impl_.root_node()->is_left_node());
532
533        YAT_ASSERT(validate());
534        return iterator(root_node());
535      }
536
537      return insert(impl_.root_node(), std::move(element));
538    }
539
540
541    // Insert \a element into the subtree in which x is the root.
542    iterator insert(ranking::NodeBase* x,
543                    std::unique_ptr<ranking::NodeValue<T>>&& element)
544    {
545      YAT_ASSERT(x);
546      YAT_ASSERT(!x->is_head_node());
547
548      while (true) {
549        ranking::NodeBase* parent = x;
550        if (compare_(element->value(), value(x))) {
551          x = x->left_;
552          if (x == nullptr)
553            return insert_and_rebalance(std::move(element), *parent, true);
554        }
555        else {
556          x = x->right_;
557          if (x == nullptr)
558            return insert_and_rebalance(std::move(element), *parent, false);
559        }
560      }
561      YAT_ASSERT(0 && "we can't reach here");
562      return iterator(element.get());
563    }
564
565
566    iterator insert(const_iterator hint,
567                    std::unique_ptr<ranking::NodeValue<T>>&& element)
568    {
569      // special case when hint == end()
570      if (hint.node_ == head_node()) {
571        YAT_ASSERT(hint == cend());
572        if (empty() || compare_(element->value(), value(impl_.right_most())))
573          return insert(std::move(element));
574        return insert_and_rebalance(std::move(element), *impl_.right_most(),
575                                    false);
576      }
577
578      YAT_ASSERT(hint != end());
579
580      // value <= hint i.e. !(hint<value)
581      if (!compare_(*hint, element->value())) {
582        // if hint == begin
583        if (hint.node_ == impl_.left_most()) {
584          YAT_ASSERT(hint == cbegin());
585          return insert_and_rebalance(std::move(element),
586                                      *impl_.left_most(),
587                                      true);
588        }
589
590        // prev <= value <= hint insert
591        YAT_ASSERT(hint != cbegin());
592        auto before = std::prev(hint);
593        if (!compare_(element->value(), *before)) {
594          return insert(const_cast<ranking::NodeBase*>(hint.node_),
595                        std::move(element));
596        }
597        else {
598          return insert(std::move(element));
599        }
600      }
601      // else value > hint
602      else {
603        YAT_ASSERT(compare_(*hint, element->value()));
604        // hint == rightmost
605        if (hint.node_ == impl_.right_most()) {
606          return insert_and_rebalance(std::move(element),
607                                      *impl_.right_most(),
608                                      false);
609        }
610        auto after = std::next(hint);
611        YAT_ASSERT(after != cend());
612        // hint < value <= after
613        if (!compare_(*after, element->value())) {
614          return insert(const_cast<ranking::NodeBase*>(after.node_),
615                        std::move(element));
616        }
617      }
618
619      return insert(std::move(element));
620    }
621
622
623    /*
624      Find the first node that is greater or equal to key, i.e., all
625      elements left of returned node are less than key.
626     */
627    const_iterator
628    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
629                const T& key) const
630    {
631      // x is used to traverse the tree
632      // y holds the result
633
634      while (x) {
635        // key is less (or equal) than x, store x as potential result
636        // and search in left branch
637        if (!compare_(x->value(), key)) {
638          y = x;
639          x = left(x);
640        }
641        // key is greater than x, the lower bound is not x; it is
642        // either in the right branch or a previously assigned
643        // ancestor. Do not store x as potential result, but search
644        // branch.
645        else
646          x = right(x);
647      }
648      // x has reached a leaf, and the result should be stored in y
649
650      // returned node is not smaller than key
651      YAT_ASSERT(y==head_node() || !compare_(value(y), key));
652      // all nodes left of returned node are smaller than key
653      YAT_ASSERT(y->left_==nullptr ||
654                 compare_(value(y->left_->right_most()), key));
655      return const_iterator(y);
656    }
657
658
659    const ranking::NodeValue<T>* parent(const ranking::NodeBase* x) const
660    {
661      YAT_ASSERT(x);
662      YAT_ASSERT(x->parent_);
663      YAT_ASSERT(x->parent_ != &impl_.head_);
664      return static_cast<const ranking::NodeValue<T>*>(x->parent_);
665    }
666
667
668    ranking::NodeValue<T>* parent(ranking::NodeBase* x) const
669    {
670      YAT_ASSERT(x);
671      YAT_ASSERT(x->parent_);
672      YAT_ASSERT(x->parent_ != &impl_.head_);
673      return static_cast<ranking::NodeValue<T>*>(x->parent_);
674    }
675
676
677    /*
678      Find the first node that is greater than key, i.e., all
679      elements left of returned node are less or equal to key.
680     */
681    const_iterator
682    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
683                const T& key) const
684    {
685      // x is used to traverse the tree
686      // y holds the result
687
688      while (x) {
689        // key is less than x value, x is a potential upper_bound,
690        // store and search in left
691        if (compare_(key, x->value())) {
692          y = x;
693          x = left(x);
694        }
695        else {
696          // key is greater (or equal) than x, x is not the upper
697          // bound. It is either in the right branch or in a
698          // previously assigned ancestor (current y).
699          x = right(x);
700        }
701      }
702      // x has reached a leaf, and the result should be stored in y
703
704      // key is less than returned node
705      YAT_ASSERT(y==head_node() || compare_(key, value(y)));
706      // all nodes left of returned node are smaller (or equal) than
707      // key, i.e., key is not smaller than any of the nodes to the
708      // left of returned node.
709      YAT_ASSERT(y->left_==nullptr ||
710                 !compare_(key, value(y->left_->right_most())));
711      return const_iterator(y);
712    }
713
714
715    const T& value(const ranking::NodeBase* p) const
716    {
717      YAT_ASSERT(p);
718      YAT_ASSERT(!p->is_head_node());
719      return static_cast<const ranking::NodeValue<T>*>(p)->value();
720    }
721
722
723    bool validate(void) const
724    {
725#ifndef YAT_DEBUG_RANKING
726      return true;
727#else
728      if (!impl_.validate()) {
729        std::cerr << "Impl::validate failed\n";
730        return false;
731      }
732
733      bool ok = true;
734      size_t rank = 0;
735      YAT_ASSERT(cbegin().node_);
736      YAT_ASSERT(cend().node_);
737      for (auto it = cbegin(); it!=cend(); ++it) {
738        size_t r = ranking(it);
739        if (r != rank) {
740          std::cerr << "ranking: " << r << "; expected: " << rank << "\n";
741          std::cerr << "size: " << it.node_->size_ << "\n";
742          std::cerr << it.node_->parent_ << " "
743                    << it.node_->is_left_node() << " "
744                    << it.node_->is_right_node() << "\n---\n";
745          ok = false;
746        }
747        ++rank;
748      }
749      return ok;
750#endif
751    }
752  };
753
754  // avoid doxygen reading code below as it has problems to to match
755  // declarations and implementations unless matching perfectly.
756
757  /// \cond IGNORE_DOXYGEN
758
759  // implementations
760  template<typename T, typename C>
761  Ranking<T,C>::Ranking(const Ranking& other)
762    : compare_(other.compare())
763  {
764    if (!other.empty())
765      impl_.root_node() = copy(other);
766    YAT_ASSERT(validate());
767  }
768
769
770  template<typename T, typename C>
771  Ranking<T,C>::Ranking(Ranking&& other)
772    : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
773  {
774    YAT_ASSERT(validate());
775  }
776
777
778  template<typename T, typename C>
779  Ranking<T, C>& Ranking<T, C>::operator=(const Ranking& other)
780  {
781    if (this != &other) {
782      Ranking tmp(other);
783      *this = std::move(tmp);
784    }
785    return *this;
786  }
787
788
789  template<typename T, typename C>
790  Ranking<T, C>& Ranking<T, C>::operator=(Ranking&& other)
791  {
792    clear();
793    compare_ = std::move(other.compare_);
794    impl_ = std::move(other.impl_);
795    return *this;
796  }
797
798
799  template<typename T, typename C>
800  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
801  {
802    YAT_ASSERT(other.root_node());
803    ranking::NodeValue<T>* root = copy(other.root_node());
804    root->parent_ = head_node();
805    head_node()->left_ = root;
806    head_node()->right_ = root->left_most();
807    head_node()->update_height();
808    head_node()->update_size();
809    if (root_node())
810      impl_.right_most() = root_node()->right_most();
811    else
812      impl_.right_most() = head_node();
813    YAT_ASSERT(validate());
814    return root;
815  }
816
817
818  template<typename T, typename C>
819  ranking::NodeValue<T>*
820  Ranking<T,C>::copy(const ranking::NodeValue<T>* x) const
821  {
822    YAT_ASSERT(x);
823    ranking::NodeValue<T>* root = clone_node(x);
824    YAT_ASSERT(root);
825    root->height_ = x->height_;
826    root->size_ = x->size_;
827
828    try {
829      if (x->left_) {
830        root->left_ = copy(left(x));
831        root->left_->parent_ = root;
832      }
833      if (x->right_) {
834        root->right_ = copy(right(x));
835        root->right_->parent_ = root;
836      }
837    }
838    catch (std::exception& e) {
839      erase(root);
840      std::rethrow_exception(std::current_exception());
841    }
842    return root;
843  }
844
845
846  template<typename T, typename C>
847  ranking::NodeValue<T>*
848  Ranking<T,C>::clone_node(const ranking::NodeValue<T>* x) const
849  {
850    YAT_ASSERT(x);
851    ranking::NodeValue<T>* res = new ranking::NodeValue<T>(x->value());
852    res->left_ = nullptr;
853    res->right_ = nullptr;
854    res->parent_ = nullptr;
855    return res;
856  }
857
858
859  template<typename T, typename C>
860  void Ranking<T, C>::erase_node(typename Ranking<T, C>::const_iterator p)
861  {
862    YAT_ASSERT(p != end());
863    const ranking::NodeBase* node = p.node_;
864    YAT_ASSERT(node);
865
866    impl_.erase_and_rebalance(node);
867    delete node;
868    YAT_ASSERT(validate());
869    return;
870  }
871
872
873  template<typename T, typename C>
874  typename Ranking<T, C>::iterator
875  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator p)
876  {
877    YAT_ASSERT(p != end());
878    const_iterator res = p;
879    ++res;
880    erase_node(p);
881    // iterator and const_iterator are same at the moment
882    return res;
883  }
884
885
886  template<typename T, typename C>
887  typename Ranking<T, C>::size_type Ranking<T, C>::erase(const T& value)
888  {
889    auto it = lower_bound(value);
890    typename Ranking<T, C>::size_type n = 0;
891    while (it!=end() && !compare_(value, *it)) {
892      erase_node(it++);
893      ++n;
894    }
895    return n;
896  }
897
898
899  template<typename T, typename C>
900  typename Ranking<T, C>::iterator
901  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator first,
902                       typename Ranking<T, C>::const_iterator last)
903  {
904    if (first == cbegin() && last == cend())
905      clear();
906    else
907      while (first != last) {
908        erase_node(first++);
909      }
910    return last;
911  }
912
913
914  template<typename T, typename C>
915  typename Ranking<T, C>::const_iterator Ranking<T, C>::find(const T& x) const
916  {
917    auto it = lower_bound(x);
918    if (it != cend() && compare_(x, *it))
919      it = cend();
920    return it;
921  }
922
923  /// \endcond
924
925}}} // of namespace utility, yat, and theplu
926#endif
Note: See TracBrowser for help on using the repository browser.