stlab.adobe.com Adobe Systems Incorporated
table_index.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_TABLE_INDEX_HPP
10 #define ADOBE_TABLE_INDEX_HPP
11 
12 /*************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
16 #include <functional>
17 #include <stdexcept>
18 #include <vector>
19 
20 #include <boost/operators.hpp>
21 #include <boost/iterator/indirect_iterator.hpp>
22 #include <boost/iterator/transform_iterator.hpp>
23 #include <boost/next_prior.hpp>
24 #include <boost/type_traits/remove_reference.hpp>
25 
29 #include <adobe/algorithm/sort.hpp>
32 
33 #include <adobe/closed_hash.hpp>
34 #include <adobe/functional.hpp>
35 
36 /*************************************************************************************************/
37 
38 namespace adobe {
39 
40 /*************************************************************************************************/
41 
531 template < typename T, // models Regular
532  typename H = boost::hash<T>, // models UnaryFunction key_type -> size_t
533  typename C = std::equal_to<T>, // models EqualityComparison(key_type, key_type)
534  typename P = identity<T> > // models UnaryFunction T -> key_type
536 {
537  public:
538  typedef T value_type;
539  typedef P key_function_type;
540 
541  typedef typename boost::remove_reference<typename key_function_type::result_type>::type
543 
544  typedef H hasher;
545  typedef C key_equal;
546  typedef value_type* pointer;
547  typedef const value_type* const_pointer;
548  typedef value_type& reference;
549  typedef const value_type& const_reference;
550  typedef std::size_t size_type;
551  typedef std::ptrdiff_t difference_type;
552 
554 
557 
558  typedef boost::indirect_iterator<typename index_type::iterator> iterator;
559  typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator;
560  typedef std::reverse_iterator<iterator> reverse_iterator;
561  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
562 
563  /*
564  REVISIT (sparent@adobe.com) : This is a very limited set of constructors - need to have a
565  general strategy for which constructors to provide.
566  */
567 
568 
570 
571  /*
572  NOTE: The constructor is templatized so things like mem_fun are not necessary.
573  */
574 
575  template <typename F> // F is convertible to key_function_type
576  hash_index(hasher hf, key_equal eq, F kf) :
577  index_m(0, hf, eq, compose(key_function_type(kf), indirect<value_type>()))
578  { }
579 
580  //allocator_type get_allocator() const;
581  size_type max_size() const { return index_m.max_size(); }
582 
583  size_type size() const { return index_m.size(); }
584  bool empty() const { return index_m.empty(); }
585  size_type capacity() const { return index_m.capacity(); }
586 
587  void reserve(size_type n) { index_m.reserve(); }
588 
589  iterator begin() { return iterator(index_m.begin()); }
590  iterator end() { return iterator(index_m.end()); }
591 
592  const_iterator begin() const { return const_iterator(index_m.begin()); }
593  const_iterator end() const { return const_iterator(index_m.end()); }
594 
595  reverse_iterator rbegin() { return reverse_iterator(index_m.rbegin()); }
596  reverse_iterator rend() { return reverse_iterator(index_m.rend()); }
597 
598  const_reverse_iterator rbegin() const { return const_reverse_iterator(index_m.rbegin()); }
599  const_reverse_iterator rend() const { return const_reverse_iterator(index_m.rend()); }
600 
601  std::pair<iterator, bool> insert(value_type& x)
602  {
603  std::pair<typename index_type::iterator, bool> result = index_m.insert(&x);
604  return std::make_pair(iterator(result.first), result.second);
605  }
606 
607  template <typename I>
608  void insert(I f, I l)
609  {
610  index_m.insert( boost::make_transform_iterator(f, pointer_to<value_type>()),
611  boost::make_transform_iterator(l, pointer_to<value_type>()));
612  }
613 
614  iterator insert(iterator i, value_type& x)
615  {
616  return iterator(index_m.insert(i, &x));
617  }
618 
619  iterator erase(iterator i) { return index_m.erase(i.base()); }
620  size_type erase(const key_type& x) { return index_m.erase(x); }
621 
622  void clear() { index_m.clear(); }
623 
624  index_type& index() { return index_m; }
625  const index_type& index() const { return index_m; }
626 
627  iterator find(const key_type& x) { return iterator(index_m.find(x)); }
628  const_iterator find(const key_type& x) const { return const_iterator(index_m.find(x)); }
629  size_type count(const key_type& x) const { return index_m.count(x); }
630 
631  iterator lower_bound(const key_type& x) { return iterator(index_m.lower_bound()); }
632  const_iterator lower_bound(const key_type& x) const
633  { return const_iterator(index_m.lower_bound()); }
634  iterator upper_bound(const key_type& x) { return iterator(index_m.upper_bound()); }
635  const_iterator upper_bound(const key_type& x) const
636  { return const_iterator(index_m.upper_bound()); }
637 
638  std::pair<iterator, iterator> equal_range(const key_type& x)
639  {
640  std::pair<typename index_type::iterator, typename index_type::iterator> result = index_m.equal_range(x);
641  return std::make_pair(iterator(result.first), iterator(result.second));
642  }
643  std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
644  {
645  std::pair<typename index_type::const_iterator, typename index_type::const_iterator> result
646  = index_m.equal_range(x);
647 
648  return std::make_pair(const_iterator(result.first), const_iterator(result.second));
649  }
650 
651  key_function_type key_function() const { return index_m.key_function(); }
652  hasher hash_function() const { return index_m.hash_function(); }
653  key_equal key_eq() const { return index_m.key_eq(); }
654 
655  friend void swap(hash_index& x, hash_index& y)
656  {
657  swap(x.index_m, y.index_m);
658  }
659  private:
660 
661  index_type index_m;
662 };
663 
664 /*************************************************************************************************/
665 
666 template < typename Key, // models Regular
667  typename T, // models Regular
668  typename Transform = mem_data_t<T, const Key>, // models UnaryFunction Key(T)
669  typename Compare = std::less<Key> // models BinaryFunction bool(Key, Key)
670  >
672 {
673 
674  public:
675  typedef typename std::vector<T*> index_type;
676  typedef Transform transform_type;
677 
678  typedef Key key_type;
679  typedef T value_type;
680  typedef Compare key_compare; // Revisit?
681 // typedef Allocator allocator_type;
682  typedef T& reference;
683  typedef const T& const_reference;
686  typedef T* pointer;
687  typedef const T* const_pointer;
688 
689  typedef boost::indirect_iterator<typename index_type::iterator> iterator;
690  typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator;
691  typedef std::reverse_iterator<iterator> reverse_iterator;
692  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
693 
694  template <class TransformPrimitive>
695  explicit table_index(TransformPrimitive transform, const key_compare& compare = key_compare()) :
696  transform_m(transform),
697  compare_m(compare)
698  { }
699  explicit table_index(const transform_type&, const key_compare& = key_compare());
700 
701  template <typename InputIterator, typename TransformPrimitive>
702  table_index( InputIterator first,
703  InputIterator last,
704  TransformPrimitive transform,
705  const key_compare& compare = key_compare()) :
706  transform_m(transform),
707  compare_m(compare)
708  {
709  insert(begin(), first, last);
710  }
711 
712  //allocator_type get_allocator() const;
713  size_type max_size() const;
714 
715  size_type size() const;
716  bool empty() const;
717 
718  iterator begin();
719  const_iterator begin() const;
720  iterator end();
721  const_iterator end() const;
722 
723  reverse_iterator rbegin();
724  const_reverse_iterator rbegin() const;
725  reverse_iterator rend();
726  const_reverse_iterator rend() const;
727 
728  const_reference at(size_type n) const;
729  reference at(size_type n);
730 
731  reference front();
732  const_reference front() const;
733  reference back();
734  const_reference back() const;
735 
736  void push_back(value_type&);
737  void pop_back();
738 
739  iterator insert(iterator, value_type&);
740  template <class InputIterator>
741  void insert(iterator position, InputIterator first, InputIterator last);
742 
743  iterator erase(iterator location);
744  iterator erase(iterator first, iterator last);
745  void clear();
746 
747  index_type& index();
748  const index_type& index() const;
749 
750  /*
751  REVISIT (sparent) : If we wanted to allow sort() and unique() - and other algoriths to
752  operate directly on the index rather than being built in, what would be required of the
753  index interface?
754  */
755 
756  void sort();
757 
758  // Operations on a sorted index.
759 
760  void unique();
761 
762  reference operator[](const key_type&);
763  const_reference operator[](const key_type&) const;
764 
765  iterator find(const key_type& x);
766  const_iterator find(const key_type& x) const;
767  size_type count(const key_type& x) const;
768 
769  iterator lower_bound(const key_type& x);
770  const_iterator lower_bound(const key_type& x) const;
771  iterator upper_bound(const key_type& x);
772  const_iterator upper_bound(const key_type& x) const;
773 
774  std::pair<iterator, iterator> equal_range(const key_type& x);
775  std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
776 
777  transform_type transform() const { return transform_m; }
778 
779  friend void swap(table_index& x, table_index& y)
780  {
781  swap(x.transform_m, y.transform_m);
782  swap(x.compare_m, y.compare_m);
783  swap(x.index_m, y.index_m);
784  }
785  private:
786 
787 #ifndef ADOBE_NO_DOCUMENTATION
788  struct indirect_compare_t : std::binary_function<pointer, pointer, bool>
789  {
790  typedef bool result_type;
791 
792  indirect_compare_t(transform_type& transform, const key_compare& compare) :
793  transform_m(transform),
794  compare_m(compare)
795  { }
796 
797  bool operator () (pointer x, pointer y) const
798  {
799  return compare_m(transform_m(*x), transform_m(*y));
800  }
801 
802  private:
803  transform_type transform_m; /* REVISIT (sparent) : want reference here? */
804  key_compare compare_m;
805  };
806 
807 #endif
808 
809  transform_type transform_m;
810  key_compare compare_m;
811  index_type index_m;
812 };
813 
814 /*************************************************************************************************/
815 
816 template <class Key, class T, class Compare, class Transform>
818  const key_compare& compare) :
819  transform_m(transform),
820  compare_m(compare)
821 { }
822 
823 /*************************************************************************************************/
824 
825 template <class Key, class T, class Compare, class Transform>
828 {
829  return iterator(index_m.begin());
830 }
831 
832 /*************************************************************************************************/
833 
834 template <class Key, class T, class Compare, class Transform>
837 {
838  return const_iterator(index_m.begin());
839 }
840 
841 /*************************************************************************************************/
842 
843 template <class Key, class T, class Compare, class Transform>
846 {
847  return iterator(index_m.end());
848 }
849 
850 /*************************************************************************************************/
851 
852 template <class Key, class T, class Compare, class Transform>
855 {
856  return const_iterator(index_m.end());
857 }
858 
859 /*************************************************************************************************/
860 
861 template <class Key, class T, class Compare, class Transform>
864 {
865  return reverse_iterator(index_m.rbegin());
866 }
867 
868 /*************************************************************************************************/
869 
870 template <class Key, class T, class Compare, class Transform>
873 {
874  return const_reverse_iterator(index_m.rbegin());
875 }
876 
877 /*************************************************************************************************/
878 
879 template <class Key, class T, class Compare, class Transform>
882 {
883  return reverse_iterator(index_m.rend());
884 }
885 
886 /*************************************************************************************************/
887 
888 template <class Key, class T, class Compare, class Transform>
891 {
892  return reverse_iterator(index_m.rend());
893 }
894 
895 /*************************************************************************************************/
896 
897 template <class Key, class T, class Compare, class Transform>
900 {
901  return index_m.max_size();
902 }
903 
904 /*************************************************************************************************/
905 
906 template <class Key, class T, class Compare, class Transform>
909 {
910  return index_m.size();
911 }
912 
913 /*************************************************************************************************/
914 
915 template <class Key, class T, class Compare, class Transform>
917 {
918  return index_m.empty();
919 }
920 
921 /*************************************************************************************************/
922 
923 template <class Key, class T, class Compare, class Transform>
925 {
926  index_m.push_back(&x);
927 }
928 
929 /*************************************************************************************************/
930 
931 template <class Key, class T, class Compare, class Transform>
933 {
934  index_m.pop_back();
935 }
936 
937 /*************************************************************************************************/
938 
939 template <class Key, class T, class Compare, class Transform>
941  table_index<Key, T, Compare, Transform>::insert(iterator position, value_type& x)
942 {
943  return index_m.insert(position, &x);
944 }
945 
946 /*************************************************************************************************/
947 
948 /*
949  REVISIT (sparent) : We should be able to greatly improve the table_index class - this function
950  in particular could be much more efficient.
951 */
952 
953 template <class Key, class T, class Compare, class Transform>
954 template <class InputIterator>
955 inline void table_index<Key, T, Compare, Transform>::insert(iterator position, InputIterator first, InputIterator last)
956 {
957  typename index_type::iterator iter = position.base();
958 
959  while (first != last) {
960  iter = index_m.insert(iter, &*first);
961  ++iter;
962  ++first;
963  }
964 }
965 
966 /*************************************************************************************************/
967 
968 template <class Key, class T, class Compare, class Transform>
971 {
972  return index_m.erase(position.base());
973 }
974 
975 /*************************************************************************************************/
976 
977 template <class Key, class T, class Compare, class Transform>
979  table_index<Key, T, Compare, Transform>::erase(iterator first, iterator last)
980 {
981  return index_m.erase(first.base(), last.base());
982 }
983 
984 /*************************************************************************************************/
985 
986 template <class Key, class T, class Compare, class Transform>
988 {
989  index_m.clear();
990 }
991 
992 /*************************************************************************************************/
993 
994 template <class Key, class T, class Compare, class Transform>
996 {
997  adobe::sort(index_m, indirect_compare_t(transform_m, compare_m));
998 }
999 
1000 /*************************************************************************************************/
1001 
1002 template <class Key, class T, class Compare, class Transform>
1004 {
1005  typename index_type::iterator i (adobe::unique(index_m, indirect_compare_t(transform_m, compare_m)));
1006  index_m.erase(i, index_m.end());
1007 }
1008 
1009 /*************************************************************************************************/
1010 
1011 template <class Key, class T, class Compare, class Transform>
1014 {
1015  return *index_m.at(n);
1016 }
1017 
1018 /*************************************************************************************************/
1019 
1020 template <class Key, class T, class Compare, class Transform>
1023 {
1024  return *index_m.at(n);
1025 }
1026 
1027 /*************************************************************************************************/
1028 
1029 template <class Key, class T, class Compare, class Transform>
1032 {
1033  iterator iter (find(key));
1034 
1035  if (iter == end())
1036  throw std::range_error("Key not present in table.");
1037 
1038  return *iter;
1039 }
1040 
1041 /*************************************************************************************************/
1042 
1043 template <class Key, class T, class Compare, class Transform>
1046 {
1047  const_iterator iter(find(key));
1048 
1049  if (iter == end())
1050  throw std::range_error("Key not present in table.");
1051 
1052  return *iter;
1053 }
1054 
1055 /*************************************************************************************************/
1056 
1057 template <class Key, class T, class Compare, class Transform>
1060 {
1061  typename index_type::iterator iter = lower_bound(key).base();
1062 
1063  if (iter != index_m.end() && transform_m(**iter) != key)
1064  iter = index_m.end();
1065 
1066  return iter;
1067 }
1068 
1069 /*************************************************************************************************/
1070 
1071 template <class Key, class T, class Compare, class Transform>
1074 {
1075  typename index_type::const_iterator iter = lower_bound(key).base();
1076 
1077  if (iter != index_m.end() && transform_m(**iter) != key)
1078  iter = index_m.end();
1079 
1080  return iter;
1081 }
1082 
1083 /*************************************************************************************************/
1084 
1085 template <class Key, class T, class Compare, class Transform>
1088 {
1089  return adobe::count_if(index_m, bound_predicate_t(key, transform_m, compare_m));
1090 }
1091 
1092 /*************************************************************************************************/
1093 
1094 template <class Key, class T, class Compare, class Transform>
1097 {
1098  return adobe::lower_bound(index_m, key, compare_m,
1099  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1100 }
1101 
1102 /*************************************************************************************************/
1103 
1104 template <class Key, class T, class Compare, class Transform>
1107 {
1108  return adobe::lower_bound(index_m, key, compare_m,
1109  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1110 }
1111 
1112 /*************************************************************************************************/
1113 
1114 template <class Key, class T, class Compare, class Transform>
1117 {
1118  return adobe::upper_bound(index_m, key, compare_m,
1119  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1120 }
1121 
1122 /*************************************************************************************************/
1123 
1124 template <class Key, class T, class Compare, class Transform>
1127 {
1128  return adobe::upper_bound(index_m, key, compare_m,
1129  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1130 }
1131 
1132 /*************************************************************************************************/
1133 
1134 template <class Key, class T, class Compare, class Transform>
1135 inline std::pair< typename table_index<Key, T, Compare, Transform>::iterator,
1138 {
1139  return adobe::equal_range(index_m, key, compare_m,
1140  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1141 }
1142 
1143 /*************************************************************************************************/
1144 
1145 template <class Key, class T, class Compare, class Transform>
1146 inline std::pair< typename table_index<Key, T, Compare, Transform>::const_iterator,
1149 {
1150  return adobe::equal_range(index_m, key, compare_m,
1151  boost::bind(transform_m, bind(indirect<value_type>(), _1)));
1152 }
1153 
1154 /*************************************************************************************************/
1155 
1156 template <class Key, class T, class Compare, class Transform>
1159 {
1160  return index_m;
1161 }
1162 
1163 /*************************************************************************************************/
1164 
1165 template <class Key, class T, class Compare, class Transform>
1168 {
1169  return index_m;
1170 }
1171 
1172 /*************************************************************************************************/
1173 
1174 } // namespace adobe
1175 
1176 /*************************************************************************************************/
1177 
1178 #endif
1179 
1180 /*************************************************************************************************/
iterator insert(iterator i, value_type &x)
const value_type & const_reference
boost::range_iterator< ForwardRange >::type unique(ForwardRange &range)
unique implementation
Definition: unique.hpp:40
unary_compose< key_function_type, indirect< value_type > > indirect_key_function_type
std::ptrdiff_t difference_type
index_type & index()
iterator find(const key_type &x)
table_index(InputIterator first, InputIterator last, TransformPrimitive transform, const key_compare &compare=key_compare())
index_type::difference_type difference_type
void reserve(size_type n)
unary_compose< F, G > compose(F f, G g)
Definition: functional.hpp:188
std::vector< T * > index_type
reverse_iterator rend()
reverse_iterator rbegin()
size_type capacity() const
Adaptor similar to boost::mem_fn() used by boost::bind.
Definition: functional.hpp:393
std::pair< iterator, iterator > equal_range(const key_type &x)
boost::indirect_iterator< typename index_type::const_iterator > const_iterator
key_equal key_eq() const
table_index(TransformPrimitive transform, const key_compare &compare=key_compare())
const_iterator find(const key_type &x) const
I lower_bound(I f, I l, const T &x)
iterator lower_bound(const key_type &x)
reverse_iterator rbegin()
reference operator[](const key_type &)
std::pair< iterator, bool > insert(value_type &x)
bool empty() const
value_type * pointer
index_type::size_type size_type
void insert(I f, I l)
const index_type & index() const
iterator erase(iterator location)
transform_type transform() const
iterator lower_bound(const key_type &x)
std::size_t count(const key_type &key) const
poly_base< poly_iterator_interface< V, R, D >, poly_iterator_instance< V, R, D >::template type > base
size_type capacity() const
const_iterator begin() const
size_type count(const key_type &x) const
iterator erase(iterator i)
key_function_type key_function() const
iterator upper_bound(const key_type &x)
iterator find(const key_type &x)
const_iterator lower_bound(const key_type &x) const
key_transform key_function() const
std::reverse_iterator< const_iterator > const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
size_type count(const key_type &x) const
std::reverse_iterator< iterator > reverse_iterator
const_iterator upper_bound(const key_type &x) const
const_iterator end() const
void sort(RandomAccessRange &range)
sort implementation
Definition: sort.hpp:41
void reserve(size_type n)
size_type max_size() const
size_type max_size() const
size_type max_size() const
friend void swap(hash_index &x, hash_index &y)
boost::indirect_iterator< typename index_type::const_iterator > const_iterator
reverse_iterator rend()
index_type & index()
size_type size() const
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
void push_back(array_t &v, T x)
Definition: array.hpp:28
bool empty() const
reverse_iterator rend()
std::reverse_iterator< iterator > reverse_iterator
boost::indirect_iterator< typename index_type::iterator > iterator
boost::indirect_iterator< typename index_type::iterator > iterator
Utility class for indexing objects based on specific member variable values.
hash_index(hasher hf, key_equal eq, F kf)
size_type size() const
const_iterator find(const key_type &key) const
const T & const_reference
std::pair< I, I > equal_range(I f, I l, const T &x)
boost::remove_reference< typename key_function_type::result_type >::type key_type
std::pair< const_iterator, const_iterator > equal_range(const key_type &x) const
size_type erase(const key_type &x)
void insert(I first, I last)
iterator erase(iterator location)
key_equal key_eq() const
std::iterator_traits< InputIterator >::difference_type count_if(InputIterator first, InputIterator last, Predicate pred)
count implementation
Definition: count.hpp:65
const T * const_pointer
const_reverse_iterator rend() const
const_reference at(size_type n) const
iterator insert(iterator, value_type &)
const_reverse_iterator rbegin() const
std::pair< iterator, iterator > equal_range(const key_type &x)
const value_type * const_pointer
void push_back(value_type &)
iterator upper_bound(const key_type &x)
std::size_t size_type
value_type & reference
reverse_iterator rbegin()
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op)
transform implementation
Definition: transform.hpp:39
pair< T1, T2 > make_pair(T1 x, T2 y)
Definition: pair.hpp:109
closed_hash_set< pointer, indirect_key_function_type, hasher, key_equal > index_type
friend void swap(table_index &x, table_index &y)
I upper_bound(I f, I l, const T &x)
hasher hash_function() const
size_type size() const
Transform transform_type
hasher hash_function() const

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