the nodes of splay trees More...

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

Collaboration diagram for gum::SplayBinaryNode< Element >:

Protected Attributes
Data Members
Element	elt
	The content. More...

Size	size
	The size of the sub-tree. More...

SplayBinaryNode *	fg
	The left child. More...

SplayBinaryNode *	fd
	The right child. More...

SplayBinaryNode *	pere
	The father, nullptr for the root. More...

Protected Member Functions
Constructors / Destructors
	SplayBinaryNode (const Element &e, HashTable< Element, SplayBinaryNode< Element > * > &addr, SplayBinaryNode g=0, SplayBinaryNode d=0, SplayBinaryNode *p=0)
	Basic constructor: creates a node with a reference to the element. More...

	SplayBinaryNode (const SplayBinaryNode< Element > &from, HashTable< Element, SplayBinaryNode< Element > * > &addr)
	Copy constructor. More...

void	copy_ (const SplayBinaryNode< Element > &from, HashTable< Element, SplayBinaryNode< Element > * > &addr)
	A function used to perform copies. More...

	~SplayBinaryNode ()
	Class destructor. More...

Friends
class	SplayTree< Element >
	Friendly with SplayTree. More...

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

Accessors / Modifiers
int	position () const
	Position of the node. More...

const Element &	getElement () const
	Returns the element in the node. More...

const SplayBinaryNode< Element > *	getFg () const
	Returns the left child. More...

const SplayBinaryNode< Element > *	getFd () const
	Returns the right child. More...

SplayBinaryNode< Element > *	zig ()
	A right rotation, the node must have a father. More...

SplayBinaryNode< Element > *	zag ()
	A left rotation, the node must hava a father. More...

SplayBinaryNode< Element > *	splay ()
	A splay rotation, the node will be the root of the tree. More...

SplayBinaryNode< Element > *	join (const SplayBinaryNode< Element > e, HashTable< Element, SplayBinaryNode< Element > > &addr)
	Concatenation of two trees. More...

Detailed Description

template<class Element>
class gum::SplayBinaryNode< Element >

the nodes of splay trees

Author: Karim Tekkal

These file implements a data structure. A splay tree is a self-balancing binary search tree.

Definition at line 41 of file splay.h.

Constructor & Destructor Documentation

◆ SplayBinaryNode() [1/2]

template<class Element >

INLINE gum::SplayBinaryNode< Element >::SplayBinaryNode	(	const Element &	e,
		HashTable< Element, SplayBinaryNode< Element > * > &	addr,
		SplayBinaryNode< Element > *	g = `0`,
		SplayBinaryNode< Element > *	d = `0`,
		SplayBinaryNode< Element > *	p = `0`
	)

protected

Basic constructor: creates a node with a reference to the element.

Parameters

e	The element in the node.
addr	TODO don't know what to do here.
g	The left child of the node, can be nullptr.
d	The right child of the node, can be nullptr.
p	The father of the node, can be nullptr if the node is the root of the tree.

Definition at line 72 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                            :
       elt(e),
       size(1), fg(g), fd(d), pere(p) {
     if (addr.exists(elt))
       addr[elt] = this;
     else
       addr.insert(elt, this);
 
     // for debugging purposes
     GUM_CONSTRUCTOR(SplayBinaryNode);
   }

Here is the call graph for this function:

◆ SplayBinaryNode() [2/2]

template<class Element >

INLINE gum::SplayBinaryNode< Element >::SplayBinaryNode	(	const SplayBinaryNode< Element > &	from,
		HashTable< Element, SplayBinaryNode< Element > * > &	addr
	)

protected

Copy constructor.

Parameters

from	the src SplayBinaryNode
addr	TODO don't know what to do here.

Definition at line 92 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                               {
     copy_(from, addr);
     // for debugging purposes
     GUM_CONSTRUCTOR(SplayBinaryNode);
   }

Here is the call graph for this function:

◆ ~SplayBinaryNode()

template<class Element >

INLINE gum::SplayBinaryNode< Element >::~SplayBinaryNode ( )

protected

Class destructor.

Definition at line 103 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                       {
     // for debugging purposes
     GUM_DESTRUCTOR(SplayBinaryNode);
     // remove the subtrees
 
     if (fg) delete fg;
 
     if (fd) delete fd;
   }

