/** -*- C++ -*-
 **
 **  KAI C++ Compiler
 **
 **  Copyright (C) 1996-2001 Intel Corp. All rights reserved.
 **/
/**
 **  Lib++  : The Modena C++ Standard Library,
 **           Version 2.4, October 1997
 **
 **  Copyright (c) 1995-1997 Modena Software Inc.
 **/

#ifndef __KAI_DEQUE
#define __KAI_DEQUE

#include <mcompile.h>

#include <memory>
#include <iterator>
#include <algobase>

#include <stdexcept>
#include <limits>

#undef Allocator	/* Old STL codes define Allocator */

namespace std {


template <class T, class Allocator = allocator<T> > 
class deque {
public:
    // types:
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    class					  iterator;
    class					  const_iterator;
    typedef typename Allocator::size_type         size_type;
    typedef typename Allocator::difference_type   difference_type;
    typedef T					  value_type;
    typedef Allocator				  allocator_type;
    typedef typename Allocator::pointer		  pointer;
    typedef typename Allocator::const_pointer	  const_pointer;
    typedef std::reverse_iterator<iterator>	  reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    friend class iterator;
    friend class const_iterator;

private:
    typedef typename Allocator:: template rebind<pointer>::other map_allocator_type;
    typedef typename map_allocator_type::pointer   map_pointer;

    static const int __sz1 = sizeof(T)>4096 ? 1 : 4096 / sizeof(T);
    static const size_type BUF_SIZE = (__sz1 < 20) ? __sz1 : 20;

    void allocate_at_begin();
    void allocate_at_end();
    void deallocate_at_begin();
    void deallocate_at_end();

    // Added by KAI to perform the magic required by the C++ Standard 23.1.1 para 9.
    template<bool b> class _Helper { };

    template<class Iterator>
    void _initialize(Iterator first, Iterator last, _Helper<true> *) {
	size_type n = (size_type)first;
	const T value = (T) last;
	insert(begin(), n, value); 
    }
    template<class Iterator>
    void _initialize(Iterator first, Iterator last, _Helper<false> *) {
	difference_type i = 0;
	MSIPL_TRY {
	    for (; first != last; ++first, ++i)
		push_back(*first);
	}
	MSIPL_CATCH {
	    for (difference_type j = i; j > 0; --j)
		pop_back();
	    MSIPL_RETHROW;
	}
    }
    template<class InputIterator>
    void _insert(iterator position, InputIterator first, InputIterator last, _Helper<true> *) {
	size_type n = static_cast<size_type>(first);
	const T value = static_cast<T>(last);
	insert(position, n, value);
    }
    template<class InputIterator>
    void _insert(iterator position, InputIterator first, InputIterator last, _Helper<false> *) {
	// KAI change to make simple input_iterators(i.e. istream_iterator) work.
	_insert_iterator(position, first, last, (iterator_traits<InputIterator>::iterator_category *)0);
    }
    template<class InputIterator>
    void _insert_iterator(iterator position, InputIterator first, InputIterator last, input_iterator_tag *) {
	// We cannot compute the distance without distructivly stepping through the iterator.
	// So we create a new deque of the values and then insert that range(which we can compute the size)
	deque tmp(first,last);
	insert(position, tmp.begin(), tmp.end());
    }
    template<class InputIterator>
    void _insert_iterator(iterator position, InputIterator first, InputIterator last, random_access_iterator_tag *);

    struct cleanup;
    friend struct cleanup;
    struct cleanup {
	deque *my_deque;
	size_t n;
	bool from_head;
	cleanup(deque *d, bool fh, size_t cnt = 0) : my_deque(d), from_head(fh), n(cnt) { }
	~cleanup() { while (n--) { from_head? my_deque->pop_front() : my_deque->pop_back(); } }
	void incr() { n++; }
	void clear() {n=0;}
    };

public:
    // 23.2.1.1   construct/copy/destroy
    explicit deque() : start(this), finish(this), length(0), map(0), map_size(0) {}
    explicit deque(const Allocator& a) : start(this), finish(this), length(0), map(0), map_size(0), alloc(a) {}

