aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
gum::SplayTree< Element > Class Template Reference
Basic data structures » Splay Trees | Basic data structures

A splay tree. More...

#include <agrum/base/core/splay.h>

Collaboration diagram for gum::SplayTree< Element >:

Public Member Functions

Constructors / Destructors
 SplayTree ()
 Basic constructor, make an empty splay tree.
 SplayTree (const Element &e)
 Basic constructor, make a splay tree with one element.
 SplayTree (const SplayTree &from)
 Copy constructor.
 ~SplayTree ()
 Class destructor.
Operators
SplayTree< Element > & operator= (const SplayTree< Element > &from)
 Assignment operator.
Methods
Element & operator[] (const unsigned int i)
 Get the element at the position n.
const Element & operator[] (const unsigned int i) const
 Get the element at the position n.
Element & front ()
 Get the first element.
Element & back ()
 Get the last element.
void popFront ()
 Remove the first element.
void popBack ()
 Remove the last element.
void pushFront (const Element &e)
 Add an element in the first position.
void pushBack (const Element &e)
 Add an element in the last position.
void insert (const Element &e)
 Add an element to the tree.
void join (const SplayTree< Element > &s)
 Concatenation of two trees.
SplayTree< Element > split (const int i)
 Divide the tree at the position.
SplayTree< Element > split_by_val (const Element &e)
 Divide the tree at the position.
Size size () const
 The number of elements in the tree.
bool contains (const Element &e) const
 Test if the tree contains the element.

Protected Member Functions

void copy_ (const SplayTree< Element > &)
 a function used to perform copies

Protected Attributes

Data Menbers
SplayBinaryNode< Element > * root
 Root of the tree.
HashTable< Element, SplayBinaryNode< Element > * > addr
 The hash table to find quickly the position of a node.

Friends

std::ostream & operator<< (std::ostream &out, const SplayTree< Element > &s)
 Friendly to display.

Detailed Description

template<class Element>
class gum::SplayTree< Element >

A splay tree.

Warning
an Element must be in just one Splay Tree, the behavior is unspecified else.
Usage example:
// Creating empty trees
SplayTree<string> a;
// Make a copy
SplayTree<string> b(a);
// Add an element
a.insert("toto");
a.insert("titi");
// Get the first element
a.front();
// And the last
a.back();
// concatenate two trees
a.join(b);
// divide a tree at the third position, the first part is placed into a
// the second into b.
b = a.split(3);
// Display the splay tree
a.printTree();
// Get the size
a.size();
gum::SplayTree::front
Element & front()
Get the first element.
Definition splay_tpl.h:507
gum::SplayTree::SplayTree
SplayTree()
Basic constructor, make an empty splay tree.
Definition splay_tpl.h:376
gum::SplayTree::size
Size size() const
The number of elements in the tree.
Definition splay_tpl.h:779
gum::SplayTree::back
Element & back()
Get the last element.
Definition splay_tpl.h:524
gum::SplayTree::join
void join(const SplayTree< Element > &s)
Concatenation of two trees.
Definition splay_tpl.h:651
gum::SplayTree::split
SplayTree< Element > split(const int i)
Divide the tree at the position.
Definition splay_tpl.h:677
gum::SplayTree::insert
void insert(const Element &e)
Add an element to the tree.
Definition splay_tpl.h:625
Template Parameters
ElementThe elements type.

Definition at line 278 of file splay.h.

Constructor & Destructor Documentation

◆ SplayTree() [1/3]

template<class Element>
INLINE gum::SplayTree< Element >::SplayTree ( )

Basic constructor, make an empty splay tree.

Definition at line 376 of file splay_tpl.h.

376 : root(0), addr() {
377 // for debugging purposes
378 GUM_CONSTRUCTOR(SplayTree);
379 }
gum::SplayTree
A splay tree.
Definition splay.h:278
gum::SplayTree::root
SplayBinaryNode< Element > * root
Root of the tree.
Definition splay.h:434
gum::SplayTree::addr
HashTable< Element, SplayBinaryNode< Element > * > addr
The hash table to find quickly the position of a node.
Definition splay.h:437

