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

58
LINES

< > BotCompany Repo | #1029031 // intersectSortedIntArrays_ofs_optimized2 [OK] - recursive version!

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

Libraryless. Click here for Pure Java version (149L/2K).

scope intersectSortedIntArrays_ofs_optimized2.

// is allowed to return null when result is empty
// ofs is added to elements of b prior to comparison
static int[] intersectSortedIntArrays_ofs_optimized2(int[] a, int[] b, int ofs, IntBuffer buf default null) {
  int i = 0, j = 0, la = lIntArray(a), lb = lIntArray(b);
  
  // swap if a is longer than b
  bool swapped = la > lb;
  if (swapped) {
    int[] temp = a; a = b; b = temp;
    int temp2 = la; la = lb; lb = temp2;
    ofs = -ofs;
  }
  
  // special case zero elements
  if (la == 0) null;
  
  // special case one element
  if (la == 1 && !swapped)
    ret intArrayBinarySearch(b, a[0]-ofs) >= 0 ? a : null;
    
  if (buf == null) buf = new IntBuffer; else buf.reset();
  recurse(a, b, ofs, buf, 0, la, 0, lb);
  int[] out = buf.toArray();
  if (swapped) {
    int n = lIntArray(out);
    for k to n:
      out[k] -= ofs;
  }
  ret out;
}

svoid #recurse(int[] a, int[] b, int ofs, IntBuffer buf, int aFrom, int aTo, int bFrom, int bTo) {
  if (aFrom >= aTo || bFrom >= bTo) ret; // nothing to do
  
  // start in the middle of a, search this element in b
  int i = (aFrom+aTo)/2;
  int x = a[i];
  int j = intArrayBinarySearch(b, bFrom, bTo, x-ofs);
  
  ifdef intersectSortedIntArrays_ofs_optimized2_debug
    printVars_str(+aFrom, +aTo, +i, +x, +ofs, +bFrom, +bTo, +j);
  endifdef
  
  if (j >= 0) {
    // element found
    recurse(a, b, ofs, buf, aFrom, i, bFrom, j);
    buf.add(x);
    recurse(a, b, ofs, buf, i+1, aTo, j+1, bTo);
  } else {
    j = -j-1;
    recurse(a, b, ofs, buf, aFrom, i, bFrom, j);
    recurse(a, b, ofs, buf, i+1, aTo, j, bTo);
  }
}

end scope

Author comment

Began life as a copy of #1029030

download  show line numbers  debug dex  old transpilations   

Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv

No comments. add comment

Snippet ID: #1029031
Snippet name: intersectSortedIntArrays_ofs_optimized2 [OK] - recursive version!
Eternal ID of this version: #1029031/18
Text MD5: 0ef1906cb6321c33c41a428ad735e488
Transpilation MD5: c0ab1bdf47921c5f44e28bb1350e9422
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2020-07-17 14:13:08
Source code size: 1695 bytes / 58 lines
Pitched / IR pitched: No / No
Views / Downloads: 186 / 308
Version history: 17 change(s)
Referenced in: [show references]