    explicit deque(size_type n)
	: start(this), finish(this), length(0), map(0), map_size(0) { insert(begin(), n, T()); }
    explicit deque(size_type n, const T& value)
	: start(this), finish(this), length(0), map(0), map_size(0) { insert(begin(), n, value); }
    explicit deque(size_type n, const T& value, const Allocator& a)
	: start(this), finish(this), length(0), map(0), map_size(0), alloc(a) { insert(begin(), n, value); }

    template <class Iterator>
    __noinline deque(Iterator first, Iterator last)
	: start(this), finish(this), length(0), map(0), map_size(0) { 
	_initialize(first, last, (_Helper<numeric_limits<Iterator>::is_integer> *)0);
    }
    template <class Iterator>
    __noinline deque(Iterator first, Iterator last, const Allocator& a)
	: start(this), finish(this), length(0), map(0), map_size(0), alloc(a) { 
	_initialize(first, last, (_Helper<numeric_limits<Iterator>::is_integer> *)0);
    }


    deque(const deque<T, Allocator>& x);
    ~deque();
    deque<T, Allocator>& operator=(const deque<T, Allocator>& x);

    template<class InputIterator>
    void assign(InputIterator first, InputIterator last) {
	erase(begin(), end());
	insert(begin(), first, last);
    }

    void assign(size_type n, const T& t) {
	erase(begin(), end());
	insert(begin(), n, t);
    }

    inline allocator_type get_allocator() const { return alloc; }

