dlib C++ Library - sequence_kernel_2.h

// 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_