Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
cutbuffer.inc
Go to the documentation of this file.
1
29#pragma once
30
36//#include <ogdf/lib/abacus/sorter.h>
37
38#include <ogdf/basic/comparer.h>
39
40namespace abacus {
41
42
43template<class BaseType, class CoType>
45{
46 for (int i = 0; i < n_; i++) {
47 psRef_[i]->conVar()->unlock();
48 delete psRef_[i];
49 }
50}
51
52
53template<class BaseType, class CoType>
56 bool keepInPool)
57{
58 if (n_ == size())
59 return 1;
60 else {
61 psRef_[n_] = new PoolSlotRef<BaseType, CoType>(slot);
62 keepInPool_[n_] = keepInPool;
63 ranking_ = false;
64 slot->conVar()->lock();
65 ++n_;
66 return 0;
67 }
68}
69
70
71template<class BaseType, class CoType>
74 bool keepInPool,
75 double rank)
76{
77 if (n_ == size())
78 return 1;
79 else {
80 psRef_[n_] = new PoolSlotRef<BaseType, CoType>(slot);
81 keepInPool_[n_] = keepInPool;
82 rank_[n_] = rank;
83 ++n_;
84 slot->conVar()->lock();
85 return 0;
86 }
87}
88
89
90template<class BaseType, class CoType>
91void CutBuffer<BaseType, CoType>::remove(ArrayBuffer<int> &index)
92{
93 PoolSlotRef<BaseType, CoType> *psr;
94
95 const int nIndex = index.size();
96
97 for (int i = 0; i < nIndex; i++) {
98 psr = psRef_[index[i]];
99 psr->conVar()->unlock();
101 delete psr;
102 if (ps->conVar()->deletable())
103 ps->removeConVarFromPool();
104 }
105 psRef_.leftShift(index);
106 keepInPool_.leftShift(index);
107 rank_.leftShift(index);
108
109 n_ -= nIndex;
110}
111
112
113template<class BaseType, class CoType>
114void CutBuffer<BaseType, CoType>::sort(int threshold)
115{
116 if (ranking_) {
117 if (n_ > threshold) {
118 // sort the buffered items
119 /* AbaSorter<int, double> sorter;
120 Array<int> index(n_);
121 Array<double> keys(n_);
122
123 for (int i = 0; i < n_; i++) {
124 index[i] = i;
125 keys[i] = -rank_[i];
126 }
127
128 sorter.quickSort(n_, index, keys);
129 */
131 for (int i = 0; i < n_; i++) {
132 things[i].setItem(i);
133 things[i].setPriority(-rank_[i]);
134 }
135 things.quicksort();
136
137
138 // reorder the buffered items
140 Array<bool> keepInPoolSorted(n_);
141
142 for (int i = 0; i < n_; i++) {
143 psRefSorted[i] = psRef_[things[i].item()];
144 keepInPoolSorted[i] = keepInPool_[things[i].item()];
145 }
146
147 for (int i = 0; i < n_; i++) {
148 psRef_[i] = psRefSorted[i];
149 keepInPool_[i] = keepInPoolSorted[i];
150 }
151
152 Logger::ilout(Logger::Level::Minor) << "\titems ranked: accepted in " << -things[0].priority() << " ... "
153 << -things[threshold - 1].priority() << ", rejected in "
154 << -things[threshold].priority() << " ... " << -things[n_ - 1].priority() << std::endl;
155
156 }
157 else
158 Logger::ilout(Logger::Level::Minor) << "\tnot enough items, no ranking required" << std::endl;
159 }
160 else
161 Logger::ilout(Logger::Level::Minor) << "\tranking of buffered items not possible" << std::endl;
162}
163
164
165template<class BaseType, class CoType>
167 int max,
169{
170 // unlock the buffered items
171 for (int i = 0; i < n_; i++)
172 psRef_[i]->conVar()->unlock();
173
174 // determine the number of items to extract
175 int nExtract;
176
177 if (n_ < max) nExtract = n_;
178 else nExtract = max;
179
180 // delete the nonextracted items
181 /* We have to check if the constraint/variable can be deleted, because the
182 * pool slot might be shared with another constraint/variable that is not
183 * deleted.
184 *
185 * The deletion of the extracted items must be performed before the
186 * deletion of the non-extracted ones. Otherwise if a \a NONDUPLPOOL
187 * is used, it can happen that a constraint is removed from the pool
188 * that is the duplicate of an extracted one.
189 */
191
192 for (int i = nExtract; i < n_; i++) {
193 if (!keepInPool_[i]) {
194 s = psRef_[i]->slot();
195 delete psRef_[i];
196 if (s->conVar()->deletable())
197 s->removeConVarFromPool();
198 }
199 else delete psRef_[i];
200 }
201
202 n_ = 0;
203
204 // extract the items
205 for (int i = 0; i < nExtract; i++) {
206 newSlots.push(psRef_[i]->slot());
207 delete psRef_[i];
208 }
209
210 // allow ranking in next iteration
211 ranking_ = true;
212}
213
214}
~CutBuffer()
The destructor.
void remove(ArrayBuffer< int > &index)
Removes the elements specified by index from the buffer.
int insert(PoolSlot< BaseType, CoType > *slot, bool keepInPool)
Adds a slot to the buffer.
void sort(int threshold)
Sorts the items according to their ranks.
void extract(int max, ArrayBuffer< PoolSlot< BaseType, CoType > * > &newSlots)
Takes the first max items from the buffer and clears the buffer.
static std::ostream & ilout(Level level=Level::Default)
Definition Logger.h:187
Declarations for Comparer objects.
constraint.
cutbuffer.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
poolslot.
poolslotref
variable.