cprover
sorted_vector.h
Go to the documentation of this file.
1 /* STL-conforming "sorted vector" container
2  *
3  * (C) 2002 Martin Holzherr (holzherr@infobrain.com). All rights reserved.
4  *
5  * Permission is granted to use, distribute and modify this code provided that:
6  * · this copyright notice appears,
7  * ·
8  * The author welcomes any suggestions on the code or reportings of actual
9  * use of the code. Please send your comments to holzherr@infobrain.com.
10  *
11  * The author makes NO WARRANTY or representation, either express or implied,
12  * with respect to this code, its quality, accuracy, merchantability, or
13  * fitness for a particular purpose. This software is provided "AS IS", and
14  * you, its user, assume the entire risk as to its quality and accuracy.
15  *
16  * Created: November 19th, 2002
17  * Last modified: November 27th, 2002
18  (changed namespace from std to codeproject;
19  uses template member functions for MSCVER>=1300)
20 
21  */
22 
23 #ifndef CPROVER_UTIL_SORTED_VECTOR_H
24 #define CPROVER_UTIL_SORTED_VECTOR_H
25 #define VERSION_SORTED_VECTOR_ 0x00010010
26 
27 #include <algorithm>
28 #include <vector>
29 #include <utility>
30 #include <functional>
31 
32 //#pragma pack(push,8)
33 //#pragma warning(push,3)
34 
35 template<
36  class K,
37  bool bNoDuplicates= false,
38  class Pr = std::less<K>,
39  class A = std::allocator<K> >
41 {
42 public:
44  typedef typename std::vector<K, A> Cont;
45  typedef typename Cont::allocator_type allocator_type;
46  typedef typename Cont::size_type size_type;
47  typedef typename Cont::difference_type difference_type;
48  typedef typename Cont::reference reference;
49  typedef typename Cont::const_reference const_reference;
50  typedef typename Cont::value_type value_type;
51  typedef K key_type;
52  typedef typename Cont::iterator iterator;
53  typedef typename Cont::const_iterator const_iterator;
54  typedef Pr key_compare;
55  typedef Pr value_compare;
56 
57  typedef typename Cont::const_reverse_iterator const_reverse_iterator;
58  typedef typename Cont::reverse_iterator reverse_iterator;
59 
60  typedef std::pair<iterator, iterator> Pairii_;
61  typedef std::pair<const_iterator, const_iterator> Paircc_;
62 
63  typedef std::pair<iterator, bool> Pairib_;
64  explicit sorted_vector(const Pr& pred = Pr(),const A& al = A())
65  :key_compare_(pred),vec_(al){}
66 
67 #if (_MSC_VER >= 1300)
68  template<class It>
69  sorted_vector(It first, It beyond,
70  const Pr& pred = Pr(),const A& al = A())
71  :key_compare_(pred),vec_(first,beyond,al)
72  {stable_sort();}
73 #else
75  const Pr& pred = Pr(),const A& al = A())
76  :key_compare_(pred),vec_(first,beyond,al)
77  {stable_sort();}
78 #endif
79  explicit sorted_vector(const Myt_& x)
81  {}
83  Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_);
85  return *this;}
86  Myt_& operator=(const Cont& x){vec_.operator=(x);
87  sort();return *this;}
88 
89  void reserve(size_type n) {vec_.reserve(n);}
90  iterator begin() {return vec_.begin(); }
91  const_iterator begin() const {return vec_.begin(); }
92  iterator end() {return vec_.end();}
93  const_iterator end() const {return vec_.end();}
94  reverse_iterator rbegin() {return vec_.rbegin();}
96  {return vec_.rbegin();}
97 
98  reverse_iterator rend() {return vec_.rend();}
100  {return vec_.rend();}
101 
102 
103  size_type size() const {return vec_.size();}
104  size_type max_size() const {return vec_.max_size();}
105  bool empty() const {return vec_.empty();}
106  A get_allocator() const {return vec_.get_allocator();}
107  const_reference at(size_type p) const {return vec_.at(p);}
108  reference at(size_type p) {return vec_.at(p);}
110  {return vec_.operator[](p);}
111 
112  reference operator[](size_type p) {return vec_.operator[](p);}
113  reference front() {return vec_.front();}
114  const_reference front() const {return vec_.front();}
115  reference back() {return vec_.back();}
116  const_reference back() const {return vec_.back();}
117  void pop_back() {vec_.pop_back();}
118 
120  {vec_.assign(first,beyond);}
121  void assign(size_type n, const K& x = K())
122  {vec_.assign(n,x);}
123 /*insert members*/
125  {
126  if(bNoDuplicates){
127  iterator p= lower_bound(x);
128  if(p==end()||key_compare_(x,*p)){
129  return Pairib_(InsertImpl_(p,x),true);
130  }else{
131  return Pairib_(p,false);
132  }
133  }else{
134  iterator p= upper_bound(x);
135  return Pairib_(InsertImpl_(p,x),true);
136  }
137  }
138  iterator insert(iterator it, const value_type& x)//it is the hint
139  {
140  if(it!=end() ){
141  if(bNoDuplicates){
142  if(key_compare_(*it,x)){
143  if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint
144  return InsertImpl_(it+1,x);
145  }else if(KeyCompare_Geq_(*(it+1),x)){
146  return end();
147  }
148  }
149  }else{
150  if( KeyCompare_Leq_(*it,x)
151  &&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){
152  return InsertImpl_(it+1,x);
153  }
154  }
155  }
156  return insert(x).first;
157  }
158 #if (_MSC_VER >= 1300)
159  template<class It>
160  void insert(It first, It beyond)
161  {
162  size_type n= std::distance(first,beyond);
163  reserve(size()+n);
164  for( ;first!=beyond;++first){
165  insert(*first);
166  }
167  }
168 #else
170  {
171  size_type n= std::distance(first,beyond);
172  reserve(size()+n);
173  for( ;first!=beyond;++first){
174  insert(*first);
175  }
176  }
177 #endif
178  iterator erase(iterator p) {return vec_.erase(p);}
180  {return vec_.erase(first,beyond);}
181  size_type erase(const K& key)
182  {
183  Pairii_ begEnd= equal_range(key);
184  size_type n= std::distance(begEnd.first,begEnd.second);
185  erase(begEnd.first,begEnd.second);
186  return n;
187  }
188  void clear() {return vec_.clear();}
189 
190  bool Eq_(const Myt_& x) const
191  {return (size() == x.size()
192  && std::equal(begin(), end(), x.begin())); }
193  bool Lt_(const Myt_& x) const
194  {return (std::lexicographical_compare(begin(), end(),
195  x.begin(), x.end()));}
196  void swap(Myt_& x)
197  {vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);}
198 
199  friend void swap(Myt_& x, Myt_& Y_)
200  {x.swap(Y_); }
201 
202  key_compare key_comp() const {return key_compare_; }
203  value_compare value_comp() const {return (key_comp()); }
204  iterator find(const K& k)
205  { iterator p = lower_bound(k);
206  return (p==end()||key_compare_(k, *p))? end():p;
207  }
208  const_iterator find(const K& k) const
209  {const_iterator p = lower_bound(k);
210  return (p==end()||key_compare_(k,*p))?end():p;}
211  size_type count(const K& k) const
212  {Paircc_ Ans_ = equal_range(k);
213  size_type n = std::distance(Ans_.first, Ans_.second);
214  return (n); }
215  iterator lower_bound(const K& k)
216  {return std::lower_bound(begin(), end(), k, key_compare_); }
217  const_iterator lower_bound(const K& k) const
218  {return std::lower_bound(begin(), end(), k, key_compare_); }
219  iterator upper_bound(const K& k)
220  {return std::upper_bound(begin(), end(), k, key_compare_); }
221  const_iterator upper_bound(const K& k) const
222  {return std::upper_bound(begin(), end(), k, key_compare_); }
223  Pairii_ equal_range(const K& k)
224  {return std::equal_range(begin(), end(), k, key_compare_); }
225  Paircc_ equal_range(const K& k) const
226  {return std::equal_range(begin(), end(), k, key_compare_); }
227 
228 /*functions for use with direct std::vector-access*/
230  {return vec_;}
231  void sort()//restore sorted order after low level access
232  { std::sort(vec_.begin(),vec_.end(),key_compare_);
233  if( bNoDuplicates ){
234  vec_.erase(Unique_(),vec_.end());
235  }
236  }
237  void stable_sort()//restore sorted order after low level access
238  { std::stable_sort(vec_.begin(),vec_.end(),key_compare_);
239  if( bNoDuplicates ){
240  erase(Unique_(),end());
241  }
242  }
243 
244 protected:
246  {
247  iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end();
248  bool bCopy_= false;
249  for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){
250  if( key_compare_(*prev_,*front_)){
251  if(bCopy_){
252  *out_= *front_;
253  out_++;
254  }
255  }else{
256  if(!bCopy_){out_=front_;bCopy_=true;}
257  }
258  }
259  return out_;
260  }
262  {return vec_.insert(p,x);}
263  bool KeyCompare_Leq_(const K& ty0,const K& ty1)
264  {return !key_compare_(ty1,ty0);}
265  bool KeyCompare_Geq_(const K& ty0,const K& ty1)
266  {return !key_compare_(ty0,ty1);}
267  bool KeyCompare_Gt_(const K& ty0,const K& ty1)
268  {return key_compare_(ty1,ty0);}
269 
272 };
273 
274 
275 template<class K,bool bNoDuplicates,class Pr, class A> inline
278  {return x.Eq_(Y_); }
279 template<class K,bool bNoDuplicates,class Pr, class A> inline
282  {return !(x == Y_); }
283 template<class K,bool bNoDuplicates,class Pr, class A> inline
284  bool operator<(const sorted_vector<K, bNoDuplicates,Pr,A>& x,
286  {return x.Lt_(Y_);}
287 template<class K,bool bNoDuplicates,class Pr,class A> inline
290  {return Y_ < x; }
291 template<class K,bool bNoDuplicates,class Pr, class A> inline
292  bool operator<=(const sorted_vector<K, bNoDuplicates,Pr,A>& x,
294  {return !(Y_ < x); }
295 template<class K, bool bNoDuplicates,class Pr,class A> inline
298  {return (!(x < Y_)); }
299 
300 //#pragma warning(pop)
301 //#pragma pack(pop)
302 #elif VERSION_SORTED_VECTOR_ != 0x00010010
303 #error You have included two sorted_vector.h with different version numbers
304 #endif // CPROVER_UTIL_SORTED_VECTOR_H
const_reference front() const
const_iterator upper_bound(const K &k) const
value_compare value_comp() const
bool Eq_(const Myt_ &x) const
sorted_vector(const Pr &pred=Pr(), const A &al=A())
Definition: sorted_vector.h:64
sorted_vector< K, bNoDuplicates, Pr, A > Myt_
Definition: sorted_vector.h:43
bool operator>(const sorted_vector< K, bNoDuplicates, Pr, A > &x, const sorted_vector< K, bNoDuplicates, Pr, A > &Y_)
size_type erase(const K &key)
iterator InsertImpl_(iterator p, const value_type &x)
iterator begin()
Definition: sorted_vector.h:90
bool KeyCompare_Geq_(const K &ty0, const K &ty1)
const_reference operator[](size_type p) const
Pairii_ equal_range(const K &k)
const_reverse_iterator rend() const
Definition: sorted_vector.h:99
reference operator[](size_type p)
const_iterator find(const K &k) const
sorted_vector(const_iterator first, const_iterator beyond, const Pr &pred=Pr(), const A &al=A())
Definition: sorted_vector.h:74
Cont::size_type size_type
Definition: sorted_vector.h:46
unsignedbv_typet size_type()
Definition: c_types.cpp:57
std::pair< iterator, bool > Pairib_
Definition: sorted_vector.h:63
key_compare key_comp() const
key_compare key_compare_
Cont::const_reference const_reference
Definition: sorted_vector.h:49
iterator Unique_()
Cont::const_reverse_iterator const_reverse_iterator
Definition: sorted_vector.h:57
reference front()
A get_allocator() const
const_reverse_iterator rbegin() const
Definition: sorted_vector.h:95
void insert(const_iterator first, const_iterator beyond)
Myt_ & operator=(const Myt_ &x)
Definition: sorted_vector.h:83
size_type size() const
Cont::const_iterator const_iterator
Definition: sorted_vector.h:53
const_reference back() const
iterator end()
Definition: sorted_vector.h:92
reverse_iterator rbegin()
Definition: sorted_vector.h:94
void assign(size_type n, const K &x=K())
Cont::iterator iterator
Definition: sorted_vector.h:52
void reserve(size_type n)
Definition: sorted_vector.h:89
size_type count(const K &k) const
std::pair< const_iterator, const_iterator > Paircc_
Definition: sorted_vector.h:61
Cont::value_type value_type
Definition: sorted_vector.h:50
Paircc_ equal_range(const K &k) const
Myt_ & operator=(const Cont &x)
Definition: sorted_vector.h:86
std::vector< K, A > Cont
Definition: sorted_vector.h:44
Cont & get_container()
reference at(size_type p)
iterator lower_bound(const K &k)
iterator find(const K &k)
void swap(Myt_ &x)
iterator erase(iterator p)
Pairib_ insert(const value_type &x)
iterator upper_bound(const K &k)
friend void swap(Myt_ &x, Myt_ &Y_)
Cont::difference_type difference_type
Definition: sorted_vector.h:47
bool KeyCompare_Gt_(const K &ty0, const K &ty1)
reference back()
const_iterator lower_bound(const K &k) const
iterator insert(iterator it, const value_type &x)
iterator erase(iterator first, iterator beyond)
Cont::allocator_type allocator_type
Definition: sorted_vector.h:45
size_type max_size() const
reverse_iterator rend()
Definition: sorted_vector.h:98
const_iterator end() const
Definition: sorted_vector.h:93
sorted_vector(const Myt_ &x)
Definition: sorted_vector.h:79
bool KeyCompare_Leq_(const K &ty0, const K &ty1)
void assign(const_iterator first, const_iterator beyond)
Cont::reverse_iterator reverse_iterator
Definition: sorted_vector.h:58
void stable_sort()
bool operator==(const sorted_vector< K, bNoDuplicates, Pr, A > &x, const sorted_vector< K, bNoDuplicates, Pr, A > &Y_)
std::pair< iterator, iterator > Pairii_
Definition: sorted_vector.h:60
const_reference at(size_type p) const
const_iterator begin() const
Definition: sorted_vector.h:91
bool empty() const
Cont::reference reference
Definition: sorted_vector.h:48
bool operator>=(const sorted_vector< K, bNoDuplicates, Pr, A > &x, const sorted_vector< K, bNoDuplicates, Pr, A > &Y_)
bool operator!=(const sorted_vector< K, bNoDuplicates, Pr, A > &x, const sorted_vector< K, bNoDuplicates, Pr, A > &Y_)
bool Lt_(const Myt_ &x) const