sclass MountainsAndValleys {

  settable double[] values;

  gettable new IntBuffer highs;

  gettable new IntBuffer lows;

  *() {}

  *(double[] *values) {}

  run {

    int n = l(values);

    if (n == 0) ret;

    highs.add(0);

    lows.add(0);

    int i = 1;

    while (i < n) {

      // find plateau

      var value = values[i];

      int j = i+1;

      while (j < n && values[j] == value) ++j;

      // are we going up or down?

      var last = values[i-1];

      var list = value > last ? highs : lows;

      //if (list.last() == i-1)

      if (values[list.last()] == last)

        list.popLast();

      list.add(i);

      i = j;

    }

  }

  double get(int idx) { ret values[idx]; }

  // returns position of previous high/low

  // or -1 if not found

  int prev(IntBuffer highsOrLows, int idx) {

    int j = intBufferBinarySearch(highsOrLows, idx-1);

    if (j >= 0) ret idx-1;

    j = -j-1;

    j--;

    ret j >= 0 ? highsOrLows.get(j) : -1;

  }

  // returns position of next high/low

  // or -1 if not found

  int next(IntBuffer highsOrLows, int idx) {

    int j = intBufferBinarySearch(highsOrLows, idx+1);

    if (j >= 0) ret idx+1;

    j = -j-1;

    ret j < l(highsOrLows) ? highsOrLows.get(j) : -1;

  }

  // direction = -1 or 1

  int prevLowerOrHigher(IntBuffer highsOrLows, int idx, int direction) {

    double value = get(idx);

    while (true) {

      int j = prev(highsOrLows, idx);

      if (j < 0 || cmp(get(j), value) == direction) ret j;

      idx = j;

    }

  }

  // direction = -1 or 1

  int nextLowerOrHigher(IntBuffer highsOrLows, int idx, int direction) {

    double value = get(idx);

    while (true) {

      int j = next(highsOrLows, idx);

      if (j < 0 || cmp(get(j), value) == direction) ret j;

      idx = j;

    }

  }

  // all the prev/next methods return -1 if not found

  int prevHigh(int idx) { ret prev(highs, idx); }

  int nextHigh(int idx) { ret next(highs, idx); }

  int prevLow(int idx) { ret prev(lows, idx); }

  int nextLow(int idx) { ret next(lows, idx); }

  int prevLowerHigh(int idx) {

    ret prevLowerOrHigher(highs, idx, 1);

  }

  int prevLowerLow(int idx) {

    ret prevLowerOrHigher(lows, idx, 1);

  }

  int nextLowerHigh(int idx) {

    ret nextLowerOrHigher(highs, idx, 1);

  }

  int nextLowerLow(int idx) {

    ret nextLowerOrHigher(lows, idx, 1);

  }

  int nextLowOrHigh(int idx) {

    int low = nextLow(idx), high = nextHigh(idx);

    ret high < 0 || low < high ? low : high;

  }

}