summaryrefslogtreecommitdiff
path: root/misc/uClibc++/include/cxx/set
diff options
context:
space:
mode:
Diffstat (limited to 'misc/uClibc++/include/cxx/set')
-rw-r--r--misc/uClibc++/include/cxx/set406
1 files changed, 406 insertions, 0 deletions
diff --git a/misc/uClibc++/include/cxx/set b/misc/uClibc++/include/cxx/set
new file mode 100644
index 000000000..f376e4700
--- /dev/null
+++ b/misc/uClibc++/include/cxx/set
@@ -0,0 +1,406 @@
+/* Copyright (C) 2004 Garrett A. Kajmowicz
+ This file is part of the uClibc++ Library.
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+
+
+#include<memory>
+#include<utility>
+#include<iterator>
+#include <deque>
+#include<functional>
+#include <associative_base>
+
+#ifndef __STD_HEADER_SET
+#define __STD_HEADER_SET
+
+#pragma GCC visibility push(default)
+
+namespace std{
+
+
+template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
+template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class multiset;
+
+
+/* This is the implementation for the set container. As noted above, it deviates
+ * from ISO spec by deriving from a base class in order to reduce code redundancy.
+ * More code could be reduced by convirting to virtual functions (thus allowing
+ * much of the erase and insert code to be duplicated), but that would deviate from
+ * the specifications too much to be worth the risk.
+ */
+
+
+//Implementation of set
+
+
+template<class Key, class Compare, class Allocator> class _UCXXEXPORT set
+ : public __single_associative<Key, Key, Compare, Allocator>
+{
+ //Default value of allocator does not meet C++ standard specs, but it works for this library
+ //Deal with it
+public:
+
+ typedef __single_associative<Key, Key, Compare, Allocator> base;
+ typedef typename base::key_type key_type;
+ typedef typename base::value_type value_type;
+ typedef typename base::key_compare key_compare;
+ typedef typename base::allocator_type allocator_type;
+ typedef typename base::reference reference;
+ typedef typename base::const_reference const_reference;
+ typedef typename base::iterator iterator;
+ typedef typename base::const_iterator const_iterator;
+ typedef typename base::size_type size_type;
+ typedef typename base::difference_type difference_type;
+ typedef typename base::pointer pointer;
+ typedef typename base::const_pointer const_pointer;
+ typedef typename base::reverse_iterator reverse_iterator;
+ typedef typename base::const_reverse_iterator const_reverse_iterator;
+
+// using base::value_compare;
+
+ static const key_type v_t_k(const value_type v){
+ return v;
+ }
+
+ explicit set(const Compare& comp = Compare(), const Allocator& al = Allocator())
+ : base(comp, al, v_t_k) { }
+
+ template <class InputIterator> set(InputIterator first, InputIterator last,
+ const Compare& comp = Compare(), const Allocator& al = Allocator())
+ : base(first, last, comp, al, v_t_k) { }
+
+ set(const set<Key, Compare,Allocator>& x) : base(x) { }
+ ~set() { }
+
+ using base::operator=;
+ using base::operator==;
+ using base::operator!=;
+
+ using base::insert;
+ using base::erase;
+
+ using base::begin;
+ using base::end;
+ using base::rbegin;
+ using base::rend;
+
+ using base::empty;
+ using base::size;
+ using base::max_size;
+
+
+ using base::find;
+ using base::count;
+ using base::lower_bound;
+ using base::upper_bound;
+ using base::equal_range;
+
+protected:
+
+};
+
+
+//Implementation of multiset
+
+
+template<class Key, class Compare, class Allocator> class _UCXXEXPORT multiset
+ : public __multi_associative<Key, Key, Compare, Allocator>
+{
+ //Default value of allocator does not meet C++ standard specs, but it works for this library
+ //Deal with it
+public:
+
+ typedef __multi_associative<Key, Key, Compare, Allocator> base;
+ typedef typename base::key_type key_type;
+ typedef typename base::value_type value_type;
+ typedef typename base::key_compare key_compare;
+ typedef typename base::allocator_type allocator_type;
+ typedef typename base::reference reference;
+ typedef typename base::const_reference const_reference;
+ typedef typename base::iterator iterator;
+ typedef typename base::const_iterator const_iterator;
+ typedef typename base::size_type size_type;
+ typedef typename base::difference_type difference_type;
+ typedef typename base::pointer pointer;
+ typedef typename base::const_pointer const_pointer;
+ typedef typename base::reverse_iterator reverse_iterator;
+ typedef typename base::const_reverse_iterator const_reverse_iterator;
+
+ static const key_type v_t_k(const value_type v){
+ return v;
+ }
+
+ explicit multiset(const Compare& comp = Compare(), const Allocator& al = Allocator())
+ : base(comp, al, v_t_k) { }
+
+ template <class InputIterator> multiset(InputIterator first, InputIterator last,
+ const Compare& comp = Compare(), const Allocator& al = Allocator())
+ : base(first, last, comp, al, v_t_k) { }
+
+
+ multiset(const multiset<Key, Compare, Allocator>& x) : base(x) { }
+ ~multiset() { }
+
+ using base::operator=;
+ using base::operator==;
+ using base::operator!=;
+
+ using base::insert;
+ using base::erase;
+
+ using base::begin;
+ using base::end;
+ using base::rbegin;
+ using base::rend;
+
+ using base::empty;
+ using base::size;
+ using base::max_size;
+
+ using base::find;
+ using base::count;
+ using base::lower_bound;
+ using base::upper_bound;
+ using base::equal_range;
+
+
+protected:
+
+};
+
+
+/* Non-member functions. These are at the end because they are not associated with any
+ particular class. These will be implemented as I figure out exactly what all of
+ them are supposed to do, and I have time.
+ */
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<
+ (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
+ {
+ typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 < *first2 ){
+ return true;
+ }
+ if( *first2 < *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1==last1 && first2 != last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>
+ (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
+ {
+ typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 > *first2 ){
+ return true;
+ }
+ if( *first2 > *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1!=last1 && first2 == last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
+ (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
+ {
+ typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 > *first2 ){
+ return true;
+ }
+ if( *first2 > *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1!=last1;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
+ (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
+ {
+ typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 < *first2 ){
+ return true;
+ }
+ if( *first2 < *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first2!=last2;
+ }
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
+ (set<Key,Compare,Allocator>& x, set<Key,Compare,Allocator>& y)
+ {
+ x.swap(y);
+ }
+
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator==
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ if(x.data == y.data){
+ return true;
+ }
+ return false;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 < *first2 ){
+ return true;
+ }
+ if( *first2 < *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1==last1 && first2 != last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator!=
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 != *first2 ){
+ return true;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1!=last1 || first2 != last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 > *first2 ){
+ return true;
+ }
+ if( *first2 > *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1!=last1 && first2 == last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 > *first2 ){
+ return true;
+ }
+ if( *first2 > *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1!=last1;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
+ (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
+ {
+ typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
+ typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
+ typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
+
+ while(first1 != last1 && first2 != last2){
+ if( *first1 < *first2 ){
+ return true;
+ }
+ if( *first2 < *first1 ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first2!=last2;
+ }
+
+ template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
+ (multiset<Key,Compare,Allocator>& x, multiset<Key,Compare,Allocator>& y)
+ {
+ x.swap(y);
+ }
+
+
+
+}
+
+#pragma GCC visibility pop
+
+#endif
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-06 20:02:19 +0000