/*
 * linear_set.hpp
 *
 * Created on: Sep 13, 2016
 * Author: Jan Travnicek
 */

#ifndef __LINEAR_SET_HPP_
#define __LINEAR_SET_HPP_

namespace std {

template < class T, class Compare = less<T>, class Alloc = allocator<T> >
class linear_set {
	vector < T, Alloc > m_data;
	Compare m_comp;

	bool eq ( const T & first, const T & second ) {
		return ! m_comp ( first, second ) && ! m_comp ( second, first );
	}

	void sort_unique ( ) {
		std::sort ( m_data.begin ( ), m_data.end ( ), m_comp );
		m_data.resize ( std::distance ( m_data.begin ( ), std::unique ( m_data.begin ( ), m_data.end ( ), std::bind ( &std::linear_set<int>::eq, std::ref( * this ), std::placeholders::_1, std::placeholders::_2 ) ) ) );
	}

public:
	typedef T value_type;

	typedef typename vector < T, Alloc >::const_iterator iterator;
	typedef typename vector < T, Alloc >::const_iterator const_iterator;
	typedef typename vector < T, Alloc >::const_reverse_iterator reverse_iterator;
	typedef typename vector < T, Alloc >::const_reverse_iterator const_reverse_iterator;

	explicit linear_set (const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( alloc ), m_comp ( comp ) {
	}

	explicit linear_set (const Alloc& alloc) : m_data ( alloc ), m_comp ( Compare ( ) ) {
	}

	template <class InputIterator>
	linear_set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( first, last, alloc ), m_comp ( comp ) {
		sort_unique ( );
	}

	linear_set (const linear_set& x) : m_data ( x.m_data ), m_comp ( x.m_comp ) {
	}

	linear_set (const linear_set& x, const Alloc& alloc) : m_data ( x.m_data, alloc ), m_comp ( x.m_comp ) {
	}

	linear_set (linear_set&& x) : m_data ( std::move ( x.m_data ) ), m_comp ( x.m_comp ) {
	}

	linear_set (linear_set&& x, const Alloc& alloc) : m_data ( std::move ( x.m_data ), alloc ), m_comp ( x.m_comp ) {
	}

	linear_set (initializer_list<T> il, const Compare& comp = Compare(), const Alloc& alloc = Alloc()) : m_data ( std::move ( il ), alloc ), m_comp ( comp ) {
		sort_unique ( );
	}

	~linear_set ( ) {
	}

	iterator begin() noexcept {
		return m_data.begin ( );
	}

	const_iterator begin() const noexcept {
		return m_data.begin ( );
	}

	const_iterator cbegin() const noexcept {
		return m_data.cbegin ( );
	}

	const_iterator cend() const noexcept {
		return m_data.cend ( );
	}

	void clear() noexcept {
		m_data.clear ( );
	}

	size_t count ( const T& value ) const {
		return std::binary_search ( m_data.begin ( ), m_data.end ( ), value );
	}

	const_reverse_iterator crbegin() const noexcept {
		return m_data.crbegin ( );
	}

	const_reverse_iterator crend() const noexcept {
		return m_data.crend ( );
	}

	template <class... Args>
	pair<iterator,bool> emplace (Args&&... args) {
		return insert ( T ( std::forward ( args ) ... ) );
	}

	template <class... Args>
	iterator emplace_hint (const_iterator position, Args&&... args) {
		return insert ( position, T ( std::forward ( args ) ... ) );
	}

	bool empty() const noexcept {
		return m_data.empty ( );
	}

	iterator end() noexcept {
		return m_data.end ( );
	}

	const_iterator end() const noexcept {
		return m_data.end ( );
	}

	pair<const_iterator,const_iterator> equal_range (const T& val) const {
		return make_pair ( lower_bound ( val ), upper_bound ( val ) );
	}

	pair<iterator,iterator> equal_range (const T& val) {
		return make_pair ( lower_bound ( val ), upper_bound ( val ) );
	}

	iterator erase (const_iterator position) {
		return m_data.erase ( position );
	}

	iterator erase (const_iterator first, const_iterator last) {
		return m_data.erace ( first, last );
	}

	const_iterator find (const T& val) const {
		const_iterator position = lower_bound ( begin ( ), end ( ), val, m_comp );
		if ( eq ( * position, val ) )
			return position;
		else
			return end ( );
	}

	Alloc get_allocator() const noexcept {
		return m_data.get_allocator ( );
	}

	iterator find (const T& val) {
		iterator position = lower_bound ( val );
		if ( eq ( * position, val ) )
			return position;
		else
			return end ( );
	}

	pair<iterator,bool> insert (const T& val) {
		return insert ( T ( val ) );
	}

	pair<iterator,bool> insert (T&& val) {
		const_iterator position = lower_bound ( val );
		if ( position != end ( ) && eq ( * position, val ) )
			return make_pair ( position, false );
		else
			return make_pair ( m_data.emplace ( position, std::move ( val ) ), true );
	}

	iterator insert (const_iterator position, const T& val) {
		return insert ( position, T ( val ) );
	}

	iterator insert (const_iterator position, T&& val) {
		if ( position != end ( ) && eq ( *  position, val ) )
			return position;

		if ( position != end ( ) && m_comp ( val, * position ) && ( position == begin ( ) || m_comp ( * std::prev ( position ), val ) ) )
			return m_data.emplace ( position, std::move ( val ) );

		return insert ( std::move ( val ) ).first;
	}

	template <class InputIterator>
	void insert (InputIterator first, InputIterator last) {
		m_data.insert ( m_data.end ( ), first, last );
		sort_unique ( );
	}

	void insert (initializer_list<T> il) {
		m_data.insert ( m_data.end ( ), std::move ( il ) );
		sort_unique ( );
	}

	Compare key_comp() const {
		return m_comp;
	}

	iterator lower_bound (const T& val) {
		return std::lower_bound ( begin ( ), end ( ), val, m_comp );
	}

	const_iterator lower_bound (const T& val) const {
		return std::lower_bound ( begin ( ), end ( ), val, m_comp );
	}

	size_t max_size() const noexcept {
		return m_data.max_size ( );
	}

	linear_set& operator= (const linear_set& x) {
		m_data = x.m_data;
		m_comp = x.m_comp;
	}

	linear_set& operator= (linear_set&& x) {
		m_data = std::move ( x.m_data );
		m_comp = std::move ( x.m_comp );
	}

	linear_set& operator= (initializer_list<T> il) {
		m_data = std::move ( il );
		std::sort ( m_data.begin ( ), m_data.end ( ), m_comp );
	}

	reverse_iterator rbegin() noexcept {
		return m_data.rbegin ( );
	}

	const_reverse_iterator rbegin() const noexcept {
		return m_data.rbegin ( );
	}

	reverse_iterator rend() noexcept {
		return m_data.rend ( );
	}

	const_reverse_iterator rend() const noexcept {
		return m_data.rend ( );
	}

	size_t size() const noexcept {
		return m_data.size ( );
	}

	void swap (linear_set& x) {
		std::swap ( m_data, x.m_data );
		std::swap ( m_comp, x.m_comp );
	}

	iterator upper_bound (const T& val) {
		return std::upper_bound ( begin ( ), end ( ), val, m_comp );
	}

	const_iterator upper_bound (const T& val) const {
		return std::upper_bound ( begin ( ), end ( ), val, m_comp );
	}

	Compare value_comp() const {
		return m_comp;
	}

	friend bool operator== ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data == rhs.m_data;
	}

	friend bool operator!= ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data != rhs.m_data;
	}

	friend bool operator<  ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data < rhs.m_data;
	}

	friend bool operator<= ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data <= rhs.m_data;
	}

	friend bool operator>  ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data > rhs.m_data;
	}

	friend bool operator>= ( const linear_set<T,Compare,Alloc>& lhs, const linear_set<T,Compare,Alloc>& rhs ) {
		return lhs.m_data >= rhs.m_data;
	}

};

template <class T, class Compare, class Alloc>
void swap ( linear_set < T, Compare, Alloc > & x, linear_set < T, Compare, Alloc > & y) {
	x.swap ( y );
}

template< class T, class ... Ts >
std::ostream& operator<<(std::ostream& out, const std::linear_set<T, Ts ...>& list) {
	out << "{";

	bool first = true;
	for(const T& item : list) {
		if(!first) out << ", ";
		first = false;
		out << item;
	}

	out << "}";
	return out;
}

template<class T, class ... Ts>
struct compare<linear_set<T, Ts ...>> {
	int operator()(const linear_set<T, Ts ...>& first, const linear_set<T, Ts ...>& second) const {
		if(first.size() < second.size()) return -1;
		if(first.size() > second.size()) return 1;

		compare<typename std::decay < T >::type > comp;
		for(auto iterF = first.begin(), iterS = second.begin(); iterF != first.end(); ++iterF, ++iterS) {
			int res = comp(*iterF, *iterS);
			if(res != 0) return res;
		}
		return 0;
	}
};

