blocxx

SortedVectorSet.hpp

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