FIM environment: set_difference.hpp Source File

00001 /*
00002  * set_difference.hpp
00003  *
00004  * Time-stamp: <05/05/18 17:33:17 lars>
00005  *
00006  */
00007 
00008 #ifndef __SET_DIFFERENCE__
00009 #define __SET_DIFFERENCE__ t
00010 
00011 #include "common/debug.hpp"
00012 
00034 template <class InputIterator1, class InputIterator2, class OutputIterator>
00035 inline 
00036 void set_difference_fast(InputIterator1& xiter, const InputIterator1& xend,
00037                          InputIterator2& yiter, const InputIterator2& yend,
00038                          OutputIterator& resultIter) {
00039   // 1. initialize loop
00040   int itemx = *xiter;
00041   int itemy = *yiter;
00042 
00043   // 2. loop over all elements
00044   while (true) {
00045     if (itemx < itemy) {
00046       *resultIter++ = itemx; 
00047       ++xiter; if (xiter == xend) return;
00048       itemx = *xiter;
00049     } else if (itemx > itemy) {
00050       ++yiter; if (yiter == yend) break;
00051       itemy = *yiter;
00052     } else { // if (itemx == itemy) {
00053       ++xiter; if (xiter == xend) return;
00054       ++yiter; if (yiter == yend) break;
00055       itemx = *xiter;
00056       itemy = *yiter;
00057     }
00058   }
00059   // 3. copy remaining items of x:
00060   for ( ; xiter != xend; ++xiter)
00061     *resultIter++ = *xiter;
00062 }
00063 
00064 
00079 template <class InputIterator1, class InputIterator2, class OutputIterator>
00080 inline 
00081 bool set_difference_upper_size_bound(InputIterator1& xiter, const InputIterator1& xend,
00082                                      InputIterator2& yiter, const InputIterator2& yend,
00083                                      OutputIterator& resultIter, const int upperSizeBound) {
00084   assert(upperSizeBound >= 0);
00085   assert(upperSizeBound <= xend-xiter);
00086 
00087   // 1. initialize loop
00088   OutputIterator resultEnd = resultIter + upperSizeBound;
00089   int itemx = *xiter;
00090   int itemy = *yiter;
00091 
00092   // 2. loop over all elements
00093   while (true) {
00094     if (itemx < itemy) {
00095       if (resultIter == resultEnd) return false; // EARLY_FILTERING
00096       *resultIter++ = itemx; 
00097       ++xiter; if (xiter == xend) return true; 
00098       itemx = *xiter;
00099     } else if (itemx > itemy) {
00100       ++yiter; if (yiter == yend) break;
00101       itemy = *yiter;
00102     } else { // if (itemx == itemy) {
00103       ++xiter; if (xiter == xend) return true; 
00104       ++yiter; if (yiter == yend) break;
00105       itemx = *xiter;
00106       itemy = *yiter;
00107     }
00108   }
00109   // 3. copy remaining items of x:
00110   if (resultIter + (xend - xiter) > resultEnd) 
00111     return false; // EARLY_FILTERING
00112   for ( ; xiter != xend; ++xiter) 
00113     *resultIter++ = *xiter;
00114 
00115   return true;
00116 }
00117 
00132 template <class InputIterator1, class InputIterator2, class OutputIterator>
00133 inline 
00134 bool set_difference_lower_size_bound(InputIterator1& xiter, InputIterator1& xend,
00135                                      InputIterator2& yiter, const InputIterator2& yend,
00136                                      OutputIterator& resultIter, const int lowerSizeBound) {
00137   assert(lowerSizeBound >= 2);
00138   assert(lowerSizeBound <= xend-xiter);
00139 
00140   // 1. initialize loop
00141   OutputIterator resultLowerBound = resultIter + lowerSizeBound - 1;
00142   xend -= lowerSizeBound - 1;
00143   int itemx = *xiter;
00144   int itemy = *yiter;
00145 
00146   // 2. loop over all elements
00147   while (true) {
00148     if (itemx < itemy) {
00149       if (resultIter < resultLowerBound)
00150         ++xend;
00151       *resultIter++ = itemx; 
00152       ++xiter; if (xiter == xend) return resultIter > resultLowerBound;
00153       itemx = *xiter;
00154     } else if (itemx > itemy) {
00155       ++yiter; if (yiter == yend) break;
00156       itemy = *yiter;
00157     } else { // if (itemx == itemy) {
00158       ++xiter; if (xiter == xend) return resultIter > resultLowerBound;
00159       ++yiter; if (yiter == yend) break;
00160       itemx = *xiter;
00161       itemy = *yiter;
00162     }
00163   }
00164   // 3. copy remaining items of x:
00165   if (resultIter < resultLowerBound) 
00166     xend += resultLowerBound - resultIter;
00167   for ( ; xiter != xend; ++xiter) 
00168     *resultIter++ = *xiter;
00169 
00170   return true;
00171 }
00172 
00173 
00185 template <class InputIterator1, class InputIterator2>
00186 inline 
00187 int size_of_set_difference(InputIterator1& xiter, const InputIterator1& xend,
00188                            InputIterator2& yiter, const InputIterator2& yend) {
00189   // 1. initialize loop
00190   int itemx = *xiter;
00191   int itemy = *yiter;
00192   int resultSize = 0;
00193 
00194   // 2. loop over all elements
00195   while (true) {
00196     if (itemx < itemy) {
00197       resultSize++;
00198       ++xiter; if (xiter == xend) return resultSize;
00199       itemx = *xiter;
00200     } else if (itemx > itemy) {
00201       ++yiter; if (yiter == yend) break;
00202       itemy = *yiter;
00203     } else { // if (itemx == itemy) {
00204       ++xiter; if (xiter == xend) return resultSize;
00205       ++yiter; if (yiter == yend) break;
00206       itemx = *xiter;
00207       itemy = *yiter;
00208     }
00209   }
00210   // 3. copy remaining items of x:
00211   resultSize += xend - xiter;
00212 
00213   return resultSize;
00214 }
00215 
00216 
00230 template <class InputIterator1, class InputIterator2>
00231 inline 
00232 int size_of_set_difference_upper_size_bound(InputIterator1& xiter, const InputIterator1& xend,
00233                                             InputIterator2& yiter, const InputIterator2& yend, 
00234                                             int upperSizeBound) {
00235   // 1. initialize loop
00236   int itemx = *xiter;
00237   int itemy = *yiter;
00238   int resultSize = 0;
00239 
00240   // 2. loop over all elements
00241   while (true) {
00242     if (itemx < itemy) {
00243       if (resultSize == upperSizeBound) return upperSizeBound+1; // EARLY_FILTERING
00244       resultSize++;
00245       ++xiter; if (xiter == xend) return resultSize;
00246       itemx = *xiter;
00247     } else if (itemx > itemy) {
00248       ++yiter; if (yiter == yend) break;
00249       itemy = *yiter;
00250     } else { // if (itemx == itemy) {
00251       ++xiter; if (xiter == xend) return resultSize;
00252       ++yiter; if (yiter == yend) break;
00253       itemx = *xiter;
00254       itemy = *yiter;
00255     }
00256   }
00257   // 3. copy remaining items of x:
00258   resultSize += xend - xiter;
00259   if (resultSize > upperSizeBound)
00260     resultSize = upperSizeBound+1;
00261 
00262   return resultSize;
00263 }
00264 
00278 template <class InputIterator1, class InputIterator2>
00279 inline 
00280 int size_of_set_difference_lower_size_bound(InputIterator1& xiter, InputIterator1& xend,
00281                                             InputIterator2& yiter, const InputIterator2& yend,
00282                                             const int lowerSizeBound) {
00283   assert(lowerSizeBound >= 2);
00284   assert(lowerSizeBound <= xend-xiter);
00285 
00286   // 1. initialize loop
00287   int resultSize = 0;
00288   const int resultLowerBound = lowerSizeBound - 1;
00289   xend -= lowerSizeBound - 1;
00290   int itemx = *xiter;
00291   int itemy = *yiter;
00292 
00293   // 2. loop over all elements
00294   while (true) {
00295     if (itemx < itemy) {
00296       if (resultSize < resultLowerBound)
00297         ++xend;
00298       resultSize++;
00299       ++xiter; if (xiter == xend) return resultSize > lowerSizeBound ? resultSize : 0;
00300       itemx = *xiter;
00301     } else if (itemx > itemy) {
00302       ++yiter; if (yiter == yend) break;
00303       itemy = *yiter;
00304     } else { // if (itemx == itemy) {
00305       ++xiter; if (xiter == xend) return resultSize > lowerSizeBound ? resultSize : 0;
00306       ++yiter; if (yiter == yend) break;
00307       itemx = *xiter;
00308       itemy = *yiter;
00309     }
00310   }
00311   // 3. copy remaining items of x:
00312   if (resultSize < resultLowerBound) 
00313     xend += resultLowerBound - resultSize;
00314   resultSize += (xend - xiter);
00315 
00316   return resultSize;
00317 }
00318 
00319 
00320 
00321 
00330 template <class InputContainer1, class InputContainer2, class OutputContainer>
00331 inline 
00332 void set_difference(const InputContainer1& x,  const InputContainer2& y, OutputContainer& result) {
00333   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00334   assert(y.size() > 0);
00335 
00336   assert(&result != &x); // 2. make sure output and inputs are not intermingled.
00337   assert(&result != &y);
00338 
00339   assert(result.capacity() >= x.size()); // 3. make sure output capacity is sufficient. 
00340 
00341   result.resize(x.size()); // STL containers do not have unbounded iterators -- therefore we have to resize the container in advance.
00342 
00343   typename InputContainer1::const_iterator xiter = x.begin();
00344   typename InputContainer2::const_iterator yiter = y.begin();
00345   typename OutputContainer::iterator resultIter = result.begin();
00346   set_difference_fast(xiter, x.end(), yiter, y.end(), resultIter);
00347   result.resize(resultIter - result.begin());
00348 }
00349 
00350 
00362 template <class InputContainer1, class InputContainer2, class OutputContainer>
00363 inline 
00364 bool set_difference_upper_size_bound(const InputContainer1& x,  const InputContainer2& y, OutputContainer& result,
00365                                      const int upperSizeBound) {
00366   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00367   assert(y.size() > 0);
00368   assert(upperSizeBound >= 0); 
00369   assert(upperSizeBound < x.size()); // otherwise EARLY_FILTERING is turned on in vain.
00370 
00371   assert(&result != &x); // 2. make sure output and inputs are not intermingled.
00372   assert(&result != &y);
00373 
00374   assert(result.capacity() >= upperSizeBound || result.capacity() >= x.size()); // 3. make sure output capacity is sufficient. 
00375 
00376   result.resize(x.size() < upperSizeBound ? x.size() : upperSizeBound); // STL containers do not have unbounded iterators -- therefore we have to resize the container in advance.
00377 
00378   typename InputContainer1::const_iterator xiter = x.begin();
00379   typename InputContainer2::const_iterator yiter = y.begin();
00380   typename OutputContainer::iterator resultIter = result.begin();
00381   bool hasMaximalSize = set_difference_upper_size_bound(xiter, x.end(), yiter, y.end(), resultIter, upperSizeBound);
00382   result.resize(resultIter - result.begin());
00383 
00384   return hasMaximalSize;
00385 }
00386 
00387 
00399 template <class InputContainer1, class InputContainer2, class OutputContainer>
00400 inline 
00401 bool set_difference_lower_size_bound(const InputContainer1& x,  const InputContainer2& y, OutputContainer& result,
00402                                      const int lowerSizeBound) {
00403   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00404   assert(y.size() > 0);
00405   assert(lowerSizeBound >= 1);       // otherwise EARLY_FILTERING is turned on in vain.
00406   assert(lowerSizeBound <= x.size());
00407 
00408   assert(&result != &x); // 2. make sure output and inputs are not intermingled.
00409   assert(&result != &y);
00410 
00411   assert(result.capacity() >= x.size()); // 3. make sure output capacity is sufficient. 
00412 
00413   result.resize(x.size()); // STL containers do not have unbounded iterators -- therefore we have to resize the container in advance.
00414 
00415   typename InputContainer1::const_iterator xiter = x.begin(), xend = x.end();
00416   typename InputContainer2::const_iterator yiter = y.begin();
00417   typename OutputContainer::iterator resultIter = result.begin();
00418   bool hasMinimumSize = set_difference_lower_size_bound(xiter, xend, yiter, y.end(), resultIter, lowerSizeBound);
00419   result.resize(resultIter - result.begin());
00420 
00421   return hasMinimumSize;
00422 }
00423 
00433 template <class InputContainer1, class InputContainer2>
00434 inline 
00435 int size_of_set_difference(const InputContainer1& x,  const InputContainer2& y) {
00436   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00437   assert(y.size() > 0);
00438 
00439   typename InputContainer1::const_iterator xiter = x.begin();
00440   typename InputContainer2::const_iterator yiter = y.begin();
00441   return size_of_set_difference(xiter, x.end(), yiter, y.end());
00442 }
00443 
00455 template <class InputContainer1, class InputContainer2>
00456 inline 
00457 int size_of_set_difference_upper_size_bound(const InputContainer1& x,  const InputContainer2& y, const int upperSizeBound) {
00458   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00459   assert(y.size() > 0);
00460   assert(upperSizeBound < x.size()); // otherwise EARLY_FILTERING is turned on in vain.
00461 
00462   typename InputContainer1::const_iterator xiter = x.begin();
00463   typename InputContainer2::const_iterator yiter = y.begin();
00464   return size_of_set_difference_upper_size_bound(xiter, x.end(), yiter, y.end(), upperSizeBound);
00465 }
00466 
00478 template <class InputContainer1, class InputContainer2>
00479 inline 
00480 int size_of_set_difference_lower_size_bound(const InputContainer1& x,  const InputContainer2& y, const int lowerSizeBound) {
00481   assert(x.size() > 0); // 1. make sure inputs are not trivial.
00482   assert(y.size() > 0);
00483   assert(lowerSizeBound >= 2); // otherwise EARLY_FILTERING is turned on in vain.
00484   assert(lowerSizeBound <= x.size());
00485 
00486   typename InputContainer1::const_iterator xiter = x.begin(),
00487     xend = x.end();
00488   typename InputContainer2::const_iterator yiter = y.begin();
00489   return size_of_set_difference_lower_size_bound(xiter, xend, yiter, y.end(), lowerSizeBound);
00490 }
00491 
00492 #endif