Here is the call graph for this function:

Member Function Documentation

◆ copy_()

template<class Element >

INLINE void gum::SplayBinaryNode< Element >::copy_	(	const SplayBinaryNode< Element > &	from,
		HashTable< Element, SplayBinaryNode< Element > * > &	addr
	)

protected

A function used to perform copies.

Parameters

from	the src SplayBinaryNode
addr	TODO don't know what to do here ..

Definition at line 41 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                                 {
     if (addr.exists(from.elt))
       addr[from.elt] = this;
     else
       addr.insert(from.elt, this);
 
     elt = from.elt;
 
     size = from.size;
 
     pere = 0;
 
     if (from.fg) {
       fg       = new SplayBinaryNode< Element >(*from.fg, addr);
       fg->pere = this;
     } else {
       fg = 0;
     }
 
     if (from.fd) {
       fd       = new SplayBinaryNode< Element >(*from.fd, addr);
       fd->pere = this;
     } else {
       fd = 0;
     }
   }

Here is the call graph for this function:

◆ getElement()

template<class Element >

INLINE const Element & gum::SplayBinaryNode< Element >::getElement ( ) const

Returns the element in the node.

Returns: Returns the element in the node.

Definition at line 319 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                      {
     return elt;
   }

Here is the call graph for this function:

◆ getFd()

template<class Element >

INLINE const SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::getFd ( ) const

Returns the right child.

Returns: Returns the right child.

Warning: The returned value can be null.

Definition at line 339 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                    {
     return fd;
   }

Here is the call graph for this function:

◆ getFg()

template<class Element >

INLINE const SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::getFg ( ) const

Returns the left child.

Returns: Returns the left child.

Warning: The returned value can be null.

Definition at line 329 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                    {
     return fg;
   }

Here is the call graph for this function:

◆ join()

template<class Element >

INLINE SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::join	(	const SplayBinaryNode< Element > *	e,
		HashTable< Element, SplayBinaryNode< Element > * > &	addr
	)

protected

Concatenation of two trees.

Parameters

e	The node to add.
addr	TODO Don't know what to do here.

Returns: Returns the root of the created tree.

Definition at line 263 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                                {
     SplayBinaryNode< Element >* b = new SplayBinaryNode< Element >(*e, addr);
     GUM_ASSERT(b != 0);
     SplayBinaryNode< Element >* act = this;
 
     for (; act->fd; act = act->fd)
       ;
 
     // act is the rightmost element
     act->splay();
 
     // insertion
     act->fd = b;
 
     b->pere = act;
 
     act->size = 1;
 
     if (act->fg) act->size += act->fg->size;
 
     act->size += act->fd->size;
 
     return act;
   }

Here is the call graph for this function:

◆ position()

template<class Element >

INLINE int gum::SplayBinaryNode< Element >::position ( ) const

Position of the node.

Returns: The position of the node into the tree.

Definition at line 292 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                         {
     if (!pere) {
       // I'm the root
       if (fg)
         return fg->size + 1;
       else
         return 0;
     } else if (pere->fg == this) {
       // I'm the left child of my father
       int pos = pere->position() - 1;
 
       if (fd) pos -= fd->size;
 
       return pos;
     } else {
       // I'm the right child of my father
       int pos = pere->position() + 1;
 
       if (fg) pos += fg->size;
 
       return pos;
     }
   }

Here is the call graph for this function:

◆ splay()

template<class Element >

INLINE SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::splay ( )

protected

A splay rotation, the node will be the root of the tree.

Returns: Returns a pointer to the root of the sub-tree after rotation.

Definition at line 217 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                        {
     SplayBinaryNode< Element >* gdp;
 
     while (pere) {
       // While this node isn't the root
       gdp = pere->pere;   // gdp can be nullptr
 
       if (!gdp) {
         if (this == pere->fg) {
           // I'm the left child of my father
           return zig();
         } else {
           GUM_ASSERT(this == pere->fd);
           // I'm the right child of my father
           return zag();
         }
       } else {
         if (this == pere->fg) {
           // I'm the left child of my father
           if (pere == gdp->fg) {
             gdp->fg = zig();
           } else {
             GUM_ASSERT(pere == gdp->fd);
             gdp->fd = zig();
           }
         } else {
           GUM_ASSERT(this == pere->fd);
           // I'm the right child of my father
 
           if (pere == gdp->fg) {
             gdp->fg = zag();
           } else {
             GUM_ASSERT(pere == gdp->fd);
             gdp->fd = zag();
           }
         }
       }
     }
 
     return this;   // for compiler satisfaction
   }

