OW_SortedVectorMap.hpp

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

Generated on Thu Feb 9 08:48:13 2006 for openwbem by  doxygen 1.4.6