content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.calcite.runtime;
  
  import com.google.common.collect.Ordering;
  
  import java.util.HashMap;
  import java.util.List;
  
  /**
   * Utilities for space-filling curves.
   *
   * <p>Includes code from
   * <a href="https://github.com/locationtech/sfcurve">LocationTech SFCurve</a>,
   * Copyright (c) 2015 Azavea.
   */
  public interface SpaceFillingCurve2D {
    long toIndex(double x, double y);
    Point toPoint(long i);
    List<IndexRange> toRanges(double xMin, double yMin, double xMax,
        double yMax, RangeComputeHints hints);
  
    /** Hints for the {@link SpaceFillingCurve2D#toRanges} method. */
    class RangeComputeHints extends HashMap<String, Object> {
    }
  
    /** Range. */
    interface IndexRange {
      long lower();
      long upper();
      boolean contained();
  
      IndexRangeTuple tuple();
    }
  
    /** Data representing a range. */
    class IndexRangeTuple {
      final long lower;
      final long upper;
      final boolean contained;
  
      IndexRangeTuple(long lower, long upper, boolean contained) {
        this.lower = lower;
        this.upper = upper;
        this.contained = contained;
      }
    }
  
    /** Base class for Range implementations. */
    abstract class AbstractRange implements IndexRange {
      final long lower;
      final long upper;
  
      protected AbstractRange(long lower, long upper) {
        this.lower = lower;
        this.upper = upper;
      }
  
      @Override public long lower() {
        return lower;
      }
  
      @Override public long upper() {
        return upper;
      }
  
      @Override public IndexRangeTuple tuple() {
        return new IndexRangeTuple(lower, upper, contained());
      }
    }
  
    /** Range that is covered. */
    class CoveredRange extends AbstractRange {
      CoveredRange(long lower, long upper) {
        super(lower, upper);
      }
  
      @Override public boolean contained() {
        return true;
      }
  
      @Override public String toString() {
        return "covered(" + lower + ", " + upper + ")";
      }
    }
  
    /** Range that is not contained. */
    class OverlappingRange extends AbstractRange {
      OverlappingRange(long lower, long upper) {
        super(lower, upper);
      }
  
      @Override public boolean contained() {
        return false;
      }
  
      @Override public String toString() {
        return "overlap(" + lower + ", " + upper + ")";
      }
    }
  
    /** Lexicographic ordering for {@link IndexRange}. */
    class IndexRangeOrdering extends Ordering<IndexRange> {
      @SuppressWarnings("override.param.invalid")
      @Override public int compare(IndexRange x, IndexRange y) {
        final int c1 = Long.compare(x.lower(), y.lower());
        if (c1 != 0) {
          return c1;
        }
        return Long.compare(x.upper(), y.upper());
      }
    }
  
    /** Utilities for {@link IndexRange}. */
    class IndexRanges {
      private IndexRanges() {}
  
      static IndexRange create(long l, long u, boolean contained) {
        return contained ? new CoveredRange(l, u) : new OverlappingRange(l, u);
      }
    }
  
    /** A 2-dimensional point. */
    class Point {
      final double x;
      final double y;
  
      Point(double x, double y) {
        this.x = x;
        this.y = y;
      }
    }
  }
  