20 #ifndef FST_PARTITION_H_ 21 #define FST_PARTITION_H_ 25 #include <type_traits> 68 static_assert(std::is_signed_v<T> && std::is_integral_v<T>,
69 "T must be a signed integer type");
81 elements_.resize(num_elements);
82 classes_.reserve(num_elements);
89 auto num_classes = classes_.size();
90 classes_.resize(num_classes + 1);
96 classes_.resize(classes_.size() + num_classes);
104 void Add(T element_id, T class_id) {
105 auto &this_element = elements_[element_id];
106 auto &this_class = classes_[class_id];
109 auto no_head = this_class.no_head;
110 if (no_head >= 0) elements_[no_head].prev_element = element_id;
111 this_class.no_head = element_id;
112 this_element.class_id = class_id;
114 this_element.yes = 0;
115 this_element.next_element = no_head;
116 this_element.prev_element = -1;
122 void Move(T element_id, T class_id) {
123 auto elements = &(elements_[0]);
124 auto &element = elements[element_id];
125 auto &old_class = classes_[element.class_id];
129 if (element.prev_element >= 0) {
130 elements[element.prev_element].next_element = element.next_element;
132 old_class.no_head = element.next_element;
134 if (element.next_element >= 0) {
135 elements[element.next_element].prev_element = element.prev_element;
138 Add(element_id, class_id);
144 auto elements = &(elements_[0]);
145 auto &element = elements[element_id];
146 if (element.yes == yes_counter_) {
149 auto class_id = element.class_id;
150 auto &this_class = classes_[class_id];
152 if (element.prev_element >= 0) {
153 elements[element.prev_element].next_element = element.next_element;
155 this_class.no_head = element.next_element;
157 if (element.next_element >= 0) {
158 elements[element.next_element].prev_element = element.prev_element;
161 if (this_class.yes_head >= 0) {
162 elements[this_class.yes_head].prev_element = element_id;
164 visited_classes_.push_back(class_id);
166 element.yes = yes_counter_;
167 element.next_element = this_class.yes_head;
168 element.prev_element = -1;
169 this_class.yes_head = element_id;
170 this_class.yes_size++;
181 template <
class Queue>
183 for (
const auto &visited_class : visited_classes_) {
184 const auto new_class = SplitRefine(visited_class);
185 if (new_class != -1 && queue) queue->Enqueue(new_class);
187 visited_classes_.clear();
192 const T
ClassId(T element_id)
const {
return elements_[element_id].class_id; }
194 const size_t ClassSize(T class_id)
const {
return classes_[class_id].size; }
218 Class() : size(0), yes_size(0), no_head(-1), yes_head(-1) {}
236 T SplitRefine(T class_id) {
237 auto yes_size = classes_[class_id].yes_size;
238 auto size = classes_[class_id].size;
239 auto no_size = size - yes_size;
243 classes_[class_id].no_head = classes_[class_id].yes_head;
244 classes_[class_id].yes_head = -1;
245 classes_[class_id].yes_size = 0;
248 auto new_class_id = classes_.size();
249 classes_.resize(classes_.size() + 1);
250 auto &old_class = classes_[class_id];
251 auto &new_class = classes_[new_class_id];
253 if (no_size < yes_size) {
255 new_class.no_head = old_class.no_head;
256 new_class.size = no_size;
258 old_class.no_head = old_class.yes_head;
259 old_class.yes_head = -1;
260 old_class.size = yes_size;
261 old_class.yes_size = 0;
264 new_class.size = yes_size;
265 new_class.no_head = old_class.yes_head;
267 old_class.size = no_size;
268 old_class.yes_size = 0;
269 old_class.yes_head = -1;
271 auto elements = &(elements_[0]);
273 for (
auto e = new_class.no_head; e >= 0; e = elements[e].next_element) {
274 elements[e].class_id = new_class_id;
281 std::vector<Element> elements_;
283 std::vector<Class> classes_;
285 std::vector<T> visited_classes_;
295 template <
typename T>
301 : partition_(partition),
302 element_id_(partition_.classes_[class_id].no_head),
303 class_id_(class_id) {}
305 bool Done() {
return element_id_ < 0; }
307 const T
Value() {
return element_id_; }
309 void Next() { element_id_ = partition_.elements_[element_id_].next_element; }
311 void Reset() { element_id_ = partition_.classes_[class_id_].no_head; }
322 #endif // FST_PARTITION_H_ const size_t ClassSize(T class_id) const
void SplitOn(T element_id)
void Move(T element_id, T class_id)
void AllocateClasses(T num_classes)
typename Partition< T >::Element Element
const T NumClasses() const
void Initialize(size_t num_elements)
Partition(T num_elements)
const T ClassId(T element_id) const
void Add(T element_id, T class_id)
PartitionIterator(const Partition< T > &partition, T class_id)
void FinalizeSplit(Queue *queue)