SHARE
TWEET

Untitled

a guest Nov 12th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "ordered_set.h"
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. OrderedSet::OrderedSet() : start_(0) {}
  7.  
  8. OrderedSet::OrderedSet(size_t size) : Set(size), start_(0) {}
  9.  
  10. OrderedSet::OrderedSet(const Set& other) : Set(other), start_(0)
  11. {
  12.     SortIntern();
  13. }
  14.  
  15. OrderedSet::OrderedSet(Set&& other) : Set(move(other)), start_(0)
  16. {
  17.     SortIntern();
  18. }
  19.  
  20. OrderedSet::OrderedSet(const OrderedSet& other) : Set(other), start_(other.start_){}
  21.  
  22. OrderedSet::OrderedSet(OrderedSet&& other) noexcept : Set(move(other))
  23. {
  24.     start_ = other.start_;
  25.     other.start_ = 0;
  26. }
  27.  
  28. OrderedSet::OrderedSet(const std::initializer_list<int>& list) : Set(list), start_(0)
  29. {
  30.     SortIntern();
  31. }
  32.  
  33. void OrderedSet::SortIntern()
  34. {
  35.     sort(begin(), begin() + size_);
  36. }
  37.  
  38. OrderedSet OrderedSet::GetSmaller(int x) const
  39. {
  40.     OrderedSet result(*this);
  41.     size_t i = 0;
  42.     while (i < size() && begin()[i] < x) ++i;
  43.     result.size_ = i;
  44.     return result;
  45. }
  46.  
  47.  
  48. OrderedSet OrderedSet::GetLarger(int x) const
  49. {
  50.     OrderedSet result(*this);
  51.     size_t i = 0;
  52.     while (i < size() && begin()[i] <= x) ++i;
  53.     result.size_ = size_ - i;
  54.     result.start_ = i;
  55.     return result;
  56. }
  57.  
  58. Set OrderedSet::Merge(const Set& other) const
  59. {
  60.     if (const auto* ordered = dynamic_cast<const OrderedSet*>(&other))
  61.     {
  62.         OrderedSet result(size() + ordered->size());
  63.         auto* a = begin();
  64.         auto* b = ordered->begin();
  65.         auto* endA = a + size();
  66.         auto* endB =b + other.size();
  67.         while(a < endA && b < endB)
  68.         {
  69.             const int val1 = *a;
  70.             const int val2 = *b;
  71.             int val = 0;
  72.             if (val1 <= val2)
  73.             {
  74.                 ++a;
  75.                 val = val1;
  76.             } else
  77.             {
  78.                 ++b;
  79.                 val = val2;
  80.             }
  81.             if (!result.Contains(val)) {
  82.                 result.AddUnchecked(val);
  83.             }
  84.         }
  85.         if (a < endA)
  86.         {
  87.             for (; a < endA; ++a) {
  88.                 if (!result.Contains(*a)) result.AddUnchecked(*a);
  89.             }
  90.         } else if (b < endB)
  91.         {
  92.             for (; b < endB; ++b) {
  93.                 if (!result.Contains(*b)) result.AddUnchecked(*b);
  94.             }
  95.         }
  96.         return static_cast<Set>(result);
  97.     }
  98.     return Set::Merge(other);
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top