aboutsummaryrefslogtreecommitdiff
path: root/List.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'List.hpp')
-rw-r--r--List.hpp319
1 files changed, 264 insertions, 55 deletions
diff --git a/List.hpp b/List.hpp
index ebe0dc2..8f13d02 100644
--- a/List.hpp
+++ b/List.hpp
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/01 09:31:07 by cacharle #+# #+# */
-/* Updated: 2020/04/24 19:16:46 by charles ### ########.fr */
+/* Updated: 2020/04/26 12:50:59 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -32,33 +32,41 @@ namespace ft
typedef size_t size_type;
explicit List(const allocator_type& alloc = allocator_type())
- : m_front(NULL), m_back(NULL), m_size(0) {}
+ : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc) {}
- List(const List& other) { *this = other; }
+ List(const List& other) : m_front(NULL), m_back(NULL) { *this = other; }
List& operator=(const List& other)
{
- if (*this == other)
+ if (this == &other)
return *this;
- delete m_front;
- m_front = NULL;
- m_back = NULL;
- // use iterator
+ clear();
+ for (iterator it = other.begin(); it != other.end(); ++it)
+ push_back(*it);
+ m_alloc = other.m_alloc;
return *this;
}
- ~List() {
- clear();
- }
+ ~List() { delete m_front; }
explicit List(size_type n,
const value_type& val = value_type(),
- const allocator_type& alloc = allocator_type()) {}
+ const allocator_type& alloc = allocator_type())
+ : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc)
+ {
+ while (n-- > 0)
+ push_back(val);
+ }
template<typename InputIterator>
List(InputIterator first,
InputIterator last,
- const allocator_type& alloc = allocator_type()) {}
+ const allocator_type& alloc = allocator_type())
+ : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc)
+ {
+ for (; first != last; ++first)
+ push_back(*first);
+ }
private:
class ListNode
@@ -66,14 +74,12 @@ namespace ft
public:
ListNode() : m_next(NULL), m_prev(NULL), m_data(value_type()) {}
- ListNode(const ListNode& other)
- {
- if (*this != other)
- *this = other;
- }
+ ListNode(const ListNode& other) { *this = other; }
ListNode& operator=(const ListNode& other)
{
+ if (this == &other)
+ return *this;
m_next = other.m_next;
m_prev = other.m_prev;
m_data = other.m_data;
@@ -92,11 +98,15 @@ namespace ft
}
}
- ListNode(value_type& data) : m_next(NULL), m_prev(NULL), m_data(data) {}
+ ListNode(const value_type& data) : m_next(NULL), m_prev(NULL), m_data(data) {}
ListNode* getNext() const { return m_next; }
ListNode* getPrev() const { return m_prev; }
- value_type& getData() const { return m_data; }
+ value_type& getData() { return m_data; }
+
+ void setNext(ListNode* val) { m_next = val; }
+ void setPrev(ListNode* val) { m_prev = val; }
+ void setData(const value_type& val) { m_data = val; }
private:
ListNode* m_next;
@@ -107,42 +117,30 @@ namespace ft
public:
class iterator
{
+ friend class List<T, Alloc>;
public:
iterator() : m_current(NULL) {}
+ iterator(const iterator& other) { *this = other; }
+ ~iterator() {}
- iterator(const iterator& other) {
- *this = other;
- }
-
- iterator& operator=(const iterator& other) {
- if (*this == other)
+ iterator& operator=(const iterator& other)
+ {
+ if (this == &other)
return *this;
m_current = other.m_current;
return *this;
}
- ~iterator() {}
-
- value_type& operator*() { return m_current->getData(); }
- value_type& operator->() { return m_current->getData(); }
+ value_type& operator*() { return m_current->getData(); }
+ value_type* operator->() { return &m_current->getData(); }
- bool operator==(const iterator& other) { return m_current == other.m_current; }
- bool operator!=(const iterator& other) { return !(operator==(other)); }
+ bool operator==(const iterator& other) const { return m_current == other.m_current; }
+ bool operator!=(const iterator& other) const { return !(*this == other); }
- iterator& operator++(int)
- {
- m_current = m_current->getNext();
- return *this;
- }
-
- iterator& operator--(int)
- {
- m_current = m_current->getPrev();
- return *this;
- }
-
- iterator& operator++() { return operator++; }
- iterator& operator--() { return operator--; }
+ iterator& operator++() { m_current = m_current->getNext(); return *this; }
+ iterator& operator--() { m_current = m_current->getPrev(); return *this; }
+ iterator operator++(int) { iterator copy(*this); operator++(); return copy; }
+ iterator operator--(int) { iterator copy(*this); operator--(); return copy; }
private:
iterator(ListNode* current) : m_current(current) {}
@@ -150,46 +148,176 @@ namespace ft
List::ListNode* m_current;
};
- iterator begin() { return iterator(m_front); }
- iterator end() { return iterator(NULL); }
+ class const_iterator : public iterator
+ {
+ public:
+ const_iterator() : iterator() {}
+ const_iterator(const iterator& other) : iterator(other) {}
+ ~const_iterator() {}
+ const value_type& operator*() const { return iterator::m_current->getData(); }
+ const value_type* operator->() const { return &iterator::m_current->getData(); }
+ };
+
+ iterator begin() { return iterator(m_front); }
+ iterator end() { return iterator(NULL); }
+ const_iterator begin() const { return const_iterator(m_front); }
+ const_iterator end() const { return const_iterator(NULL); }
+
+ bool empty() const { return m_size == 0; }
+ size_type size() const { return m_size; }
+ size_type max_size() const { return UINT_MAX; }
- bool empty() const { return m_front == NULL; }
- size_type size() const { return m_size; }
- size_type max_size() const { return m_size; }
+ reference front() { return m_front->getData(); }
+ reference back() { return m_back->getData(); }
+ const_reference front() const { return m_front->getData(); }
+ const_reference back() const { return m_back->getData(); }
- reference front() { return m_front->getData(); }
- reference back() { return m_back->getData(); }
+ template <typename InputIterator>
+ void assign(InputIterator first, InputIterator last)
+ {
+ clear();
+ for (; first != last; ++first)
+ push_back(*first);
+ }
+
+ void assign(size_type n, const value_type& val)
+ {
+ clear();
+ while (n-- > 0)
+ push_back(val);
+ }
void push_front(const value_type& val)
{
ListNode* new_front = new ListNode(val);
new_front->setNext(m_front);
- m_front->setPrev(new_front);
+ if (m_front != NULL)
+ m_front->setPrev(new_front);
+ else
+ m_back = new_front;
m_front = new_front;
+ m_size++;
}
void push_back(const value_type& val)
{
ListNode* new_back = new ListNode(val);
new_back->setPrev(m_back);
- m_back->setNext(new_back);
+ if (m_back != NULL)
+ m_back->setNext(new_back);
+ else
+ m_front = new_back;
m_back = new_back;
+ m_size++;
}
void pop_front()
{
ListNode* tmp = m_front->getNext();
tmp->setPrev(NULL);
+ m_front->setNext(NULL);
delete m_front;
m_front = tmp;
+ m_size--;
}
void pop_back()
{
ListNode* tmp = m_back->getPrev();
tmp->setNext(NULL);
+ m_back->setPrev(NULL);
delete m_back;
m_back = tmp;
+ m_size--;
+ }
+
+ iterator insert(iterator position, const value_type& val)
+ {
+ ListNode* inserted = new ListNode(val);
+
+ if (position.m_current->m_prev != NULL)
+ position.m_current->m_prev->m_next = inserted;
+ else
+ m_front = inserted;
+ if (position.m_current->m_next != NULL)
+ position.m_current->m_next->m_prev = inserted;
+ else
+ m_back = inserted;
+ m_size++;
+ return iterator(inserted);
+ }
+
+ void insert(iterator position, size_type n, const value_type& val)
+ {
+ while (n-- > 0)
+ insert(position, val);
+ }
+
+ template <typename InputIterator>
+ void insert(iterator position, InputIterator first, InputIterator last)
+ {
+ if (first == last)
+ return;
+ --last;
+ for (; last != first; --last)
+ insert(position, *last);
+ insert(position, *last);
+ }
+
+ iterator erase(iterator position)
+ {
+ iterator ret(position.m_current->m_next);
+
+ if (position.m_current->m_prev != NULL)
+ position.m_current->m_prev->m_next = position.m_current->m_next;
+ if (position.m_current->m_next != NULL)
+ position.m_current->m_next->m_prev = position.m_current->m_prev;
+ delete position.m_current;
+ m_size--;
+ return ret;
+ }
+
+ iterator erase(iterator first, iterator last)
+ {
+ iterator tmp(first);
+
+ while (first != last)
+ {
+ ++tmp;
+ erase(first);
+ first = tmp;
+ }
+ return last;
+ }
+
+ void swap(List& x)
+ {
+ ListNode* tmp_front = x.m_front;
+ ListNode* tmp_back = x.m_back;
+ size_type tmp_size = x.m_size;
+ allocator_type tmp_alloc = x.m_alloc;
+
+ x.m_front = m_front;
+ x.m_back = m_back;
+ x.m_size = m_size;
+ x.m_alloc = m_alloc;
+
+ m_front = tmp_front;
+ m_back = tmp_back;
+ m_size = tmp_size;
+ m_alloc = tmp_alloc;
+ }
+
+ void resize(size_type n, value_type val = value_type())
+ {
+ if (n == m_size)
+ return;
+ if (n < m_size)
+ while (n-- > 0)
+ pop_back();
+ else
+ while (n-- > 0)
+ push_back(val);
}
void clear()
@@ -200,11 +328,92 @@ namespace ft
m_size = 0;
}
+ void remove(const value_type& val) { remove_if(EqualPredicate(val)); }
+
+ template <typename Predicate>
+ void remove_if(Predicate pred)
+ {
+ for (iterator it = begin(); it != end(); ++it)
+ if (pred(*it))
+ erase(it);
+ }
+
+ void merge(List& x) { merge(x, &compar); }
+
+ template <typename Compare>
+ void merge(List& x, Compare comp)
+ {
+ iterator it = begin();
+ while (!x.empty())
+ {
+ while (it != end() && comp(*it, x.front()))
+ ++it;
+ insert(it, x.front());
+ x.pop_front();
+ }
+ }
+
+ void sort() { sort(&compar); }
+
+ template <typename Compare>
+ void sort(Compare comp)
+ {
+ (void)comp;
+ // for (iterator it = begin(); it != end(); ++it)
+ // {
+ // for (iterator it2(it); it2 != end(); ++it)
+ // }
+ }
+
+ void reverse()
+ {
+
+ }
+
+ bool operator==(const List& other) const
+ {
+ if (m_size != other.m_size)
+ return false;
+ iterator it1 = begin();
+ iterator it2 = begin();
+ for (; it1 != end(); ++it1, ++it2)
+ if (*it1 != *it2)
+ return false;
+ return true;
+ }
+
+ bool operator!=(const List& other) const { return !(*this == other); }
+
+ bool operator<(const List& other) const
+ {
+ iterator it1 = begin();
+ iterator it2 = begin();
+ for (; it1 != end() && it2 != end() && *it1 == *it2; ++it1, ++it2);
+
+ if (it1 == end() && it2 == other.end())
+ return false;
+ if (it1 == end() || it2 == other.end())
+ return it1 == end();
+ return *it1 < *it2;
+ }
+
+ bool operator>(const List& other) const { return other < *this; }
+ bool operator<=(const List& other) const { return !(*this > other); }
+ bool operator>=(const List& other) const { return !(*this < other); }
private:
ListNode* m_front;
ListNode* m_back;
size_type m_size;
+ allocator_type m_alloc;
+
+ static bool compar(const value_type& a, const value_type& b) { return a < b; }
+
+ struct EqualPred
+ {
+ bool operator()(const value_type& other) const { return val == other; }
+ const value_type& val;
+ };
};
}
generated by cgit (git 2.34.1) at 2026-05-16 00:26:35 +0000