    // iterators:
    iterator	   begin()	 { return start; }
    const_iterator begin() const { return start; }
    iterator	   end()       { return finish; }
    const_iterator end() const { return finish; }
    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()); } 

    // 23.2.1.2  capacity:
    size_type size() const { return length; }
    size_type max_size() const { return alloc.max_size(); }
    void resize(size_type new_size) { resize(new_size, T()); }
    void resize(size_type new_size, T c) {
	if (new_size > length)
	    insert(end(), new_size - length, c);
	else if (new_size < length)
	    erase(begin() + new_size, end());
    }
    bool empty() const { return length == 0; }

    // element access:
    reference	    operator[](size_type n)	  { return *(begin() + n); }
    const_reference operator[](size_type n) const { return *(begin() + n); }
    reference at(size_type n) {
	if (n>=length)
	    out_of_range::__throw("Out of range exception occurred");
	return *(begin() + n);
    }
    const_reference at(size_type n) const { 
	if (n>=length)
	    out_of_range::__throw("Out of range exception occurred");
	return *(begin() + n);
    }
    reference	    front()	  { return *start; }
    const_reference front() const { return *start; }
    reference	    back()	 { iterator tmp = finish; --tmp; return *tmp; }
    const_reference back() const { iterator tmp = finish; --tmp; return *tmp; }

    // 23.2.1.3  modifiers:
    void push_front(const T& x);
    void push_back(const T& x);

    iterator insert(iterator position, const T& x);
    void     insert(iterator position, size_type n, const T& x);

    template <class InputIterator>
    __noinline void insert(iterator position, InputIterator first, InputIterator last) {
	_insert(position, first, last, (_Helper<numeric_limits<InputIterator>::is_integer> *)0);
    }

    void pop_front();
    void pop_back();

    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);    

    void swap(deque<T, Allocator>& x) {
        std::swap(start, x.start);
        std::swap(finish, x.finish);
        std::swap(map, x.map);
        std::swap(length, x.length);
        std::swap(map_size, x.map_size);
        std::swap(alloc, x.alloc);
    }

    void clear() { erase(begin(), end()); }

    // iterator
    class iterator : public std::iterator<random_access_iterator_tag, T, difference_type, pointer, reference>
    {
	friend class deque;
	friend class deque::const_iterator;
	friend iterator operator+(const difference_type n, const iterator& iter) { 
	    deque<T, Allocator>::iterator tmp = iter; 
	    return tmp += n; 
	}

    protected:
	pointer current;
	pointer first;
	pointer last;
	map_pointer node;

	iterator(pointer x, map_pointer y, deque<T, Allocator>* dq) 
	    : current(x), first(*y), last(*y + BUF_SIZE), node(y) 
	    {}

	iterator(deque<T, Allocator> *dq) : current(0), first(0), last(0), node(0) {}

    public:
	iterator() : current(0), first(0), last(0), node(0) { }

	reference operator*() const { return *current; }
	pointer operator->() const { return &(operator*()); }
	iterator& operator++() {
	    if (++current == last){
		first = *(++node);
		current = first;
		last = first + BUF_SIZE;
	    }
	    return *this; 
	}
	iterator operator++(int) {
	    iterator tmp = *this;
	    ++*this;
	    return tmp;
	}
	iterator& operator--() {
	    if (current == first) {
		first = *(--node);
		last = first + BUF_SIZE;
		current = last;
	    }
	    --current;
	    return *this;
	}
	iterator operator--(int) {
	    iterator tmp = *this;
	    --*this;
	    return tmp;
	}
	__noinline
	iterator& operator+=(const difference_type n) {
	    difference_type offset = n + (current - first);
	    difference_type num_node_to_jump =
		offset >= 0 ? offset / BUF_SIZE 
		: -((-offset + BUF_SIZE - 1) / BUF_SIZE);
	    if (num_node_to_jump == 0)
		current += n;
	    else {
		node = node + num_node_to_jump;
		first = *node;
		last = first + BUF_SIZE;
		current = first + (offset - num_node_to_jump * BUF_SIZE);
	    }
	    return *this;
	}
	iterator& operator-=(const difference_type n) { return *this += -n; }
	iterator operator+(const difference_type n) const {
	    iterator tmp = *this;
	    return tmp += n;
	}
	iterator operator-(const difference_type n) const {
	    iterator tmp = *this;
	    return tmp -= n;
	}
	reference operator[](const difference_type n) const { return *(*this + n); }
	difference_type operator-(const iterator& x) const {
	    return node == x.node ? current - x.current 
		: BUF_SIZE *(node - x.node - 1) +
		(current - first)+ (x.last - x.current); 
	}
	difference_type operator-(const const_iterator& x) const {
	    return node == x.node ? current - x.current 
		: BUF_SIZE *(node - x.node - 1) +
		(current - first)+ (x.last - x.current); 
	}
	bool operator==(const iterator& x) const { return current == x.current; }
	bool operator==(const const_iterator& x) const { return current == x.current; }
	bool operator<(const iterator& x) const {
	    return(node == x.node) ? (current < x.current) : (node < x.node);
	}
	bool operator<(const const_iterator& x) const {
	    return(node == x.node) ? (current < x.current) : (node < x.node);
	}
	bool operator!=(const iterator& y) const { return ! (*this == y); }
	bool operator>(const iterator& y) const { return y < *this; }
	bool operator<=(const iterator& y) const { return  ! (y < *this); }
	bool operator>=(const iterator& y) const { return  ! (*this < y); }
	bool operator!=(const const_iterator& y) const { return ! (*this == y); }
	bool operator>(const const_iterator& y) const { return y < *this; }
	bool operator<=(const const_iterator& y) const { return  ! (y < *this); }
	bool operator>=(const const_iterator& y) const { return(y < *this); }
    };

    // const_iterator
    class const_iterator : public std::iterator<random_access_iterator_tag, T, difference_type, const_pointer, const_reference>
    {
	friend class deque;
	friend class deque::iterator;

	friend const_iterator operator+(const difference_type n, const const_iterator& iter) { 
	    deque<T, Allocator>::const_iterator tmp = iter; 
	    return tmp += n; 
	}

    protected:
	const_pointer current;
	const_pointer first;
	const_pointer last;
	map_pointer node;

	const_iterator(pointer x, map_pointer y, deque<T, Allocator>* dq) 
	    : current(x), first(*y), last(*y + BUF_SIZE), node(y) 
	    {}

    public:
	const_iterator() : current(0), first(0), last(0), node(0) {}

	const_iterator(const deque::iterator& x) : current(x.current), first(x.first), last(x.last), node(x.node) {}     

	const_reference operator*() const { return *current; }
	const_pointer operator->() const { return &(operator*()); }
	const_iterator& operator++() {
	    if (++current == last) {
		first = *(++node);
		current = first;
		last = first + BUF_SIZE;
	    }
	    return *this; 
	}
	const_iterator operator++(int) {
	    const_iterator tmp = *this;
	    ++*this;
	    return tmp;
	}
	const_iterator& operator--() {
	    if (current == first) {
		first = *(--node);
		last = first + BUF_SIZE;
		current = last;
	    }
	    --current;
	    return *this;
	}
	const_iterator operator--(int) {
	    const_iterator tmp = *this;
	    --*this;
	    return tmp;
	}
	__noinline
	const_iterator& operator+=(const difference_type n) {
	    difference_type offset = n + (current - first);
	    difference_type num_node_to_jump = offset >= 0
		? offset / BUF_SIZE
		: -((-offset + BUF_SIZE - 1) / BUF_SIZE);
	    if (num_node_to_jump == 0)
		current += n;
	    else {
		node = node + num_node_to_jump;
		first = *node;
		last = first + BUF_SIZE;
		current = first + (offset - num_node_to_jump * BUF_SIZE);
	    }
	    return *this;
	}
	const_iterator& operator-=(const difference_type n) { return *this += -n; }
	const_iterator operator+(const difference_type n) const {
	    const_iterator tmp = *this;
	    return tmp += n;
	}
	const_iterator operator-(const difference_type n) const {
	    const_iterator tmp = *this;
	    return tmp -= n;
	}
	const_reference operator[](const difference_type n) const { return *(*this + n); }
	difference_type operator-(const const_iterator& x) const {
	    return node == x.node ? current - x.current 
		: BUF_SIZE *(node - x.node - 1) +
		(current - first)+ (x.last - x.current);
	}
	bool operator==(const const_iterator& x) const { return current == x.current; }
	bool operator<(const const_iterator& x) const {
	    return(node == x.node) ? (current < x.current) 
		: (node < x.node);
	}
	difference_type operator-(const deque::iterator& x) const {
	    return node == x.node ? current - x.current 
		: BUF_SIZE *(node - x.node - 1) +
		(current - first)+ (x.last - x.current);
	}
	bool operator==(const deque::iterator& x) const { return current == x.current; }
	bool operator<(const deque::iterator& x) const {
	    return(node == x.node) ? (current < x.current) 
		: (node < x.node);
	}
	bool operator!=(const deque::iterator& y) const { return ! (*this == y); }
	bool operator>(const deque::iterator& y) const { return y < *this; }
	bool operator<=(const deque::iterator& y) const { return  ! (y < *this); }
	bool operator>=(const deque::iterator& y) const { return(y < *this); }
	bool operator!=(const const_iterator& y) const { return ! (*this == y); }
	bool operator>(const const_iterator& y) const { return y < *this; }
	bool operator<=(const const_iterator& y) const { return  ! (y < *this); }
	bool operator>=(const const_iterator& y) const { return(y < *this); }
    };

    // Members sorted to minimize size of class.
    iterator	start;
    iterator	finish;
    map_pointer map;
    size_type	length;
    size_type	map_size;
    allocator_type alloc;
};

template <class T, class Allocator> 
static const deque<T,Allocator>::size_type deque<T,Allocator>::BUF_SIZE;

template <class T, class Allocator>
inline bool
operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
{
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class T, class Allocator>
inline bool
operator<(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
{
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class T, class Allocator>
inline bool operator!=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) { return ! (x == y); }
template <class T, class Allocator>
inline bool operator>(const deque<T, Allocator>& x, const deque<T, Allocator>& y) { return(y < x); }
template <class T, class Allocator>
inline bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) { return ! (x < y); }
template <class T, class Allocator>
inline bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) { return ! (y < x); }
template <class T, class Allocator>
inline void swap(deque<T, Allocator>& x, deque<T, Allocator>& y) { x.swap(y); }

template <class T, class Allocator>
void deque<T, Allocator>::allocate_at_begin()
{
    pointer p = alloc.allocate(BUF_SIZE);
    MSIPL_TRY {
	if (length) {
	    if (start.node == map) {
		difference_type i = finish.node - start.node;
		size_type old_map_size = map_size;
		map_size = (i + 1) * 2;
		map_pointer tmp = map_allocator_type(alloc).allocate(map_size);
		copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
		map_allocator_type(alloc).deallocate(map, old_map_size);
		map = tmp;
		map[map_size / 4] = p;
		start = iterator(p + BUF_SIZE, map + map_size / 4, this);
		finish = iterator(finish.current, map + map_size / 4 + i + 1, this);
	    } else {
		*--start.node = p;
		start = iterator(p + BUF_SIZE, start.node, this);
	    }
	} else {
	    map_size = 2;
	    map = map_allocator_type(alloc).allocate(map_size);
	    map[map_size / 2] = p;
	    start = iterator(p + BUF_SIZE / 2 + 1, map + map_size / 2, this);
	    finish = start;
	}
    } 
    MSIPL_CATCH {
	alloc.deallocate(p, BUF_SIZE);
	MSIPL_RETHROW;
    }
}

template <class T, class Allocator>
void deque<T, Allocator>::allocate_at_end()
{
    pointer p = alloc.allocate(BUF_SIZE);
    MSIPL_TRY {
	if (length) {
	    if (finish.node == map + map_size - 1) {
		difference_type i = finish.node - start.node;
		size_type old_map_size = map_size;
		map_size = (i + 1) * 2;
		map_pointer tmp = map_allocator_type(alloc).allocate(map_size);
		copy(start.node, finish.node + 1, tmp + map_size / 4);
		map_allocator_type(alloc).deallocate(map, old_map_size);
		map = tmp;
		map[map_size / 4 + i + 1] = p;
		start = iterator(start.current, map + map_size / 4, this);
		finish = iterator(p, map + map_size / 4 + i + 1, this);
	    } else {
		*++finish.node = p;
		finish = iterator(p, finish.node, this);
	    }
	} else {
	    map_size = 2;
	    map = map_allocator_type(alloc).allocate(map_size);
	    map[map_size / 2] = p;
	    start = iterator(p + BUF_SIZE / 2, map + map_size / 2, this);
	    finish = start;
	}
    } 
    MSIPL_CATCH {
	alloc.deallocate(p, BUF_SIZE);
	MSIPL_RETHROW;
    }
}

template <class T, class Allocator>
void deque<T, Allocator>::deallocate_at_begin()
{
    alloc.deallocate(*start.node++, BUF_SIZE);
    if (!length) {
	if (finish.current == finish.first)
	    alloc.deallocate(*start.node, BUF_SIZE);
	start = iterator(this);
	finish = start;
	map_allocator_type(alloc).deallocate(map, map_size);
    } else
	start = iterator(*start.node, start.node, this);
}

template <class T, class Allocator>
void deque<T, Allocator>::deallocate_at_end()
{
    alloc.deallocate(*finish.node--, BUF_SIZE);
    if (!length) {
	start = iterator(this);
	finish = start;
	map_allocator_type(alloc).deallocate(map, map_size);
    } else
	finish = iterator(*finish.node + BUF_SIZE, finish.node, this);
}

template <class T, class Allocator>
deque<T, Allocator>::deque(const deque<T, Allocator>& x) : start(this), finish(this), length(0), map(0), map_size(0), alloc(x.alloc) { 
    const_iterator first = x.begin();
    const_iterator last = x.end();
    difference_type i = 0;
    MSIPL_TRY {
	for (; first != last; ++first, ++i)
	    push_back(*first);
    }
    MSIPL_CATCH {
	for (difference_type j = i; j > 0; --j)
	    pop_back();
	MSIPL_RETHROW;
    }
}

template <class T, class Allocator>
deque<T, Allocator>::~deque() { 
    while (length) 
	pop_front(); 
}     


template <class T, class Allocator>
deque<T, Allocator>& deque<T, Allocator>::operator=(const deque<T, Allocator>& x) {
    if (this == &x)
	return *this;
    if (length >= x.length) 
	erase(copy(x.start, x.finish, start), finish);
    else
	copy(x.start + length, x.finish, inserter(*this, copy(x.start, x.start + length, start)));
    return *this;
}

template <class T, class Allocator>
void deque<T, Allocator>::push_front(const T& x)
{
    bool constructed = false;
    bool alloc_at_begin = !length || start.current == start.first;
    if (alloc_at_begin) 
	allocate_at_begin();
    MSIPL_TRY {
	alloc.construct(start.current - 1, x);
	constructed = true;
	--start.current;
	++length;
	//if (end().current == end().last) // this seems wrong
	//    allocate_at_end();
    }
    MSIPL_CATCH {
	if (constructed) {
	    alloc.destroy(start.current);
	    ++start.current;
	    --length;
	}
	if (alloc_at_begin)
	    deallocate_at_begin();
	MSIPL_RETHROW;
    }
}

template <class T, class Allocator>
void deque<T, Allocator>::push_back(const T& x)
{
    bool constructed = false;
    if (!length)
	allocate_at_end();
    MSIPL_TRY {
	alloc.construct(finish.current, x);
	constructed = true;
	++finish.current;
	++length;
    }
    MSIPL_CATCH {
	if (constructed) {
	    alloc.destroy(finish.current - 1);
	    --finish.current;
	    --length;
	}
	if (!length)
	    deallocate_at_end();
	MSIPL_RETHROW;
    }
    if (finish.current == finish.last)
	allocate_at_end();
}

template <class T, class Allocator>
deque<T, Allocator>::iterator 
deque<T, Allocator>::insert(iterator position, const T& x)
{
    if ( position < start || position > finish)
	out_of_range::__throw("Out of range exception occurred");
    if (position.current == start.current) {
	push_front(x);
	return start;
    } else if (position.current == finish.current) {
	push_back(x);
	iterator tmp = finish;
	--tmp;
	return tmp;
    } else {
	difference_type index = position - start;
	difference_type remainder = length - index;
	if (index < remainder) {
	    push_front(front());
	    iterator front1 = start;
	    ++front1;
	    iterator front2 = front1;
	    ++front2;
	    position = start + index;
	    iterator pos1 = position;
	    ++pos1;
	    copy(front2, pos1, front1);
	} else {
	    push_back(back());
	    iterator back1 = finish;
	    --back1;
	    iterator back2 = back1;
	    --back2;
	    position = start + index;
	    copy_backward(position, back2, back1);
	}
	*position = x;
	return position;
    }
}

template <class T, class Allocator>
void deque<T, Allocator>::insert(iterator position, size_type n, const T& x)
{
    if ( position < start || position > finish)
	out_of_range::__throw("Out of range exception occurred");
    difference_type index = position - begin();
    difference_type remainder = length - index;
    if (remainder > index) {
	if (n > index) {
	    difference_type m = n - index;
	    MSIPL_TRY {
		for (; m > 0 ; --m)
		    push_front(x);
	    }
	    MSIPL_CATCH {
		for (difference_type j = (n - index) - m; j > 0; --j)
		    pop_front();
		MSIPL_RETHROW;
	    }     
	    difference_type i = index;
	    MSIPL_TRY {
		for (; i > 0 ; --i)
		    push_front(*(start + n -1));
	    }
	    MSIPL_CATCH {
		for (difference_type j = index - i; j > 0; --j)
		    pop_front();
		MSIPL_RETHROW;
	    }
	    fill(start + n, start + n + index, x);
	} else {
	    difference_type i = n;
	    MSIPL_TRY {
		for (; i > 0 ; --i)
		    push_front(*(start + n -1));
	    }
	    MSIPL_CATCH {
		for (difference_type j = n - i; j > 0 ; --j)
		    pop_front();
		MSIPL_RETHROW;
	    }
	    copy(start + n + n, start + n + index, start + n);
	    fill(start + index, start + n + index, x);
	}
    } else {
	difference_type orig_len = index + remainder;
	if (n > remainder) {
	    difference_type m = n - remainder;
	    MSIPL_TRY {
		for (; m > 0; --m)
		    push_back(x);
	    }
	    MSIPL_CATCH {
		for (difference_type j = (n - remainder) - m; j > 0; --j)
		    pop_back();
		MSIPL_RETHROW;
	    }
	    difference_type i = 0;
	    MSIPL_TRY {
		for (; i < remainder; ++i)
		    push_back(*(start + index + i));
	    }
	    MSIPL_CATCH {
		for (difference_type j = i; j > 0; --j)
		    pop_back();
		MSIPL_RETHROW;
	    }
	    fill(start + index, start + orig_len, x);
	} else {
	    difference_type i = 0;
	    MSIPL_TRY {
		for (; i < n; ++i)
		    push_back(*(start + orig_len - n + i));
	    }
	    MSIPL_CATCH {
		for (difference_type j = i; j > 0; --j)
		    pop_back();
		MSIPL_RETHROW;
	    }
	    copy_backward(start + index, start + orig_len - n, 
			  start + orig_len);
	    fill(start + index, start + index + n, x);
	}
    }
}