References SplayTree(), addr, and root.

Referenced by SplayTree(), SplayTree(), SplayTree(), ~SplayTree(), copy_(), join(), operator<<, operator=(), split(), and split_by_val().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SplayTree() [2/3]

template<class Element>
INLINE gum::SplayTree< Element >::SplayTree ( const Element & e)

Basic constructor, make a splay tree with one element.

Parameters
eThe element of the tree.

Definition at line 387 of file splay_tpl.h.

387 : root(0), addr() {
388 root = new SplayBinaryNode< Element >(e, addr);
389 // for debugging purposes
390 GUM_CONSTRUCTOR(SplayTree);
391 }

References SplayTree(), addr, and root.

Here is the call graph for this function:

◆ SplayTree() [3/3]

template<class Element>
INLINE gum::SplayTree< Element >::SplayTree ( const SplayTree< Element > & from)

Copy constructor.

Parameters
fromThe gum::SplayTree to copy.

Definition at line 396 of file splay_tpl.h.

396 : addr() {
397 copy_(from);
398 // for debugging purposes
399 GUM_CONS_CPY(SplayTree);
400 }
gum::SplayTree::copy_
void copy_(const SplayTree< Element > &)
a function used to perform copies
Definition splay_tpl.h:365

References SplayTree(), addr, and copy_().

Here is the call graph for this function:

◆ ~SplayTree()

template<class Element>
INLINE gum::SplayTree< Element >::~SplayTree ( )

Class destructor.

Definition at line 425 of file splay_tpl.h.

425 {
426 // for debugging purposes
427 GUM_DESTRUCTOR(SplayTree);
428
429 if (root) delete (root);
430 }

References SplayTree(), and root.

Here is the call graph for this function:

Member Function Documentation

◆ back()

template<class Element>
INLINE Element & gum::SplayTree< Element >::back ( )

Get the last element.

Exceptions
NotFoundRaised if the splay tree is empty.

Definition at line 524 of file splay_tpl.h.

524 {
525 SplayBinaryNode< Element >* act = root;
526
527 if (!root) { GUM_ERROR(NotFound, "The splay tree is empty") }
528
529 if (act->fd)
530 for (; act->fd; act = act->fd)
531 ;
532
533 root = act->splay();
534
535 return root->elt;
536 }
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition exceptions.h:72

References gum::SplayBinaryNode< Element >::fd, GUM_ERROR, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ contains()

template<class Element>
INLINE bool gum::SplayTree< Element >::contains ( const Element & e) const

Test if the tree contains the element.

Parameters
eThe element to test if it is in the splay tree.
Returns
Returns true if e is in this splay tree.

Definition at line 787 of file splay_tpl.h.

787 {
788 return addr.exists(e);
789 }

References addr.

◆ copy_()

template<class Element>
INLINE void gum::SplayTree< Element >::copy_ ( const SplayTree< Element > & from)
protected

a function used to perform copies

Definition at line 365 of file splay_tpl.h.

365 {
366 if (from.root) {
367 root = new SplayBinaryNode< Element >(*from.root, addr);
368 } else {
369 root = 0;
370 }
371 }

References SplayTree(), addr, and root.

Referenced by SplayTree(), and operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ front()

template<class Element>
INLINE Element & gum::SplayTree< Element >::front ( )

Get the first element.

Exceptions
NotFoundRaised if the splay tree is empty.

Definition at line 507 of file splay_tpl.h.

507 {
508 SplayBinaryNode< Element >* act = root;
509
510 if (!root) { GUM_ERROR(NotFound, "The splay tree is empty") }
511
512 if (act->fg)
513 for (; act->fg; act = act->fg)
514 ;
515
516 root = act->splay();
517
518 return root->elt;
519 }

