Line data    Source code

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