Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdexcept>
- #include <cstdlib>
- #include <ctime>
- #include <chrono>
- namespace vp {
- template<class T>
- class list {
- private:
- struct node {
- node();
- node(T Value, node *pnode);
- node(T Value, node *Prev, node *Next);
- ~node();
- void insert_after(node *pnode);
- void insert_before(node *pnode);
- void remove();
- T value;
- node *prev;
- node *next;
- };
- node *firstNode;
- node *lastNode;
- unsigned int mSize;
- typedef T& reference;
- typedef const T& const_reference;
- public:
- class iterator {
- private:
- node *current;
- public:
- friend class list<T>;
- iterator();
- iterator(node* node);
- reference operator ->();
- reference operator *();
- bool operator ==(const iterator it) const;
- bool operator !=(const iterator it) const;
- iterator& operator ++();
- iterator operator ++(int);
- iterator& operator --();
- iterator operator --(int);
- };
- private:
- typedef const typename vp::list<T>::iterator const_iterator;
- public:
- list();
- list(unsigned n, const_reference value = T());
- list(list<T>& x);
- ~list();
- bool operator == (const list<T>& l);
- bool operator < (const list<T>& l);
- bool operator > (const list<T>& l);
- bool operator != (const list<T>& l);
- bool operator >= (const list<T>& l);
- bool operator <= (const list<T>& l);
- list<T>& operator =(const list<T>& l);
- void assign(iterator first, iterator last);
- void assign(unsigned n, const_reference value);
- reference back();
- const_reference back() const;
- iterator begin();
- const_iterator begin() const;
- void clear();
- bool empty() const;
- iterator end();
- const_iterator end() const;
- iterator erase(iterator it);
- iterator erase(iterator first, iterator last);
- reference front();
- const_reference front() const;
- iterator insert(iterator it, const_reference value);
- void insert(iterator it, unsigned n, const_reference value);
- void insert(iterator it, iterator first, iterator last);
- unsigned max_size() const;
- void merge(list<T> l);
- // void merge (list<T>& l, Compare comp);
- void pop_back();
- void pop_front();
- void push_back(T x);
- void push_front(T x);
- iterator rbegin();
- // reverse_iterator rbegin();
- // const_reverse_iterator rbegin() const;
- void remove(const_reference value);
- // void remove_if(Predicate pred);
- iterator rend();
- // reverse_iterator rend();
- // const_reverse_iterator rend() const;
- void resize(unsigned n, T value = T());
- void reverse();
- unsigned int size() const;
- void sort();
- // void sort(Compare comp);
- // void splice(iterator it, list<T>& l);
- // void splice(iterator it, list<T>& l, iterator i);
- // void splice(iterator it, list<T>& l, iterator first, iterator last);
- void swap(list<T> l);
- void unique();
- void unique(BinaryPredicate binary_pred);
- };
- }
- /** Node definitions **/
- template<class T>
- vp::list<T>::node::node() : value(T()), prev(NULL), next(NULL) {}
- template<class T>
- vp::list<T>::node::node(T Value, node *pnode) :
- value(Value), prev(pnode->prev), next(pnode) {
- pnode->prev = this;
- if (prev)
- prev->next = this;
- }
- template<class T>
- vp::list<T>::node::node(T Value, node *Prev, node *Next) :
- value(Value), prev(Prev), next(Next) {
- if (prev)
- prev->next = this;
- if (next)
- next->prev = this;
- }
- template<class T>
- vp::list<T>::node::~node() {
- remove();
- }
- template<class T>
- void vp::list<T>::node::insert_after(node *pnode) {
- if (!pnode || pnode == this)
- return;
- remove();
- prev = pnode;
- next = pnode->next;
- if (pnode->next)
- pnode->next->prev = this;
- pnode->next = this;
- }
- template<class T>
- void vp::list<T>::node::insert_before(node *pnode) {
- if (!pnode || pnode == this)
- return;
- remove();
- next = pnode;
- prev = pnode->prev;
- if (pnode->prev)
- pnode->prev->next = this;
- pnode->prev = this;
- }
- template<class T>
- void vp::list<T>::node::remove() {
- if (prev)
- prev->next = next;
- if (next)
- next->prev = prev;
- next = prev = NULL;
- }
- /** Iterator definitions **/
- template<class T>
- vp::list<T>::iterator::iterator() :
- current(NULL) {}
- template<class T>
- vp::list<T>::iterator::iterator(node *n) :
- current(n) {}
- template<class T>
- typename vp::list<T>::reference vp::list<T>::iterator::operator ->() {
- return current->value;
- }
- template<class T>
- typename vp::list<T>::reference vp::list<T>::iterator::operator *() {
- return current->value;
- }
- template<class T>
- bool vp::list<T>::iterator::operator ==(const iterator it) const {
- return (current == it.current);
- }
- template<class T>
- bool vp::list<T>::iterator::operator !=(const iterator it) const {
- return !operator == (it);
- }
- template<class T>
- typename vp::list<T>::iterator& vp::list<T>::iterator::operator ++() {
- if (current)
- current = current->next;
- return *this;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::iterator::operator ++(int) {
- iterator result = *this;
- if (current)
- current = current->next;
- return result;
- }
- template<class T>
- typename vp::list<T>::iterator& vp::list<T>::iterator::operator --() {
- if (current)
- current = current->prev;
- return *this;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::iterator::operator --(int) {
- iterator result = *this;
- if (current)
- current = current->prev;
- return result;
- }
- /** List definitions **/
- template<class T>
- vp::list<T>::list() :
- firstNode(NULL), lastNode(NULL), mSize(0) {}
- template<class T>
- vp::list<T>::list(unsigned n, const_reference value) :
- firstNode(NULL), lastNode(NULL), mSize(0) {
- for (unsigned i = 0; i < n; i ++)
- push_back(value);
- }
- template<class T>
- vp::list<T>::list(list<T>& x) :
- firstNode(NULL), lastNode(NULL), mSize(0) {
- for (auto it : x)
- push_back(it);
- }
- template<class T>
- vp::list<T>::~list() {
- while (firstNode != NULL) {
- node *n = firstNode->next;
- delete firstNode;
- firstNode = n;
- }
- }
- template<class T>
- bool vp::list<T>::operator == (const list<T>& l) {
- if (mSize != l.mSize)
- return false;
- for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
- if (*lhsIt != *rhsIt)
- return false;
- return true;
- }
- template<class T>
- bool vp::list<T>::operator < (const list<T>& l) {
- if (mSize < l.mSize)
- return true;
- else if (mSize > l.mSize)
- return false;
- for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
- if (*lhsIt < *rhsIt)
- return true;
- else if (*lhsIt > *rhsIt)
- return false;
- return false;
- }
- template<class T>
- bool vp::list<T>::operator > (const list<T>& l) {
- if (mSize > l.mSize)
- return true;
- else if (mSize < l.mSize)
- return false;
- for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
- if (*lhsIt > *rhsIt)
- return true;
- else if (*lhsIt < *rhsIt)
- return false;
- return false;
- }
- template<class T>
- bool vp::list<T>::operator != (const list<T>& l) {
- return !(*this == l);
- }
- template<class T>
- bool vp::list<T>::operator >= (const list<T>& l) {
- return !(*this < l);
- }
- template<class T>
- bool vp::list<T>::operator <= (const list<T>& l) {
- return !(*this > l);
- }
- template<class T>
- vp::list<T>& vp::list<T>::operator = (const list<T>& l) {
- clear();
- for (T val : l)
- push_back(val);
- return *this;
- }
- template<class T>
- void vp::list<T>::assign(iterator first, iterator last) {
- clear();
- for (; first != last; first ++)
- push_back(*first);
- }
- template<class T>
- void vp::list<T>::assign(unsigned n, const_reference value) {
- clear();
- for (unsigned i = 0; i < n; i ++)
- push_back(value);
- }
- template<class T>
- typename vp::list<T>::reference vp::list<T>::back() {
- if (empty())
- throw std::logic_error("list: Invoked back() on empty list") ;
- return lastNode->value;
- }
- template<class T>
- typename vp::list<T>::const_reference vp::list<T>::back() const {
- if (empty())
- throw std::logic_error("list: Invoked back() on empty list") ;
- return lastNode->value;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::begin() {
- return iterator(firstNode);
- }
- template<class T>
- typename vp::list<T>::const_iterator vp::list<T>::begin() const {
- return iterator(firstNode);
- }
- template<class T>
- void vp::list<T>::clear() {
- while (firstNode != NULL) {
- node *n = firstNode->next;
- delete firstNode;
- firstNode = n;
- }
- lastNode = firstNode;
- mSize = 0;
- }
- template<class T>
- bool vp::list<T>::empty() const {
- return !mSize;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
- if (it != end()) {
- if (firstNode == it.current)
- firstNode = it.current->next;
- if (lastNode == it.current)
- lastNode = it.current->prev;
- mSize --;
- delete(it++).current;
- }
- return it;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::erase(iterator first, iterator last) {
- for (; first != last; first ++)
- erase(first);
- return (++ last);
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::end() {
- return iterator();
- }
- template<class T>
- typename vp::list<T>::const_iterator vp::list<T>::end() const {
- return iterator();
- }
- template<class T>
- typename vp::list<T>::reference vp::list<T>::front() {
- if (empty())
- throw std::logic_error("list: Invoked front() on empty list") ;
- return firstNode->value;
- }
- template<class T>
- typename vp::list<T>::const_reference vp::list<T>::front() const {
- if (empty())
- throw std::logic_error("list: Invoked front() on empty list") ;
- return firstNode->value;
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::insert(iterator it, const_reference value) {
- iterator result(new node(value, it.current->prev, it.current->next));
- mSize ++;
- return result;
- }
- template<class T>
- void vp::list<T>::insert(iterator it, unsigned n, const_reference value) {
- for (unsigned i = 0; i < n; i ++)
- it = insert(it, value);
- }
- template<class T>
- void vp::list<T>::insert(iterator it, iterator first, iterator last) {
- for (; first != last; first ++)
- it = insert(it, *first);
- }
- template<class T>
- unsigned vp::list<T>::max_size() const {
- return mSize;
- }
- template<class T>
- void vp::list<T>::merge(list<T> l) {
- node *p = firstNode;
- while (l.size()) {
- node *q = l.firstNode;
- if (q->value < p->value) {
- l.firstNode = l.firstNode->next;
- q->insert_before(p);
- if (p == firstNode)
- firstNode = q;
- mSize ++;
- l.mSize --;
- }
- else if (p == lastNode) {
- l.firstNode = l.firstNode->next;
- q->insert_after(p);
- p = lastNode = q;
- mSize ++;
- l.mSize --;
- }
- else
- p = p->next;
- }
- }
- template<class T>
- void vp::list<T>::pop_back() {
- if (empty())
- return;
- node *n = lastNode->prev;
- n->next = NULL;
- delete lastNode;
- lastNode = n;
- mSize --;
- if (empty())
- firstNode = lastNode;
- }
- template<class T>
- void vp::list<T>::pop_front() {
- if (empty())
- return;
- node *n = firstNode->next;
- n->prev = NULL;
- delete firstNode;
- firstNode = n;
- mSize --;
- if (empty())
- lastNode = firstNode;
- }
- template<class T>
- void vp::list<T>::push_back(T x) {
- lastNode = new node(x, lastNode, NULL);
- if (firstNode == NULL)
- firstNode = lastNode;
- mSize ++;
- }
- template<class T>
- void vp::list<T>::push_front(T x) {
- firstNode = new node(x, NULL, firstNode);
- if (lastNode == NULL)
- lastNode = firstNode;
- mSize ++;
- }
- /** Need to add and change to reverse_iterator **/
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::rbegin() {
- return iterator(lastNode);
- }
- template<class T>
- void vp::list<T>::remove(const_reference value) {
- for (iterator it(firstNode); it != end(); it ++)
- if (*it == value)
- erase(it);
- }
- template<class T>
- typename vp::list<T>::iterator vp::list<T>::rend() {
- return iterator();
- }
- template<class T>
- void vp::list<T>::resize(unsigned n, T value) {
- if (n < mSize)
- while (mSize > n)
- pop_back();
- else
- for (unsigned i = 0; i < n; i ++)
- push_back(value);
- }
- template<class T>
- void vp::list<T>::reverse() {
- node* temp = lastNode;
- lastNode = firstNode;
- firstNode = temp;
- for (node* tempNode = temp; temp; temp = temp->next) {
- tempNode = temp->prev;
- temp->prev = temp->next;
- temp->next = tempNode;
- }
- }
- template<class T>
- unsigned int vp::list<T>::size() const {
- return mSize;
- }
- template<class T>
- void vp::list<T>::sort() {
- if (size() <= 1)
- return;
- for (int merges = 0, k = 1; merges != 1; k *= 2) {
- node *p = firstNode, *q = p;
- for (int qsize = merges = 0; p; merges ++, p = q) {
- for (qsize = 0; qsize < k && q; qsize ++, q = q->next);
- while (qsize && q) {
- if (q->value <= p->value) {
- if (q->next) {
- q = q->next;
- q->prev->insert_before(p);
- }
- else {
- q->insert_before(p);
- q = NULL;
- lastNode = lastNode->prev;
- }
- if (p == firstNode)
- firstNode = firstNode->prev;
- qsize --;
- }
- else
- p = p->next;
- }
- }
- }
- }
- //void splice(iterator it, list<T>& l);
- //void splice(iterator it, list<T>& l, iterator i);
- //void splice(iterator it, list<T>& l, iterator first, iterator last);
- template<class T>
- void vp::list<T>::swap(list<T> l) {
- list<T> temp = l;
- l = *this;
- this = temp;
- }
- template<class T>
- void vp::list<T>::unique() {
- for (iterator it = begin(); it != end(); it ++)
- if ((it != begin()) && (*it == it.current->prev->value))
- erase(it --);
- }
- template<class T>
- void vp::list<T>::unique(BinaryPredicate binary_pred) {
- for (iterator it = begin(); it != end(); it ++)
- if ((it != begin()) && (binary_pred(*it, it.current->prev->value)))
- erase(it --);
- }
- bool isSame(int a, int b) {
- return a == b;
- }
- int main() {
- vp::list<int> list1, list2;
- for (int i = 0; i < 10; i ++) {
- list1.push_back(i);
- list2.push_back(i);
- }
- list1.pop_back();
- list1.push_back(7);
- list1.sort();
- list1.unique(isSame);
- for (auto it : list1)
- std::cout << *it << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement