19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// This file is part of the ustl library, an STL implementation. 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// This file is free software, distributed under the MIT License. 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// umap.h 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#ifndef UMAP_H_45643F516E02A87A3DCEA5024052A6F5 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define UMAP_H_45643F516E02A87A3DCEA5024052A6F5 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "uassert.h" 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "ufunction.h" 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "uvector.h" 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectnamespace ustl { 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \class map umap.h ustl.h 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup AssociativeContainers 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief A sorted associative container of pair<K,V> 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectclass map : public vector<pair<K,V> > { 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic: 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef K key_type; 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef V data_type; 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef const K& const_key_ref; 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef const V& const_data_ref; 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef const map<K,V>& rcself_t; 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef vector<pair<K,V> > base_class; 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::value_type value_type; 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::size_type size_type; 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::pointer pointer; 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::const_pointer const_pointer; 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::reference reference; 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::const_reference const_reference; 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::const_iterator const_iterator; 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::iterator iterator; 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::reverse_iterator reverse_iterator; 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename base_class::const_reverse_iterator const_reverse_iterator; 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef pair<const_iterator,const_iterator> const_range_t; 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef pair<iterator,iterator> range_t; 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic: 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline map (void) : vector<pair<K,V> > () {} 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project explicit inline map (size_type n) : vector<pair<K,V> > (n) {} 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline map (rcself_t v) : vector<pair<K,V> > (v) {} 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline map (const_iterator i1, const_iterator i2) : vector<pair<K,V> >() { insert (i1, i2); } 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline rcself_t operator= (rcself_t v) { base_class::operator= (v); return (*this); } 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline const_data_ref operator[] (const_key_ref i) const; 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project data_type& operator[] (const_key_ref i); 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline size_type size (void) const { return (base_class::size()); } 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator begin (void) { return (base_class::begin()); } 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline const_iterator begin (void) const { return (base_class::begin()); } 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator end (void) { return (base_class::end()); } 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline const_iterator end (void) const { return (base_class::end()); } 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline void assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); } 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline void push_back (const_reference v) { insert (v); } 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline const_iterator find (const_key_ref k) const; 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator find (const_key_ref k) { return (const_cast<iterator> (const_cast<rcself_t>(*this).find (k))); } 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline const_iterator find_data (const_data_ref v, const_iterator first = NULL, const_iterator last = NULL) const; 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator find_data (const_data_ref v, iterator first = NULL, iterator last = NULL); 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iterator insert (const_reference v); 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project void insert (const_iterator i1, const_iterator i2); 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline void erase (const_key_ref k); 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator erase (iterator ep) { return (base_class::erase (ep)); } 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); } 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline void clear (void) { base_class::clear(); } 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectprivate: 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const_iterator lower_bound (const_key_ref k) const; 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project inline iterator lower_bound (const_key_ref k) { return (const_cast<iterator>(const_cast<rcself_t>(*this).lower_bound (k))); } 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project}; 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttypename map<K,V>::const_iterator map<K,V>::lower_bound (const_key_ref k) const 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const_iterator first (begin()), last (end()); 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (first != last) { 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const_iterator mid = advance (first, distance (first,last) / 2); 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mid->first < k) 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project first = advance (mid, 1); 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project last = mid; 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the pair<K,V> where K = \p k. 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline typename map<K,V>::const_iterator map<K,V>::find (const_key_ref k) const 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const_iterator i = lower_bound (k); 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ((i < end() && k < i->first) ? end() : i); 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the pair<K,V> where V = \p v, occuring in range [first,last). 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline typename map<K,V>::const_iterator map<K,V>::find_data (const_data_ref v, const_iterator first, const_iterator last) const 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!first) first = begin(); 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!last) last = end(); 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last && first->second != v; ++first); 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the pair<K,V> where V = \p v, occuring in range [first,last). 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline typename map<K,V>::iterator map<K,V>::find_data (const_data_ref v, iterator first, iterator last) 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (const_cast<iterator> (find_data (v, const_cast<const_iterator>(first), const_cast<const_iterator>(last)))); 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns data associated with key \p k. 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline const typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) const 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project assert (find(k) != end() && "operator[] const can not insert non-existent keys"); 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (find(k)->second); 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns data associated with key \p k. 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttypename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iterator ip = lower_bound (k); 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip == end() || k < ip->first) 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip = base_class::insert (ip, make_pair (k, V())); 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (ip->second); 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Inserts the pair into the container. 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttypename map<K,V>::iterator map<K,V>::insert (const_reference v) 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iterator ip = lower_bound (v.first); 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip == end() || v.first < ip->first) 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip = base_class::insert (ip, v); 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *ip = v; 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (ip); 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Inserts elements from range [i1,i2) into the container. 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid map<K,V>::insert (const_iterator i1, const_iterator i2) 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project assert (i1 <= i2); 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reserve (size() + distance (i1, i2)); 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; i1 != i2; ++i1) 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project insert (*i1); 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Erases the element with key value \p k. 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename K, typename V> 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void map<K,V>::erase (const_key_ref k) 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iterator ip = find (k); 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip != end()) 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project erase (ip); 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} // namespace ustl 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#endif 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 166