SortedVectorMap.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_MAP_HPP_
00038 #define BLOCXX_SORTED_VECTOR_MAP_HPP_
00039 #include "blocxx/BLOCXX_config.h"
00040 #include "blocxx/COWReference.hpp"
00041 #include "blocxx/vector.hpp"
00042 #include "blocxx/CommonFwd.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 Key, class T, class Compare>
00051 class SortedVectorMapDataCompare
00052 {
00053    typedef std::pair<Key, T> Data;
00054 public:
00055    bool operator()(const Data& lhs, const Data& rhs) const
00056    {
00057       return keyLess(lhs.first, rhs.first);
00058    }
00059    
00060    bool operator()(const Data& lhs, const typename Data::first_type& k) const
00061    {
00062       return keyLess(lhs.first, k);
00063    }
00064    
00065    bool operator()(const typename Data::first_type& k, const Data& rhs) const
00066    {
00067       return keyLess(k, rhs.first);
00068    }
00069    bool operator()(const typename Data::first_type& k, const typename Data::first_type& rhs) const
00070    {
00071       return keyLess(k, rhs);
00072    }
00073 private:
00074    bool keyLess(const typename Data::first_type& k1,
00075       const typename Data::first_type& k2) const
00076    {
00077       return Compare()(k1, k2);
00078    }
00079 };
00080 
00081 
00082 // forward declarations are necessary for template friends.
00083 template<class Key, class T, class Compare>
00084 inline bool operator==(const SortedVectorMap<Key, T, Compare>& x,
00085    const SortedVectorMap<Key, T, Compare>& y);
00086 
00087 template<class Key, class T, class Compare>
00088 inline bool operator<(const SortedVectorMap<Key, T, Compare>& x,
00089    const SortedVectorMap<Key, T, Compare>& y);
00090 
00091 template <class Key, class T, class Compare>
00092 inline void swap(SortedVectorMap<Key, T, Compare>& x,
00093    SortedVectorMap<Key, T, Compare>& y);
00094 
00095 template<class Key, class T, class Compare>
00096 class SortedVectorMap
00097 {
00098    typedef std::pair<Key, T> Data;
00099    typedef std::vector<Data> container_t;
00100    COWReference<container_t> m_impl;
00101 public:
00102    typedef          Key key_type;
00103    typedef          T data_type;
00104    typedef          std::pair<const key_type, data_type> value_type;
00105    typedef          Compare key_compare;
00106    typedef          Compare value_compare;
00107    typedef typename container_t::pointer pointer;
00108    typedef typename container_t::reference reference;
00109    typedef typename container_t::const_reference const_reference;
00110    typedef typename container_t::iterator iterator;
00111    typedef typename container_t::const_iterator const_iterator;
00112    typedef typename container_t::reverse_iterator reverse_iterator;
00113    typedef typename container_t::const_reverse_iterator const_reverse_iterator;
00114    typedef typename container_t::size_type size_type;
00115    typedef typename container_t::difference_type difference_type;
00116    SortedVectorMap() : m_impl(new container_t) {  }
00117    explicit SortedVectorMap(container_t* toWrap) : m_impl(toWrap)
00118       { }
00119    template <class InputIterator>
00120    SortedVectorMap(InputIterator first, InputIterator last) :
00121       m_impl(new container_t(first, last))
00122    {
00123       std::sort(m_impl->begin(), m_impl->end(), Compare());
00124    }
00125    const_iterator begin() const
00126    {
00127       return m_impl->begin();
00128    }
00129    const_iterator end() const
00130    {
00131       return m_impl->end();
00132    }
00133    // These are slightly dangerous, if you use them, DON'T CHANGE THE KEY!
00134    iterator begin()
00135    {
00136       return m_impl->begin();
00137    }
00138    iterator end()
00139    {
00140       return m_impl->end();
00141    }
00142    const_reverse_iterator rbegin() const
00143    {
00144       return m_impl->rbegin();
00145    }
00146    const_reverse_iterator rend() const
00147    {
00148       return m_impl->rend();
00149    }
00150    bool empty() const
00151    {
00152       return m_impl->empty();
00153    }
00154    size_type size() const
00155    {
00156       return m_impl->size();
00157    }
00158    size_type max_size() const
00159    {
00160       return m_impl->max_size();
00161    }
00162    data_type& operator[](const key_type& k)
00163    {
00164       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), k, Compare());
00165       if (i != m_impl->end() && equivalent(i->first, k))
00166       {
00167          return i->second;
00168       }
00169       return (*(m_impl->insert(i, value_type(k, data_type())))).second;
00170    }
00171    void swap(SortedVectorMap<Key, T, Compare>& x)
00172    {
00173       m_impl.swap(x.m_impl);
00174    }
00175    std::pair<iterator, bool> insert(const value_type& x)
00176    {
00177       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00178       if (i != m_impl->end() && equivalent(i->first, x.first))
00179       {
00180          return std::pair<iterator, bool>(i, false);
00181       }
00182       else
00183       {
00184          return std::pair<iterator, bool>(m_impl->insert(i, x), true);
00185       }
00186    }
00187    iterator insert(iterator, const value_type& x)
00188    {
00189       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00190       
00191       return m_impl->insert(i, x);
00192    }
00193    template <class InputIterator>
00194    void insert(InputIterator first, InputIterator last)
00195    {
00196       for (; first != last; ++first)
00197       {
00198          m_impl->push_back(*first);
00199       }
00200       std::sort(m_impl->begin(), m_impl->end(), Compare());
00201    }
00202    void erase(iterator position)
00203    {
00204       m_impl->erase(position);
00205    }
00206    size_type erase(const key_type& x)
00207    {
00208       iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00209       if (i != m_impl->end() && equivalent(i->first, x))
00210       {
00211          m_impl->erase(i);
00212          return 1;
00213       }
00214       else
00215       {
00216          return 0;
00217       }
00218    }
00219    void erase(iterator first, iterator last)
00220    {
00221       m_impl->erase(first, last);
00222    }
00223    void clear()
00224    {
00225       m_impl->clear();
00226    }
00227    const_iterator find(const key_type& x) const
00228    {
00229       const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00230       if (pos != m_impl->end() && equivalent(pos->first, x))
00231       {
00232          return pos;
00233       }
00234       else
00235       {
00236          return m_impl->end();
00237       }
00238    }
00239    iterator find(const key_type& x)
00240    {
00241       iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00242       if (pos != m_impl->end() && equivalent(pos->first, x))
00243       {
00244          return pos;
00245       }
00246       else
00247       {
00248          return m_impl->end();
00249       }
00250    }
00251    size_type count(const key_type& x) const
00252    {
00253       if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare()))
00254       {
00255          return 1;
00256       }
00257       else
00258       {
00259          return 0;
00260       }
00261    }
00262    const_iterator lower_bound(const key_type& x) const
00263    {
00264       return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00265    }
00266    const_iterator upper_bound(const key_type& x) const
00267    {
00268       return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
00269    }
00270    std::pair<const_iterator, const_iterator>
00271       equal_range(const key_type& x) const
00272    {
00273       return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
00274    }
00275    friend bool operator== <>(const SortedVectorMap<Key, T, Compare>& x,
00276       const SortedVectorMap<Key, T, Compare>& y);
00277    friend bool operator< <>(const SortedVectorMap<Key, T, Compare>& x,
00278       const SortedVectorMap<Key, T, Compare>& y);
00279 private:
00280    bool equivalent(const key_type& x, const key_type& y) const
00281    {
00282       // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false.
00283       return (!Compare()(x, y) && !Compare()(y, x));
00284    }
00285 };
00286 template<class Key, class T, class Compare>
00287 inline bool operator==(const SortedVectorMap<Key, T, Compare>& x,
00288    const SortedVectorMap<Key, T, Compare>& y)
00289 {
00290    return *x.m_impl == *y.m_impl;
00291 }
00292 template<class Key, class T, class Compare>
00293 inline bool operator<(const SortedVectorMap<Key, T, Compare>& x,
00294    const SortedVectorMap<Key, T, Compare>& y)
00295 {
00296    return *x.m_impl < *y.m_impl;
00297 }
00298 template <class Key, class T, class Compare>
00299 inline void swap(SortedVectorMap<Key, T, Compare>& x,
00300    SortedVectorMap<Key, T, Compare>& y)
00301 {
00302    x.swap(y);
00303 }
00304 
00305 } // end namespace BLOCXX_NAMESPACE
00306 
00307 #endif

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