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

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

#ifndef DLIB_SEQUENCE_KERNEl_2_

#define DLIB_SEQUENCE_KERNEl_2_

#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_2 : public enumerable<T>,

public remover<T>

{

/*!

INITIAL VALUE

sequence_size == 0

at_start_ == true

current_enumeration_node == 0

CONVENTION

sequence_size == the number of elements in the sequence

at_start_ == at_start()

(current_enumeration_node!=0) == current_element_valid()

if (current_enumeration_node!=0) then

current_enumeration_node->item == element()

current_enumeration_pos == the position of the node pointed to by

current_enumeration_node

if ( sequence_size > 0 )

{

current_node == pointer to a node in the linked list and

current_node->right->right->... eventually == current_node and

current_node->left->left->... eventually == current_node and

current_pos == the position in the sequence of

current_node->item

}

!*/

struct node {

T item;

node* right;

node* left;

};

public:

typedef T type;

typedef mem_manager mem_manager_type;

sequence_kernel_2 (

) :

sequence_size(0),

at_start_(true),

current_enumeration_node(0)

{}

virtual ~sequence_kernel_2 (

);

inline void clear (

);

void add (

unsigned long pos,

T& item

);

void remove (

unsigned long pos,

T& item

);

void cat (

sequence_kernel_2& item

);

const T& operator[] (

unsigned long pos

) const;

T& operator[] (

unsigned long pos

);

void swap (

sequence_kernel_2& 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* current_node,

unsigned long sequence_size

);

/*!

requires

CONVENTION IS CORRECT

ensures

all memory associated with the ring of nodes has been freed

!*/

void move_to_pos (

node*& current_node,

unsigned long& current_pos,

unsigned long pos,

unsigned long size

) const;

/*!

requires

everything in the CONVENTION is correct and

there is a node corresponding to pos in the CONVENTION and

0 <= pos < size

ensures

current_pos == pos and

current_node->item is the item in the sequence associated with

position pos

!*/

// data members

unsigned long sequence_size;

mutable node* current_node;

mutable unsigned long current_pos;

mutable bool at_start_;

mutable node* current_enumeration_node;

mutable unsigned long current_enumeration_pos;

// restricted functions

sequence_kernel_2(sequence_kernel_2&); // copy constructor

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

};

template <

typename T,

typename mem_manager

>

inline void swap (

sequence_kernel_2<T,mem_manager>& a,

sequence_kernel_2<T,mem_manager>& b

) { a.swap(b); }

template <

typename T,

typename mem_manager

>

void deserialize (

sequence_kernel_2<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_2");

}

}

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

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

// member function definitions

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

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

template <

typename T,

typename mem_manager

>

sequence_kernel_2<T,mem_manager>::

~sequence_kernel_2 (

)

