Implementation source code
my_check.hpp
#ifndef MY_CHECK_HPP
#define MY_CHECK_HPP
#include<stdexcept>
#include<iostream>
#include"my_config.h"
#if _GLIBCXX_VER
#define CHECK(x, y) check_pointer_range::check(x, y)
#else
#define CHECK(x, y)
#endif
#if _GLIBCXX_VER
#define CHECK_N_PTR(x) check_nullptr::check(x)
#else
#define CHECK_N_PTR(x)
#endif
#if _WIN32
#define DEBUG() std::cerr << __LINE__ << "\
"
#else
#define DEBUG()
#endif // _WIN32
struct check_pointer_range {
template<typename T>
static constexpr void check(T* x, T* y) {
if(!x || !(--y))
std::cerr << "The pointer is nullptr" << "\
";
}
};
struct check_nullptr {
template<typename T>
static constexpr void check(T* x) {
if(!x)
std::cerr << "The pointer is nullptr" << "\
";
}
};
#endif // !MY_CHECK_HPP
link_list.hpp
#ifndef LINK_LIST_HPP
#define LINK_LIST_HPP
#include<initializer_list>
#include<type_traits>
#include"my_check.hpp"
template<class T>
struct Node {
Node() : data(T{}), next(nullptr) {}
T data;
Node* next;
};
template<class T>
class LinkList {
public:
using size_type = std::int64_t;
using value_type = T;
using reference = T &;
using const_reference = const T &;
using const_pointer_type = const Node<T>*;
using pointer_type = Node<T>*;
public:
LinkList(): _head(new Node<value_type>), _ret_ptr(nullptr) {}
explicit LinkList(std::initializer_list<T> li) : _head(new Node<value_type>), _ret_ptr(nullptr) {
for(auto it = li.begin(); it != li.end(); + + it)
this->push(*it);
}
LinkList(const LinkList & amp; x) : _head(new Node<value_type>), _ret_ptr(nullptr) {
this->copyElement(x.getHeadPtr());
}
~LinkList() {
if(_ret_ptr)
_ret_ptr = nullptr;
if(_head) {
while(_head->next) {
this->pop();
}
delete _head;
_head = nullptr;
}
}
public:
template<typename U,
typename std::enable_if<std::is_same<U, value_type>::value, int>::type = 0>
void push(U val) {
Node<U>* tmp = new Node<T>;
tmp->data = val;
tmp->next = _head->next;
_head->next = tmp;
}
void pop() {
this->checkNullContainer("the list isn't elements");
pointer_type del = _head->next;
_head->next = del->next;
delete del;
del = nullptr;
}
/// @brief deletes the element pointed to by @c p
/// @return returns the next pointer to the currently deleted element
pointer_type erease(pointer_type p) {
this->checkNullContainer("the list isn't elements");
CHECK_N_PTR(p->next);
CHECK_N_PTR(p);
pointer_type del_p = p->next;
//swap next node's value
::swap(p->data, del_p->data);
p->next = del_p->next;
delete del_p;
del_p = nullptr;
return p;
}
/// @brief deletes data in the range from @a beg to @a end
/// @return end's pointer
pointer_type erease(pointer_type beg, pointer_type end) {
this->checkNullContainer("the list isn't elements");
CHECK_N_PTR(beg);
while(beg->next != end)
beg = this->erease(beg);
end = this->erease(beg);
return end;
}
reference front() {
this->checkNullContainer("the list isn't elements");
return _head->next->data;
}
const_reference front() const {
this->checkNullContainer("the list isn't elements");
return _head->next->data;
}
value_type back(size_type k) const {
this->checkNullContainer("The link list is empty");
pointer_type p = nullptr;
value_type tmp {};
size_type n = this->size();
if(k > n || k <= 0)
return INT_MIN;
n = n - k + 1;
p = _head;
for(; n > 0; --n)
p = p->next;
tmp = p->data;
return tmp;
}
/// @brief returns the pointer to the @b kth element at the end
/// @return pointer
pointer_type backPtr(size_type k) {
this->checkNullContainer("The link list is empty");
_ret_ptr = nullptr;
size_type n = this->size();
if(k > n)
return nullptr;
n = n - k + 1;
_ret_ptr = _head;
for(; n > 0; --n)
_ret_ptr = _ret_ptr->next;
return _ret_ptr;
}
bool empty() const {
return !_head->next;
}
size_type size() const {
size_type count{};
pointer_type p = _head->next;
for(; p; p = p->next, + + count);
return count;
}
/// @brief reverse range(_head, ...)
void reverse() {
this->checkNullContainer("The link list is empty");
this->reverse(_head);
}
/// @brief reverse range[beg, ...)
template<typename U,
typename std::enable_if<std::is_same<value_type, U>::value, int>::type = 0>
void reverse(Node<U>* beg) {
CHECK_N_PTR(beg);
Node<U>* prev(beg->next), * curr(nullptr);
while(prev->next) {
curr = prev->next;
prev->next = curr->next;
curr->next = beg->next;
beg->next = curr;
}
}
//reverse range[beg->next, end)
template<typename U,
typename std::enable_if<std::is_same<value_type, U>::value, int>::type = 0>
void reverse(Node<U>* beg, Node<U>* end) {
CHECK_N_PTR(beg);
Node<U>* prev(beg->next), * curr(nullptr);
while(prev->next != end) {
curr = prev->next;
prev->next = curr->next;
curr->next = beg->next;
beg->next = curr;
}
}
/// @brief Find @a val
/// @return pointer to the element being searched
pointer_type find(value_type val) {
_ret_ptr = _head->next;
while(_ret_ptr) {
if(_ret_ptr->data == val)
break;
_ret_ptr = _ret_ptr->next;
}
if(_ret_ptr)
return _ret_ptr;
else
return nullptr;
}
/// @brief select sort
template<typename Compare = std::less<T>>
void sort() {
pointer_type prev = _head, curr(prev->next), cir(curr->next);
while(curr) {
while(cir) {
if(Compare()(cir->data, curr->data))
::swap(cir->data, curr->data);
cir = cir->next;
}
prev = curr;
curr = curr->next;
if(curr)
cir = curr->next;
}
}
pointer_type headNode() {
return _head;
}
const_pointer_type headNode() const {
return _head;
}
pointer_type midPtr() {
pointer_type slow(_head->next), fast(slow);
_ret_ptr = nullptr;
while(fast) {
slow = slow->next;
fast = fast->next->next;
if(!fast || !fast->next)
break;
}
if(slow)
_ret_ptr = slow;
return _ret_ptr;
}
/// @brief exchange head node
template<typename U,
typename std::enable_if<std::is_same<U, value_type>::value, int>::type = 0>
void swap(Node<U>* x) noexcept {
pointer_type tmp = _head->next;
_head->next = x->next;
x->next = tmp;
tmp = nullptr;
}
/// @brief links to nodes in other singly linked lists
/// @param x other singly linked list nodes
template<typename U,
typename std::enable_if<std::is_same<U, value_type>::value, int>::type = 0>
void link(Node<U>* x) {
pointer_type p = _head;
while(p->next)
p = p->next;
p->next = x;
}
private:
void check(const char* msg) const {
if(!_head->next)
throw std::out_of_range(msg);
}
void checkNullContainer(const char* msg) const {
try {
this->check(msg);
} catch(const std::exception & amp; exc) {
exc.what();
}
}
template<typename U,
typename std::enable_if<std::is_same<U, value_type>::value, int>::type = 0>
void copyElement(Node<U>* x) {
if(x) {
x = x->next;
while(x) {
this->push(x->data);
x = x->next;
}
}
}
private:
pointer_type _head;
pointer_type _ret_ptr;
};
//algorithm
template<class T>
using pointer_type = Node<T>*;
template<class T>
using const_pointer_type = const Node<T>*;
template<typename T>
void swap(LinkList<T> & amp; x, LinkList<T> & amp; y) {
x.swap(y.getHeadPtr());
}
#endif // !LINK_LIST_HPP