References gum::SplayBinaryNode< Element >::fg, GUM_ERROR, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ insert()

template<class Element>
INLINE void gum::SplayTree< Element >::insert ( const Element & e)

Add an element to the tree.

Parameters
eThe element to add.

Definition at line 625 of file splay_tpl.h.

625 {
626 SplayBinaryNode< Element >* act = root;
627
628 if (!root) {
629 root = new SplayBinaryNode< Element >(e, addr);
630 } else {
631 while (act->fd) {
632 ++act->size;
633 act = act->fd;
634 }
635
636 // act->fd == nullptr
637 act->fd = new SplayBinaryNode< Element >(e, addr, 0, 0, act);
638
639 ++act->size;
640
641 root = act->fd->splay();
642 }
643 }

References addr, gum::SplayBinaryNode< Element >::fd, root, gum::SplayBinaryNode< Element >::size, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ join()

template<class Element>
INLINE void gum::SplayTree< Element >::join ( const SplayTree< Element > & s)

Concatenation of two trees.

Parameters
sThe tree to add.

Definition at line 651 of file splay_tpl.h.

651 {
652 if (s.root) {
653 if (root) {
654 root = root->join(s.root, addr);
655 } else {
656 root = new SplayBinaryNode< Element >(*s.root, addr);
657 }
658 }
659 }

References SplayTree(), addr, and root.

Here is the call graph for this function:

◆ operator=()

template<class Element>
INLINE SplayTree< Element > & gum::SplayTree< Element >::operator= ( const SplayTree< Element > & from)

Assignment operator.

Parameters
fromThe gum::SplayTree to copy.
Returns
This gum::SplayTree.

Definition at line 405 of file splay_tpl.h.

405 {
406 // avoid self assignment
407 if (this != &from) {
408 // for debugging purposes
409 GUM_OP_CPY(SplayTree);
410 // delete the old contents
411
412 if (root) delete root;
413
414 addr.clear();
415
416 copy_(from);
417 }
418
419 return *this;
420 }

References SplayTree(), addr, copy_(), and root.

Here is the call graph for this function:

◆ operator[]() [1/2]

template<class Element>
Element & gum::SplayTree< Element >::operator[] ( const unsigned int i)

Get the element at the position n.

Parameters
iThe position of the element to return.
Exceptions
NotFoundRaised if no element was found.
Returns
Returns the element at the position n.

Definition at line 435 of file splay_tpl.h.

435 {
436 int val = i;
437
438 if (!root) {
439 GUM_ERROR(NotFound, "The tree is empty !")
440 } else if (val >= root->size) {
441 GUM_ERROR(NotFound, "The index is too large !")
442 } else {
443 // The element exists
444 // Find it
445 SplayBinaryNode< Element >* act = root;
446 int pos_act = val - 1;
447 bool next = true;
448
449 while (next) {
450 if (!act->fg) pos_act = 0;
451 else pos_act = act->fg->size;
452
453 if (pos_act > val) {
454 act = act->fg;
455 } else if (pos_act < val) {
456 act = act->fd;
457 val -= (pos_act + 1);
458 } else {
459 next = false;
460 }
461 }
462
463 root = act->splay();
464
465 return root->elt;
466 }
467 }

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, GUM_ERROR, root, gum::SplayBinaryNode< Element >::size, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ operator[]() [2/2]

template<class Element>
const Element & gum::SplayTree< Element >::operator[] ( const unsigned int i) const

Get the element at the position n.

Parameters
iThe position of the element to return.
Exceptions
NotFoundRaised if no element was found.
Returns
Returns the element at the position n.

Definition at line 470 of file splay_tpl.h.

470 {
471 int val = i;
472
473 if (!root) {
474 GUM_ERROR(NotFound, "The tree is empty !")
475 } else if (val >= root->size) {
476 GUM_ERROR(NotFound, "The index is too large !")
477 } else {
478 // The element exists
479 // Find it
480 SplayBinaryNode< Element >* act = root;
481 int pos_act = val - 1;
482 bool next = true;
483
484 while (next) {
485 if (!act->fg) pos_act = 0;
486 else pos_act = act->fg->size;
487
488 if (pos_act > val) {
489 act = act->fg;
490 } else if (pos_act < val) {
491 act = act->fd;
492 val -= (pos_act + 1);
493 } else {
494 next = false;
495 }
496 }
497
498 root = act->splay();
499
500 return root->elt;
501 }
502 }

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, GUM_ERROR, root, gum::SplayBinaryNode< Element >::size, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ popBack()

template<class Element>
INLINE void gum::SplayTree< Element >::popBack ( )

Remove the last element.

Definition at line 564 of file splay_tpl.h.

564 {
565 SplayBinaryNode< Element >* act = root;
566
567 if (root) {
568 if (root->fd)
569 for (; act->fd; act = act->fd)
570 ;
571
572 act = act->splay();
573
574 root = act->fg;
575
576 if (root) root->pere = 0;
577
578 act->fg = 0;
579
580 delete act;
581 }
582 }

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ popFront()

template<class Element>
INLINE void gum::SplayTree< Element >::popFront ( )

Remove the first element.

Definition at line 541 of file splay_tpl.h.

541 {
542 SplayBinaryNode< Element >* act = root;
543
544 if (root) {
545 if (root->fg)
546 for (; act->fg; act = act->fg)
547 ;
548
549 act = act->splay();
550
551 root = act->fd;
552
553 if (root) root->pere = 0;
554
555 act->fd = 0;
556
557 delete act;
558 }
559 }

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ pushBack()

template<class Element>
INLINE void gum::SplayTree< Element >::pushBack ( const Element & e)

Add an element in the last position.

Parameters
eThe element to push.

Definition at line 606 of file splay_tpl.h.

606 {
607 SplayBinaryNode< Element >* act = root;
608
609 if (root) {
610 if (root->fd)
611 for (; act->fd; act = act->fd)
612 ;
613
614 root = act->splay();
615
616 root->fd = new SplayBinaryNode< Element >(e, addr, 0, 0, root);
617 } else {
618 root = new SplayBinaryNode< Element >(e, addr);
619 }
620 }

References addr, gum::SplayBinaryNode< Element >::fd, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ pushFront()

template<class Element>
INLINE void gum::SplayTree< Element >::pushFront ( const Element & e)

Add an element in the first position.

Parameters
eThe element to push.

Definition at line 587 of file splay_tpl.h.

587 {
588 SplayBinaryNode< Element >* act = root;
589
590 if (root) {
591 if (root->fg)
592 for (; act->fg; act = act->fg)
593 ;
594
595 root = act->splay();
596
597 root->fg = new SplayBinaryNode< Element >(e, addr, 0, 0, root);
598 } else {
599 root = new SplayBinaryNode< Element >(e, addr);
600 }
601 }

References addr, gum::SplayBinaryNode< Element >::fg, root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ size()

template<class Element>
INLINE Size gum::SplayTree< Element >::size ( ) const

The number of elements in the tree.

Returns
the size of the tree

Definition at line 779 of file splay_tpl.h.

779 {
780 if (root) return root->size;
781 else return Size(0);
782 }

References root.

Referenced by split().

Here is the caller graph for this function:

◆ split()

template<class Element>
INLINE SplayTree< Element > gum::SplayTree< Element >::split ( const int i)

Divide the tree at the position.

Warning
all the elements less than e are stored into the tree and those who are greater than e in the returned tree.
Parameters
iThe position of the element (e) for split.
Returns
Returns a tree with all the elements greater than i.

Definition at line 677 of file splay_tpl.h.

