the nodes of splay trees More...

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

Collaboration diagram for gum::SplayBinaryNode< Element >:

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.
	SplayBinaryNode (const SplayBinaryNode< Element > &from, HashTable< Element, SplayBinaryNode< Element > * > &addr)
	Copy constructor.
void	copy_ (const SplayBinaryNode< Element > &from, HashTable< Element, SplayBinaryNode< Element > * > &addr)
	A function used to perform copies.
	~SplayBinaryNode ()
	Class destructor.

Protected Attributes
Data Members
Element	elt
	The content.
Size	size
	The size of the sub-tree.
SplayBinaryNode *	fg
	The left child.
SplayBinaryNode *	fd
	The right child.
SplayBinaryNode *	pere
	The father, nullptr for the root.

Friends
class	SplayTree< Element >
	Friendly with SplayTree.
std::ostream &	operator<< (std::ostream &out, const SplayBinaryNode< Element > &e)
	Friendly to display.

Accessors / Modifiers
int	position () const
	Position of the node.
const Element &	getElement () const
	Returns the element in the node.
const SplayBinaryNode< Element > *	getFg () const
	Returns the left child.
const SplayBinaryNode< Element > *	getFd () const
	Returns the right child.
SplayBinaryNode< Element > *	zig ()
	A right rotation, the node must have a father.
SplayBinaryNode< Element > *	zag ()
	A left rotation, the node must hava a father.
SplayBinaryNode< Element > *	splay ()
	A splay rotation, the node will be the root of the tree.
SplayBinaryNode< Element > *	join (const SplayBinaryNode< Element > e, HashTable< Element, SplayBinaryNode< Element > > &addr)
	Concatenation of two trees.

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 91 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 91 of file splay_tpl.h.

                          : 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);
  }

References SplayBinaryNode(), elt, fd, fg, pere, and size.

Referenced by SplayBinaryNode(), SplayBinaryNode(), ~SplayBinaryNode(), copy_(), getFd(), getFg(), join(), operator<<, splay(), zag(), and zig().

Here is the call graph for this function:

Here is the caller 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 107 of file splay_tpl.h.

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

References SplayBinaryNode(), and copy_().

Here is the call graph for this function:

◆ ~SplayBinaryNode()

template<class Element>

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

protected

Class destructor.

Definition at line 118 of file splay_tpl.h.

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

References SplayBinaryNode(), fd, and fg.

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 62 of file splay_tpl.h.

                                                                                                 {
    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;
    }
  }

References SplayBinaryNode(), elt, fd, fg, pere, and size.

Referenced by SplayBinaryNode().

Here is the call graph for this function:

Here is the caller 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 332 of file splay_tpl.h.

                                                                     {
    return elt;
  }

References elt.

Referenced by gum::removeInfo().

Here is the caller 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 352 of file splay_tpl.h.

                                                                                   {
    return fd;
  }

References SplayBinaryNode(), and fd.

Referenced by gum::removeInfo().

Here is the call graph for this function:

Here is the caller 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 342 of file splay_tpl.h.

                                                                                   {
    return fg;
  }

References SplayBinaryNode(), and fg.

Referenced by gum::removeInfo().

Here is the call graph for this function:

Here is the caller 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 278 of file splay_tpl.h.

                                                                                                {
    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;
  }

References SplayBinaryNode(), fd, fg, pere, size, and splay().

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 307 of file splay_tpl.h.

                                                        {
    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;
    }
  }

References fd, fg, and pere.

Referenced by gum::SplayTree< Element >::split().

Here is the caller 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 232 of file splay_tpl.h.

                                                                       {
    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
  }

References SplayBinaryNode(), fd, fg, pere, zag(), and zig().

Referenced by gum::SplayTree< Element >::back(), gum::SplayTree< Element >::front(), gum::SplayTree< Element >::insert(), join(), gum::SplayTree< Element >::operator[](), gum::SplayTree< Element >::operator[](), gum::SplayTree< Element >::popBack(), gum::SplayTree< Element >::popFront(), gum::SplayTree< Element >::pushBack(), gum::SplayTree< Element >::pushFront(), gum::SplayTree< Element >::split(), and gum::SplayTree< Element >::split_by_val().

Here is the call graph for this function:

Here is the caller 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 182 of file splay_tpl.h.

                                                                     {
    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;
  }

References SplayBinaryNode(), fd, fg, pere, and size.

Referenced by splay().

Here is the call graph for this function:

Here is the caller 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 131 of file splay_tpl.h.

                                                                     {
    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;
  }

References SplayBinaryNode(), fd, fg, pere, and size.

Referenced by splay().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator<<

template<class Element>

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

friend

Friendly to display.

Definition at line 794 of file splay_tpl.h.

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