template <class T, class Allocator>
template <class InputIterator>
void deque<T, Allocator>::_insert_iterator(iterator position, 
				      InputIterator first, InputIterator last,
				      random_access_iterator_tag *)
{
    if ( position < start || position > finish)
	out_of_range::__throw("Out of range exception occurred");
    difference_type index = position - begin();
    difference_type remainder = length - index;
    size_type n = distance(first, last);
    if (remainder > index) {
	if (n > index) {
	    InputIterator m = last - index;
	    cleanup c(this,true);
	    while (m != first) { push_front(*--m); c.incr(); }
	    difference_type i = index;
	    while (i--) { push_front(*(start + n - 1)); c.incr(); }
	    c.clear();
	    copy(last - index, last, start + n);
	} else {
	    difference_type i = n;
	    cleanup c(this,true);
	    while (i--) { push_front(*(start + n - 1)); c.incr(); }
	    c.clear();
	    copy(start + n + n, start  + n + index, start + n);
	    copy(first, last, start + index);
	}
    } else {
	difference_type orig_len = index + remainder;
	if (n > remainder) {
	    InputIterator m = first + remainder;
	    cleanup c(this,false);
	    while (m != last) { push_back(*m++); c.incr(); }
	    difference_type i = 0;
	    while (i < remainder) { push_back(*(start + index + i++)); c.incr(); }
	    c.clear();
	    copy(first, first + remainder, start + index);
	} else {
	    difference_type i = 0;
	    cleanup c(this,false);
	    while (i < n) { push_back(*(start + orig_len - n + i++)); c.incr(); }
	    c.clear();
	    copy_backward(begin() + index, start + orig_len - n, 
			  start + orig_len);
	    copy(first, last, start + index);
	}
    }
}

template <class T, class Allocator>
void deque<T, Allocator>::pop_front()
{
    if (!length)
	out_of_range::__throw("Out of range exception occurred");
    alloc.destroy(start.current);
    ++start.current;
    --length; 
    if (!length || start.current == start.last)
	deallocate_at_begin();
}

template <class T, class Allocator>
void deque<T, Allocator>::pop_back() {
    if (!length)
	out_of_range::__throw("Out of range exception occurred");
    if (finish.current == finish.first) 
	deallocate_at_end();
    --finish.current;
    alloc.destroy(finish.current);
    --length; 
    if (!length) 
	deallocate_at_end();
}

template <class T, class Allocator>
deque<T, Allocator>::iterator 
deque<T, Allocator>::erase(iterator position)
{
    if ( position < start || position > finish)
	out_of_range::__throw("Out of range exception occurred");
    deque<T, Allocator>::iterator iter(this);
    if (position != finish )
	iter = position + 1;
    else
	iter = finish;

    if (finish - position > position - start) {
	copy_backward(start, position, position + 1);
	pop_front();
    } else {
	copy(position + 1, finish, position);
	pop_back();
    }
    return iter;
}
 
template <class T, class Allocator>
deque<T, Allocator>::iterator 
deque<T, Allocator>::erase(iterator first, iterator last)
{
    // KAI fix: Modena disallowed case first==last.  
    if ( first > last || first < start || last > finish )
	out_of_range::__throw("Out of range exception occurred");
    deque<T, Allocator>::iterator iter = last;
    difference_type n = last - first;
    if ((finish - last) > (first - start)) {
	copy_backward(start, first, last);
	while (n-- > 0) pop_front();
    } else {
	copy(last, finish, first);
	while (n-- > 0) pop_back();
    }
    return iter;
}

} // namespace std

#endif /* __KAI_DEQUE */