677 {
678 GUM_ASSERT(i >= 0 && i < root->size);
679 GUM_ASSERT(root != 0);
680
681 if (i == 0) {
682 // the tree will be empty
683 // the returned tree is a copy of the present tree
684 SplayTree< Element > s = *this;
685 addr.clear();
686 delete root;
687 root = 0;
688 return s;
689 } else if (i == root->size - 1) {
690 SplayTree< Element > s;
691 return s;
692 } else {
693 // We will find the node at position i
694 SplayBinaryNode< Element >* act = root;
695 int pos = root->position();
696
697 while (pos != i) {
698 GUM_ASSERT(act != 0);
699
700 if (i < pos) {
701 act = act->fg;
702 } else {
703 act = act->fd;
704 }
705
706 pos = act->position();
707 }
708
709 // We reorganize the tree
710 act->splay();
711
712 // We take the first part
713 root = act->fg;
714
715 if (root) root->pere = 0;
716
717 // We take the second part
718 SplayTree< Element > s;
719
720 s.root = act;
721
722 s.root->fg = 0;
723
724 Size size_ = 1;
725
726 if (s.root->fd) size_ += s.root->fd->size;
727
728 s.root->size = size_;
729
730 // We remove the old nodes in the hash table
731 // Complexity O(n) => very expensive
732 removeInfo(act, addr);
733
734 return s;
735 }
736 }

References SplayTree(), addr, gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::position(), gum::removeInfo(), root, size(), and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ split_by_val()

template<typename Element>
INLINE SplayTree< Element > gum::SplayTree< Element >::split_by_val ( const Element & e)

Divide the tree at the position.

Parameters
ethe element for split
Warning
All the elements less than e are stored into the tree and those greater than e are in the returned tree
The element e is neither in the trees.
Returns
Returns the tree with all value greather than e.

Definition at line 741 of file splay_tpl.h.

741 {
742 GUM_ASSERT(root != 0);
743
744 if (!addr.exists(e)) { GUM_ERROR(NotFound, "not enough elements in the splay tree") }
745
746 // We will find the node at position i
747 SplayBinaryNode< Element >* act = addr[e];
748
749 // We reorganize the tree
750 act->splay();
751
752 // We take the two parts
753 SplayTree< Element > s;
754
755 s.root = act->fd;
756
757 if (s.root) { s.root->pere = 0; }
758
759 root = act->fg;
760
761 if (root) root->pere = 0;
762
763 act->fg = 0;
764
765 // We remove the old nodes in the hash table
766 // Complexity O(n) => very expensive
767 removeInfo(act, addr);
768
769 act->fd = 0;
770
771 delete act;
772
773 return s;
774 }

References SplayTree(), addr, gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, GUM_ERROR, gum::removeInfo(), root, and gum::SplayBinaryNode< Element >::splay().

Here is the call graph for this function:

◆ operator<<

template<class Element>
std::ostream & operator<< ( std::ostream & out,
const SplayTree< Element > & s )
friend

Friendly to display.

Definition at line 807 of file splay_tpl.h.

807 {
808 out << "|[";
809
810 if (s.root) out << *s.root;
811
812 out << "]|";
813
814 return out;
815 }

References SplayTree(), and root.

Member Data Documentation

◆ addr

template<class Element>
HashTable< Element, SplayBinaryNode< Element >* > gum::SplayTree< Element >::addr
protected

The hash table to find quickly the position of a node.

Definition at line 437 of file splay.h.

Referenced by SplayTree(), SplayTree(), SplayTree(), contains(), copy_(), insert(), join(), operator=(), pushBack(), pushFront(), split(), and split_by_val().

◆ root

template<class Element>
SplayBinaryNode< Element >* gum::SplayTree< Element >::root
protected

Root of the tree.

Definition at line 434 of file splay.h.

Referenced by SplayTree(), SplayTree(), ~SplayTree(), back(), copy_(), front(), insert(), join(), operator<<, operator=(), operator[](), operator[](), popBack(), popFront(), pushBack(), pushFront(), size(), split(), and split_by_val().

The documentation for this class was generated from the following files:
aGrUM 2.3.2

© PHW&CG&others - 2022
DoXyGeN 1.16.1