{

delete_nodes(current_node,sequence_size);

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

clear (

)

{

if (sequence_size != 0)

{

delete_nodes(current_node,sequence_size);

sequence_size = 0;

}

// reset the enumerator

reset();

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

add (

unsigned long pos,

T& item

)

{

// make new node and swap item into it

node* new_node = new node;

exchange(item,new_node->item);

if (sequence_size > 0)

{

if (pos == sequence_size)

{

move_to_pos(current_node,current_pos,pos-1,sequence_size);

node& n_node = *new_node;

node& c_node = *current_node;

// make new node point to the nodes to its left and right

n_node.right = c_node.right;

n_node.left = current_node;

// make the left node point back to new_node

c_node.right->left = new_node;

// make the right node point back to new_node

c_node.right = new_node;

current_pos = pos;

}

else

{

move_to_pos(current_node,current_pos,pos,sequence_size);

node& n_node = *new_node;

node& c_node = *current_node;

// make new node point to the nodes to its left and right

n_node.right = current_node;

n_node.left = c_node.left;

// make the left node point back to new_node

c_node.left->right = new_node;

// make the right node point back to new_node

c_node.left = new_node;

}

}

else

{

current_pos = 0;

new_node->left = new_node;

new_node->right = new_node;

}

// make the new node the current node

current_node = new_node;

++sequence_size;

// reset the enumerator

reset();

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

remove (

unsigned long pos,

T& item

)

{

move_to_pos(current_node,current_pos,pos,sequence_size);

node& c_node = *current_node;

exchange(c_node.item,item);

node* temp = current_node;

// close up gap left by remove

c_node.left->right = c_node.right;

c_node.right->left = c_node.left;

current_node = c_node.right;

--sequence_size;

delete temp;

// reset the enumerator

reset();

}

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

template <

typename T,

typename mem_manager

>

const T& sequence_kernel_2<T,mem_manager>::

operator[] (

unsigned long pos

) const

{

move_to_pos(current_node,current_pos,pos,sequence_size);

return current_node->item;

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

cat (

sequence_kernel_2<T,mem_manager>& item

)

{

if (item.sequence_size > 0)

{

if (sequence_size > 0)

{

// move both sequences to a convenient location

move_to_pos(current_node,current_pos,0,sequence_size);

item.move_to_pos (

item.current_node,

item.current_pos,

item.sequence_size-1,

item.sequence_size

);

// make copies of poitners

node& item_right = *item.current_node->right;

node& left = *current_node->left;

item.current_node->right = current_node;

current_node->left = item.current_node;

left.right = &item_right;

item_right.left = &left;

// set sizes

sequence_size += item.sequence_size;

item.sequence_size = 0;

}

else

{

// *this is empty so just swap

item.swap(*this);

}

}

item.clear();

// reset the enumerator

reset();

}

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

template <

typename T,

typename mem_manager

>

T& sequence_kernel_2<T,mem_manager>::

operator[] (

unsigned long pos

)

{

move_to_pos(current_node,current_pos,pos,sequence_size);

return current_node->item;

}

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

template <

typename T,

typename mem_manager

>

size_t sequence_kernel_2<T,mem_manager>::

size (

) const

{

return sequence_size;

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

swap (

sequence_kernel_2<T,mem_manager>& item

)

{

unsigned long sequence_size_temp = item.sequence_size;

node* current_node_temp = item.current_node;

unsigned long current_pos_temp = item.current_pos;

bool at_start_temp = item.at_start_;

node* current_enumeration_node_temp = item.current_enumeration_node;

unsigned long current_enumeration_pos_temp = item.current_enumeration_pos;

item.sequence_size = sequence_size;

item.current_node = current_node;

item.current_pos = current_pos;

item.at_start_ = at_start_;

item.current_enumeration_node = current_enumeration_node;

item.current_enumeration_pos = current_enumeration_pos;

sequence_size = sequence_size_temp;

current_node = current_node_temp;

current_pos = current_pos_temp;

at_start_ = at_start_temp;

current_enumeration_node = current_enumeration_node_temp;

current_enumeration_pos = current_enumeration_pos_temp;

}

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

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

// enumerable function definitions

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

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

template <

typename T,

typename mem_manager

>

bool sequence_kernel_2<T,mem_manager>::

at_start (

) const

{

return at_start_;

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

reset (

) const

{

at_start_ = true;

current_enumeration_node = 0;

}

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

template <

typename T,

typename mem_manager

>

bool sequence_kernel_2<T,mem_manager>::

current_element_valid (

) const

{

return (current_enumeration_node!=0);

}

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

template <

typename T,

typename mem_manager

>

const T& sequence_kernel_2<T,mem_manager>::

element (

) const

{

return current_enumeration_node->item;

}

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

template <

typename T,

typename mem_manager

>

T& sequence_kernel_2<T,mem_manager>::

element (

)

{

return current_enumeration_node->item;

}

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

template <

typename T,

typename mem_manager

>

bool sequence_kernel_2<T,mem_manager>::

move_next (

) const

{

if (at_start_ && sequence_size>0)

{

move_to_pos(current_node,current_pos,0,sequence_size);

current_enumeration_node = current_node;

current_enumeration_pos = 0;

}

else if (current_enumeration_node!=0)

{

++current_enumeration_pos;

if (current_enumeration_pos<sequence_size)

{

current_enumeration_node = current_enumeration_node->right;

}

else

{

// we have reached the end of the sequence

current_enumeration_node = 0;

}

}

at_start_ = false;

return (current_enumeration_node!=0);

}

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

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

// remover function definitions

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

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

remove_any (

T& item

)

{

remove(0,item);

}

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

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

// private member function definitions

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

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

delete_nodes (

node* current_node,

unsigned long sequence_size

)

{

node* temp;

while (sequence_size)

{

temp = current_node->right;

delete current_node;

current_node = temp;

--sequence_size;

}

}

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

template <

typename T,

typename mem_manager

>

void sequence_kernel_2<T,mem_manager>::

move_to_pos (

node*& current_node,

unsigned long& current_pos,

unsigned long pos,

unsigned long size

) const

{

if ( current_pos > pos)

{

// number of hops in each direction needed to reach pos

unsigned long right = size + pos - current_pos;

unsigned long left = current_pos - pos;

current_pos = pos;

if (left < right)

{

// move left to position pos

for (; left > 0; --left)

current_node = current_node->left;

}

else

{

// move left to position pos

for (; right > 0; --right)

current_node = current_node->right;

}

}

else if (current_pos != pos)

{

// number of hops in each direction needed to reach pos

unsigned long right = pos - current_pos;

unsigned long left = size - pos + current_pos;

current_pos = pos;

if (left < right)

{

// move left to position pos

for (; left > 0; --left)

current_node = current_node->left;

}

else

{

// move left to position pos

for (; right > 0; --right)

current_node = current_node->right;

}

}

}

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

}

#endif // DLIB_SEQUENCE_KERNEl_2_