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