template <class Iterator>
class linear_set_move_iterator {
	Iterator current;

public:
	typedef Iterator iterator_type;
	typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
	typedef typename iterator_traits<Iterator>::value_type        value_type;
	typedef Iterator pointer;
	typedef value_type&& reference;

	explicit linear_set_move_iterator() {
	}

	explicit linear_set_move_iterator (Iterator it) : current(it) {
	}

	linear_set_move_iterator (const linear_set_move_iterator<Iterator>& it) : current(it.current) {
	}

	linear_set_move_iterator& operator= (const linear_set_move_iterator<Iterator>& it) {
		current = it.current;
	}

	iterator_type base() const {
		return current;
	}

	pointer operator->() const {
		return current;
	}

	reference operator*() const {
		return std::move(const_cast<value_type&>(*current));
	}

	linear_set_move_iterator& operator++() {
		++current;
		return *this;
	}

	linear_set_move_iterator& operator--() {
		--current;
		return *this;
	}

	linear_set_move_iterator operator++(int) {
		linear_set_move_iterator temp = *this;
		++current;
		return temp;
	}

	linear_set_move_iterator operator--(int) {
		linear_set_move_iterator temp = *this;
		--current;
		return temp;
	}

	bool operator== (const linear_set_move_iterator<Iterator>& other) {
		return this->current == other.current;
	}

	bool operator!= (const linear_set_move_iterator<Iterator>& other) {
		return ! ( *this == other );
	}

};

template<class Iterator>
linear_set_move_iterator<Iterator> make_linear_set_move_iterator (Iterator it) {
	return linear_set_move_iterator<Iterator>(it);
}

template<class T>
class moveable_linear_set_ref {
	linear_set<T>& theSet;
public:
	moveable_linear_set_ref(linear_set<T>& param) : theSet(param) {}

	linear_set_move_iterator<typename linear_set<T>::iterator> begin() {
		return make_linear_set_move_iterator(theSet.begin());
	}

	linear_set_move_iterator<typename linear_set<T>::iterator> end() {
		return make_linear_set_move_iterator(theSet.end());
	}
};

template<class T>
moveable_linear_set_ref<T> make_moveable_set (std::linear_set<T>& linear_set) {
	return moveable_linear_set_ref<T>(linear_set);
}

template<class T>
class moveable_linear_set {
	linear_set<T> theSet;
public:
	moveable_linear_set(linear_set<T> param) : theSet(std::move(param)) {}

	linear_set_move_iterator<typename linear_set<T>::iterator> begin() {
		return make_linear_set_move_iterator(theSet.begin());
	}

	linear_set_move_iterator<typename linear_set<T>::iterator> end() {
		return make_linear_set_move_iterator(theSet.end());
	}
};

template<class T>
moveable_linear_set<T> make_moveable_set (std::linear_set<T>&& linear_set) {
	return moveable_linear_set<T>(std::move(linear_set));
}

template < class T >
std::linear_set < T > operator +( const std::linear_set < T > & first, const std::linear_set < T > & second ) {
	std::linear_set < T > res ( first );

	res.insert ( second.begin ( ), second.end ( ) );
	return res;
}

} /* namespace std */

#endif /* __LINEAR_SET_HPP_ */