19 #ifndef __TPIE_TINY_H__
20 #define __TPIE_TINY_H__
24 #include <tpie/config.h>
35 template <
typename T,
typename Comp>
36 void sort(T start, T end, Comp comp=Comp()) {
37 for (T i = start; i != end; ++i)
38 std::rotate(std::upper_bound(start, i, *i, comp), i, std::next(i));
48 void sort(T start, T end) {
49 for (T i = start; i != end; ++i)
50 std::rotate(std::upper_bound(start, i, *i), i, std::next(i));
60 const T & operator()(
const T & x)
const {
return x;}
66 template <
typename A,
typename B>
70 const T & operator()(
const T & x)
const {
return x;}
71 const A & operator()(
const std::pair<A, B> & x)
const {
return x.first;}
78 template <
typename Inner>
80 static const bool multi=
false;
81 typedef typename Inner::iterator iterator;
82 typedef std::pair<iterator, bool> result;
84 template <
typename Comp>
85 static result handle(Inner & inner,
const Comp & comp) {
86 iterator fend=std::prev(inner.end());
87 iterator i=std::lower_bound(inner.begin(), fend, *fend, comp);
88 if (i != fend && !comp(*fend, *i)) {
90 return std::make_pair(i,
false);
92 std::rotate(i, fend, std::next(fend));
93 return std::make_pair(i,
true);
102 template <
typename Inner>
104 static const bool multi=
true;
105 typedef typename Inner::iterator iterator;
106 typedef iterator result;
108 template <
typename Comp>
109 static result handle(Inner & inner,
const Comp &) {
110 iterator y=std::upper_bound(inner.begin(), inner.end()-1, inner.back());
111 std::rotate(y, inner.end()-1, inner.end());
131 template <
typename T,
139 typedef std::vector<T, Alloc> Inner;
140 typedef typename InsertHelp::template type<Inner> IH;
142 typedef T value_type;
143 typedef Key key_type;
144 typedef typename Inner::iterator iterator;
145 typedef typename Inner::const_iterator const_iterator;
146 typedef typename Inner::reverse_iterator reverse_iterator;
147 typedef typename Inner::const_reverse_iterator const_reverse_iterator;
148 typedef Comp key_compare;
149 typedef Alloc allocator_type;
150 typedef typename IH::result insert_result;
153 template <
typename L,
typename R>
154 bool operator()(
const L & l,
const R & r)
const {
155 return comp(extract(l), extract(r));
170 explicit set_impl(
const Comp & comp,
const Alloc & alloc=Alloc()): comp(comp), inner(alloc) {}
175 explicit set_impl(
const Alloc & alloc): inner(alloc) {}
185 set_impl(
const set_impl & other,
const Alloc & alloc): comp(other.comp), inner(other.inner, alloc) {}
195 set_impl(
set_impl && other,
const Alloc & alloc): comp(std::move(other.comp)), inner(std::move(other.inner), alloc) {}
200 template<
class InputIterator >
202 const Comp& comp = Comp(),
203 const Alloc& alloc = Alloc()): comp(comp), inner(alloc) {
211 const Comp& comp = Comp(),
212 const Alloc& alloc = Alloc() ): comp(comp), inner(alloc) {
219 iterator
begin() noexcept {
return inner.begin();}
224 const_iterator
begin() const noexcept {
return inner.cbegin();}
229 const_iterator
cbegin() const noexcept {
return inner.cbegin();}
234 reverse_iterator
rbegin() noexcept {
return inner.rbegin();}
239 const_reverse_iterator
rbegin() const noexcept {
return inner.rbegin();}
244 const_reverse_iterator
crbegin() const noexcept {
return inner.rbegin();}
249 iterator
end() noexcept {
return inner.end();}
254 const_iterator
end() const noexcept {
return inner.cend();}
259 const_iterator
cend() const noexcept {
return inner.cend();}
265 reverse_iterator
rend() noexcept {
return inner.rend();}
271 const_reverse_iterator
rend() const noexcept {
return inner.rend();}
277 const_reverse_iterator
crend() const noexcept {
return inner.rend();}
283 bool empty() const noexcept {
return inner.empty();}
288 size_t size() const noexcept {
return inner.size();}
295 size_t max_size() const noexcept {
return inner.max_size();}
307 std::rotate(pos, std::next(pos), inner.end());
317 iterator
erase(iterator first, iterator last) {
318 std::rotate(first, last, inner.end());
319 inner.resize(
size() - (last-first));
329 erase(x.first, x.second);
330 return x.second - x.first;
339 std::swap(comp, o.comp);
340 std::swap(inner, o.inner);
347 iterator
find(
const Key & key) noexcept {
349 if (x ==
end() || comp(key, *x))
return end();
357 const_iterator
find(
const Key & key)
const noexcept {
359 if (x ==
end() || comp(key, *x))
return end();
369 std::pair<iterator, iterator>
equal_range(
const Key & key) noexcept {
370 return std::equal_range(inner.begin(), inner.end(), key, comp);
379 std::pair<const_iterator, const_iterator>
equal_range(
const Key & key)
const noexcept {
380 return std::equal_range(inner.begin(), inner.end(), key, comp);
388 return std::lower_bound(inner.begin(), inner.end(), key, comp);
396 return std::lower_bound(inner.begin(), inner.end(), key, comp);
404 return std::upper_bound(inner.begin(), inner.end(), key, comp);
412 return std::upper_bound(inner.begin(), inner.end(), key, comp);
436 return inner.get_allocator();
454 inner = std::move(other.inner);
455 comp = std::move(other.comp);
472 return lhs.inner == rhs.inner;
479 return lhs.inner != rhs.inner;
487 return std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end(), lhs.comp);
495 return !std::lexicographical_compare(rhs.
begin(), rhs.
end(), lhs.
begin(), lhs.
end());
504 return std::lexicographical_compare(rhs.
begin(), rhs.
end(), lhs.
begin(), lhs.
end());
512 return !std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end(), lhs.comp);
525 size_t count(
const Key k)
const noexcept {
528 return x.second - x.first;
531 if (x ==
end() || comp(k, *x))
return 0;
547 return IH::handle(inner, comp);
559 template <
typename TT>
561 return emplace(std::forward<TT>(t));
567 insert_result
insert(const_iterator ,
const T & t) {
574 template <
typename TT>
575 insert_result
insert(const_iterator , TT && t) {
576 return insert(std::forward<TT>(t));
582 template <
class InputIt>
583 void insert(InputIt first, InputIt last) {
584 inner.reserve(
size() + last-first);
585 for (InputIt i=first; i != last; ++i)
592 void insert(std::initializer_list<value_type> list) {
593 insert(list.begin(), list.end());
606 template <
class... Args>
608 inner.emplace_back(std::forward<Args>(args)...);
609 return IH::handle(inner, comp);
615 template <
class... Args>
617 return emplace(std::forward<Args>(args)...);
626 void reserve(
size_t new_cap) {inner.reserve(new_cap);}
637 size_t capacity() const noexcept {
return inner.capacity();}
640 std::vector<value_type, Alloc> inner;
646 template <
typename T,
647 typename Comp=std::less<T>,
648 typename Alloc=std::allocator<T> >
649 using set = set_impl<T, T, bits::IdentityExtract, Comp, Alloc, bits::SingleInsertHelp>;
654 template <
typename T,
655 typename Comp=std::less<T>,
656 typename Alloc=std::allocator<T> >
657 using multiset = set_impl<T, T, bits::IdentityExtract, Comp, Alloc, bits::MultiInsertHelp>;
662 template <
typename Key,
664 typename Comp=std::less<Key>,
665 typename Alloc=std::allocator<std::pair<Key, T> > >
666 using multimap = set_impl<std::pair<Key, T>, T, bits::PairExtract<Key, T>, Comp, Alloc, bits::MultiInsertHelp>;
671 template <
typename Key,
673 typename Comp=std::less<Key>,
674 typename Alloc=std::allocator<std::pair<Key, T> >
675 >
class map:
public set_impl<std::pair<Key, T>, T, bits::PairExtract<Key, T>, Comp, Alloc, bits::SingleInsertHelp> {
681 explicit map(
const Comp & comp,
const Alloc & alloc = Alloc()) :
P(comp, alloc) {}
682 explicit map(
const Alloc & alloc) :
P(alloc) {}
683 map(
const map & other) :
P(other) {}
684 map(
const map & other,
const Alloc & alloc) :
P(other, alloc) {}
685 map(
map && other) :
P(other) {}
686 map(
map && other,
const Alloc & alloc) :
P(std::move(other), alloc) {}
687 template<
class InputIterator >
688 map(InputIterator first, InputIterator last,
689 const Comp& comp = Comp(),
690 const Alloc& alloc = Alloc()) :
P(first, last, comp, alloc) {}
691 map(std::initializer_list<typename P::value_type> init,
692 const Comp& comp = Comp(),
693 const Alloc& alloc = Alloc()) :
P(init, comp, alloc) {}
703 return this->
emplace(key, T()).first->second;
712 return this->
emplace(std::move(key), T()).first->second;
720 T&
at(
const Key& key ) {
722 if (x ==
P::end() || P::comp(key, *x))
throw std::out_of_range(
"tiny::map::at");
731 const T&
at(
const Key& key )
const {
733 if (x ==
P::end() || P::comp(key, *x))
throw std::out_of_range(
"tiny::map::at");
741 #endif //__TPIE_TINY_H__
void sort(uncompressed_stream< T > &instream, uncompressed_stream< T > &outstream, Compare comp, progress_indicator_base &indicator)
Sort elements of a stream using the given STL-style comparator object.
friend void swap(set_impl &lhs, set_impl &rhs)
Specializes the std::swap algorithm using adl.
size_t capacity() const noexcept
Returns the number of elements that the container has currently allocated space for.
friend bool operator<=(const set_impl &lhs, const set_impl &rhs)
true if the contents of the lhs are lexicographically less than or equal the contents of rhs...
friend bool operator>=(const set_impl &lhs, const set_impl &rhs)
true if the contents of the lhs are lexicographically greater than or equal the contents of rhs...
void shrink_to_fit()
Requests the removal of unused capacity.
void reserve(size_t new_cap)
Increase the capacity of the container to a value that's greater or equal to new_cap.
friend bool operator==(const set_impl &lhs, const set_impl &rhs)
true if the contents of the containers are equal, false otherwise.
set_impl & operator=(set_impl &&other)
Move assignment operator.
A std::map compatible map, useful when we do not have many elements (less then 512) ...
set_impl(std::initializer_list< value_type > init, const Comp &comp=Comp(), const Alloc &alloc=Alloc())
Constructs the container with the contents of the initializer list init.
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the first element of the reversed container.
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the element following the last element of the reversed container...
size_t erase(const Key &key)
Removes all elements with the key value key.
iterator find(const Key &key) noexcept
Finds an element with key equivalent to key.
set_impl & operator=(const set_impl &other)
Copy assignment operator.
iterator begin() noexcept
Returns an iterator to the first element of the container.
value_compare value_comp() const noexcept
Returns a function object that compares objects of type std::map::value_type (key-value pairs) by usi...
const_iterator find(const Key &key) const noexcept
Finds an element with key equivalent to key.
set_impl(const Comp &comp, const Alloc &alloc=Alloc())
Default constructor.
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the first element of the reversed container.
size_t size() const noexcept
Returns the number of elements in the container, i.e.
const_iterator end() const noexcept
Returns an iterator to the element following the last element of the container.
set_impl(set_impl &&other, const Alloc &alloc)
Move constructor.
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the first element of the reversed container.
T & at(const Key &key)
Returns a reference to the mapped value of the element with key equivalent to key.
allocator_type get_allocator() const
Returns the allocator associated with the container.
const_iterator lower_bound(const Key &key) const noexcept
Returns an iterator pointing to the first element that is not less than key.
set_impl(const set_impl &other, const Alloc &alloc)
Copy constructor.
bool empty() const noexcept
Checks if the container has no elements, i.e.
friend bool operator!=(const set_impl &lhs, const set_impl &rhs)
true if the contents of the containers are not equal, false otherwise.
T & operator[](Key &&key)
Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion i...
reverse_iterator rend() noexcept
Returns a reverse iterator to the element following the last element of the reversed container...
std::pair< iterator, iterator > equal_range(const Key &key) noexcept
Returns a range containing all elements with the given key in the container.
iterator erase(iterator first, iterator last)
Removes the elements in the range [first; last), which must be a valid range in *this.
const_iterator cbegin() const noexcept
Returns an iterator to the first element of the container.
iterator end() noexcept
Returns an iterator to the element following the last element of the container.
When inserting do not allow elements with equivalest keys.
set_impl(InputIterator first, InputIterator last, const Comp &comp=Comp(), const Alloc &alloc=Alloc())
Constructs the container with the contents of the range [first, last).
class implementing a tiny::set, tiny::multiset, and tiny::multimap.
const_iterator upper_bound(const Key &key) const noexcept
Returns an iterator pointing to the first element that is greater than key.
const_iterator begin() const noexcept
Returns an iterator to the first element of the container.
void clear()
Removes all elements from the container.
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const noexcept
Returns a range containing all elements with the given key in the container.
set_impl & operator=(std::initializer_list< value_type > ilist)
Replaces the contents with those identified by initializer list ilist.
insert_result emplace_hint(const_iterator, Args &&...args)
Do the same as emplace, and ignore the hint.
set_impl()
Default constructor.
insert_result insert(const_iterator, TT &&t)
Does the same as normal insert, we ignore the hint.
set_impl(set_impl &&other)
Move constructor.
When inserting allow elements with equivalest keys.
friend bool operator<(const set_impl &lhs, const set_impl &rhs)
true if the contents of the lhs are lexicographically less than the contents of rhs, false otherwise.
key_compare key_comp() const noexcept
Returns the function object that compares the keys, which is a copy of this container's constructor a...
set_impl(const Alloc &alloc)
Default constructor.
iterator upper_bound(const Key &key) noexcept
Returns an iterator pointing to the first element that is greater than key.
void swap(set_impl &o)
Exchanges the contents of the container with those of other.
T & operator[](const Key &key)
Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion i...
insert_result insert(TT &&t)
Inserts element(s) into the container, if the container doesn't already contain an element with an eq...
insert_result emplace(Args &&...args)
Inserts a new element into the container by constructing it in-place with the given args if there is ...
insert_result insert(const T &t)
Inserts element(s) into the container, if the container doesn't already contain an element with an eq...
set_impl(const set_impl &other)
Copy constructor.
void insert(InputIt first, InputIt last)
Inserts elements from range [first, last).
const_iterator cend() const noexcept
Returns an iterator to the element following the last element of the container.
void insert(std::initializer_list< value_type > list)
Inserts elements from initializer list ilist.
size_t count(const Key k) const noexcept
Returns the number of elements with key k.
iterator erase(iterator pos)
Removes the element at pos.
insert_result insert(const_iterator, const T &t)
Does the same as normal insert, we ignore the hint.
const T & at(const Key &key) const
Returns a reference to the mapped value of the element with key equivalent to key.
size_t max_size() const noexcept
Returns the maximum number of elements the container is able to hold due to system or library impleme...
friend bool operator>(const set_impl &lhs, const set_impl &rhs)
true if the contents of the lhs are lexicographically greater than the contents of rhs...
iterator lower_bound(const Key &key) noexcept
Returns an iterator pointing to the first element that is not less than key.
const_reverse_iterator rend() const noexcept
Returns a reverse iterator to the element following the last element of the reversed container...