Documentation Overview Building ASL Documentation Library Wiki Docs Indices Browse Perforce More Info Release Notes Wiki Site Search License Success Stories Contributors Media Download Perforce Depots Support ASL SourceForge Home Mailing Lists Discussion Forums Report Bugs Suggest Features Contribute to ASL RSS Short-text news Full-text news File releases Other Adobe Projects Adobe Air Adobe GIL C++ Benchmarks Adobe Labs Adobe Media Gallery Adobe XMP Tamarin project (Mozilla Foundation) Other Resources Boost RIAForge SGI STL

table_index.hpp Go to the documentation of this file. /* Copyright 2005-2007 Adobe Systems Incorporated Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt or a copy at http://stlab.adobe.com/licenses.html) */ /*************************************************************************************************/ #ifndef ADOBE_TABLE_INDEX_HPP #define ADOBE_TABLE_INDEX_HPP /*************************************************************************************************/ #include <adobe/config.hpp> #include <functional> #include <stdexcept> #include <vector> #include <boost/operators.hpp> #include <boost/iterator/indirect_iterator.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/next_prior.hpp> #include <boost/type_traits/remove_reference.hpp> #include <adobe/algorithm/count.hpp> #include <adobe/algorithm/equal_range.hpp> #include <adobe/algorithm/lower_bound.hpp> #include <adobe/algorithm/sort.hpp> #include <adobe/algorithm/unique.hpp> #include <adobe/algorithm/upper_bound.hpp> #include <adobe/closed_hash.hpp> #include <adobe/functional.hpp> /*************************************************************************************************/ namespace adobe { /*************************************************************************************************/ template < typename T, // models Regular typename H = boost::hash<T>, // models UnaryFunction key_type -> size_t typename C = std::equal_to<T>, // models EqualityComparison(key_type, key_type) typename P = identity<T> > // models UnaryFunction T -> key_type class hash_index { public: typedef T value_type; typedef P key_function_type; typedef typename boost::remove_reference<typename key_function_type::result_type>::type key_type; typedef H hasher; typedef C key_equal; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef unary_compose< key_function_type, indirect<value_type> > indirect_key_function_type; typedef closed_hash_set<pointer, indirect_key_function_type, hasher, key_equal> index_type; typedef boost::indirect_iterator<typename index_type::iterator> iterator; typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; /* REVISIT (sparent@adobe.com) : This is a very limited set of constructors - need to have a general strategy for which constructors to provide. */ hash_index() { } /* NOTE: The constructor is templatized so things like mem_fun are not necessary. */ template <typename F> // F is convertible to key_function_type hash_index(hasher hf, key_equal eq, F kf) : index_m(0, hf, eq, compose(key_function_type(kf), indirect<value_type>())) { } //allocator_type get_allocator() const; size_type max_size() const { return index_m.max_size(); } size_type size() const { return index_m.size(); } bool empty() const { return index_m.empty(); } size_type capacity() const { return index_m.capacity(); } void reserve(size_type n) { index_m.reserve(); } iterator begin() { return iterator(index_m.begin()); } iterator end() { return iterator(index_m.end()); } const_iterator begin() const { return const_iterator(index_m.begin()); } const_iterator end() const { return const_iterator(index_m.end()); } reverse_iterator rbegin() { return reverse_iterator(index_m.rbegin()); } reverse_iterator rend() { return reverse_iterator(index_m.rend()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(index_m.rbegin()); } const_reverse_iterator rend() const { return const_reverse_iterator(index_m.rend()); } std::pair<iterator, bool> insert(value_type& x) { std::pair<typename index_type::iterator, bool> result = index_m.insert(&x); return std::make_pair(iterator(result.first), result.second); } template <typename I> void insert(I f, I l) { index_m.insert( boost::make_transform_iterator(f, pointer_to<value_type>()), boost::make_transform_iterator(l, pointer_to<value_type>())); } iterator insert(iterator i, value_type& x) { return iterator(index_m.insert(i, &x)); } iterator erase(iterator i) { return index_m.erase(i.base()); } size_type erase(const key_type& x) { return index_m.erase(x); } void clear() { index_m.clear(); } index_type& index() { return index_m; } const index_type& index() const { return index_m; } iterator find(const key_type& x) { return iterator(index_m.find(x)); } const_iterator find(const key_type& x) const { return const_iterator(index_m.find(x)); } size_type count(const key_type& x) const { return index_m.count(x); } iterator lower_bound(const key_type& x) { return iterator(index_m.lower_bound()); } const_iterator lower_bound(const key_type& x) const { return const_iterator(index_m.lower_bound()); } iterator upper_bound(const key_type& x) { return iterator(index_m.upper_bound()); } const_iterator upper_bound(const key_type& x) const { return const_iterator(index_m.upper_bound()); } std::pair<iterator, iterator> equal_range(const key_type& x) { std::pair<typename index_type::iterator, typename index_type::iterator> result = index_m.equal_range(x); return std::make_pair(iterator(result.first), iterator(result.second)); } std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const { std::pair<typename index_type::const_iterator, typename index_type::const_iterator> result = index_m.equal_range(x); return std::make_pair(const_iterator(result.first), const_iterator(result.second)); } key_function_type key_function() const { return index_m.key_function(); } hasher hash_function() const { return index_m.hash_function(); } key_equal key_eq() const { return index_m.key_eq(); } friend void swap(hash_index& x, hash_index& y) { swap(x.index_m, y.index_m); } private: index_type index_m; }; /*************************************************************************************************/ template < typename Key, // models Regular typename T, // models Regular typename Transform = mem_data_t<T, const Key>, // models UnaryFunction Key(T) typename Compare = std::less<Key> // models BinaryFunction bool(Key, Key) > class table_index { public: typedef typename std::vector<T*> index_type; typedef Transform transform_type; typedef Key key_type; typedef T value_type; typedef Compare key_compare; // Revisit? // typedef Allocator allocator_type; typedef T& reference; typedef const T& const_reference; typedef typename index_type::size_type size_type; typedef typename index_type::difference_type difference_type; typedef T* pointer; typedef const T* const_pointer; typedef boost::indirect_iterator<typename index_type::iterator> iterator; typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; template <class TransformPrimitive> explicit table_index(TransformPrimitive transform, const key_compare& compare = key_compare()) : transform_m(transform), compare_m(compare) { } explicit table_index(const transform_type&, const key_compare& = key_compare()); template <typename InputIterator, typename TransformPrimitive> table_index( InputIterator first, InputIterator last, TransformPrimitive transform, const key_compare& compare = key_compare()) : transform_m(transform), compare_m(compare) { insert(begin(), first, last); } //allocator_type get_allocator() const; size_type max_size() const; size_type size() const; bool empty() const; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; reverse_iterator rbegin(); const_reverse_iterator rbegin() const; reverse_iterator rend(); const_reverse_iterator rend() const; const_reference at(size_type n) const; reference at(size_type n); reference front(); const_reference front() const; reference back(); const_reference back() const; void push_back(value_type&); void pop_back(); iterator insert(iterator, value_type&); template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last); iterator erase(iterator location); iterator erase(iterator first, iterator last); void clear(); index_type& index(); const index_type& index() const; /* REVISIT (sparent) : If we wanted to allow sort() and unique() - and other algoriths to operate directly on the index rather than being built in, what would be required of the index interface? */ void sort(); // Operations on a sorted index. void unique(); reference operator[](const key_type&); const_reference operator[](const key_type&) const; iterator find(const key_type& x); const_iterator find(const key_type& x) const; size_type count(const key_type& x) const; iterator lower_bound(const key_type& x); const_iterator lower_bound(const key_type& x) const; iterator upper_bound(const key_type& x); const_iterator upper_bound(const key_type& x) const; std::pair<iterator, iterator> equal_range(const key_type& x); std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const; transform_type transform() const { return transform_m; } friend void swap(table_index& x, table_index& y) { swap(x.transform_m, y.transform_m); swap(x.compare_m, y.compare_m); swap(x.index_m, y.index_m); } private: #ifndef ADOBE_NO_DOCUMENTATION struct indirect_compare_t : std::binary_function<pointer, pointer, bool> { typedef bool result_type; indirect_compare_t(transform_type& transform, const key_compare& compare) : transform_m(transform), compare_m(compare) { } bool operator () (pointer x, pointer y) const { return compare_m(transform_m(*x), transform_m(*y)); } private: transform_type transform_m; /* REVISIT (sparent) : want reference here? */ key_compare compare_m; }; #endif transform_type transform_m; key_compare compare_m; index_type index_m; }; /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> table_index<Key, T, Compare, Transform>::table_index( const transform_type& transform, const key_compare& compare) : transform_m(transform), compare_m(compare) { } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::begin() { return iterator(index_m.begin()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_iterator table_index<Key, T, Compare, Transform>::begin() const { return const_iterator(index_m.begin()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::end() { return iterator(index_m.end()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_iterator table_index<Key, T, Compare, Transform>::end() const { return const_iterator(index_m.end()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::reverse_iterator table_index<Key, T, Compare, Transform>::rbegin() { return reverse_iterator(index_m.rbegin()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_reverse_iterator table_index<Key, T, Compare, Transform>::rbegin() const { return const_reverse_iterator(index_m.rbegin()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::reverse_iterator table_index<Key, T, Compare, Transform>::rend() { return reverse_iterator(index_m.rend()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_reverse_iterator table_index<Key, T, Compare, Transform>::rend() const { return reverse_iterator(index_m.rend()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::size_type table_index<Key, T, Compare, Transform>::max_size() const { return index_m.max_size(); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::size_type table_index<Key, T, Compare, Transform>::size() const { return index_m.size(); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline bool table_index<Key, T, Compare, Transform>::empty() const { return index_m.empty(); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline void table_index<Key, T, Compare, Transform>::push_back(value_type& x) { index_m.push_back(&x); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline void table_index<Key, T, Compare, Transform>::pop_back() { index_m.pop_back(); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::insert(iterator position, value_type& x) { return index_m.insert(position, &x); } /*************************************************************************************************/ /* REVISIT (sparent) : We should be able to greatly improve the table_index class - this function in particular could be much more efficient. */ template <class Key, class T, class Compare, class Transform> template <class InputIterator> inline void table_index<Key, T, Compare, Transform>::insert(iterator position, InputIterator first, InputIterator last) { typename index_type::iterator iter = position.base(); while (first != last) { iter = index_m.insert(iter, &*first); ++iter; ++first; } } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::erase(iterator position) { return index_m.erase(position.base()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::erase(iterator first, iterator last) { return index_m.erase(first.base(), last.base()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline void table_index<Key, T, Compare, Transform>::clear() { index_m.clear(); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> void table_index<Key, T, Compare, Transform>::sort() { adobe::sort(index_m, indirect_compare_t(transform_m, compare_m)); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> void table_index<Key, T, Compare, Transform>::unique() { typename index_type::iterator i (adobe::unique(index_m, indirect_compare_t(transform_m, compare_m))); index_m.erase(i, index_m.end()); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::reference table_index<Key, T, Compare, Transform>::at(const size_type n) { return *index_m.at(n); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_reference table_index<Key, T, Compare, Transform>::at(const size_type n) const { return *index_m.at(n); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::reference table_index<Key, T, Compare, Transform>::operator [] (const key_type& key) { iterator iter (find(key)); if (iter == end()) throw std::range_error("Key not present in table."); return *iter; } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_reference table_index<Key, T, Compare, Transform>::operator [] (const key_type& key) const { const_iterator iter(find(key)); if (iter == end()) throw std::range_error("Key not present in table."); return *iter; } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::find(const key_type& key) { typename index_type::iterator iter = lower_bound(key).base(); if (iter != index_m.end() && transform_m(**iter) != key) iter = index_m.end(); return iter; } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_iterator table_index<Key, T, Compare, Transform>::find(const key_type& key) const { typename index_type::const_iterator iter = lower_bound(key).base(); if (iter != index_m.end() && transform_m(**iter) != key) iter = index_m.end(); return iter; } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::size_type table_index<Key, T, Compare, Transform>::count(const key_type& key) const { return adobe::count_if(index_m, bound_predicate_t(key, transform_m, compare_m)); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::lower_bound(const key_type& key) { return adobe::lower_bound(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_iterator table_index<Key, T, Compare, Transform>::lower_bound(const key_type& key) const { return adobe::lower_bound(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::iterator table_index<Key, T, Compare, Transform>::upper_bound(const key_type& key) { return adobe::upper_bound(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::const_iterator table_index<Key, T, Compare, Transform>::upper_bound(const key_type& key) const { return adobe::upper_bound(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline std::pair< typename table_index<Key, T, Compare, Transform>::iterator, typename table_index<Key, T, Compare, Transform>::iterator> table_index<Key, T, Compare, Transform>::equal_range(const key_type& key) { return adobe::equal_range(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline std::pair< typename table_index<Key, T, Compare, Transform>::const_iterator, typename table_index<Key, T, Compare, Transform>::const_iterator> table_index<Key, T, Compare, Transform>::equal_range(const key_type& key) const { return adobe::equal_range(index_m, key, compare_m, boost::bind(transform_m, bind(indirect<value_type>(), _1))); } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline typename table_index<Key, T, Compare, Transform>::index_type& table_index<Key, T, Compare, Transform>::index() { return index_m; } /*************************************************************************************************/ template <class Key, class T, class Compare, class Transform> inline const typename table_index<Key, T, Compare, Transform>::index_type& table_index<Key, T, Compare, Transform>::index() const { return index_m; } /*************************************************************************************************/ } // namespace adobe /*************************************************************************************************/ #endif /*************************************************************************************************/

• Company | 
• Online Privacy Policy | 
• Terms of Use | 
• Contact Us | 
• Accessibility | 
• Report Piracy | 
• Permissions & Trademarks | 
• Product License Agreements | 
• Send Feedback

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google