A NavigableMap inspired class for PHP

Written by Ben Wendt

Java has a nifty class named NavigableMap. It abstracts away some of the logic for mapping ranges to values. Java is reknowned for it’s ridiculously large library of collections.

Here’s a PHP implementation of some of its functionality.

class NavigableMap {
  private $data = array();
  private function checkKeyNumeric($key) {
    if (!is_numeric($key)) {
      throw new Exception("keys must be numeric. Given $key");
    }
  }
  public function put($key, $value) {
    $this->checkKeyNumeric($key);
    $this->data[$key] = $value;
    ksort($this->data);
  }
  public function firstEntry() {
    return key($this->data);
  }
  public function lastEntry() {
    $end = key($this->data);
    reset($this->data);
    return $end;
  }
  public function floorEntry($point) {
    return $this->data[$this->floorKey($point)];
  }
  public function floorKey($point) {
    $this->checkKeyNumeric($point);
    $lowest = $this->firstEntry();
    if ($lowest > $point) {
      throw new OutOfBoundsException("no point exists " .
            "below $point. Lowest map entry is $lowest");
    }
    foreach($this->data as $key => $value) {
      if ($key > $point) {
        return $previous_key;
      }
      $previous_key = $key;
    }
    return $previous_key;
  }
  public function ceilingEntry($point) {
    return $this->data[$this->ceilingKey($point)];
  }
  public function ceilingKey($point) {
    $this->checkKeyNumeric($point);
    $highest = $this->lastEntry();
    if ($highest > $point) {
      throw new OutOfBoundsException("no point exists " .
            "above $point. Highest map entry is $highest");
    }
    $keys = array_reverse(array_keys($this->data));
    foreach($keys as $key) {
      if ($key > $point) {
        return $previous_key;
      }
      $previous_key = $key;
    }
    return $previous_key;
  }
}