#ifndef __TYPETRAIT__H__
#define __TYPETRAIT__H__
#include <cstddef>
namespace stc{
class trueType{};
class falseType{};
template <typename type>
class typeTrait{
public:
typedef trueType thisDummyMemberMustBeFirst;
typedef falseType hasTrivalDefaultCtor;
typedef falseType hasTrivalCopyCtor;
typedef falseType hasTrivalAssignmentOperator;
typedef falseType hasTrivalDtor;
typedef falseType isPODType;
};
template <> class typeTrait < signed char > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned char > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < wchar_t > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < short > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned short > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < int > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned int > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long long> {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < unsigned long > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < float > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < double > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < long double > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <class type> class typeTrait < type* > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
template <> class typeTrait < bool > {
public:
typedef trueType hasTrivalDefaultCtor;
typedef trueType hasTrivalCopyCtor;
typedef trueType hasTrivalAssignmentOperator;
typedef trueType hasTrivalDtor;
typedef trueType isPODType;
};
}
#endif
#ifndef __ITERATOR__TRAIT__H__
#define __ITERATOR__TRAIT__H__
#include <cstddef>
namespace stc{
class inputIteratorTag{};
class outputIteratorTag{};
class forwardIteratorTag{};
class bidirectionalIteratorTag{};
class randomAccessIteratorTag{};
template < typename type,
typename category = forwardIteratorTag,
typename distance = std::ptrdiff_t,
typename pointer = type*,
typename reference = type& >
class iterator{
public:
typedef type valueType;
typedef category iteratorCategory;
typedef distance differenceType;
typedef pointer pointer;
typedef reference reference;
};
template <typename iterator>
class iteratorTrait{
public:
typedef typename iterator::iteratorCategory
iteratorCategory;
typedef typename iterator::valueType
valueType;
typedef typename iterator::differenceType
differenceType;
typedef typename iterator::pointer
pointer;
typedef typename iterator::reference
reference;
};
template <> class iteratorTrait < signed char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef signed char valueType;
typedef std::ptrdiff_t differenceType;
typedef signed char* pointer;
typedef signed char& reference;
};
template <> class iteratorTrait < const signed char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const signed char valueType;
typedef std::ptrdiff_t differenceType;
typedef const signed char* pointer;
typedef const signed char& reference;
};
template <> class iteratorTrait < unsigned char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned char valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned char* pointer;
typedef unsigned char& reference;
};
template <> class iteratorTrait < const unsigned char > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned char valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned char* pointer;
typedef const unsigned char& reference;
};
template <> class iteratorTrait < wchar_t > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef wchar_t valueType;
typedef std::ptrdiff_t differenceType;
typedef wchar_t* pointer;
typedef wchar_t& reference;
};
template <> class iteratorTrait < const wchar_t > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const wchar_t valueType;
typedef std::ptrdiff_t differenceType;
typedef const wchar_t* pointer;
typedef const wchar_t& reference;
};
template <> class iteratorTrait < short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef short valueType;
typedef std::ptrdiff_t differenceType;
typedef short* pointer;
typedef short& reference;
};
template <> class iteratorTrait < const short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const short valueType;
typedef std::ptrdiff_t differenceType;
typedef const short* pointer;
typedef const short& reference;
};
template <> class iteratorTrait < unsigned short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned short valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned short* pointer;
typedef unsigned short& reference;
};
template <> class iteratorTrait < const unsigned short > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned short valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned short* pointer;
typedef const unsigned short& reference;
};
template <> class iteratorTrait < int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef int valueType;
typedef std::ptrdiff_t differenceType;
typedef int* pointer;
typedef int& reference;
};
template <> class iteratorTrait < const int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const int valueType;
typedef std::ptrdiff_t differenceType;
typedef const int* pointer;
typedef const int& reference;
};
template <> class iteratorTrait < unsigned int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned int valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned int* pointer;
typedef unsigned int& reference;
};
template <> class iteratorTrait < const unsigned int > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned int valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned int* pointer;
typedef const unsigned int& reference;
};
template <> class iteratorTrait < long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long valueType;
typedef std::ptrdiff_t differenceType;
typedef long* pointer;
typedef long& reference;
};
template <> class iteratorTrait < const long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long valueType;
typedef std::ptrdiff_t differenceType;
typedef const long* pointer;
typedef const long& reference;
};
template <> class iteratorTrait < long long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long long valueType;
typedef std::ptrdiff_t differenceType;
typedef long long * pointer;
typedef long long & reference;
};
template <> class iteratorTrait < const long long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long long valueType;
typedef std::ptrdiff_t differenceType;
typedef const long long * pointer;
typedef const long long & reference;
};
template <> class iteratorTrait < unsigned long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef unsigned long valueType;
typedef std::ptrdiff_t differenceType;
typedef unsigned long* pointer;
typedef unsigned long& reference;
};
template <> class iteratorTrait < const unsigned long > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const unsigned long valueType;
typedef std::ptrdiff_t differenceType;
typedef const unsigned long* pointer;
typedef const unsigned long& reference;
};
template <> class iteratorTrait < float > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef float valueType;
typedef std::ptrdiff_t differenceType;
typedef float* pointer;
typedef float& reference;
};
template <> class iteratorTrait < const float > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const float valueType;
typedef std::ptrdiff_t differenceType;
typedef const float* pointer;
typedef const float& reference;
};
template <> class iteratorTrait < double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef double valueType;
typedef std::ptrdiff_t differenceType;
typedef double* pointer;
typedef double& reference;
};
template <> class iteratorTrait < const double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const double valueType;
typedef std::ptrdiff_t differenceType;
typedef const double* pointer;
typedef const double& reference;
};
template <> class iteratorTrait < long double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef long double valueType;
typedef std::ptrdiff_t differenceType;
typedef long double* pointer;
typedef long double& reference;
};
template <> class iteratorTrait < const long double > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const long double valueType;
typedef std::ptrdiff_t differenceType;
typedef const long double* pointer;
typedef const long double& reference;
};
template <> class iteratorTrait < bool > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef bool valueType;
typedef std::ptrdiff_t differenceType;
typedef bool* pointer;
typedef bool& reference;
};
template <> class iteratorTrait < const bool > {
public:
typedef randomAccessIteratorTag
iteratorCategory;
typedef const bool valueType;
typedef std::ptrdiff_t differenceType;
typedef const bool* pointer;
typedef const bool& reference;
};
}
#endif
#ifndef __LIST__H__
#define __LIST__H__
#include <memory>
#include <cassert>
#include <stdexcept>
#include "typeTrait.h"
#include "iteratorTrait.h"
namespace stc{
template <typename type>
class listNode{
typedef listNode<type>* pointer;
public:
listNode() :mNext(0), mNext(0){}
listNode(const type&, pointer = NULL, pointer = NULL);
type mData;
listNode<type>* mNext;
listNode<type>* mPrev;
};
template <typename type>
listNode<type>::
listNode(const type& val, pointer next, pointer prev)
:mData(val), mNext(next), mPrev(prev)
{
}
template <typename type,
typename ref,
typename ptr>
class listIterator{
typedef listNode<type>* linkType;
typedef listIterator<type, type&, type*> iterator;
typedef listIterator<type, ref, ptr> self;
public:
typedef stc::bidirectionalIteratorTag
iteratorCategory;
typedef type valueType;
typedef ptr pointer;
typedef ref reference;
typedef std::size_t sizeType;
typedef std::ptrdiff_t differenceType;
listIterator() = default;
listIterator(linkType node)
:mNode(node){}
listIterator(const listIterator& rhs)
:mNode(rhs.mNode){}
bool operator ==(const self& x) const{ return mNode == x.mNode; }
bool operator !=(const self& x) const{ return mNode != x.mNode; }
linkType getNode() const{ return mNode; }
reference operator *() const{ return mNode->mData; }
pointer operator ->() const{ return &(mNode->mData); }
self& operator ++();
self& operator ++(int);
self& operator --();
self& operator --(int);
private:
linkType mNode;
};
template <typename type,
typename ref,
typename ptr>
inline typename listIterator<type,ref,ptr>::self&
listIterator<type, ref, ptr>::
operator ++(){
mNode = mNode->mNext;
return *this;
}
template <typename type,
typename ref,
typename ptr>
inline typename listIterator<type, ref, ptr>::self&
listIterator<type, ref, ptr>::
operator ++(int){
self temp = *this;
++(*this);
return temp;
}
template <typename type,
typename ref,
typename ptr>
inline typename listIterator<type, ref, ptr>::self&
listIterator<type, ref, ptr>::
operator --(){
mNode = mNode->mPrev;
return *this;
}
template <typename type,
typename ref,
typename ptr>
inline typename listIterator<type, ref, ptr>::self&
listIterator<type, ref, ptr>::
operator --(int){
self temp = *this;
--(*this);
return temp;
}
template <typename type,
class Alloc = std::allocator<
stc::listNode<type> > >
class list{
typedef listNode<type>* listNode;
public:
typedef type valueType;
typedef type* pointer;
typedef listIterator <type, type&, type*>
iterator;
typedef type& reference;
typedef std::size_t sizeType;
typedef std::ptrdiff_t differenceType;
public:
~list();
list();
list(list<type>&&);
list(const list<type>&);
const sizeType size()const { return mSize; }
bool empty() const{ return !mSize; }
iterator begin() const{ return mHead->mNext; }
iterator end() const{ return mHead; }
reference front() { assert(!empty()); return *(begin()); }
reference back() { assert(!empty()), return *(--end()); }
void push_back(const type&);
void push_head(const type&);
iterator insert(const type&, iterator);
iterator erase(iterator);
void pop_back();
void pop_front();
void clear();
void remove(const type&);
void unique();
void splice(iterator, list<type>&);
void splice(iterator, list<type>&, iterator);
void splice(iterator, list<type>&, iterator, iterator);
void reverse();
list<type>& memcopy(const list<type>&);
list<type>& memcopy(list<type>&&);
list<type>& operator =(const list<type>&);
list<type>& operator =(list<type>&&);
private:
listNode getNode();
void putNode(listNode&);
listNode creatNode(const type&);
listNode creatNode(const type&, listNode, falseType);
listNode creatNode(const type&, listNode, trueType);
void destroyNode(listNode&);
void destroyNode(listNode&, falseType);
void destroyNode(listNode&, trueType);
void emptyInit();
void transfer(iterator, iterator, iterator);
sizeType distance(iterator, iterator);
private:
Alloc mAllocator;
listNode mHead;
sizeType mSize;
const size_t sDefaultSz = 1;
};
template <typename type,class Alloc>
list<type, Alloc>::
list()
:mHead(0),mSize(0){
this->emptyInit();
}
template <typename type,class Alloc>
list<type, Alloc>::
~list(){
this->clear();
this->putNode(mHead);
}
template <typename type,class Alloc>
list<type, Alloc>::
list(const list<type>& rhs)
:mHead(0), mSize(0){
emptyInit();
memcopy(rhs);
}
template <typename type,class Alloc>
list<type,Alloc>::
list(list<type>&& rhs){
emptyInit();
if (!rhs.empty()){
transfer(begin(), rhs, rhs.begin(), rhs.end());
rhs.mSize = 0;
}
}
template <typename type,class Alloc>
typename stc::list<type,Alloc>::listNode
list<type,Alloc>::
getNode(){
return mAllocator.allocate(sDefaultSz);
}
template <typename type,class Alloc>
void list<type,Alloc>::
putNode(listNode& ptr){
mAllocator.deallocate(ptr,sDefaultSz);
ptr = NULL;
}
template <typename type,class Alloc>
typename list<type,Alloc>::listNode
list<type,Alloc>::
creatNode(const type& val){
listNode ptr = getNode();
typedef typename typeTrait <type>::
isPODType isPODType;
return creatNode(val, ptr, isPODType());
}
template <typename type, class Alloc>
typename list<type, Alloc>::listNode
list<type, Alloc>::
creatNode(const type& val,listNode ptr,falseType){
assert(ptr);
mAllocator.construct(ptr, val);
return ptr;
}
template <typename type, class Alloc>
inline typename list<type, Alloc>::listNode
list<type, Alloc>::
creatNode(const type& val, listNode ptr, trueType){
*ptr = val;
return ptr;
}
template <typename type,class Alloc>
void list<type,Alloc>::
destroyNode(listNode& ptr){
typedef typename typeTrait<type>::
isPODType isPODType;
this->destroyNode(ptr, isPODType());
}
template <typename type,class Alloc>
void list<type,Alloc>::
destroyNode(listNode& ptr, falseType){
mAllocator.destroy(ptr);
this->putNode(ptr);
}
template <typename type,class Alloc>
void list<type,Alloc>::
destroyNode(listNode& ptr, trueType){
this->putNode(ptr);
}
template <typename type,class Alloc>
void list<type,Alloc>::
emptyInit(){
mHead = getNode();
mHead->mPrev = mHead;
mHead->mPrev = mHead;
}
template <typename type,class Alloc>
void list<type,Alloc>::
push_back(const type& val){
insert(val, end());
}
template <typename type,class Alloc>
void list<type,Alloc>::
push_head(const type& val){
insert(val, begin());
}
template <typename type,class Alloc>
typename list<type,Alloc>::iterator
list<type,Alloc>::
insert(const type& val,iterator pos){
listNode tmp = creatNode(val);
listNode curr = pos.getNode();
listNode prev = curr->mPrev;
tmp->mPrev = prev;
prev->mNext = tmp;
tmp->mNext = curr;
curr->mPrev = tmp;
++mSize;
return tmp;
}
template <typename type,class Alloc>
typename list<type,Alloc>::iterator
list<type,Alloc>::
erase(iterator pos){
assert(!empty());
assert(pos != end());
listNode curr = pos.getNode();
listNode prev = curr->mPrev;
listNode next = curr->mNext;
--mSize;
prev->mNext = next;
next->mPrev = prev;
destroyNode(curr);
return next;
}
template <typename type,class Alloc>
void list<type, Alloc>::
pop_back(){
erase(--(end()));
}
template <typename type,class Alloc>
void list<type,Alloc>::
pop_front(){
erase(begin());
}
template <typename type,class Alloc>
void list<type,Alloc>::
clear(){
if (empty()) return;
sizeType Sz = size();
for (size_t i = 0; i != Sz; ++i)
this->pop_back();
}
template <typename type,class Alloc>
void list<type,Alloc>::
remove(const type& val){
if (empty()) return;
for (iterator it = begin(); it != end(); ++it)
if (*it == val) erase(it);
}
template <typename type,class Alloc>
void list<type,Alloc>::
unique(){
if (empty()) return;
iterator first = begin();
iterator last = end();
iterator next = first;
while (&(*(++next)) != &(*first) &&
&(*next) != &(*last)){
if (*first == *next)
erase(next);
else first = next;
next = first;
}
}
template <typename type,class Alloc>
void list<type,Alloc>::
transfer(iterator pos, iterator first, iterator last){
assert(pos != last);
listNode curr = pos.getNode();
listNode prev = curr->mPrev;
listNode fcurr = first.getNode();
listNode fprev = fcurr->mPrev;
listNode lcurr = last.getNode();
listNode lprev = lcurr->mPrev;
prev->mNext = fcurr;
fcurr->mPrev = prev;
curr->mPrev = lprev;
lprev->mNext = curr;
fprev->mNext = lcurr;
lcurr->mPrev = fprev;
}
template <typename type,class Alloc>
typename list<type,Alloc>::sizeType
list<type, Alloc>::
distance(iterator first, iterator last){
sizeType res = 0;
while (&(*first) != &(*last)){
++first;
++res;
}
return res;
}
template <typename type,class Alloc>
void list<type,Alloc>::
splice(iterator pos, list<type>& rhs){
if (rhs.empty()) return;
if (this == &rhs) return;
transfer(pos, rhs.begin(), rhs.end());
mSize += rhs.mSize;
rhs.mSize = NULL;
}
template <typename type,class Alloc>
void list<type,Alloc>::
splice(iterator pos, list<type>& rhs, iterator item){
insert(*item, pos);
rhs.erase(item);
++mSize;
}
template <typename type,class Alloc>
void list<type, Alloc>::
splice(iterator pos, list<type>& rhs,
iterator first, iterator last){
sizeType Sz = distance(first, last);
transfer(pos, first, last);
rhs.mSize -= Sz;
mSize += Sz;
}
template <typename type,class Alloc>
void list<type,Alloc>::
reverse(){
assert(!empty());
iterator first = begin();
iterator last = --end();
for(sizeType i = 0;i != size() / 2;++i){
std::swap(*first, *last);
++first;
--last;
}
}
template <typename type,class Alloc>
list<type>& list<type,Alloc>::
memcopy(const list<type>& rhs){
if (this == &rhs)
return *this;
else if (rhs.empty()){
this->clear();
return *this;
}
list<type> temp;
for (iterator it = rhs.begin(); it != rhs.end(); ++it)
temp.push_back(*it);
clear();
return memcopy(std::move(temp));
}
template <typename type,class Alloc>
list<type>& list<type,Alloc>::
memcopy(list<type>&& rhs){
if (this == &rhs) return *this;
this->clear();
if (rhs.empty()) return *this;
this->clear();
listNode end = rhs.end().getNode();
listNode prev = end->mPrev;
listNode next = end->mNext;
mSize = rhs.size();
prev->mNext = mHead;
mHead->mPrev = prev;
mHead->mNext = next;
next->mPrev = mHead;
rhs.mSize = 0;
rhs.mHead->mNext = rhs.mHead;
rhs.mHead->mPrev = rhs.mHead;
return *this;
}
template <typename type,class Alloc>
list<type>& list<type,Alloc>::
operator =(const list<type>& rhs){
return memcopy(rhs);
}
template <typename type,class Alloc>
list<type>& list<type,Alloc>::
operator =(list<type>&& rhs){
return memcopy(std::move(rhs));
}
}
#endif