1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2012 Google Inc. All rights reserved.
3 // http://code.google.com/p/ceres-solver/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 //   this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 //   this list of conditions and the following disclaimer in the documentation
12 //   and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 //   used to endorse or promote products derived from this software without
15 //   specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
28 //
29 // Author: sameeragarwal@google.com (Sameer Agarwal)
30 
31 #ifndef CERES_PUBLIC_ORDERED_GROUPS_H_
32 #define CERES_PUBLIC_ORDERED_GROUPS_H_
33 
34 #include <map>
35 #include <set>
36 #include <vector>
37 #include "ceres/internal/port.h"
38 #include "glog/logging.h"
39 
40 namespace ceres {
41 
42 // A class for storing and manipulating an ordered collection of
43 // groups/sets with the following semantics:
44 //
45 // Group ids are non-negative integer values. Elements are any type
46 // that can serve as a key in a map or an element of a set.
47 //
48 // An element can only belong to one group at a time. A group may
49 // contain an arbitrary number of elements.
50 //
51 // Groups are ordered by their group id.
52 template <typename T>
53 class OrderedGroups {
54  public:
55   // Add an element to a group. If a group with this id does not
56   // exist, one is created. This method can be called any number of
57   // times for the same element. Group ids should be non-negative
58   // numbers.
59   //
60   // Return value indicates if adding the element was a success.
AddElementToGroup(const T element,const int group)61   bool AddElementToGroup(const T element, const int group) {
62     if (group < 0) {
63       return false;
64     }
65 
66     typename map<T, int>::const_iterator it = element_to_group_.find(element);
67     if (it != element_to_group_.end()) {
68       if (it->second == group) {
69         // Element is already in the right group, nothing to do.
70         return true;
71       }
72 
73       group_to_elements_[it->second].erase(element);
74       if (group_to_elements_[it->second].size() == 0) {
75         group_to_elements_.erase(it->second);
76       }
77     }
78 
79     element_to_group_[element] = group;
80     group_to_elements_[group].insert(element);
81     return true;
82   }
83 
Clear()84   void Clear() {
85     group_to_elements_.clear();
86     element_to_group_.clear();
87   }
88 
89   // Remove the element, no matter what group it is in. Return value
90   // indicates if the element was actually removed.
Remove(const T element)91   bool Remove(const T element) {
92     const int current_group = GroupId(element);
93     if (current_group < 0) {
94       return false;
95     }
96 
97     group_to_elements_[current_group].erase(element);
98 
99     if (group_to_elements_[current_group].size() == 0) {
100       // If the group is empty, then get rid of it.
101       group_to_elements_.erase(current_group);
102     }
103 
104     element_to_group_.erase(element);
105     return true;
106   }
107 
108   // Bulk remove elements. The return value indicates the number of
109   // elements successfully removed.
Remove(const vector<T> & elements)110   int Remove(const vector<T>& elements) {
111     if (NumElements() == 0 || elements.size() == 0) {
112       return 0;
113     }
114 
115     int num_removed = 0;
116     for (int i = 0; i < elements.size(); ++i) {
117       num_removed += Remove(elements[i]);
118     }
119     return num_removed;
120   }
121 
122   // Reverse the order of the groups in place.
Reverse()123   void Reverse() {
124     typename map<int, set<T> >::reverse_iterator it =
125         group_to_elements_.rbegin();
126     map<int, set<T> > new_group_to_elements;
127     new_group_to_elements[it->first] = it->second;
128 
129     int new_group_id = it->first + 1;
130     for (++it; it != group_to_elements_.rend(); ++it) {
131       for (typename set<T>::const_iterator element_it = it->second.begin();
132            element_it != it->second.end();
133            ++element_it) {
134         element_to_group_[*element_it] = new_group_id;
135       }
136       new_group_to_elements[new_group_id] = it->second;
137       new_group_id++;
138     }
139 
140     group_to_elements_.swap(new_group_to_elements);
141   }
142 
143   // Return the group id for the element. If the element is not a
144   // member of any group, return -1.
GroupId(const T element)145   int GroupId(const T element) const {
146     typename map<T, int>::const_iterator it = element_to_group_.find(element);
147     if (it == element_to_group_.end()) {
148       return -1;
149     }
150     return it->second;
151   }
152 
IsMember(const T element)153   bool IsMember(const T element) const {
154     typename map<T, int>::const_iterator it = element_to_group_.find(element);
155     return (it != element_to_group_.end());
156   }
157 
158   // This function always succeeds, i.e., implicitly there exists a
159   // group for every integer.
GroupSize(const int group)160   int GroupSize(const int group) const {
161     typename map<int, set<T> >::const_iterator it =
162         group_to_elements_.find(group);
163     return (it ==  group_to_elements_.end()) ? 0 : it->second.size();
164   }
165 
NumElements()166   int NumElements() const {
167     return element_to_group_.size();
168   }
169 
170   // Number of groups with one or more elements.
NumGroups()171   int NumGroups() const {
172     return group_to_elements_.size();
173   }
174 
175   // The first group with one or more elements. Calling this when
176   // there are no groups with non-zero elements will result in a
177   // crash.
MinNonZeroGroup()178   int MinNonZeroGroup() const {
179     CHECK_NE(NumGroups(), 0);
180     return group_to_elements_.begin()->first;
181   }
182 
group_to_elements()183   const map<int, set<T> >& group_to_elements() const {
184     return group_to_elements_;
185   }
186 
element_to_group()187   const map<T, int>& element_to_group() const {
188     return element_to_group_;
189   }
190 
191  private:
192   map<int, set<T> > group_to_elements_;
193   map<T, int> element_to_group_;
194 };
195 
196 // Typedef for the most commonly used version of OrderedGroups.
197 typedef OrderedGroups<double*> ParameterBlockOrdering;
198 
199 }  // namespace ceres
200 
201 #endif  // CERES_PUBLIC_ORDERED_GROUP_H_
202