LEMUR Packages: ompl_lemur or_lemur pr_bgl prpy_lemur
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Groups Pages
BisectPerm.h
Go to the documentation of this file.
1 
9 namespace ompl_lemur
10 {
11 
13 {
14 public:
15  BisectPerm() {}
16 
27  const std::vector< std::pair<int,int> > & get(int n)
28  {
29  // look it up in the cache
30  std::map<int, const std::vector< std::pair<int,int> > >::iterator it;
31  it = cache.find(n);
32  if (it != cache.end())
33  return it->second;
34  // else calculate it
35  //printf("calculating perm for n=%d ...\n", n);
36  int i;
37  int last_true;
38  int max_i;
39  int max_val;
40  std::vector< std::pair<int,int> > perm;
41  std::vector<bool> done(n, false);
42  std::vector<int> dist(n);
43  for (;;)
44  {
45  last_true = -1;
46  for (i=0; i<n; i++)
47  {
48  if (done[i]) last_true = i;
49  dist[i] = (i-last_true);
50  }
51  last_true = n;
52  for (i=n-1; i>=0; i--)
53  {
54  if (done[i]) last_true = i;
55  dist[i] = (last_true-i) < dist[i] ? (last_true-i) : dist[i];
56  }
57  max_val = 0;
58  max_i = 0;
59  for (i=0; i<n; i++) if (max_val < dist[i])
60  {
61  max_val = dist[i];
62  max_i = i;
63  }
64  if (!max_val)
65  break;
66  perm.push_back(std::make_pair(max_i,max_val));
67  done[max_i] = true;
68  }
69 #if 0
70  printf(" result: [");
71  for (i=0; i<n; i++)
72  printf(" %d-%d", perm[i].first, perm[i].second);
73  printf(" ]\n");
74 #endif
75  cache.insert(std::make_pair(n,perm));
76  return cache[n];
77  }
78 
79 private:
80  // cache of edge permutations
81  std::map<int, const std::vector< std::pair<int,int> > > cache;
82 };
83 
84 } // namespace ompl_lemur
Definition: BisectPerm.h:12