SortedVectorSet.hpp

Go to the documentation of this file.
00001 /*******************************************************************************
00002 * Copyright (C) 2004 Vintela, Inc. All rights reserved.
00003 * Copyright (C) 2005 Novell, Inc. All rights reserved.
00004 *
00005 * Redistribution and use in source and binary forms, with or without
00006 * modification, are permitted provided that the following conditions are met:
00007 *
00008 *  - Redistributions of source code must retain the above copyright notice,
00009 *    this list of conditions and the following disclaimer.
00010 *
00011 *  - Redistributions in binary form must reproduce the above copyright notice,
00012 *    this list of conditions and the following disclaimer in the documentation
00013 *    and/or other materials provided with the distribution.
00014 *
00015 *  - Neither the name of Vintela, Inc., Novell, Inc., nor the names of its
00016 *    contributors may be used to endorse or promote products derived from this
00017 *    software without specific prior written permission.
00018 *
00019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
00020 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00021 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00022 * ARE DISCLAIMED. IN NO EVENT SHALL Vintela, Inc., Novell, Inc., OR THE 
00023 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
00024 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
00025 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 
00026 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
00027 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 
00028 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 
00029 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030 *******************************************************************************/
00031 
00032 
00037 #ifndef BLOCXX_SORTED_VECTOR_SET_HPP_
00038 #define BLOCXX_SORTED_VECTOR_SET_HPP_
00039 #include "blocxx/BLOCXX_config.h"
00040 #include "blocxx/COWReference.hpp"
00041 #include "blocxx/vector.hpp"
00042 #include <utility> // for std::pair
00043 #include <functional> // for std::less
00044 #include <algorithm>
00045 
00046 namespace BLOCXX_NAMESPACE
00047 {
00048 
00049 template<class T, class Compare >
00050 class SortedVectorSet;
00051 
00052 template<class T, class Compare>
00053 inline bool operator==(const SortedVectorSet<T, Compare>& x,
00054    const SortedVectorSet<T, Compare>& y);
00055 
00056 template<class T, class Compare>
00057 inline bool operator<(const SortedVectorSet<T, Compare>& x,
00058    const SortedVectorSet<T, Compare>& y);
00059 
00060 template<class T, class Compare = std::less<T> >
00061 class SortedVectorSet
00062 {
00063    typedef std::vector<T> container_t;
00064 #ifdef BLOCXX_WIN32
00065 #pragma warning (push)
00066 #pragma warning (disable: 4251)
00067 #endif
00068    COWReference<container_t> m_impl;
00069 #ifdef BLOCXX_WIN32
00070 #pragma warning (pop)
00071 #endif
00072 public:
00073    typedef          T key_type;
00074    typedef          T data_type;
00075    typedef          T value_type;
00076    typedef          Compare key_compare;
00077    typedef          Compare value_compare;
00078    typedef typename container_t::pointer pointer;
00079    typedef typename container_t::const_pointer const_pointer;
00080    typedef typename container_t::reference reference;
00081    typedef typename container_t::const_reference const_reference;
00082    typedef typename container_t::iterator iterator;
00083    typedef typename container_t::const_iterator const_iterator;
00084    typedef typename container_t::reverse_iterator reverse_iterator;
00085    typedef typename container_t::const_reverse_iterator const_reverse_iterator;
00086    typedef typename container_t::size_type size_type;
00087    typedef typename container_t::difference_type difference_type;
00088    SortedVectorSet() : m_impl(new container_t) {  }
00089    explicit SortedVectorSet(container_t* toWrap) : m_impl(toWrap)
00090       { }
00091    template <class InputIterator>
00092    SortedVectorSet(InputIterator first, InputIterator last) :
00093       m_impl(new container_t(first, last))
00094    {
00095       std::sort(m_impl->begin(), m_impl->end(), Compare());
00096    }
00097    const_iterator begin() const { return m_impl->begin(); }
00098    const_iterator end() const { return m_impl->end(); }
00099    const_reverse_iterator rbegin() const { return m_impl->rbegin(); }
00100    const_reverse_iterator rend() const { return m_impl->rend(); }
00101    bool empty() const { return m_impl->empty(); }
00102    size_type size() const { return m_impl->size(); }
00103    size_type max_size() const { return m_impl->max_size(); }
00104    void swap(SortedVectorSet<T, Compare>& x)
00105    {
00106       m_impl.swap(x.m_impl);
00107    }
00108    std::pair<iterator, bool> insert(const value_type& x)
00109    {
00110       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00111       if (i != m_impl->end() && equivalent(*i, x))
00112       {
00113          return std::pair<iterator, bool>(i, false);
00114       }
00115       else
00116       {
00117          return std::pair<iterator, bool>(m_impl->insert(i, x), true);
00118       }
00119    }
00120    iterator insert(iterator, const value_type& x)
00121    {
00122       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00123       
00124       return m_impl->insert(i, x);
00125    }
00126    template <class InputIterator>
00127    void insert(InputIterator first, InputIterator last)
00128    {
00129       for (; first != last; ++first)
00130       {
00131          m_impl->push_back(*first);
00132       }
00133       std::sort(m_impl->begin(), m_impl->end(), Compare());
00134    }
00135    void erase(iterator position)
00136    {
00137       m_impl->erase(position);
00138    }
00139    size_type erase(const key_type& x)
00140    {
00141       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00142       if (i != m_impl->end() && equivalent(*i, x))
00143       {
00144          m_impl->erase(i);
00145          return 1;
00146       }
00147       else
00148       {
00149          return 0;
00150       }
00151    }
00152    void erase(iterator first, iterator last)
00153    {
00154       m_impl->erase(first, last);
00155    }
00156    void clear()
00157    {
00158       m_impl->clear();
00159    }
00160    iterator find(const key_type& x)
00161    {
00162       iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00163       if (pos != m_impl->end() && equivalent(*pos, x)) 
00164       {
00165          return pos;
00166       }
00167       else
00168       {
00169          return m_impl->end();
00170       }
00171    }
00172    const_iterator find(const key_type& x) const
00173    {
00174       const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00175       if (pos != m_impl->end() && equivalent(*pos, x)) 
00176       {
00177          return pos;
00178       }
00179       else
00180       {
00181          return m_impl->end();
00182       }
00183    }
00184    size_type count(const key_type& x) const
00185    {
00186       if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare()))
00187       {
00188          return 1;
00189       }
00190       else
00191       {
00192          return 0;
00193       }
00194    }
00195    iterator lower_bound(const key_type& x)
00196    {
00197       return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00198    }
00199    const_iterator lower_bound(const key_type& x) const
00200    {
00201       return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00202    }
00203    iterator upper_bound(const key_type& x)
00204    {
00205       return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
00206    }
00207    const_iterator upper_bound(const key_type& x) const
00208    {
00209       return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
00210    }
00211 
00212    std::pair<iterator, iterator>
00213       equal_range(const key_type& x)
00214    {
00215       return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
00216    }
00217 
00218    std::pair<const_iterator, const_iterator>
00219       equal_range(const key_type& x) const
00220    {
00221       return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
00222    }
00223 
00224    friend bool operator== <>(const SortedVectorSet<T, Compare>& x,
00225       const SortedVectorSet<T, Compare>& y);
00226    friend bool operator< <>(const SortedVectorSet<T, Compare>& x,
00227       const SortedVectorSet<T, Compare>& y);
00228 
00229 private:
00230    bool equivalent(const key_type& x, const key_type& y) const
00231    {
00232       // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false.
00233       return (!Compare()(x, y) && !Compare()(y, x)); 
00234    }
00235 };
00236 template<class T, class Compare>
00237 inline bool operator==(const SortedVectorSet<T, Compare>& x,
00238    const SortedVectorSet<T, Compare>& y)
00239 {
00240    return *x.m_impl == *y.m_impl;
00241 }
00242 template<class T, class Compare>
00243 inline bool operator<(const SortedVectorSet<T, Compare>& x,
00244    const SortedVectorSet<T, Compare>& y)
00245 {
00246    return *x.m_impl < *y.m_impl;
00247 }
00248 template <class T, class Compare>
00249 inline void swap(SortedVectorSet<T, Compare>& x,
00250    SortedVectorSet<T, Compare>& y)
00251 {
00252    x.swap(y);
00253 }
00254 
00255 } // end namespace BLOCXX_NAMESPACE
00256 
00257 #endif

Generated on Fri Jun 16 15:39:09 2006 for blocxx by  doxygen 1.4.6