Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef ctrlplane_subset_h
       6             : #define ctrlplane_subset_h
       7             : 
       8             : #include <cassert>
       9             : #include <vector>
      10             : 
      11             : // Generates all the possible subset permutations of a particular set.
      12             : template <typename Container>
      13             : class SubsetGenerator {
      14             : public:
      15           4 :     SubsetGenerator(const Container &container)
      16           4 :         : container_(container) {
      17           4 :         stack_.push_back(0);
      18           4 :     }
      19             : 
      20          99 :     bool HasNext() const {
      21          99 :         if (container_.size() <= 1) {
      22           1 :             return false;
      23             :         }
      24          98 :         return (stack_.front() < 1);
      25             :     }
      26             : 
      27             :     // generate the next permutation.
      28             :     // rhs is the complement of lhs in container.
      29          95 :     void Next(Container *lhs, Container *rhs) {
      30          95 :         lhs->clear();
      31          95 :         rhs->clear();
      32             : 
      33          95 :         int prev = 0;
      34         451 :         for (unsigned int i = 0; i < stack_.size(); i++) {
      35         356 :             int index = stack_[i];
      36         356 :             assert((std::size_t)index < container_.size());
      37             : 
      38         534 :             for (int n = prev; n < index; n++) {
      39         178 :                 rhs->push_back(container_[n]);
      40             :             }
      41             : 
      42         356 :             lhs->push_back(container_[index]);
      43         356 :             prev = index + 1;
      44             :         }
      45         190 :         for (unsigned int n = prev; n < container_.size(); n++) {
      46          95 :             rhs->push_back(container_[n]);
      47             :         }        
      48          95 :         int last = stack_.back();
      49          95 :         if (stack_.size() < container_.size() - 1) {
      50          83 :             last++;
      51          83 :             if ((std::size_t) last < container_.size()) {
      52          46 :                 stack_.push_back(last);
      53          46 :                 return;
      54             :             }
      55             :         }
      56             :         while (true) {
      57          95 :             stack_.back() += 1;
      58          95 :             if ((std::size_t) stack_.back() < container_.size()) {
      59          49 :                 break;
      60             :             }
      61          46 :             if (stack_.size() == 1) {
      62           0 :                 break;
      63             :             }
      64          46 :             stack_.pop_back();
      65             :         }
      66             :     }
      67             : 
      68             : private:
      69             :     const Container &container_;
      70             :     std::vector<int> stack_;
      71             : };
      72             : 
      73             : #endif