#ifndef _INCL_JL_DLIST
#define _INCL_JL_DLIST
// JL_Dlist.h: STL-compatible doubly-linked list template.
// Designed to use less memory than the STL list<>, so it
// is useful when many small lists must be stored.
// This is not as general-purpose as list<>.
// Many of the more advanced methods of STL list<> have not
// been implemented.
/***************************************************************************
*
* Copyright (c) 1994 Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
**************************************************************************
* Copyright (c) 1996 Empathy Software
* The above notice applies to portions written by Empathy Software
**************************************************************************/
#ifdef _MSC_VER
// #pragma warning (disable:4786) // long debug names
// #pragma warning (disable:4146) // unary minus operator applied to unsigned type
// #pragma warning (disable:4018) // '>' : signed/unsigned mismatch
#endif
#include "STLIncomplete.h"
#include <functional>
#include <algorithm>
#include <iterator>
#include <memory>
#include <assert.h>
using namespace std;
// declare this outside of the class because of the multitude of
// namespace vs class scope bugs in various compilers.
template<class T, class D> struct _JL_DList_bdit :
public iterator<bidirectional_iterator_tag, T, D> {};
// Helper functions
// You may need to rewrite this if your compiler does not support
// calling a destructor directly (especially for a builtin types).
template <class T> inline void JL_DList_destroy(T* ptr)
{
ptr->~T();
}
// class defintition
template <class T, class Allocator STLI_DEFAULT_ALLOCATOR_ARG(T) >
class JL_DList
{
#undef THIS_ARG
#ifdef _DEBUG
#define THIS_ARG ,this
#else
#define THIS_ARG
#endif
protected:
struct list_node;
friend struct list_node;
public:
//
// types
//
typedef T value_type;
typedef Allocator allocator_type;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
typedef JL_DList<T, Allocator> list_type;
#if STLI_STANDARD_ALLOCATOR
typedef typename allocator_type::types<T>::reference reference;
typedef typename allocator_type::types<T>::const_reference const_reference;
typedef typename allocator_type::types<T>::pointer pointer;
typedef typename allocator_type::types<T>::const_pointer const_pointer;
#else
// Use a hack that works with homogeneous memory models
typedef T& reference;
typedef const T& const_reference;
typedef T* pointer;
typedef const T* const_pointer;
#endif
protected:
#if STLI_STANDARD_ALLOCATOR
typedef typename allocator_type::types<list_node>::pointer link_type;
typedef typename allocator_type::types<list_node>::const_pointer const_link_type;
#else
// Use a hack that works with homogeneous memory models
typedef list_node* link_type;
typedef const list_node* const_link_type;
#endif
struct list_node
{
link_type next;
link_type prev;
T data;
};
size_type length;
list_node end_node;
Allocator the_allocator;
#ifdef _DEBUG
enum { MAGIC = 0x83F0 };
unsigned short magic;
void assertValid() const { assert(magic == MAGIC); }
#else
void assertValid() const {}
#endif
#if STLI_STANDARD_ALLOCATOR
link_type alloc_node()
{
return the_allocator.allocate<list_node,void>(1);
}
void free_node(link_type node)
{
assert(node != &end_node);
the_allocator.deallocate<list_node>(node);
}
#else
link_type alloc_node()
{
return (link_type)STLI_BYTE_ALLOCATE(the_allocator, sizeof(list_node));
}
void free_node(link_type node)
{
STLI_BYTE_DEALLOCATE(the_allocator, (void*)node);
}
#endif
public:
class iterator;
class const_iterator;
class iterator : public _JL_DList_bdit<T, difference_type>
{
friend class JL_DList<T, Allocator>;
friend class const_iterator;
protected:
link_type node;
#ifdef _DEBUG
list_type* owner;
#endif
iterator(
link_type node_
#ifdef _DEBUG
,list_type* owner_
#endif
) :
node(node_)
#ifdef _DEBUG
,owner(owner_)
#endif
{}
public:
iterator () : node(0) {}
bool operator== (const iterator& rhs) const
{
#ifdef _DEBUG
assert(owner == rhs.owner);
#endif
return node == rhs.node;
}
bool operator != (const iterator& rhs) const
{
return !(*this == rhs);
}
reference operator* () const { return (*node).data; }
// increment/decrement
iterator& operator++ ()
{
// prefix
#ifdef _DEBUG
assert(*this != owner->end());
#endif
node = node->next; return *this;
}
iterator operator++ (int)
{
// postfix
#ifdef _DEBUG
assert(*this != owner->end());
#endif
iterator tmp = *this; ++*this; return tmp;
}
iterator& operator-- ()
{
// prefix
#ifdef _DEBUG
assert(*this != owner->begin());
#endif
node = node->prev; return *this;
}
iterator operator-- (int)
{
// postfix
#ifdef _DEBUG
assert(*this != owner->begin());
#endif
iterator tmp = *this; --*this; return tmp;
}
}; // iterator
class const_iterator : public _JL_DList_bdit<T, difference_type>
{
friend class JL_DList<T, Allocator>;
protected:
const_link_type node;
#ifdef _DEBUG
const list_type* owner;
#endif
const_iterator(
const_link_type node_
#ifdef _DEBUG
,const list_type* owner_
#endif
) :
node(node_)
#ifdef _DEBUG
,owner(owner_)
#endif
{}
public:
const_iterator () : node(0) {}
const_iterator (const iterator& rhs) :
node(rhs.node)
#ifdef _DEBUG
,owner(rhs.owner)
#endif
{}
bool operator== (const const_iterator& rhs) const
{
#ifdef _DEBUG
assert(owner == rhs.owner);
#endif
return node == rhs.node;
}
bool operator != (const const_iterator& rhs) const
{
return !(*this == rhs);
}
const_reference operator*() const { return (*node).data; }
// iterator increment/decrement
const_iterator& operator++ ()
{
// prefix
#ifdef _DEBUG
assert(*this != owner->end());
#endif
node = node->next; return *this;
}
const_iterator operator++ (int)
{
// postfix
#ifdef _DEBUG
assert(*this != owner->end());
#endif
const_iterator tmp = *this; ++*this; return tmp;
}
const_iterator& operator-- ()
{
// prefix
#ifdef _DEBUG
assert(*this != owner->begin());
#endif
node = node->prev;
return *this;
}
const_iterator operator-- (int)
{
// postfix
#ifdef _DEBUG
assert(*this != owner->begin());
#endif
const_iterator tmp = *this;
--*this;
return tmp;
}
}; // const_iterator
typedef reverse_bidirectional_iterator<
iterator,
value_type,
reference,
pointer,
difference_type
> reverse_iterator;
typedef reverse_bidirectional_iterator<
const_iterator,
value_type,
const_reference,
const_pointer,
difference_type
> const_reverse_iterator;
//
// constructors
//
// Default ctor
JL_DList(
const Allocator& alloc = Allocator()
) :
length(0),
the_allocator(alloc)
#ifdef _DEBUG
,magic(MAGIC)
#endif
{
end_node.next = end_node.prev = &end_node;
}
// iterator-range-copy ctor
#if STLI_MEMBER_TEMPLATES
// Can insert from any list
template<class InputIterator> JL_DList(
InputIterator input_first,
InputIterator input_last,
Allocator alloc = Allocator()
)
#else
// Can only insert from identically-typed list
JL_DList(
const_iterator input_first,
const_iterator input_last,
Allocator alloc = Allocator()
)
#endif
:
length(0),
the_allocator(alloc)
#ifdef _DEBUG
,magic(MAGIC)
#endif
{
#ifdef _DEBUG
assert(input_first.owner == input_last.owner);
#endif
end_node.next = end_node.prev = &end_node;
insert(begin(), input_first, input_last);
}
// Copy ctor
JL_DList(
const list_type& rhs
) :
length(0),
the_allocator(rhs.get_allocator())
#ifdef _DEBUG
,magic(MAGIC)
#endif
{
end_node.next = end_node.prev = &end_node;
insert(begin(), rhs.begin(), rhs.end());
}
//
// Destructor
//
~JL_DList()
{
assertValid();
clear();
#ifdef _DEBUG
magic = 0;
#endif
}
// Assignment operator
JL_DList<T,Allocator>& operator=(
const list_type& rhs
)
{
assertValid();
if (this != &rhs)
{
assign(rhs.begin(), rhs.end());
}
return *this;
}
#if STLI_MEMBER_TEMPLATES
// Can assign from any iterator range
template<class InputIterator>
void assign (InputIterator input_first, InputIterator input_last)
#else
// Can only assign from compatible iterator range
void assign (const_iterator input_first, const_iterator input_last)
#endif
{
assertValid();
#ifdef _DEBUG
assert(input_first.owner == input_last.owner);
#endif
clear();
insert(begin(), input_first, input_last);
}
allocator_type get_allocator() const
{
assertValid();
return the_allocator;
}
//
// Iterators.
//
iterator begin() {
assertValid();
return iterator(end_node.next THIS_ARG);
}
const_iterator begin() const {
assertValid();
return const_iterator(end_node.next THIS_ARG);
}
iterator end() {
assertValid();
return iterator(&end_node THIS_ARG);
}
const_iterator end() const {
assertValid();
return const_iterator(&end_node THIS_ARG);
}
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
//
// Capacity.
//
bool empty() const { assertValid(); return length == 0; }
size_type size() const { assertValid(); return length; }
// What is the maximum size of the list?
// You may have to tweak the allocator call for non-standard allocators.
size_type max_size() const {
assertValid();
return the_allocator.max_size();
}
//
// Resizing the list
//
void resize(size_type new_size) { resize(new_size, T()); }
void resize(size_type new_size, T value)
{
while (length < new_size)
{
push_back(value);
}
while (length > new_size)
{
pop_back();
}
}
//
// Element access to list ends
//
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }
//
// Insert rhs before position.
//
iterator insert(
iterator position,
const T& rhs
)
{
assertValid();
#ifdef _DEBUG
assert(position.owner == this);
#endif
link_type tmp = alloc_node();
#if STLI_STANDARD_ALLOCATOR
the_allocator.construct(the_allocator.address((*tmp).data), rhs);
#else
// Use "placement new" directly
new ((void*)&tmp->data) T(rhs);
#endif
tmp->next = position.node;
tmp->prev = position.node->prev;
tmp->prev->next = tmp;
tmp->next->prev = tmp;
++length;
return iterator(tmp THIS_ARG);
}
//
// Insert a range into this list
//
#if STLI_MEMBER_TEMPLATES
// Can insert from any iterator
template<class InputIterator>
void insert(
iterator position,
InputIterator input_first,
InputIterator input_last
)
#else
// Can only insert from compatible iterator
void insert(
iterator position,
const_iterator input_first,
const_iterator input_last
)
#endif
{
while (input_first != input_last)
{
insert(position, *input_first);
input_first++;
}
}
//
// Remove an element from this list
//
iterator erase(iterator position)
{
#ifdef _DEBUG
assert(position.owner == this);
#endif
assert(position != end());
// Save an iterator pointing at next element
iterator tmp(position.node->next THIS_ARG);
// Unlink this node from the list
position.node->prev->next = position.node->next;
position.node->next->prev = position.node->prev;
// Destruct the "T" object in the node
#if STLI_STANDARD_ALLOCATOR
the_allocator.destroy(the_allocator.address(position.node->data));
#else
// call destructor helper function
JL_DList_destroy(&position.node->data);
#endif
// Free the node memory
free_node(position.node);
--length;
return tmp;
}
//
// Remove a range of elements from the list
//
iterator erase(
iterator first,
iterator last
)
{
while (first != last)
{
first = erase(first);
}
return last;
}
//
// Add/remove elements to front/end of list
//
void push_front(const T& val) { insert(begin(), val); }
void push_back(const T& val) { insert(end(), val); }
void pop_front() { assert(!empty()); erase(begin()); }
void pop_back() { assert(!empty()); erase(--end()); }
// Remove all elements from the list
void clear() { erase(begin(),end()); }
#undef THIS_ARG
};
// Non-member function for comparison of two lists
template <class T, class Allocator>
inline bool operator==(
const JL_DList<T,Allocator>& lhs,
const JL_DList<T,Allocator>& rhs
)
{
return
lhs.size() == rhs.size() &&
equal(lhs.begin(), lhs.end(), rhs.begin());
}
// Non-member template function for lexicographical comparison of two lists
template <class T, class Allocator>
inline bool operator< (
const JL_DList<T,Allocator>& lhs,
const JL_DList<T,Allocator>& rhs
)
{
return lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
#endif