SitePoint Sponsor

User Tag List

Results 1 to 3 of 3
  1. #1
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,684
    Mentioned
    99 Post(s)
    Tagged
    4 Thread(s)

    Are there more expressive ways to do <, =, > conditions than if/elseif/else ?

    I'm using an iterative binary search to help find some stuff, and am wondering if anyone knows of a more expressive way to perform these greater than, equal to or less than statements.

    Code javascript:
    ...
    while (low <= high && position === -1) {
        mid = Math.floor((low + high) / 2);
        if (haystack[mid] > needle) {
            high = mid - 1;
        } else if (haystack[mid] < needle) {
            low = mid + 1;
        } else {
            position = mid;
        }
    }

    If we use (haystack[mid] - needle) we can then end up with a condition that's either positive, equal to, or negative; but other than going recursive on things, are there more expressive ways to make use of this kind of condition other than an if/elseif/else construct?
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  2. #2
    Utopia, Inc. silver trophy
    ScallioXTX's Avatar
    Join Date
    Aug 2008
    Location
    The Netherlands
    Posts
    9,031
    Mentioned
    152 Post(s)
    Tagged
    2 Thread(s)
    How about this?

    Code javascript:
    ...
    while (low <= high && position === -1) {
        mid = Math.floor((low + high) / 2);
        diff = haystack[mid] - needle;
        position = mid + Math.max(-1, Math.min(diff, 1));
    }

    Basically I'm taking the difference between haystack[mid] and needle and then clamp it on the open interval (-1, 1) and then add that to position.
    End effect is the same as your code, but without (explicit) if/then/else.

    Are more readable version:

    Code javascript:
    function clamp(val, min, max) {
        return Math.max(min, Math.min(val, max))
    }
    ...
    while (low <= high && position === -1) {
        mid = Math.floor((low + high) / 2);
        diff = haystack[mid] - needle;
        position = mid + clamp(diff, -1, 1);
    }
    Rémon - Hosting Advisor

    Minimal Bookmarks Tree
    My Google Chrome extension: browsing bookmarks made easy

  3. #3
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,684
    Mentioned
    99 Post(s)
    Tagged
    4 Thread(s)
    Clamping is a good way to get a -1/0/+1 value, but without low or high being adjusted, means that we loop forever over the same area.

    So, while using clamping we now end up with the following code:

    Code javascript:
    while (low <= high && position === -1) {
        mid = Math.floor((low + high) / 2);
        direction = clamp(needle - haystack[mid], -1, 1);
        newPosition = mid + direction;
        switch (direction) {
        case +1:
            low = newPosition;
            break;
        case -1:
            high = newPosition;
            break;
        case 0:
            position = newPosition;
            break;
        default:
            // do nothing
        }
    }

    Can we refactor so this so that high and/or low are given in terms of mid, direction, and possibly distance? I'll give that a shot.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •