summaryrefslogtreecommitdiff
path: root/STL/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'STL/list.h')
-rw-r--r--STL/list.h366
1 files changed, 188 insertions, 178 deletions
diff --git a/STL/list.h b/STL/list.h
index 095962f6c51..b86184a777f 100644
--- a/STL/list.h
+++ b/STL/list.h
@@ -33,11 +33,11 @@
/*
- *Added by d:\Terris\convert.pl --begin--
+ *Added by d:\\convert.pl --begin--
*/
namespace std {
/*
- *Added by d:\Terris\convert.pl --end--
+ *Added by d:\\convert.pl --end--
*/
template <class T>
@@ -47,9 +47,9 @@ protected:
struct list_node;
friend list_node;
struct list_node {
- void_pointer next;
- void_pointer prev;
- T data;
+ void_pointer next;
+ void_pointer prev;
+ T data;
};
static Allocator<list_node> list_node_allocator;
static Allocator<T> value_allocator;
@@ -65,13 +65,13 @@ public:
typedef Allocator<list_node>::difference_type difference_type;
protected:
size_type buffer_size() {
- return list_node_allocator.init_page_size();
+ return list_node_allocator.init_page_size();
}
struct list_node_buffer;
friend list_node_buffer;
struct list_node_buffer {
- void_pointer next_buffer;
- link_type buffer;
+ void_pointer next_buffer;
+ link_type buffer;
};
public:
typedef Allocator<list_node_buffer> buffer_allocator_type;
@@ -86,12 +86,12 @@ protected:
/*static*/ link_type next_avail;
/*static*/ link_type last;
void add_new_buffer() {
- buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
- tmp->buffer = list_node_allocator.allocate(buffer_size());
- tmp->next_buffer = buffer_list;
- buffer_list = tmp;
- next_avail = buffer_list->buffer;
- last = next_avail + buffer_size();
+ buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
+ tmp->buffer = list_node_allocator.allocate(buffer_size());
+ tmp->next_buffer = buffer_list;
+ buffer_list = tmp;
+ next_avail = buffer_list->buffer;
+ last = next_avail + buffer_size();
}
/*
* Changed by Terris
@@ -99,15 +99,15 @@ protected:
/*static*/ size_type number_of_lists;
void deallocate_buffers();
link_type get_node() {
- link_type tmp = free_list;
- return free_list ? (free_list = (link_type)(free_list->next), tmp)
- : (next_avail == last ? (add_new_buffer(), next_avail++)
- : next_avail++);
- // ugly code for inlining - avoids multiple returns
+ link_type tmp = free_list;
+ return free_list ? (free_list = (link_type)(free_list->next), tmp)
+ : (next_avail == last ? (add_new_buffer(), next_avail++)
+ : next_avail++);
+ // ugly code for inlining - avoids multiple returns
}
void put_node(link_type p) {
- p->next = free_list;
- free_list = p;
+ p->next = free_list;
+ free_list = p;
}
protected:
@@ -121,63 +121,63 @@ public:
friend class const_iterator;
// friend bool operator==(const iterator& x, const iterator& y);
protected:
- link_type node;
- iterator(link_type x) : node(x) {}
+ link_type node;
+ iterator(link_type x) : node(x) {}
public:
- iterator() {}
- bool operator==(const iterator& x) const { return node == x.node; }
- reference operator*() const { return (*node).data; }
- iterator& operator++() {
- node = (link_type)((*node).next);
- return *this;
- }
- iterator operator++(int) {
- iterator tmp = *this;
- ++*this;
- return tmp;
- }
- iterator& operator--() {
- node = (link_type)((*node).prev);
- return *this;
- }
- iterator operator--(int) {
- iterator tmp = *this;
- --*this;
- return tmp;
- }
+ iterator() {}
+ bool operator==(const iterator& x) const { return node == x.node; }
+ reference operator*() const { return (*node).data; }
+ iterator& operator++() {
+ node = (link_type)((*node).next);
+ return *this;
+ }
+ iterator operator++(int) {
+ iterator tmp = *this;
+ ++*this;
+ return tmp;
+ }
+ iterator& operator--() {
+ node = (link_type)((*node).prev);
+ return *this;
+ }
+ iterator operator--(int) {
+ iterator tmp = *this;
+ --*this;
+ return tmp;
+ }
};
class const_iterator : public bidirectional_iterator<T, difference_type> {
friend class list<T>;
protected:
- link_type node;
- const_iterator(link_type x) : node(x) {}
+ link_type node;
+ const_iterator(link_type x) : node(x) {}
public:
- const_iterator() {}
- const_iterator(const iterator& x) : node(x.node) {}
- bool operator==(const const_iterator& x) const { return node == x.node; }
- const_reference operator*() const { return (*node).data; }
- const_iterator& operator++() {
- node = (link_type)((*node).next);
- return *this;
- }
- const_iterator operator++(int) {
- const_iterator tmp = *this;
- ++*this;
- return tmp;
- }
- const_iterator& operator--() {
- node = (link_type)((*node).prev);
- return *this;
- }
- const_iterator operator--(int) {
- const_iterator tmp = *this;
- --*this;
- return tmp;
- }
+ const_iterator() {}
+ const_iterator(const iterator& x) : node(x.node) {}
+ bool operator==(const const_iterator& x) const { return node == x.node; }
+ const_reference operator*() const { return (*node).data; }
+ const_iterator& operator++() {
+ node = (link_type)((*node).next);
+ return *this;
+ }
+ const_iterator operator++(int) {
+ const_iterator tmp = *this;
+ ++*this;
+ return tmp;
+ }
+ const_iterator& operator--() {
+ node = (link_type)((*node).prev);
+ return *this;
+ }
+ const_iterator operator--(int) {
+ const_iterator tmp = *this;
+ --*this;
+ return tmp;
+ }
};
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type>
- const_reverse_iterator;
+ const_reverse_iterator;
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type>
reverse_iterator;
@@ -185,10 +185,10 @@ public:
* Changed by Terris
*/
list() : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) {
- ++number_of_lists;
- node = get_node();
- (*node).next = node;
- (*node).prev = node;
+ ++number_of_lists;
+ node = get_node();
+ (*node).next = node;
+ (*node).prev = node;
}
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
@@ -210,109 +210,119 @@ public:
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }
void swap(list<T>& x) {
- std::swap(node, x.node);
- std::swap(length, x.length);
- }
+ std::swap(node, x.node);
+ std::swap(length, x.length);
+ /*
+ * Added By Terris
+ */
+ std::swap(buffer_list, x.buffer_list);
+ std::swap(free_list, x.free_list);
+ std::swap(next_avail, x.next_avail);
+ std::swap(last, x.last);
+ /*
+ * Added By Terris
+ */
+ }
iterator insert(iterator position, const T& x) {
- link_type tmp = get_node();
- construct(value_allocator.address((*tmp).data), x);
- (*tmp).next = position.node;
- (*tmp).prev = (*position.node).prev;
- (*(link_type((*position.node).prev))).next = tmp;
- (*position.node).prev = tmp;
- ++length;
- return tmp;
+ link_type tmp = get_node();
+ construct(value_allocator.address((*tmp).data), x);
+ (*tmp).next = position.node;
+ (*tmp).prev = (*position.node).prev;
+ (*(link_type((*position.node).prev))).next = tmp;
+ (*position.node).prev = tmp;
+ ++length;
+ return tmp;
}
void insert(iterator position, const T* first, const T* last);
void insert(iterator position, const_iterator first,
- const_iterator last);
+ const_iterator last);
void insert(iterator position, size_type n, const T& x);
void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }
void erase(iterator position) {
- (*(link_type((*position.node).prev))).next = (*position.node).next;
- (*(link_type((*position.node).next))).prev = (*position.node).prev;
- destroy(value_allocator.address((*position.node).data));
- put_node(position.node);
- --length;
+ (*(link_type((*position.node).prev))).next = (*position.node).next;
+ (*(link_type((*position.node).next))).prev = (*position.node).prev;
+ destroy(value_allocator.address((*position.node).data));
+ put_node(position.node);
+ --length;
}
void erase(iterator first, iterator last);
void pop_front() { erase(begin()); }
void pop_back() {
- iterator tmp = end();
- erase(--tmp);
+ iterator tmp = end();
+ erase(--tmp);
}
/*
* Changed by Terris
*/
list(size_type n, const T& value = T()) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) {
- ++number_of_lists;
- node = get_node();
- (*node).next = node;
- (*node).prev = node;
- insert(begin(), n, value);
+ ++number_of_lists;
+ node = get_node();
+ (*node).next = node;
+ (*node).prev = node;
+ insert(begin(), n, value);
}
/*
* Changed by Terris
*/
list(const T* first, const T* last) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) {
- ++number_of_lists;
- node = get_node();
- (*node).next = node;
- (*node).prev = node;
- insert(begin(), first, last);
+ ++number_of_lists;
+ node = get_node();
+ (*node).next = node;
+ (*node).prev = node;
+ insert(begin(), first, last);
}
/*
* Changed by Terris
*/
list(const list<T>& x) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) {
- ++number_of_lists;
- node = get_node();
- (*node).next = node;
- (*node).prev = node;
- insert(begin(), x.begin(), x.end());
+ ++number_of_lists;
+ node = get_node();
+ (*node).next = node;
+ (*node).prev = node;
+ insert(begin(), x.begin(), x.end());
}
~list() {
- erase(begin(), end());
- put_node(node);
- if (--number_of_lists == 0) deallocate_buffers();
+ erase(begin(), end());
+ put_node(node);
+ if (--number_of_lists == 0) deallocate_buffers();
}
list<T>& operator=(const list<T>& x);
protected:
void transfer(iterator position, iterator first, iterator last) {
- (*(link_type((*last.node).prev))).next = position.node;
- (*(link_type((*first.node).prev))).next = last.node;
- (*(link_type((*position.node).prev))).next = first.node;
- link_type tmp = link_type((*position.node).prev);
- (*position.node).prev = (*last.node).prev;
- (*last.node).prev = (*first.node).prev;
- (*first.node).prev = tmp;
+ (*(link_type((*last.node).prev))).next = position.node;
+ (*(link_type((*first.node).prev))).next = last.node;
+ (*(link_type((*position.node).prev))).next = first.node;
+ link_type tmp = link_type((*position.node).prev);
+ (*position.node).prev = (*last.node).prev;
+ (*last.node).prev = (*first.node).prev;
+ (*first.node).prev = tmp;
}
public:
void splice(iterator position, list<T>& x) {
- if (!x.empty()) {
- transfer(position, x.begin(), x.end());
- length += x.length;
- x.length = 0;
- }
+ if (!x.empty()) {
+ transfer(position, x.begin(), x.end());
+ length += x.length;
+ x.length = 0;
+ }
}
void splice(iterator position, list<T>& x, iterator i) {
- iterator j = i;
- if (position == i || position == ++j) return;
- transfer(position, i, j);
- ++length;
- --x.length;
+ iterator j = i;
+ if (position == i || position == ++j) return;
+ transfer(position, i, j);
+ ++length;
+ --x.length;
}
void splice(iterator position, list<T>& x, iterator first, iterator last) {
- if (first != last) {
- if (&x != this) {
- difference_type n = 0;
- distance(first, last, n);
- x.length -= n;
- length += n;
- }
- transfer(position, first, last);
- }
+ if (first != last) {
+ if (&x != this) {
+ difference_type n = 0;
+ distance(first, last, n);
+ x.length -= n;
+ length += n;
+ }
+ transfer(position, first, last);
+ }
}
void remove(const T& value);
void unique();
@@ -375,10 +385,10 @@ inline bool operator<(const list<T>& x, const list<T>& y) {
template <class T>
void list<T>::deallocate_buffers() {
while (buffer_list) {
- buffer_pointer tmp = buffer_list;
- buffer_list = (buffer_pointer)(buffer_list->next_buffer);
- list_node_allocator.deallocate(tmp->buffer);
- buffer_allocator.deallocate(tmp);
+ buffer_pointer tmp = buffer_list;
+ buffer_list = (buffer_pointer)(buffer_list->next_buffer);
+ list_node_allocator.deallocate(tmp->buffer);
+ buffer_allocator.deallocate(tmp);
}
free_list = 0;
next_avail = 0;
@@ -389,10 +399,10 @@ template <class T>
void list<T>::insert(iterator position, const T* first, const T* last) {
while (first != last) insert(position, *first++);
}
-
+
template <class T>
void list<T>::insert(iterator position, const_iterator first,
- const_iterator last) {
+ const_iterator last) {
while (first != last) insert(position, *first++);
}
@@ -409,15 +419,15 @@ void list<T>::erase(iterator first, iterator last) {
template <class T>
list<T>& list<T>::operator=(const list<T>& x) {
if (this != &x) {
- iterator first1 = begin();
- iterator last1 = end();
- const_iterator first2 = x.begin();
- const_iterator last2 = x.end();
- while (first1 != last1 && first2 != last2) *first1++ = *first2++;
- if (first2 == last2)
- erase(first1, last1);
- else
- insert(last1, first2, last2);
+ iterator first1 = begin();
+ iterator last1 = end();
+ const_iterator first2 = x.begin();
+ const_iterator last2 = x.end();
+ while (first1 != last1 && first2 != last2) *first1++ = *first2++;
+ if (first2 == last2)
+ erase(first1, last1);
+ else
+ insert(last1, first2, last2);
}
return *this;
}
@@ -427,10 +437,10 @@ void list<T>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
- iterator next = first;
- ++next;
- if (*first == value) erase(first);
- first = next;
+ iterator next = first;
+ ++next;
+ if (*first == value) erase(first);
+ first = next;
}
}
@@ -441,11 +451,11 @@ void list<T>::unique() {
if (first == last) return;
iterator next = first;
while (++next != last) {
- if (*first == *next)
- erase(next);
- else
- first = next;
- next = first;
+ if (*first == *next)
+ erase(next);
+ else
+ first = next;
+ next = first;
}
}
@@ -456,12 +466,12 @@ void list<T>::merge(list<T>& x) {
iterator first2 = x.begin();
iterator last2 = x.end();
while (first1 != last1 && first2 != last2)
- if (*first2 < *first1) {
- iterator next = first2;
- transfer(first1, first2, ++next);
- first2 = next;
- } else
- ++first1;
+ if (*first2 < *first1) {
+ iterator next = first2;
+ transfer(first1, first2, ++next);
+ first2 = next;
+ } else
+ ++first1;
if (first2 != last2) transfer(last1, first2, last2);
length += x.length;
x.length= 0;
@@ -471,8 +481,8 @@ template <class T>
void list<T>::reverse() {
if (size() < 2) return;
for (iterator first = ++begin(); first != end();) {
- iterator old = first++;
- transfer(begin(), old, first);
+ iterator old = first++;
+ transfer(begin(), old, first);
}
}
@@ -483,14 +493,14 @@ void list<T>::sort() {
list<T> counter[64];
int fill = 0;
while (!empty()) {
- carry.splice(carry.begin(), *this, begin());
- int i = 0;
- while(i < fill && !counter[i].empty()) {
- counter[i].merge(carry);
- carry.swap(counter[i++]);
- }
- carry.swap(counter[i]);
- if (i == fill) ++fill;
+ carry.splice(carry.begin(), *this, begin());
+ int i = 0;
+ while(i < fill && !counter[i].empty()) {
+ counter[i].merge(carry);
+ carry.swap(counter[i++]);
+ }
+ carry.swap(counter[i]);
+ if (i == fill) ++fill;
}
while(fill--) merge(counter[fill]);
}
@@ -500,11 +510,11 @@ void list<T>::sort() {
/*
- *Added by d:\Terris\convert.pl --begin--
+ *Added by d:\\convert.pl --begin--
*/
}
/*
- *Added by d:\Terris\convert.pl --end--
+ *Added by d:\\convert.pl --end--
*/
#endif
View Lorry Controller Status