Here is the call graph for this function:

◆ zag()

template<class Element >

INLINE SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::zag ( )

protected

A left rotation, the node must hava a father.

Returns: Returns a pointer to the root of the sub-tree after rotation.

Definition at line 167 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                      {
     Size size_;
     // Must be call on a node with a father
     GUM_ASSERT(pere != 0);
     // We chain childs
     pere->fd = fg;
 
     if (fg) fg->pere = pere;
 
     fg = pere;
 
     SplayBinaryNode< Element >* p = fg->pere;
 
     fg->pere = this;
 
     // We compute the size of rigth child
     size_ = 1;
 
     if (fg->fg) size_ += fg->fg->size;
 
     if (fg->fd) size_ += fg->fd->size;
 
     fg->size = size_;
 
     if (fd) size_ += fd->size;
 
     ++size_;
 
     size = size_;
 
     // We chain father
     pere = p;
 
     if (pere) {
       if (pere->fg == fg) {
         // I'm left child of my father
         pere->fg = this;
       } else {
         // I'm right child of my father
         GUM_ASSERT(pere->fd == fg);
         pere->fd = this;
       }
     }
 
     return this;
   }

Here is the call graph for this function:

◆ zig()

template<class Element >

INLINE SplayBinaryNode< Element > * gum::SplayBinaryNode< Element >::zig ( )

protected

A right rotation, the node must have a father.

Returns: Returns a pointer to the root of the sub-tree after rotation.

Definition at line 116 of file splay_tpl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                      {
     Size size_;
     // Must be called on a node with a father
     GUM_ASSERT(pere != 0);
     // We chain childs
     pere->fg = fd;
 
     if (fd) fd->pere = pere;
 
     fd = pere;
 
     SplayBinaryNode< Element >* p = fd->pere;
 
     fd->pere = this;
 
     // We compute the size of rigth child
     size_ = 1;
 
     if (fd->fg) size_ += fd->fg->size;
 
     if (fd->fd) size_ += fd->fd->size;
 
     fd->size = size_;
 
     // size_ == fd->size
     if (fg) size_ += fg->size;
 
     ++size_;
 
     size = size_;
 
     // We chain father
     pere = p;
 
     if (pere) {
       if (pere->fg == fd) {
         // I'm left child of my father
         pere->fg = this;
       } else {
         // I'm right child of my father
         GUM_ASSERT(pere->fd == fd);
         pere->fd = this;
       }
     }
 
     return this;
   }

Here is the call graph for this function:

Friends And Related Function Documentation

◆ operator<<

template<class Element >

std::ostream& operator<<	(	std::ostream &	out,
		const SplayBinaryNode< Element > &	e
	)

friend

Friendly to display.

Definition at line 787 of file splay_tpl.h.

                                                                                {
     if (e.fg) out << *e.fg << ",";
 
     out << e.elt;
 
     if (e.fd) out << "," << *e.fd;
 
     return out;
   }

◆ SplayTree< Element >

template<class Element >

template<class Element >

Size gum::SplayBinaryNode< Element >::size

protected

The size of the sub-tree.

Definition at line 190 of file splay.h.

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

agrum/tools/core/splay.h
agrum/tools/core/splay_tpl.h

Protected Attributes

Protected Member Functions

Friends

Accessors / Modifiers

Detailed Description

template<class Element> class gum::SplayBinaryNode< Element >

Constructor & Destructor Documentation

◆ SplayBinaryNode() [1/2]

◆ SplayBinaryNode() [2/2]

◆ ~SplayBinaryNode()

Member Function Documentation

◆ copy_()

◆ getElement()

◆ getFd()

◆ getFg()

◆ join()

◆ position()

◆ splay()

◆ zag()

◆ zig()

Friends And Related Function Documentation

◆ operator<<

◆ SplayTree< Element >

Member Data Documentation

◆ elt

◆ fd

◆ fg

◆ pere

◆ size

template<class Element>
class gum::SplayBinaryNode< Element >