Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*      Copyright (C) 2004 Garrett A. Kajmowicz
  2.         This file is part of the uClibc++ Library.
  3.  
  4.         This library is free software; you can redistribute it and/or
  5.         modify it under the terms of the GNU Lesser General Public
  6.         License as published by the Free Software Foundation; either
  7.         version 2.1 of the License, or (at your option) any later version.
  8.  
  9.         This library is distributed in the hope that it will be useful,
  10.         but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12.         Lesser General Public License for more details.
  13.  
  14.         You should have received a copy of the GNU Lesser General Public
  15.         License along with this library; if not, write to the Free Software
  16.         Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17. */
  18.  
  19.  
  20.  
  21. #include<memory>
  22. #include<utility>
  23. #include<iterator>
  24. #include <deque>
  25. #include<functional>
  26. #include <associative_base>
  27.  
  28. #ifndef __STD_HEADER_SET
  29. #define __STD_HEADER_SET
  30.  
  31. #pragma GCC visibility push(default)
  32.  
  33. namespace std{
  34.  
  35.  
  36. template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
  37. template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class multiset;
  38.  
  39.  
  40. /* This is the implementation for the set container.  As noted above, it deviates
  41.  * from ISO spec by deriving from a base class in order to reduce code redundancy.
  42.  * More code could be reduced by convirting to virtual functions (thus allowing
  43.  * much of the erase and insert code to be duplicated), but that would deviate from
  44.  * the specifications too much to be worth the risk.
  45.  */
  46.  
  47.  
  48. //Implementation of set
  49.  
  50.  
  51. template<class Key, class Compare, class Allocator> class _UCXXEXPORT set
  52.         : public __single_associative<Key, Key, Compare, Allocator>
  53. {
  54.                 //Default value of allocator does not meet C++ standard specs, but it works for this library
  55.                 //Deal with it
  56. public:
  57.  
  58.         typedef __single_associative<Key, Key, Compare, Allocator>      base;
  59.         typedef typename base::key_type                                 key_type;
  60.         typedef typename base::value_type                               value_type;
  61.         typedef typename base::key_compare                              key_compare;
  62.         typedef typename base::allocator_type                           allocator_type;
  63.         typedef typename base::reference                                reference;
  64.         typedef typename base::const_reference                          const_reference;
  65.         typedef typename base::iterator                                 iterator;
  66.         typedef typename base::const_iterator                           const_iterator;
  67.         typedef typename base::size_type                                size_type;
  68.         typedef typename base::difference_type                          difference_type;
  69.         typedef typename base::pointer                                  pointer;
  70.         typedef typename base::const_pointer                            const_pointer;
  71.         typedef typename base::reverse_iterator                         reverse_iterator;
  72.         typedef typename base::const_reverse_iterator                   const_reverse_iterator;
  73.  
  74. //      using base::value_compare;
  75.  
  76.         static const key_type v_t_k(const value_type v){
  77.                 return v;
  78.         }
  79.  
  80.         explicit set(const Compare& comp = Compare(), const Allocator& al = Allocator())
  81.                 : base(comp, al, v_t_k) {  }
  82.  
  83.         template <class InputIterator> set(InputIterator first, InputIterator last,
  84.                 const Compare& comp = Compare(), const Allocator& al = Allocator())
  85.                 : base(first, last, comp, al, v_t_k) {  }
  86.  
  87.         set(const set<Key, Compare,Allocator>& x) : base(x) {  }
  88.         ~set() {  }
  89.  
  90.         using base::operator=;
  91.         using base::operator==;
  92.         using base::operator!=;
  93.  
  94.         using base::insert;
  95.         using base::erase;
  96.  
  97.         using base::begin;
  98.         using base::end;
  99.         using base::rbegin;
  100.         using base::rend;
  101.  
  102.         using base::empty;
  103.         using base::size;
  104.         using base::max_size;
  105.  
  106.  
  107.         using base::find;
  108.         using base::count;
  109.         using base::lower_bound;
  110.         using base::upper_bound;
  111.         using base::equal_range;
  112.  
  113. protected:
  114.  
  115. };
  116.  
  117.  
  118. //Implementation of multiset
  119.  
  120.  
  121. template<class Key, class Compare, class Allocator> class _UCXXEXPORT multiset
  122.         : public __multi_associative<Key, Key, Compare, Allocator>
  123. {
  124.                 //Default value of allocator does not meet C++ standard specs, but it works for this library
  125.                 //Deal with it
  126. public:
  127.  
  128.         typedef __multi_associative<Key, Key, Compare, Allocator>       base;
  129.         typedef typename base::key_type                                 key_type;
  130.         typedef typename base::value_type                               value_type;
  131.         typedef typename base::key_compare                              key_compare;
  132.         typedef typename base::allocator_type                           allocator_type;
  133.         typedef typename base::reference                                reference;
  134.         typedef typename base::const_reference                          const_reference;
  135.         typedef typename base::iterator                                 iterator;
  136.         typedef typename base::const_iterator                           const_iterator;
  137.         typedef typename base::size_type                                size_type;
  138.         typedef typename base::difference_type                          difference_type;
  139.         typedef typename base::pointer                                  pointer;
  140.         typedef typename base::const_pointer                            const_pointer;
  141.         typedef typename base::reverse_iterator                         reverse_iterator;
  142.         typedef typename base::const_reverse_iterator                   const_reverse_iterator;
  143.  
  144.         static const key_type v_t_k(const value_type v){
  145.                 return v;
  146.         }
  147.  
  148.         explicit multiset(const Compare& comp = Compare(), const Allocator& al = Allocator())
  149.                 : base(comp, al, v_t_k) {  }
  150.  
  151.         template <class InputIterator> multiset(InputIterator first, InputIterator last,
  152.                 const Compare& comp = Compare(), const Allocator& al = Allocator())
  153.                 : base(first, last, comp, al, v_t_k) {  }
  154.  
  155.  
  156.         multiset(const multiset<Key, Compare, Allocator>& x) : base(x) {  }
  157.         ~multiset() {  }
  158.  
  159.         using base::operator=;
  160.         using base::operator==;
  161.         using base::operator!=;
  162.  
  163.         using base::insert;
  164.         using base::erase;
  165.  
  166.         using base::begin;
  167.         using base::end;
  168.         using base::rbegin;
  169.         using base::rend;
  170.  
  171.         using base::empty;
  172.         using base::size;
  173.         using base::max_size;
  174.  
  175.         using base::find;
  176.         using base::count;
  177.         using base::lower_bound;
  178.         using base::upper_bound;
  179.         using base::equal_range;
  180.  
  181.  
  182. protected:
  183.  
  184. };
  185.  
  186.  
  187. /* Non-member functions.  These are at the end because they are not associated with any
  188.    particular class.  These will be implemented as I figure out exactly what all of
  189.    them are supposed to do, and I have time.
  190.  */
  191.  
  192.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<
  193.                 (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
  194.         {
  195.                 typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  196.                 typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  197.                 typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
  198.                 typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
  199.  
  200.                 while(first1 != last1 && first2 != last2){
  201.                         if( *first1 < *first2 ){
  202.                                 return true;
  203.                         }
  204.                         if( *first2 < *first1 ){
  205.                                 return false;
  206.                         }
  207.                         ++first1;
  208.                         ++first2;
  209.                 }
  210.                 return first1==last1 && first2 != last2;
  211.         }
  212.  
  213.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>
  214.                 (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
  215.         {
  216.                 typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  217.                 typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  218.                 typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
  219.                 typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
  220.  
  221.                 while(first1 != last1 && first2 != last2){
  222.                         if( *first1 > *first2 ){
  223.                                 return true;
  224.                         }
  225.                         if( *first2 > *first1 ){
  226.                                 return false;
  227.                         }
  228.                         ++first1;
  229.                         ++first2;
  230.                 }
  231.                 return first1!=last1 && first2 == last2;
  232.         }
  233.  
  234.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
  235.                 (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
  236.         {
  237.                 typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  238.                 typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  239.                 typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
  240.                 typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
  241.  
  242.                 while(first1 != last1 && first2 != last2){
  243.                         if( *first1 > *first2 ){
  244.                                 return true;
  245.                         }
  246.                         if( *first2 > *first1 ){
  247.                                 return false;
  248.                         }
  249.                         ++first1;
  250.                         ++first2;
  251.                 }
  252.                 return first1!=last1;
  253.         }
  254.  
  255.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
  256.                 (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
  257.         {
  258.                 typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  259.                 typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  260.                 typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
  261.                 typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
  262.  
  263.                 while(first1 != last1 && first2 != last2){
  264.                         if( *first1 < *first2 ){
  265.                                 return true;
  266.                         }
  267.                         if( *first2 < *first1 ){
  268.                                 return false;
  269.                         }
  270.                         ++first1;
  271.                         ++first2;
  272.                 }
  273.                 return first2!=last2;
  274.         }
  275.         template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
  276.                 (set<Key,Compare,Allocator>& x, set<Key,Compare,Allocator>& y)
  277.         {
  278.                 x.swap(y);
  279.         }
  280.  
  281.  
  282.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator==
  283.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  284.         {
  285.                 if(x.data == y.data){
  286.                         return true;
  287.                 }
  288.                 return false;
  289.         }
  290.  
  291.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<
  292.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  293.         {
  294.                 typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  295.                 typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  296.                 typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
  297.                 typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
  298.  
  299.                 while(first1 != last1 && first2 != last2){
  300.                         if( *first1 < *first2 ){
  301.                                 return true;
  302.                         }
  303.                         if( *first2 < *first1 ){
  304.                                 return false;
  305.                         }
  306.                         ++first1;
  307.                         ++first2;
  308.                 }
  309.                 return first1==last1 && first2 != last2;
  310.         }
  311.  
  312.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator!=
  313.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  314.         {
  315.                 typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  316.                 typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  317.                 typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
  318.                 typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
  319.  
  320.                 while(first1 != last1 && first2 != last2){
  321.                         if( *first1 != *first2 ){
  322.                                 return true;
  323.                         }
  324.                         ++first1;
  325.                         ++first2;
  326.                 }
  327.                 return first1!=last1 || first2 != last2;
  328.         }
  329.  
  330.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>
  331.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  332.         {
  333.                 typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  334.                 typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  335.                 typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
  336.                 typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
  337.  
  338.                 while(first1 != last1 && first2 != last2){
  339.                         if( *first1 > *first2 ){
  340.                                 return true;
  341.                         }
  342.                         if( *first2 > *first1 ){
  343.                                 return false;
  344.                         }
  345.                         ++first1;
  346.                         ++first2;
  347.                 }
  348.                 return first1!=last1 && first2 == last2;
  349.         }
  350.  
  351.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
  352.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  353.         {
  354.                 typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  355.                 typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  356.                 typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
  357.                 typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
  358.  
  359.                 while(first1 != last1 && first2 != last2){
  360.                         if( *first1 > *first2 ){
  361.                                 return true;
  362.                         }
  363.                         if( *first2 > *first1 ){
  364.                                 return false;
  365.                         }
  366.                         ++first1;
  367.                         ++first2;
  368.                 }
  369.                 return first1!=last1;
  370.         }
  371.  
  372.         template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
  373.                 (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
  374.         {
  375.                 typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
  376.                 typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
  377.                 typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
  378.                 typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
  379.  
  380.                 while(first1 != last1 && first2 != last2){
  381.                         if( *first1 < *first2 ){
  382.                                 return true;
  383.                         }
  384.                         if( *first2 < *first1 ){
  385.                                 return false;
  386.                         }
  387.                         ++first1;
  388.                         ++first2;
  389.                 }
  390.                 return first2!=last2;
  391.         }
  392.  
  393.         template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
  394.                 (multiset<Key,Compare,Allocator>& x, multiset<Key,Compare,Allocator>& y)
  395.         {
  396.                 x.swap(y);
  397.         }
  398.  
  399.  
  400.  
  401. }
  402.  
  403. #pragma GCC visibility pop
  404.  
  405. #endif
  406.  
  407.