gum::SplayTree< Element > Class Template Reference

A splay tree. More...

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

Collaboration diagram for gum::SplayTree< Element >:

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

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

Protected Member Functions
void	copy_ (const SplayTree< Element > &)
	a function used to perform copies More...

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

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();

Template Parameters

Element

The elements type.

Definition at line 43 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 363 of file splay_tpl.h.

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

                                         : root(0), addr() {
    // for debugging purposes
    GUM_CONSTRUCTOR(SplayTree);
  }

Here is the call 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

e	The element of the tree.

Definition at line 374 of file splay_tpl.h.

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

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

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

from	The gum::SplayTree to copy.

Definition at line 383 of file splay_tpl.h.

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

                                                              : addr() {
    copy_(from);
    // for debugging purposes
    GUM_CONS_CPY(SplayTree);
  }

Here is the call graph for this function:

~SplayTree()

template<class Element >

INLINE gum::SplayTree< Element >::~SplayTree

(

)

Class destructor.

Definition at line 412 of file splay_tpl.h.

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

                                          {
    // for debugging purposes
    GUM_DESTRUCTOR(SplayTree);

    if (root) delete (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

NotFound

Raised if the splay tree is empty.

Definition at line 515 of file splay_tpl.h.

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

                                             {
    SplayBinaryNode< Element >* act = root;

    if (!root) { GUM_ERROR(NotFound, "The splay tree is empty") }

    if (act->fd)
      for (; act->fd; act = act->fd)
        ;

    root = act->splay();

    return root->elt;
  }

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

e	The element to test if it is in the splay tree.

Returns

Returns true if e is in this splay tree.

Definition at line 780 of file splay_tpl.h.

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

                                                                   {
    return addr.exists(e);
  }

Here is the call graph for this function:

copy_()

template<class Element >

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

protected

a function used to perform copies

Definition at line 352 of file splay_tpl.h.

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

                                                                          {
    if (from.root) {
      root = new SplayBinaryNode< Element >(*from.root, addr);
    } else {
      root = 0;
    }
  }

Here is the call graph for this function:

front()

template<class Element >

INLINE Element & gum::SplayTree< Element >::front

(

)

Get the first element.

Exceptions

NotFound

Raised if the splay tree is empty.

Definition at line 498 of file splay_tpl.h.

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

                                              {
    SplayBinaryNode< Element >* act = root;

    if (!root) { GUM_ERROR(NotFound, "The splay tree is empty") }

    if (act->fg)
      for (; act->fg; act = act->fg)
        ;

    root = act->splay();

    return root->elt;
  }

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

e	The element to add.

Definition at line 616 of file splay_tpl.h.

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

                                                           {
    SplayBinaryNode< Element >* act = root;

    if (!root) {
      root = new SplayBinaryNode< Element >(e, addr);
    } else {
      while (act->fd) {
        ++act->size;
        act = act->fd;
      }

      // act->fd == nullptr
      act->fd = new SplayBinaryNode< Element >(e, addr, 0, 0, act);

      ++act->size;

      root = act->fd->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

s	The tree to add.

Definition at line 642 of file splay_tpl.h.

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

                                                                      {
    if (s.root) {
      if (root) {
        root = root->join(s.root, addr);
      } else {
        root = new SplayBinaryNode< Element >(*s.root, addr);
      }
    }
  }

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

from	The gum::SplayTree to copy.

Returns

This gum::SplayTree.

Definition at line 392 of file splay_tpl.h.

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

                                                                                               {
    // avoid self assignment
    if (this != &from) {
      // for debugging purposes
      GUM_OP_CPY(SplayTree);
      // delete the old contents

      if (root) delete root;

      addr.clear();

      copy_(from);
    }

    return *this;
  }

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

i	The position of the element to return.

Exceptions

NotFound

Raised if no element was found.

Returns

Returns the element at the position n.

Definition at line 422 of file splay_tpl.h.

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

                                                                {
    int val = i;

    if (!root) {
      GUM_ERROR(NotFound, "The tree is empty !")
    } else if (val >= root->size) {
      GUM_ERROR(NotFound, "The index is too large !")
    } else {
      // The element exists
      // Find it
      SplayBinaryNode< Element >* act     = root;
      int                         pos_act = val - 1;
      bool                        next    = true;

      while (next) {
        if (!act->fg)
          pos_act = 0;
        else
          pos_act = act->fg->size;

        if (pos_act > val) {
          act = act->fg;
        } else if (pos_act < val) {
          act = act->fd;
          val -= (pos_act + 1);
        } else {
          next = false;
        }
      }

      root = act->splay();

      return root->elt;
    }
  }

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

i	The position of the element to return.

Exceptions

NotFound

Raised if no element was found.

Returns

Returns the element at the position n.

Definition at line 459 of file splay_tpl.h.

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

                                                                            {
    int val = i;

    if (!root) {
      GUM_ERROR(NotFound, "The tree is empty !")
    } else if (val >= root->size) {
      GUM_ERROR(NotFound, "The index is too large !")
    } else {
      // The element exists
      // Find it
      SplayBinaryNode< Element >* act     = root;
      int                         pos_act = val - 1;
      bool                        next    = true;

      while (next) {
        if (!act->fg)
          pos_act = 0;
        else
          pos_act = act->fg->size;

        if (pos_act > val) {
          act = act->fg;
        } else if (pos_act < val) {
          act = act->fd;
          val -= (pos_act + 1);
        } else {
          next = false;
        }
      }

      root = act->splay();

      return root->elt;
    }
  }

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

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

                                            {
    SplayBinaryNode< Element >* act = root;

    if (root) {
      if (root->fd)
        for (; act->fd; act = act->fd)
          ;

      act = act->splay();

      root = act->fg;

      if (root) root->pere = 0;

      act->fg = 0;

      delete act;
    }
  }

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

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

                                             {
    SplayBinaryNode< Element >* act = root;

    if (root) {
      if (root->fg)
        for (; act->fg; act = act->fg)
          ;

      act = act->splay();

      root = act->fd;

      if (root) root->pere = 0;

      act->fd = 0;

      delete act;
    }
  }

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

e	The element to push.

Definition at line 597 of file splay_tpl.h.

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

                                                             {
    SplayBinaryNode< Element >* act = root;

    if (root) {
      if (root->fd)
        for (; act->fd; act = act->fd)
          ;

      root = act->splay();

      root->fd = new SplayBinaryNode< Element >(e, addr, 0, 0, root);
    } else {
      root = new SplayBinaryNode< Element >(e, addr);
    }
  }

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

e	The element to push.

Definition at line 578 of file splay_tpl.h.

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

                                                              {
    SplayBinaryNode< Element >* act = root;

    if (root) {
      if (root->fg)
        for (; act->fg; act = act->fg)
          ;

      root = act->splay();

      root->fg = new SplayBinaryNode< Element >(e, addr, 0, 0, root);
    } else {
      root = new SplayBinaryNode< Element >(e, addr);
    }
  }

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

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

                                               {
    if (root)
      return root->size;
    else
      return Size(0);
  }

Here is the call 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

i	The position of the element (e) for split.

Returns

Returns a tree with all the elements greater than i.

Definition at line 668 of file splay_tpl.h.

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

                                                                     {
    GUM_ASSERT(i >= 0 && i < root->size);
    GUM_ASSERT(root != 0);

    if (i == 0) {
      // the tree will be empty
      // the returned tree is a copy of the present tree
      SplayTree< Element > s = *this;
      addr.clear();
      delete root;
      root = 0;
      return s;
    } else if (i == root->size - 1) {
      SplayTree< Element > s;
      return s;
    } else {
      // We will find the node at position i
      SplayBinaryNode< Element >* act = root;
      int                         pos = root->position();

      while (pos != i) {
        GUM_ASSERT(act != 0);

        if (i < pos) {
          act = act->fg;
        } else {
          act = act->fd;
        }

        pos = act->position();
      }

      // We reorganize the tree
      act->splay();

      // We take the first part
      root = act->fg;

      if (root) root->pere = 0;

      // We take the second part
      SplayTree< Element > s;

      s.root = act;

      s.root->fg = 0;

      Size size_ = 1;

      if (s.root->fd) size_ += s.root->fd->size;

      s.root->size = size_;

      // We remove the old nodes in the hash table
      // Complexity O(n) => very expensive
      removeInfo(act, addr);

      return s;
    }
  }

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

e	the 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 732 of file splay_tpl.h.

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

                                                                                 {
    GUM_ASSERT(root != 0);

    if (!addr.exists(e)) { GUM_ERROR(NotFound, "not enough elements in the splay tree") }

    // We will find the node at position i
    SplayBinaryNode< Element >* act = addr[e];

    // We reorganize the tree
    act->splay();

    // We take the two parts
    SplayTree< Element > s;

    s.root = act->fd;

    if (s.root) { s.root->pere = 0; }

    root = act->fg;

    if (root) root->pere = 0;

    act->fg = 0;

    // We remove the old nodes in the hash table
    // Complexity O(n) => very expensive
    removeInfo(act, addr);

    act->fd = 0;

    delete act;

    return s;
  }

Here is the call graph for this function:

Friends And Related Function Documentation

operator<<

template<class Element >

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

friend

Friendly to display.

Definition at line 800 of file splay_tpl.h.

                                                                                {
    out << "|[";

    if (s.root) out << *s.root;

    out << "]|";

    return out;
  }

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 416 of file splay.h.

root

template<class Element >

SplayBinaryNode< Element >* gum::SplayTree< Element >::root

protected

Root of the tree.

Definition at line 413 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