|
#ifndef SJTU_DEQUE_HPP |
|
#define SJTU_DEQUE_HPP |
|
|
|
#include "exceptions.hpp" |
|
|
|
#include <cstddef> |
|
#include <cstring> |
|
#include <cstdlib> |
|
|
|
namespace sjtu |
|
{ |
|
|
|
template <class T> |
|
class deque |
|
{ |
|
private: |
|
friend class iterator; |
|
|
|
static const unsigned chunk_size = 512; // cannot be 1 otherwise there'd be something wrong with iterator |
|
struct Chunk |
|
{ |
|
T *data; |
|
Chunk *prev; |
|
Chunk *next; |
|
std::allocator<T> allocator; |
|
|
|
/* TODO: write our own allocator */ |
|
Chunk(Chunk *prev = NULL, Chunk *next = NULL) : prev(prev), |
|
next(next) |
|
{ |
|
data = allocator.allocate(chunk_size); |
|
} |
|
|
|
Chunk(const Chunk &other) = delete; |
|
|
|
static Chunk *construct_from(const Chunk &other, int data_begin, int data_end) |
|
{ |
|
Chunk *chunk = new Chunk; |
|
for (int i = data_begin; i < data_end; i++) |
|
chunk->allocator.construct(chunk->data + i, other.data[i]); |
|
return chunk; |
|
} |
|
|
|
void destruct_range(int data_begin, int data_end) |
|
{ |
|
for (int i = data_begin; i < data_end; i++) |
|
allocator.destroy(data + i); |
|
} |
|
|
|
~Chunk() { allocator.deallocate(data, chunk_size); } |
|
} * head, *tail; |
|
|
|
T *chunk_head, *chunk_tail; |
|
|
|
void destruct() |
|
{ |
|
Chunk *ptr = head; |
|
while (ptr->prev) |
|
ptr = ptr->prev; |
|
bool is_in_range = false; |
|
while (ptr) |
|
{ |
|
Chunk *tmp = ptr->next; |
|
int data_begin = 0; |
|
int data_end = chunk_size; |
|
if (ptr == head) |
|
{ |
|
data_begin = chunk_head - head->data; |
|
is_in_range = true; |
|
} |
|
if (ptr == tail) |
|
data_end = chunk_tail - tail->data; |
|
if (is_in_range) |
|
ptr->destruct_range(data_begin, data_end); |
|
if (ptr == tail) |
|
is_in_range = false; |
|
delete ptr; |
|
ptr = tmp; |
|
} |
|
} |
|
|
|
void copy_from(const deque &other) |
|
{ |
|
Chunk *ptr = other.head; |
|
Chunk *prev = NULL; |
|
while (ptr) |
|
{ |
|
int data_begin = 0; |
|
int data_end = chunk_size; |
|
if (ptr == other.head) |
|
data_begin = other.chunk_head - other.head->data; |
|
if (ptr == other.tail) |
|
data_end = other.chunk_tail - other.tail->data; |
|
Chunk *cur = Chunk::construct_from(*ptr, data_begin, data_end); |
|
cur->prev = prev; |
|
if (prev) |
|
prev->next = cur; |
|
else |
|
this->head = cur; |
|
prev = cur; |
|
ptr = ptr->next; |
|
} |
|
this->tail = prev; |
|
this->chunk_head = this->head->data + (other.chunk_head - other.head->data); |
|
this->chunk_tail = this->tail->data + (other.chunk_tail - other.tail->data); |
|
} |
|
|
|
void create_new() |
|
{ |
|
tail = head = new Chunk; |
|
chunk_head = chunk_tail = head->data; |
|
} |
|
|
|
void append_chunk() |
|
{ |
|
if (!tail->next) |
|
tail->next = new Chunk(tail); |
|
tail = tail->next; |
|
} |
|
|
|
void prepend_chunk() |
|
{ |
|
if (!head->prev) |
|
head->prev = new Chunk(NULL, head); |
|
head = head->prev; |
|
} |
|
|
|
void shrink_tail_chunk() |
|
{ |
|
Chunk *tmp = tail->prev; |
|
delete tail; |
|
tail = tmp; |
|
tail->next = NULL; |
|
} |
|
|
|
void shrink_head_chunk() |
|
{ |
|
Chunk *tmp = head->next; |
|
delete head; |
|
head = tmp; |
|
head->prev = NULL; |
|
} |
|
|
|
void throw_when_empty() const |
|
{ |
|
if (this->empty()) |
|
throw container_is_empty(); |
|
} |
|
|
|
public: |
|
class const_iterator; |
|
|
|
class iterator |
|
{ |
|
private: |
|
friend deque<T>; |
|
|
|
void debug(const char *msg) const |
|
{ |
|
fprintf(stderr, "%s: chunk %x at %d\n", msg, chunk, pos - chunk->data); |
|
} |
|
|
|
bool is_at_the_end() const { return pos == chunk->data + chunk_size; } |
|
|
|
int distance_to_head() const |
|
{ |
|
Chunk *ptr = q->head; |
|
int chunk_cnt = 0; |
|
while (ptr != chunk) |
|
{ |
|
++chunk_cnt; |
|
ptr = ptr->next; |
|
} |
|
int head_offset = q->chunk_head - q->head->data; |
|
int tail_offset = pos - chunk->data; |
|
return tail_offset + chunk_cnt * chunk_size - head_offset; |
|
}; |
|
|
|
protected: |
|
deque *q; |
|
Chunk *chunk; |
|
T *pos; |
|
|
|
iterator(deque *q, Chunk *chunk, T *pos) : q(q), chunk(chunk), pos(pos) {} |
|
|
|
void move_chunk(int i) |
|
{ |
|
if (i == 0) |
|
return; |
|
int offset = pos - chunk->data; |
|
while (i > 0) |
|
{ |
|
--i; |
|
if (!chunk->next) |
|
{ |
|
if (chunk == q->tail && offset == 0) |
|
{ |
|
offset = chunk_size; |
|
} |
|
else |
|
throw index_out_of_bound(); |
|
} |
|
else |
|
chunk = chunk->next; |
|
} |
|
while (i < 0) |
|
{ |
|
++i; |
|
if (!chunk->prev) |
|
{ |
|
throw index_out_of_bound(); |
|
} |
|
chunk = chunk->prev; |
|
} |
|
pos = chunk->data + offset; |
|
} |
|
|
|
void move_forward(int i) |
|
{ |
|
if (i == 0) |
|
return; |
|
while (i < 0) |
|
{ |
|
++i; |
|
if (pos == chunk->data) |
|
{ |
|
if (!chunk->prev) |
|
throw index_out_of_bound(); |
|
chunk = chunk->prev; |
|
pos = chunk->data + chunk_size; |
|
} |
|
--pos; |
|
if (chunk == q->head && pos < q->chunk_head) |
|
throw index_out_of_bound(); |
|
} |
|
while (i > 0) |
|
{ |
|
--i; |
|
++pos; |
|
if (pos == chunk->data + chunk_size) |
|
{ |
|
if (chunk != q->tail) |
|
{ |
|
if (!chunk->next) |
|
throw index_out_of_bound(); |
|
chunk = chunk->next; |
|
pos = chunk->data; |
|
} |
|
} |
|
if (chunk == q->tail && pos > q->chunk_tail) |
|
throw index_out_of_bound(); |
|
} |
|
} |
|
|
|
public: |
|
/** constructors **/ |
|
iterator() : q(NULL), chunk(NULL), pos(NULL) {} |
|
|
|
iterator(const iterator &other) : iterator(other.q, other.chunk, other.pos) {} |
|
|
|
/** |
|
* return a new iterator which pointer n-next elements |
|
* even if there are not enough elements, the behaviour is **undefined**. |
|
* as well as operator- |
|
*/ |
|
iterator operator+(const int &n) const |
|
{ |
|
iterator that(*this); |
|
if (n > 0) |
|
{ |
|
if (n <= chunk_size) |
|
that.move_forward(n); |
|
else |
|
{ |
|
that.move_forward(n % chunk_size); |
|
that.move_chunk(n / chunk_size); |
|
} |
|
} |
|
else if (n < 0) |
|
{ |
|
if (n >= -chunk_size) |
|
that.move_forward(n); |
|
else |
|
{ |
|
that.move_forward(-(int)((-n) % chunk_size)); |
|
that.move_chunk(-(int)((-n) / chunk_size)); |
|
} |
|
} |
|
|
|
return that; |
|
} |
|
|
|
iterator operator-(const int &n) const { return this->operator+(-n); } |
|
|
|
// return th distance between two iterator, |
|
// if these two iterators points to different vectors, throw invaild_iterator. |
|
int operator-(const iterator &rhs) const |
|
{ |
|
if (rhs.q != this->q) |
|
throw invalid_iterator(); |
|
return this->distance_to_head() - rhs.distance_to_head(); |
|
} |
|
|
|
iterator operator+=(const int &n) |
|
{ |
|
this->move_forward(n); |
|
return *this; |
|
} |
|
|
|
iterator operator-=(const int &n) |
|
{ |
|
this->move_forward(-n); |
|
return *this; |
|
} |
|
|
|
/** |
|
* iter++ |
|
*/ |
|
iterator operator++(int) |
|
{ |
|
iterator that(*this); |
|
this->move_forward(1); |
|
return that; |
|
} |
|
|
|
/** |
|
* ++iter |
|
*/ |
|
iterator &operator++() |
|
{ |
|
this->move_forward(1); |
|
return *this; |
|
} |
|
|
|
/** |
|
* iter-- |
|
*/ |
|
iterator operator--(int) |
|
{ |
|
iterator that(*this); |
|
this->move_forward(-1); |
|
return that; |
|
} |
|
|
|
/** |
|
* --iter |
|
*/ |
|
iterator &operator--() |
|
{ |
|
this->move_forward(-1); |
|
return *this; |
|
} |
|
|
|
/** |
|
* *it |
|
*/ |
|
T &operator*() const |
|
{ |
|
if (chunk == q->tail && pos == q->chunk_tail) |
|
throw index_out_of_bound(); |
|
return *pos; |
|
} |
|
|
|
/** |
|
* it->field |
|
*/ |
|
T *operator->() const noexcept { return pos; } |
|
|
|
/** |
|
* a operator to check whether two iterators are same (pointing to the same memory). |
|
*/ |
|
bool operator==(const iterator &rhs) const |
|
{ |
|
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos); |
|
} |
|
|
|
bool operator==(const const_iterator &rhs) const |
|
{ |
|
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos); |
|
} |
|
|
|
/** |
|
* some other operator for iterator. |
|
*/ |
|
bool operator!=(const iterator &rhs) const { return !(*this == rhs); } |
|
|
|
bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); } |
|
}; |
|
|
|
class const_iterator |
|
{ |
|
// it should has similar member method as iterator. |
|
// and it should be able to construct from an iterator. |
|
private: |
|
friend deque<T>; |
|
|
|
bool is_at_the_end() { return pos == chunk->data + chunk_size; } |
|
|
|
int distance_to_head() const |
|
{ |
|
Chunk *ptr = q->head; |
|
int chunk_cnt = 0; |
|
while (ptr != chunk) |
|
{ |
|
++chunk_cnt; |
|
ptr = ptr->next; |
|
} |
|
int head_offset = q->chunk_head - q->head->data; |
|
int tail_offset = pos - chunk->data; |
|
return tail_offset + chunk_cnt * chunk_size - head_offset; |
|
}; |
|
|
|
void move_chunk(int i) |
|
{ |
|
if (i == 0) |
|
return; |
|
int offset = pos - chunk->data; |
|
while (i > 0) |
|
{ |
|
--i; |
|
if (!chunk->next) |
|
{ |
|
if (chunk == q->tail && offset == 0) |
|
{ |
|
offset = chunk_size; |
|
} |
|
else |
|
throw index_out_of_bound(); |
|
} |
|
else |
|
chunk = chunk->next; |
|
} |
|
while (i < 0) |
|
{ |
|
++i; |
|
if (!chunk->prev) |
|
{ |
|
throw index_out_of_bound(); |
|
} |
|
chunk = chunk->prev; |
|
} |
|
pos = chunk->data + offset; |
|
} |
|
|
|
void move_forward(int i) |
|
{ |
|
if (i == 0) |
|
return; |
|
while (i < 0) |
|
{ |
|
++i; |
|
if (pos == chunk->data) |
|
{ |
|
if (!chunk->prev) |
|
throw index_out_of_bound(); |
|
chunk = chunk->prev; |
|
pos = chunk->data + chunk_size; |
|
} |
|
--pos; |
|
if (chunk == q->head && pos < q->chunk_head) |
|
throw index_out_of_bound(); |
|
} |
|
while (i > 0) |
|
{ |
|
--i; |
|
++pos; |
|
if (pos == chunk->data + chunk_size) |
|
{ |
|
if (chunk != q->tail) |
|
{ |
|
if (!chunk->next) |
|
throw index_out_of_bound(); |
|
chunk = chunk->next; |
|
pos = chunk->data; |
|
} |
|
} |
|
if (chunk == q->tail && pos > q->chunk_tail) |
|
throw index_out_of_bound(); |
|
} |
|
} |
|
|
|
protected: |
|
const deque *q; |
|
const Chunk *chunk; |
|
const T *pos; |
|
|
|
const_iterator(const deque *q, const Chunk *chunk, const T *pos) : q(q), chunk(chunk), pos(pos) {} |
|
|
|
public: |
|
const_iterator(const const_iterator &other) : const_iterator(other.q, other.chunk, other.pos) {} |
|
|
|
const_iterator(const iterator &other) : const_iterator(other.q, other.chunk.other.pos) {} |
|
|
|
const_iterator() {} |
|
|
|
/** |
|
* return a new iterator which pointer n-next elements |
|
* even if there are not enough elements, the behaviour is **undefined**. |
|
* as well as operator- |
|
*/ |
|
const_iterator operator+(const int &n) const |
|
{ |
|
const_iterator that(*this); |
|
if (n > 0) |
|
{ |
|
that.move_forward(n % chunk_size); |
|
that.move_chunk(n / chunk_size); |
|
} |
|
else if (n < 0) |
|
{ |
|
/* TODO: is chunk_size is 1, then move_forward is always called with 0, which may cause exception */ |
|
that.move_forward(-(int)((-n) % chunk_size)); |
|
that.move_chunk(-(int)((-n) / chunk_size)); |
|
} |
|
return that; |
|
} |
|
|
|
const_iterator operator-(const int &n) const { return this->operator+(-n); } |
|
|
|
// return th distance between two iterator, |
|
// if these two iterators points to different vectors, throw invaild_iterator. |
|
int operator-(const const_iterator &rhs) const |
|
{ |
|
if (rhs.q != this->q) |
|
throw invalid_iterator(); |
|
return this->distance_to_head() - rhs.distance_to_head(); |
|
} |
|
|
|
/** |
|
* *it |
|
*/ |
|
const T &operator*() const |
|
{ |
|
if (chunk == q->tail && pos == q->chunk_tail) |
|
throw index_out_of_bound(); |
|
return *pos; |
|
} |
|
|
|
/** |
|
* it->field |
|
*/ |
|
const T *operator->() const noexcept { return this->pos; } |
|
|
|
bool operator==(const iterator &rhs) const |
|
{ |
|
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos); |
|
} |
|
|
|
bool operator==(const const_iterator &rhs) const |
|
{ |
|
return (q == rhs.q) && (chunk == rhs.chunk) && (pos == rhs.pos); |
|
} |
|
|
|
/** |
|
* some other operator for iterator. |
|
*/ |
|
bool operator!=(const iterator &rhs) const { return !(*this == rhs); } |
|
|
|
bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); } |
|
|
|
const_iterator operator+=(const int &n) |
|
{ |
|
this->move_forward(n); |
|
return *this; |
|
} |
|
|
|
const_iterator operator-=(const int &n) |
|
{ |
|
this->move_forward(-n); |
|
return *this; |
|
} |
|
|
|
/** |
|
* iter++ |
|
*/ |
|
const_iterator operator++(int) |
|
{ |
|
iterator that(*this); |
|
this->move_forward(1); |
|
return that; |
|
} |
|
|
|
/** |
|
* ++iter |
|
*/ |
|
const_iterator &operator++() |
|
{ |
|
this->move_forward(1); |
|
return *this; |
|
} |
|
|
|
/** |
|
* iter-- |
|
*/ |
|
const_iterator operator--(int) |
|
{ |
|
iterator that(*this); |
|
this->move_forward(-1); |
|
return that; |
|
} |
|
|
|
/** |
|
* --iter |
|
*/ |
|
const_iterator &operator--() |
|
{ |
|
this->move_forward(-1); |
|
return *this; |
|
} |
|
}; |
|
|
|
/** |
|
* constructors |
|
*/ |
|
deque() { create_new(); } |
|
|
|
deque(const deque &other) { this->copy_from(other); } |
|
|
|
/** |
|
* deconstructor |
|
*/ |
|
~deque() { this->destruct(); } |
|
|
|
/** |
|
* assignment operator |
|
*/ |
|
deque &operator=(const deque &other) |
|
{ |
|
if (this == &other) |
|
return *this; |
|
this->destruct(); |
|
this->copy_from(other); |
|
return *this; |
|
} |
|
|
|
/** |
|
* access specified element with bounds checking |
|
* throw index_out_of_bound if out of bound. |
|
*/ |
|
T &at(const size_t &pos) { return *(begin() + pos); } |
|
|
|
const T &at(const size_t &pos) const { return *(cbegin() + pos); } |
|
|
|
T &operator[](const size_t &pos) { return this->at(pos); } |
|
|
|
const T &operator[](const size_t &pos) const { return this->at(pos); } |
|
|
|
/** |
|
* access the first element |
|
* throw container_is_empty when the container is empty. |
|
*/ |
|
const T &front() const |
|
{ |
|
throw_when_empty(); |
|
return *chunk_head; |
|
} |
|
|
|
/** |
|
* access the last element |
|
* throw container_is_empty when the container is empty. |
|
*/ |
|
const T &back() const |
|
{ |
|
throw_when_empty(); |
|
return *(chunk_tail - 1); |
|
} |
|
|
|
/** |
|
* returns an iterator to the beginning. |
|
*/ |
|
iterator begin() { return iterator(this, head, chunk_head); } |
|
|
|
const_iterator cbegin() const { return const_iterator(this, head, chunk_head); } |
|
|
|
/** |
|
* returns an iterator to the end. |
|
*/ |
|
iterator end() { return iterator(this, tail, chunk_tail); } |
|
|
|
const_iterator cend() const { return const_iterator(this, tail, chunk_tail); } |
|
|
|
/** |
|
* checks whether the container is empty. |
|
*/ |
|
bool empty() const |
|
{ |
|
if (head == tail && chunk_head == chunk_tail) |
|
return true; |
|
else |
|
return false; |
|
} |
|
|
|
/** |
|
* returns the number of elements |
|
*/ |
|
size_t size() const { return cend() - cbegin(); } |
|
|
|
/** |
|
* clears the contents |
|
*/ |
|
void clear() |
|
{ |
|
this->destruct(); |
|
this->create_new(); |
|
} |
|
|
|
/** |
|
* inserts elements at the specified locat on in the container. |
|
* inserts value before pos |
|
* returns an iterator pointing to the inserted value |
|
* throw if the iterator is invalid or it point to a wrong place. |
|
*/ |
|
iterator insert(iterator pos, const T &value) |
|
{ |
|
if (pos == end()) |
|
{ |
|
push_back(value); |
|
return end() - 1; |
|
} |
|
push_back(value); |
|
iterator cur = end(); |
|
--cur; |
|
while (cur != pos) |
|
{ |
|
iterator next = cur; |
|
--cur; |
|
std::swap_ranges(next.pos, next.pos + 1, cur.pos); |
|
} |
|
return pos; |
|
} |
|
|
|
/** |
|
* removes specified element at pos. |
|
* removes the element at pos. |
|
* returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned. |
|
* throw if the container is empty, the iterator is invalid or it points to a wrong place. |
|
*/ |
|
iterator erase(iterator pos) |
|
{ |
|
iterator lst = end(); |
|
--lst; |
|
iterator cur = pos; |
|
while (cur != lst) |
|
{ |
|
iterator prev = cur; |
|
++cur; |
|
std::swap_ranges(prev.pos, prev.pos + 1, cur.pos); |
|
} |
|
pop_back(); |
|
return pos; |
|
} |
|
|
|
/** |
|
* adds an element to the end |
|
*/ |
|
void push_back(const T &value) |
|
{ |
|
if (chunk_tail - tail->data == chunk_size) |
|
{ |
|
append_chunk(); |
|
chunk_tail = tail->data; |
|
} |
|
tail->allocator.construct(chunk_tail, value); |
|
++chunk_tail; |
|
} |
|
|
|
/** |
|
* removes the last element |
|
* throw when the container is empty. |
|
*/ |
|
void pop_back() |
|
{ |
|
throw_when_empty(); |
|
--chunk_tail; |
|
tail->allocator.destroy(chunk_tail); |
|
if (chunk_tail - tail->data == 0) |
|
{ |
|
if (head != tail) |
|
{ |
|
shrink_tail_chunk(); |
|
chunk_tail = tail->data + chunk_size; |
|
} |
|
} |
|
} |
|
|
|
/** |
|
* inserts an element to the beginning. |
|
*/ |
|
void push_front(const T &value) |
|
{ |
|
if (chunk_head - head->data == 0) |
|
{ |
|
prepend_chunk(); |
|
chunk_head = head->data + chunk_size; |
|
} |
|
--chunk_head; |
|
head->allocator.construct(chunk_head, value); |
|
} |
|
|
|
/** |
|
* removes the first element. |
|
* throw when the container is empty. |
|
*/ |
|
void pop_front() |
|
{ |
|
throw_when_empty(); |
|
head->allocator.destroy(chunk_head); |
|
++chunk_head; |
|
if (chunk_head - head->data == chunk_size) |
|
{ |
|
if (head == tail) |
|
{ |
|
chunk_head = chunk_tail = head->data; |
|
} |
|
else |
|
{ |
|
shrink_head_chunk(); |
|
chunk_head = head->data; |
|
} |
|
} |
|
} |
|
|
|
void debug() |
|
{ |
|
Chunk *ptr = head; |
|
while (ptr) |
|
{ |
|
for (int i = 0; i < chunk_size; i++) |
|
fprintf(stderr, "%d ", ptr->data[i]); |
|
ptr = ptr->next; |
|
} |
|
fprintf(stderr, "\n"); |
|
} |
|
}; |
|
|
|
} // namespace sjtu |
|
|
|
#endif |