Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

27
LINES

< > BotCompany Repo | #1030515 // indexOfRangePredicate_IIntIntPred - faster version of indexOfRangePredicate

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (2719L/16K).

// finds lowest index where predicate turns true.
// returns "to" when predicate is false on whole range.
// Predicate operates on a range and returns true
// iff any value in the range is contained in the set.
static <A> int indexOfRangePredicate_IIntIntPred(int from default 0, int to, IIntIntPred pred) {
  // interval empty?
  if (from >= to) ret to;
  
  // predicate false on whole range?
  if (!pred.get(from, to)) ret to;
  
  while ping (to-from > 1) {
    // predicate turns true somewhere in range. split in middle.
    int mid = (from + to) >>> 1;
    
    // check lower half
    if (pred.get(from, mid))
      // predicate turns true in lower half. move there.
      to = mid;
    else
      // lower half is clean, move to higher half
      from = mid;
  }

  // we've narrowed things down to at most one element, return index
  ret from;
}

Author comment

Began life as a copy of #1030504

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, vouqrxazstgt

No comments. add comment

Snippet ID: #1030515
Snippet name: indexOfRangePredicate_IIntIntPred - faster version of indexOfRangePredicate
Eternal ID of this version: #1030515/1
Text MD5: 6e76e52d80ea6701d1a935ea1e09b9ee
Transpilation MD5: 34f72a96efee9ba7201f914dd0de70a9
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2021-01-04 01:14:20
Source code size: 881 bytes / 27 lines
Pitched / IR pitched: No / No
Views / Downloads: 122 / 177
Referenced in: [show references]