blocxx

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