gum::SplayBinaryNode< Element > Class Template Reference

the nodes of splay trees More...

#include <agrum/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 39 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 70 of file splay_tpl.h.

References gum::SplayBinaryNode< Element >::elt.

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

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

References gum::SplayBinaryNode< Element >::_copy().

                                                              {
    _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 101 of file splay_tpl.h.

References gum::SplayBinaryNode< Element >::fd, and gum::SplayBinaryNode< Element >::fg.

                                                      {
    // for debugging purposes
    GUM_DESTRUCTOR(SplayBinaryNode);
    // remove the subtrees

    if (fg) delete fg;

    if (fd) delete fd;
  }

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

References gum::SplayBinaryNode< Element >::elt, gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::pere, and gum::SplayBinaryNode< Element >::size.

Referenced by gum::SplayBinaryNode< Element >::SplayBinaryNode().

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

References gum::SplayBinaryNode< Element >::elt.

Referenced by gum::removeInfo().

                                                                     {
    return elt;
  }

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

References gum::SplayBinaryNode< Element >::fd.

Referenced by gum::removeInfo().

                                                       {
    return fd;
  }

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

References gum::SplayBinaryNode< Element >::fg.

Referenced by gum::removeInfo().

                                                       {
    return fg;
  }

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

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

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

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::pere, gum::SplayBinaryNode< Element >::position(), and gum::SplayBinaryNode< Element >::size.

Referenced by gum::SplayBinaryNode< Element >::position(), and gum::SplayTree< Element >::split().

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

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

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::pere, gum::SplayBinaryNode< Element >::zag(), and gum::SplayBinaryNode< Element >::zig().

Referenced by gum::SplayTree< Element >::back(), gum::SplayTree< Element >::front(), gum::SplayBinaryNode< Element >::join(), 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().

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

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

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::pere, and gum::SplayBinaryNode< Element >::size.

Referenced by gum::SplayBinaryNode< Element >::splay().

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

References gum::SplayBinaryNode< Element >::fd, gum::SplayBinaryNode< Element >::fg, gum::SplayBinaryNode< Element >::pere, and gum::SplayBinaryNode< Element >::size.

Referenced by gum::SplayBinaryNode< Element >::splay().

                                                                     {
    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 caller 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 792 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>

friend class SplayTree< Element >

friend

Friendly with SplayTree.

Definition at line 205 of file splay.h.

Member Data Documentation

elt

template<class Element>

Element gum::SplayBinaryNode< Element >::elt

protected

The content.

Definition at line 188 of file splay.h.

Referenced by gum::SplayBinaryNode< Element >::_copy(), gum::SplayBinaryNode< Element >::getElement(), gum::operator<<(), and gum::SplayBinaryNode< Element >::SplayBinaryNode().

fd

template<class Element>

SplayBinaryNode* gum::SplayBinaryNode< Element >::fd

protected

The right child.

Definition at line 197 of file splay.h.

Referenced by gum::SplayBinaryNode< Element >::_copy(), gum::SplayTree< Element >::back(), gum::SplayBinaryNode< Element >::getFd(), gum::SplayTree< Element >::insert(), gum::SplayBinaryNode< Element >::join(), gum::operator<<(), gum::SplayTree< Element >::operator[](), gum::SplayTree< Element >::popBack(), gum::SplayTree< Element >::popFront(), gum::SplayBinaryNode< Element >::position(), gum::SplayTree< Element >::pushBack(), gum::SplayBinaryNode< Element >::splay(), gum::SplayTree< Element >::split(), gum::SplayTree< Element >::split_by_val(), gum::SplayBinaryNode< Element >::zag(), gum::SplayBinaryNode< Element >::zig(), and gum::SplayBinaryNode< Element >::~SplayBinaryNode().

fg

template<class Element>

SplayBinaryNode* gum::SplayBinaryNode< Element >::fg

protected

The left child.

Definition at line 194 of file splay.h.

Referenced by gum::SplayBinaryNode< Element >::_copy(), gum::SplayTree< Element >::front(), gum::SplayBinaryNode< Element >::getFg(), gum::SplayBinaryNode< Element >::join(), gum::operator<<(), gum::SplayTree< Element >::operator[](), gum::SplayTree< Element >::popBack(), gum::SplayTree< Element >::popFront(), gum::SplayBinaryNode< Element >::position(), gum::SplayTree< Element >::pushFront(), gum::SplayBinaryNode< Element >::splay(), gum::SplayTree< Element >::split(), gum::SplayTree< Element >::split_by_val(), gum::SplayBinaryNode< Element >::zag(), gum::SplayBinaryNode< Element >::zig(), and gum::SplayBinaryNode< Element >::~SplayBinaryNode().

pere

template<class Element>

SplayBinaryNode* gum::SplayBinaryNode< Element >::pere

protected

The father, nullptr for the root.

Definition at line 200 of file splay.h.

Referenced by gum::SplayBinaryNode< Element >::_copy(), gum::SplayBinaryNode< Element >::join(), gum::SplayBinaryNode< Element >::position(), gum::SplayBinaryNode< Element >::splay(), gum::SplayBinaryNode< Element >::zag(), and gum::SplayBinaryNode< Element >::zig().

size

template<class Element>

Size gum::SplayBinaryNode< Element >::size

protected

The size of the sub-tree.

Definition at line 191 of file splay.h.

Referenced by gum::SplayBinaryNode< Element >::_copy(), gum::SplayTree< Element >::insert(), gum::SplayBinaryNode< Element >::join(), gum::SplayBinaryNode< Element >::position(), gum::SplayBinaryNode< Element >::zag(), and gum::SplayBinaryNode< Element >::zig().

---

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

• agrum/core/splay.h
• agrum/core/splay_tpl.h