1 #if !defined  HAVE_LEFT_RIGHT_ARRAY_H__
2 #define       HAVE_LEFT_RIGHT_ARRAY_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2012, 2014, 2019 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7 
8 
9 #include "fxttypes.h"
10 
11 
12 // whether to include some O(n) methods for testing purposes
13 //#define LR_WITH_DUMB_METHODS  // default off
14 
15 
16 class left_right_array
17 // Maintain index array [0,...,n-1], keep track which index is set or free.
18 // Allows, in time O(log(n)), to
19 // - find k-th free index (where 0<=k<=num_free())
20 // - find k-th set index (where 0<=k<=num_set())
21 // - determine how many indices are free/set to the left/right of
22 //   an absolute index i (where 0<=i<n).
23 {
24 public:
25     ulong *fl_;  // Free indices Left (including current element) in bsearch interval
26     bool *tg_;   // tags: tg[i]==true if and only if index i is free
27     ulong n_;    // total number of indices
28     ulong f_;    // number of free indices
29 
30     left_right_array(const left_right_array&) = delete;
31     left_right_array & operator = (const left_right_array&) = delete;
32 
33 public:
left_right_array(ulong n)34     explicit left_right_array(ulong n)
35     {
36         n_ = n;
37         fl_ = new ulong[n_];
38         tg_ = new bool[n_];
39         free_all();
40     }
41 
~left_right_array()42     ~left_right_array()
43     {
44         delete [] fl_;
45         delete [] tg_;
46     }
47 
num_free()48     ulong num_free() const  { return f_; }
num_set()49     ulong num_set() const  { return  n_ - f_; }
is_free(ulong i)50     bool is_free(ulong i) const  { return  tg_[i]; }
is_set(ulong i)51     bool is_set(ulong i) const  { return  ! tg_[i]; }
52 
53 private:
init_rec(ulong i0,ulong i1)54     void init_rec(ulong i0, ulong i1)
55     // Set elements of fl[0,...,n-2] according to all indices free.
56     // The element fl[n-1] needs to be set to 1 afterwards.
57     // Work is O(n).
58     {
59         if ( (i1-i0)!=0 )
60         {
61             ulong t = (i1+i0)/2;
62             init_rec(i0, t);
63             init_rec(t+1, i1);
64         }
65         fl_[i1] = i1-i0+1;
66     }
67 
68 public:
free_all()69     void free_all()
70     // Mark all indices as free.
71     {
72         f_ = n_;
73         for (ulong j=0; j<n_; ++j)  tg_[j] = true;
74         init_rec(0, n_-1);
75         fl_[n_-1] = 1;
76     }
77 
set_all()78     void set_all()
79     // Mark all indices of as set.
80     {
81         f_ = 0;
82         for (ulong j=0; j<n_; ++j)  tg_[j] = false;
83         for (ulong j=0; j<n_; ++j)  fl_[j] = 0;
84     }
85 
86 
get_free_idx(ulong k)87     ulong get_free_idx(ulong k)  const
88     // Return the k-th ( 0 <= k < num_free() ) free index.
89     // Return ~0UL if k is out of bounds.
90     // Work is O(log(n)).
91     {
92         if ( k >= num_free() )  return ~0UL;
93 
94         ulong i0 = 0,  i1 = n_-1;
95         while ( 1 )
96         {
97             ulong t = (i1+i0)/2;
98             if ( (fl_[t] == k+1) && (tg_[t]) )  return t;
99 
100             if ( fl_[t] > k )  // left:
101             {
102                 i1 = t;
103             }
104             else   // right:
105             {
106                 i0 = t+1;  k-=fl_[t];
107             }
108         }
109     }
110 
111 
get_free_idx_chg(ulong k)112     ulong get_free_idx_chg(ulong k)
113     // Return the k-th ( 0 <= k < num_free() ) free index.
114     // Return ~0UL if k is out of bounds.
115     // Change the arrays and fl[] and tg[] reflecting
116     //   that index i will be set afterwards.
117     // Work is O(log(n)).
118     {
119         if ( k >= num_free() )  return ~0UL;
120 
121         --f_;
122 
123         ulong i0 = 0,  i1 = n_-1;
124         while ( 1 )
125         {
126             ulong t = (i1+i0)/2;
127 
128             if ( (fl_[t] == k+1) && (tg_[t]) )
129             {
130                 --fl_[t];
131                 tg_[t] = false;
132                 return t;
133             }
134 
135             if ( fl_[t] > k )  // left:
136             {
137                 --fl_[t];
138                 i1 = t;
139             }
140             else    // right:
141             {
142                 i0 = t+1;  k-=fl_[t];
143             }
144         }
145     }
146 
147 
get_set_idx(ulong k)148     ulong get_set_idx(ulong k)  const
149     // Return the k-th ( 0 <= k < num_set() ) set index.
150     // Return ~0UL if k is out of bounds.
151     // Work is O(log(n)).
152     {
153         if ( k >= num_set() )  return ~0UL;
154 
155         ulong i0 = 0,  i1 = n_-1;
156         while ( 1 )
157         {
158             ulong t = (i1+i0)/2;
159             // how many elements to the left are set:
160             ulong slt = t-i0+1 - fl_[t];
161 
162             if ( (slt == k+1) && (tg_[t]==false) )  return t;
163 
164             if ( slt > k )  // left:
165             {
166                 i1 = t;
167             }
168             else   // right:
169             {
170                 i0 = t+1;  k-=slt;
171             }
172         }
173     }
174 
get_set_idx_chg(ulong k)175     ulong get_set_idx_chg(ulong k)
176     // Return the k-th ( 0 <= k < num_set() ) set index.
177     // Return ~0UL if k is out of bounds.
178     // Change the arrays and fl[] and tg[] reflecting
179     //   that index i will be freed afterwards.
180     // Work is O(log(n)).
181     {
182         if ( k >= num_set() )  return ~0UL;
183 
184         ++f_;
185 
186         ulong i0 = 0,  i1 = n_-1;
187         while ( 1 )
188         {
189             ulong t = (i1+i0)/2;
190             // how many elements to the left are set:
191             ulong slt = t-i0+1 - fl_[t];
192 
193             if ( (slt == k+1) && (tg_[t]==false) )
194             {
195                 ++fl_[t];
196                 tg_[t] = true;
197                 return t;
198             }
199 
200             if ( slt > k )  // left:
201             {
202                 ++fl_[t];
203                 i1 = t;
204             }
205             else   // right:
206             {
207                 i0 = t+1;  k-=slt;
208             }
209         }
210     }
211 
212 
213     // The methods num_[FS][LR][IE](ulong i) return the number of
214     // Free/Set indices Left/Right if (absolute) index i, Including/Excluding i.
215     // Return ~0UL if i >= n.
216 
num_FLE(ulong i)217     ulong num_FLE(ulong i)  const
218     // Return number of Free indices Left of (absolute) index i (Excluding i).
219     // Work is O(log(n)).
220     {
221         if ( i >= n_ )  { return ~0UL; }  // out of bounds
222 
223         ulong i0 = 0,  i1 = n_-1;
224         ulong ns = i;  // number of set element left to i (including i)
225         while ( 1 )
226         {
227             if ( i0==i1 )  break;
228 
229             ulong t = (i1+i0)/2;
230             if ( i<=t )  // left:
231             {
232                 i1 = t;
233             }
234             else   // right:
235             {
236                 ns -= fl_[t];
237                 i0 = t+1;
238             }
239         }
240 
241         return  i-ns;
242     }
243 
num_FLI(ulong i)244     ulong num_FLI(ulong i)  const
245     // Return number of Free indices Left of (absolute) index i (Including i).
246     {
247         if ( i >= n_ )  { return ~0UL; }
248         return num_FLE(i) + tg_[i];
249     }
250 
251 
num_FRE(ulong i)252     ulong num_FRE(ulong i)  const
253     // Return number of Free indices Right of (absolute) index i (Excluding i).
254     {
255         if ( i >= n_ )  { return ~0UL; }
256         return  num_free() - num_FLI(i);
257     }
258 
num_FRI(ulong i)259     ulong num_FRI(ulong i)  const
260     // Return number of Free indices Right of (absolute) index i (Including i).
261     {
262         if ( i >= n_ )  { return ~0UL; }
263         return  num_free() - num_FLE(i);
264     }
265 
266 
num_SLE(ulong i)267     ulong num_SLE(ulong i)  const
268     // Return number of Set indices Left of (absolute) index i (Excluding i).
269     {
270         if ( i >= n_ )  { return ~0UL; }
271         return i - num_FLE(i);
272     }
273 
num_SLI(ulong i)274     ulong num_SLI(ulong i)  const
275     // Return number of Set indices Left of (absolute) index i (Including i).
276     {
277         if ( i >= n_ )  { return ~0UL; }
278         return i - num_FLE(i) + !tg_[i];
279     }
280 
281 
num_SRE(ulong i)282     ulong num_SRE(ulong i)  const
283     // Return number of Set indices Right of (absolute) index i (Excluding i).
284     {
285         if ( i >= n_ )  { return ~0UL; }
286         return  num_set() - num_SLI(i);
287     }
288 
num_SRI(ulong i)289     ulong num_SRI(ulong i)  const
290     // Return number of Set indices Right of (absolute) index i (Including i).
291     {
292         if ( i >= n_ )  { return ~0UL; }
293         return  num_set() - i + num_FLE(i);
294     }
295 
296 
297 #ifdef LR_WITH_DUMB_METHODS   // Work with all methods *_dumb() is O(n).
get_free_idx_dumb(ulong k)298     ulong get_free_idx_dumb(ulong k)  const
299     // Return the k-th ( 0 <= k < num_free() ) free index.
300     // Return ~0UL if k is out of bounds.
301     {
302         if ( k >= num_free() )  return ~0UL;
303 
304         ulong idx = 0;
305         for ( ; idx<n_; ++idx)
306         {
307             if ( tg_[idx]==true )
308             {
309                 if ( k==0 )  break;
310                 --k;
311             }
312         }
313         return idx;
314     }
315 
get_set_idx_dumb(ulong k)316     ulong get_set_idx_dumb(ulong k)  const
317     // Return the k-th ( 0 <= k < num_set() ) set index.
318     // Return ~0UL if k is out of bounds.
319     {
320         if ( k >= num_set() )  return ~0UL;
321 
322         ulong idx = 0;
323         for ( ; idx<n_; ++idx)
324         {
325             if ( tg_[idx]==false )
326             {
327                 if ( k==0 )  break;
328                 --k;
329             }
330         }
331         return idx;
332     }
333 
334 
num_FLE_dumb(ulong i)335     ulong num_FLE_dumb(ulong i)  const
336     // Return number of Free indices Left of (absolute) index i (Excluding i).
337     {
338         if ( i >= n_ )  { return ~0UL; }
339         ulong nf = 0;
340         for (ulong j=0; j<i; ++j)  nf += tg_[j];
341         return nf;
342     }
343 
num_FLI_dumb(ulong i)344     ulong num_FLI_dumb(ulong i)  const
345     // Return number of Free indices Left of (absolute) index i (Including i).
346     {
347         if ( i >= n_ )  { return ~0UL; }
348         ulong nf = 0;
349         for (ulong j=0; j<=i; ++j)  nf += tg_[j];
350         return nf;
351     }
352 
353 
num_FRE_dumb(ulong i)354     ulong num_FRE_dumb(ulong i)  const
355     // Return number of Free indices Right of (absolute) index i (Excluding i).
356     {
357         if ( i >= n_ )  { return ~0UL; }
358         ulong nf = 0;
359         for (ulong j=i+1; j<n_; ++j)  nf += tg_[j];
360         return nf;
361     }
362 
num_FRI_dumb(ulong i)363     ulong num_FRI_dumb(ulong i)  const
364     // Return number of Free indices Right of (absolute) index i (Including i).
365     {
366         if ( i >= n_ )  { return ~0UL; }
367         ulong nf = 0;
368         for (ulong j=i; j<n_; ++j)  nf += tg_[j];
369         return nf;
370     }
371 
372 
num_SLE_dumb(ulong i)373     ulong num_SLE_dumb(ulong i)  const
374     // Return number of Set indices Left of (absolute) index i (Excluding i).
375     {
376         if ( i >= n_ )  { return ~0UL; }
377         ulong nf = 0;
378         for (ulong j=0; j<i; ++j)  nf += !tg_[j];
379         return nf;
380     }
381 
num_SLI_dumb(ulong i)382     ulong num_SLI_dumb(ulong i)  const
383     // Return number of Set indices Left of (absolute) index i (Including i).
384     {
385         if ( i >= n_ )  { return ~0UL; }
386         ulong nf = 0;
387         for (ulong j=0; j<=i; ++j)  nf += !tg_[j];
388         return nf;
389     }
390 
391 
num_SRE_dumb(ulong i)392     ulong num_SRE_dumb(ulong i)  const
393     // Return number of Set indices Right of (absolute) index i (Excluding i).
394     {
395         if ( i >= n_ )  { return ~0UL; }
396         ulong nf = 0;
397         for (ulong j=i+1; j<n_; ++j)  nf += !tg_[j];
398         return nf;
399     }
400 
num_SRI_dumb(ulong i)401     ulong num_SRI_dumb(ulong i)  const
402     // Return number of Set indices Right of (absolute) index i (Including i).
403     {
404         if ( i >= n_ )  { return ~0UL; }
405         ulong nf = 0;
406         for (ulong j=i; j<n_; ++j)  nf += !tg_[j];
407         return nf;
408     }
409 
410 #endif  // LR_WITH_DUMB_METHODS
411 };
412 // -------------------------
413 
414 //#undef LR_WITH_DUMB_METHODS  // leave defined
415 
416 
417 #endif  // !defined HAVE_LEFT_RIGHT_ARRAY_H__
418