// Copyright (C) 2003 Davis E. King (davis@dlib.net)

// License: Boost Software License See LICENSE.txt for the full license.

#ifndef DLIB_SEQUENCE_KERNEl_1_

#define DLIB_SEQUENCE_KERNEl_1_

#include "sequence_kernel_abstract.h"

#include "../algs.h"

#include "../interfaces/enumerable.h"

#include "../interfaces/remover.h"

#include "../serialize.h"

namespace dlib

{

template <

typename T,

typename mem_manager = default_memory_manager

>

class sequence_kernel_1 : public enumerable<T>,

public remover<T>

{

/*!

INITIAL VALUE

- tree_root == 0

- tree_size == 0

- at_start_ == true

- current_element == 0

- stack == array of 50 node pointers

- stack_pos == 0

CONVENTION

- if (tree_size > 0)

- tree_root == pointer to the root node of the binary search tree

- else

- tree_root == 0

- stack[stack_pos-1] == pop()

- current_element_valid() == (current_element != 0)

- at_start_ == at_start()

- if (current_element != 0 && current_element != tree_root) then

- stack[stack_pos-1] == the parent of the node pointed to by current_element

- if (current_element_valid()) then

- element() == current_element->item

- tree_size == size()

- (*this)[i] == return_reference(i)

- for all nodes:

- left_size == the number of elements in the left subtree.

- left points to the left subtree or 0 if there is no left subtree.

- right points to the right subtree or 0 if there is no right subtree.

- all elements in a left subtree have a position in the sequence < that

of the root of the current tree.

- all elements in a right subtree have a position in the

sequence > that of the root of the current tree.

- item is the sequence element for that node.

- balance:

- balance == 0 if both subtrees have the same height

- balance == -1 if the left subtree has a height that is

greater than the height of the right subtree by 1

- balance == 1 if the right subtree has a height that is

greater than the height of the left subtree by 1

- for all subtrees:

- the height of the left and right subtrees differ by at most one

!*/

class node

{

public:

node* left;

node* right;

unsigned long left_size;

T item;

signed char balance;

};

public:

typedef T type;

typedef mem_manager mem_manager_type;

sequence_kernel_1 (

) :

tree_root(0),

tree_size(0),

stack(ppool.allocate_array(50)),

current_element(0),

at_start_(true),

stack_pos(0)

{}

virtual ~sequence_kernel_1 (

);

inline void clear (

);

void add (

unsigned long pos,

T& item

);

void remove (

unsigned long pos,

T& item

);

void cat (

sequence_kernel_1& item

);

const T& operator[] (

unsigned long pos

) const;

T& operator[] (

unsigned long pos

);

inline void swap (

sequence_kernel_1& item

);

// functions from the remover interface

inline void remove_any (

T& item

);

// functions from the enumerable interface

inline size_t size (

) const;

bool at_start (

) const;

inline void reset (

) const;

bool current_element_valid (

) const;

const T& element (

) const;

T& element (

);

bool move_next (

) const;

private:

void delete_nodes (

node* t

);

/*!

requires

- t == a pointer to a valid node

ensures

- deletes t and all its sub nodes.

!*/

inline void rotate_left (

node*& t

);

/*!

requires

- t->balance == 2

- t->right->balance == 0 or 1

ensures

- #t is still a binary search tree

- #t->balance is between 1 and -1

- #t now has a height smaller by 1 if #t->balance == 0

!*/

inline void rotate_right (

node*& t

);

/*!

requires

- t->balance == -2

- t->left->balance == 0 or -1

ensures

- #t is still a binary search tree

- #t->balance is between 1 and -1

- #t now has a height smaller by 1 if #t->balance == 0

!*/

inline void double_rotate_right (

node*& t

);

/*!

requires

- #t->balance == -2

- #t->left->balance == 1

ensures

- #t is still a binary search tree

- #t now has a balance of 0

- #t now has a height smaller by 1

!*/

inline void double_rotate_left (

node*& t

);

/*!

requires

- #t->balance == 2

- #t->right->balance == -1

ensures

- #t is still a binary search tree

- #t now has a balance of 0 and

- #t now has a height smaller by 1

!*/

bool remove_least_element_in_tree (

node*& t,

T& item

);

/*!

requires

- t != 0 (i.e. there must be something in the tree to remove)

ensures

- the least node in t has been removed

- the least node element in t has been put into #item

- #t is still a binary search tree

- returns false if the height of the tree has not changed

- returns true if the height of the tree has shrunk by one

!*/

bool add_to_tree (

node*& t,

unsigned long pos,

T& item

);

/*!

requires

- pos <= the number of items in the tree

ensures

- item has been added to #t

- #return_reference(pos) == item

- the convention is still satisfied

- #item has an initial value for its type

- returns false if the height of the tree has not changed

- returns true if the height of the tree has grown by one

!*/

bool remove_from_tree (

node*& t,

unsigned long pos,

T& item

);

/*!

requires

- there is an item in the tree associated with pos

ensures

- the element in the tree associated with pos has been removed

and put into #item

- the convention is still satisfied

- returns false if the height of the tree has not changed

- returns true if the height of the tree has shrunk by one

!*/

const T& return_reference (

const node* t,

unsigned long pos

) const;

/*!

requires

- there is an item in the tree associated with pos

ensures

- returns a const reference to the item in the tree associated with pos

!*/

T& return_reference (

node* t,

unsigned long pos

);

/*!

requires

- there is an item in the tree associated with pos

ensures

- returns a non-const reference to the item in the tree associated

with pos

!*/

inline bool keep_node_balanced (

node*& t

);

/*!

requires

- t != 0

ensures

- if (t->balance is < 1 or > 1) then

- keep_node_balanced() will ensure that t->balance == 0, -1, or 1

- returns true if it made the tree one height shorter

- returns false if it didn't change the height

!*/

void push (

node* n

) const { stack[stack_pos] = n; ++stack_pos; }

/*!

ensures

- pushes n onto the stack

!*/

node* pop (

) const { --stack_pos; return stack[stack_pos]; }

/*!

ensures

- pops the top of the stack and returns it

!*/

// data members

typename mem_manager::template rebind<node>::other pool;

typename mem_manager::template rebind<node*>::other ppool;

node* tree_root;

unsigned long tree_size;

mutable node** stack;

mutable node* current_element;

mutable bool at_start_;

mutable unsigned char stack_pos;

// restricted functions

sequence_kernel_1(sequence_kernel_1&); // copy constructor

sequence_kernel_1& operator=(sequence_kernel_1&); // assignment operator

};

template <

typename T,

typename mem_manager

>

inline void swap (

sequence_kernel_1<T,mem_manager>& a,

sequence_kernel_1<T,mem_manager>& b

) { a.swap(b); }

template <

typename T,

typename mem_manager

>

void deserialize (

sequence_kernel_1<T,mem_manager>& item,

std::istream& in

)

{

try

{

item.clear();

unsigned long size;

deserialize(size,in);

T temp;

for (unsigned long i = 0; i < size; ++i)

{

deserialize(temp,in);

item.add(i,temp);

}

}

catch (serialization_error& e)

{

item.clear();

throw serialization_error(e.info + "\n while deserializing object of type sequence_kernel_1");

}

}

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

// member function definitions

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

sequence_kernel_1<T,mem_manager>::

~sequence_kernel_1 (

)

{

ppool.deallocate_array(stack);

if (tree_size > 0)

{

delete_nodes(tree_root);

}

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

swap (

sequence_kernel_1<T,mem_manager>& item

)

{

exchange(stack,item.stack);

exchange(stack_pos,item.stack_pos);

pool.swap(item.pool);

ppool.swap(item.ppool);

node* tree_root_temp = item.tree_root;

unsigned long tree_size_temp = item.tree_size;

node* current_element_temp = item.current_element;

bool at_start_temp = item.at_start_;

item.tree_root = tree_root;

item.tree_size = tree_size;

item.current_element = current_element;

item.at_start_ = at_start_;

tree_root = tree_root_temp;

tree_size = tree_size_temp;

current_element = current_element_temp;

at_start_ = at_start_temp;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

size_t sequence_kernel_1<T,mem_manager>::

size (

) const

{

return tree_size;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

const T& sequence_kernel_1<T,mem_manager>::

operator[] (

unsigned long pos

) const

{

return return_reference(tree_root,pos);

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

T& sequence_kernel_1<T,mem_manager>::

operator[] (

unsigned long pos

)

{

return return_reference(tree_root,pos);

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

add (

unsigned long pos,

T& item

)

{

add_to_tree(tree_root,pos,item);

++tree_size;

// reset the enumerator

reset();

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

remove (

unsigned long pos,

T& item

)

{

remove_from_tree(tree_root,pos,item);

--tree_size;

// reset the enumerator

reset();

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

cat (

sequence_kernel_1<T,mem_manager>& item

)

{

for (unsigned long i = 0; i < item.tree_size; ++i)

{

add_to_tree(

tree_root,

tree_size,

return_reference(item.tree_root,i)

);

++tree_size;

}

item.clear();

// reset the enumerator

reset();

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

clear (

)

{

if (tree_size > 0)

{

delete_nodes(tree_root);

tree_root = 0;

tree_size = 0;

}

// reset the enumerator

reset();

}

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

// enumerable function definitions

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

bool sequence_kernel_1<T,mem_manager>::

at_start (

) const

{

return at_start_;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

reset (

) const

{

at_start_ = true;

current_element = 0;

stack_pos = 0;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

bool sequence_kernel_1<T,mem_manager>::

current_element_valid (

) const

{

return (current_element != 0);

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

const T& sequence_kernel_1<T,mem_manager>::

element (

) const

{

return current_element->item;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

T& sequence_kernel_1<T,mem_manager>::

element (

)

{

return current_element->item;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

bool sequence_kernel_1<T,mem_manager>::

move_next (

) const

{

// if we haven't started iterating yet

if (at_start_)

{

at_start_ = false;

if (tree_size == 0)

{

return false;

}

else

{

// find the first element in the tree

current_element = tree_root;

node* temp = current_element->left;

while (temp != 0)

{

push(current_element);

current_element = temp;

temp = current_element->left;

}

return true;

}

}

else

{

if (current_element == 0)

{

return false;

}

else

{

node* temp;

bool went_up; // true if we went up the tree from a child node to parent

bool from_left = false; // true if we went up and were coming from a left child node

// find the next element in the tree

if (current_element->right != 0)

{

// go right and down

temp = current_element;

push(current_element);

current_element = temp->right;

went_up = false;

}

else

{

// go up to the parent if we can

if (current_element == tree_root)

{

// in this case we have iterated over all the element of the tree

current_element = 0;

return false;

}

went_up = true;

node* parent = pop();

from_left = (parent->left == current_element);

// go up to parent

current_element = parent;

}

while (true)

{

if (went_up)

{

if (from_left)

{

// in this case we have found the next node

break;

}

else

{

if (current_element == tree_root)

{

// in this case we have iterated over all the elements

// in the tree

current_element = 0;

return false;

}

// we should go up

node* parent = pop();

from_left = (parent->left == current_element);

current_element = parent;

}

}

else

{

// we just went down to a child node

if (current_element->left != 0)

{

// go left

went_up = false;

temp = current_element;

push(current_element);

current_element = temp->left;

}

else

{

// if there is no left child then we have found the next node

break;

}

}

}

return true;

}

}

}

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

// remover function definitions

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

remove_any (

T& item

)

{

remove(0,item);

}

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

// private member function definitions

// ----------------------------------------------------------------------------------------

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

rotate_left (

node*& t

)

{

// set the new balance numbers

if (t->right->balance == 1)

{

t->balance = 0;

t->right->balance = 0;

}

else

{

t->balance = 1;

t->right->balance = -1;

}

// perform the rotation

node* temp = t->right;

t->right = temp->left;

temp->left = t;

t = temp;

// set left_size to its correct value

t->left_size += t->left->left_size + 1;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

rotate_right (

node*& t

)

{

// set the new balance numbers

if (t->left->balance == -1)

{

t->balance = 0;

t->left->balance = 0;

}

else

{

t->balance = -1;

t->left->balance = 1;

}

// preform the rotation

node* temp = t->left;

t->left = temp->right;

temp->right = t;

t = temp;

// set left_size to its correct value

t->right->left_size -= t->left_size + 1;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

double_rotate_right (

node*& t

)

{

node* temp = t;

t = t->left->right;

temp->left->right = t->left;

t->left = temp->left;

temp->left = t->right;

t->right = temp;

if (t->balance < 0)

{

t->left->balance = 0;

t->right->balance = 1;

}

else if (t->balance > 0)

{

t->left->balance = -1;

t->right->balance = 0;

}

else

{

t->left->balance = 0;

t->right->balance = 0;

}

t->balance = 0;

// set left_size to its correct value

t->left_size += t->left->left_size + 1;

t->right->left_size -= t->left_size + 1;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

void sequence_kernel_1<T,mem_manager>::

double_rotate_left (

node*& t

)

{

node* temp = t;

t = t->right->left;

temp->right->left = t->right;

t->right = temp->right;

temp->right = t->left;

t->left = temp;

if (t->balance < 0)

{

t->left->balance = 0;

t->right->balance = 1;

}

else if (t->balance > 0)

{

t->left->balance = -1;

t->right->balance = 0;

}

else

{

t->left->balance = 0;

t->right->balance = 0;

}

t->balance = 0;

// set left_size to its correct value

t->right->left_size -= t->left_size + 1;

t->left_size += t->left->left_size + 1;

}

// ----------------------------------------------------------------------------------------

template <

typename T,

typename mem_manager

>

bool sequence_kernel_1<T,mem_manager>::

remove_least_element_in_tree (

node*& t,

T& item

)

{

// make a reference to the current node so we don't have to dereference

// a pointer a bunch of times

node& tree = *t;

// if the left tree is an empty tree

if ( tree.left == 0)

{

// swap nodes element into item

exchange(tree.item,item);

// plug hole left by removing this node

t = tree.right;

// delete the node that was just removed

tree.right = 0;

delete_nodes(&tree);

// return that the height of this part of the tree has decreased

return true;

}

else

{

// subtract one from the left size

--tree.left_size;

// keep going left

// if remove made the tree one height shorter

if ( remove_least_element_in_tree(tree.left,item) )

{

// if this caused the current tree to strink then report that

if ( tree.balance == -1)

{

++tree.balance;

return true;

}

else

{

++tree.balance;

return keep_node_balanced(t);

}

}

return false;

}

}

// ----------------------------------------------------------------------------------------

template <

typename T,