text: import binarySearch from "./binarySearch.js";
  import Cartographic from "./Cartographic.js";
  import defined from "./defined.js";
  import Rectangle from "./Rectangle.js";
  
  /**
   * Reports the availability of tiles in a {@link TilingScheme}.
   *
   * @alias TileAvailability
   * @constructor
   *
   * @param {TilingScheme} tilingScheme The tiling scheme in which to report availability.
   * @param {Number} maximumLevel The maximum tile level that is potentially available.
   */
  function TileAvailability(tilingScheme, maximumLevel) {
    this._tilingScheme = tilingScheme;
    this._maximumLevel = maximumLevel;
  
    this._rootNodes = [];
  }
  
  var rectangleScratch = new Rectangle();
  
  function findNode(level, x, y, nodes) {
    var count = nodes.length;
    for (var i = 0; i < count; ++i) {
      var node = nodes[i];
      if (node.x === x && node.y === y && node.level === level) {
        return true;
      }
    }
  
    return false;
  }
  
  /**
   * Marks a rectangular range of tiles in a particular level as being available.  For best performance,
   * add your ranges in order of increasing level.
   *
   * @param {Number} level The level.
   * @param {Number} startX The X coordinate of the first available tiles at the level.
   * @param {Number} startY The Y coordinate of the first available tiles at the level.
   * @param {Number} endX The X coordinate of the last available tiles at the level.
   * @param {Number} endY The Y coordinate of the last available tiles at the level.
   */
  TileAvailability.prototype.addAvailableTileRange = function (
    level,
    startX,
    startY,
    endX,
    endY
  ) {
    var tilingScheme = this._tilingScheme;
  
    var rootNodes = this._rootNodes;
    if (level === 0) {
      for (var y = startY; y <= endY; ++y) {
        for (var x = startX; x <= endX; ++x) {
          if (!findNode(level, x, y, rootNodes)) {
            rootNodes.push(new QuadtreeNode(tilingScheme, undefined, 0, x, y));
          }
        }
      }
    }
  
    tilingScheme.tileXYToRectangle(startX, startY, level, rectangleScratch);
    var west = rectangleScratch.west;
    var north = rectangleScratch.north;
  
    tilingScheme.tileXYToRectangle(endX, endY, level, rectangleScratch);
    var east = rectangleScratch.east;
    var south = rectangleScratch.south;
  
    var rectangleWithLevel = new RectangleWithLevel(
      level,
      west,
      south,
      east,
      north
    );
  
    for (var i = 0; i < rootNodes.length; ++i) {
      var rootNode = rootNodes[i];
      if (rectanglesOverlap(rootNode.extent, rectangleWithLevel)) {
        putRectangleInQuadtree(this._maximumLevel, rootNode, rectangleWithLevel);
      }
    }
  };
  
  /**
   * Determines the level of the most detailed tile covering the position.  This function
   * usually completes in time logarithmic to the number of rectangles added with
   * {@link TileAvailability#addAvailableTileRange}.
   *
   * @param {Cartographic} position The position for which to determine the maximum available level.  The height component is ignored.
   * @return {Number} The level of the most detailed tile covering the position.
   * @throws {DeveloperError} If position is outside any tile according to the tiling scheme.
   */
  TileAvailability.prototype.computeMaximumLevelAtPosition = function (position) {
    // Find the root node that contains this position.
    var node;
    for (var nodeIndex = 0; nodeIndex < this._rootNodes.length; ++nodeIndex) {
      var rootNode = this._rootNodes[nodeIndex];
      if (rectangleContainsPosition(rootNode.extent, position)) {
        node = rootNode;
        break;
      }
    }
  
    if (!defined(node)) {
      return -1;
    }
  
    return findMaxLevelFromNode(undefined, node, position);
  };
  
  var rectanglesScratch = [];
  var remainingToCoverByLevelScratch = [];
  var westScratch = new Rectangle();
  var eastScratch = new Rectangle();
  
  /**
   * Finds the most detailed level that is available _everywhere_ within a given rectangle.  More detailed
   * tiles may be available in parts of the rectangle, but not the whole thing.  The return value of this
   * function may be safely passed to {@link sampleTerrain} for any position within the rectangle.  This function
   * usually completes in time logarithmic to the number of rectangles added with
   * {@link TileAvailability#addAvailableTileRange}.
   *
   * @param {Rectangle} rectangle The rectangle.
   * @return {Number} The best available level for the entire rectangle.
   */
  TileAvailability.prototype.computeBestAvailableLevelOverRectangle = function (
    rectangle
  ) {
    var rectangles = rectanglesScratch;
    rectangles.length = 0;
  
    if (rectangle.east < rectangle.west) {
      // Rectangle crosses the IDL, make it two rectangles.
      rectangles.push(
        Rectangle.fromRadians(
          -Math.PI,
          rectangle.south,
          rectangle.east,
          rectangle.north,
          westScratch
        )
      );
      rectangles.push(
        Rectangle.fromRadians(
          rectangle.west,
          rectangle.south,
          Math.PI,
          rectangle.north,
          eastScratch
        )
      );
    } else {
      rectangles.push(rectangle);
    }
  
    var remainingToCoverByLevel = remainingToCoverByLevelScratch;
    remainingToCoverByLevel.length = 0;
  
    var i;
    for (i = 0; i < this._rootNodes.length; ++i) {
      updateCoverageWithNode(
        remainingToCoverByLevel,
        this._rootNodes[i],
        rectangles
      );
    }
  
    for (i = remainingToCoverByLevel.length - 1; i >= 0; --i) {
      if (
        defined(remainingToCoverByLevel[i]) &&
        remainingToCoverByLevel[i].length === 0
      ) {
        return i;
      }
    }
  
    return 0;
  };
  
  var cartographicScratch = new Cartographic();
  
  /**
   * Determines if a particular tile is available.
   * @param {Number} level The tile level to check.
   * @param {Number} x The X coordinate of the tile to check.
   * @param {Number} y The Y coordinate of the tile to check.
   * @return {Boolean} True if the tile is available; otherwise, false.
   */
  TileAvailability.prototype.isTileAvailable = function (level, x, y) {
    // Get the center of the tile and find the maximum level at that position.
    // Because availability is by tile, if the level is available at that point, it
    // is sure to be available for the whole tile.  We assume that if a tile at level n exists,
    // then all its parent tiles back to level 0 exist too.  This isn't really enforced
    // anywhere, but Cesium would never load a tile for which this is not true.
    var rectangle = this._tilingScheme.tileXYToRectangle(
      x,
      y,
      level,
      rectangleScratch
    );
    Rectangle.center(rectangle, cartographicScratch);
    return this.computeMaximumLevelAtPosition(cartographicScratch) >= level;
  };
  
  /**
   * Computes a bit mask indicating which of a tile's four children exist.
   * If a child's bit is set, a tile is available for that child.  If it is cleared,
   * the tile is not available.  The bit values are as follows:
   * <table>
   *     <tr><th>Bit Position</th><th>Bit Value</th><th>Child Tile</th></tr>
   *     <tr><td>0</td><td>1</td><td>Southwest</td></tr>
   *     <tr><td>1</td><td>2</td><td>Southeast</td></tr>
   *     <tr><td>2</td><td>4</td><td>Northwest</td></tr>
   *     <tr><td>3</td><td>8</td><td>Northeast</td></tr>
   * </table>
   *
   * @param {Number} level The level of the parent tile.
   * @param {Number} x The X coordinate of the parent tile.
   * @param {Number} y The Y coordinate of the parent tile.
   * @return {Number} The bit mask indicating child availability.
   */
  TileAvailability.prototype.computeChildMaskForTile = function (level, x, y) {
    var childLevel = level + 1;
    if (childLevel >= this._maximumLevel) {
      return 0;
    }
  
    var mask = 0;
  
    mask |= this.isTileAvailable(childLevel, 2 * x, 2 * y + 1) ? 1 : 0;
    mask |= this.isTileAvailable(childLevel, 2 * x + 1, 2 * y + 1) ? 2 : 0;
    mask |= this.isTileAvailable(childLevel, 2 * x, 2 * y) ? 4 : 0;
    mask |= this.isTileAvailable(childLevel, 2 * x + 1, 2 * y) ? 8 : 0;
  
    return mask;
  };
  
  function QuadtreeNode(tilingScheme, parent, level, x, y) {
    this.tilingScheme = tilingScheme;
    this.parent = parent;
    this.level = level;
    this.x = x;
    this.y = y;
    this.extent = tilingScheme.tileXYToRectangle(x, y, level);
  
    this.rectangles = [];
    this._sw = undefined;
    this._se = undefined;
    this._nw = undefined;
    this._ne = undefined;
  }
  
  Object.defineProperties(QuadtreeNode.prototype, {
    nw: {
      get: function () {
        if (!this._nw) {
          this._nw = new QuadtreeNode(
            this.tilingScheme,
            this,
            this.level + 1,
            this.x * 2,
            this.y * 2
          );
        }
        return this._nw;
      },
    },
  
    ne: {
      get: function () {
        if (!this._ne) {
          this._ne = new QuadtreeNode(
            this.tilingScheme,
            this,
            this.level + 1,
            this.x * 2 + 1,
            this.y * 2
          );
        }
        return this._ne;
      },
    },
  
    sw: {
      get: function () {
        if (!this._sw) {
          this._sw = new QuadtreeNode(
            this.tilingScheme,
            this,
            this.level + 1,
            this.x * 2,
            this.y * 2 + 1
          );
        }
        return this._sw;
      },
    },
  
    se: {
      get: function () {
        if (!this._se) {
          this._se = new QuadtreeNode(
            this.tilingScheme,
            this,
            this.level + 1,
            this.x * 2 + 1,
            this.y * 2 + 1
          );
        }
        return this._se;
      },
    },
  });
  
  function RectangleWithLevel(level, west, south, east, north) {
    this.level = level;
    this.west = west;
    this.south = south;
    this.east = east;
    this.north = north;
  }
  
  function rectanglesOverlap(rectangle1, rectangle2) {
    var west = Math.max(rectangle1.west, rectangle2.west);
    var south = Math.max(rectangle1.south, rectangle2.south);
    var east = Math.min(rectangle1.east, rectangle2.east);
    var north = Math.min(rectangle1.north, rectangle2.north);
    return south < north && west < east;
  }
  
  function putRectangleInQuadtree(maxDepth, node, rectangle) {
    while (node.level < maxDepth) {
      if (rectangleFullyContainsRectangle(node.nw.extent, rectangle)) {
        node = node.nw;
      } else if (rectangleFullyContainsRectangle(node.ne.extent, rectangle)) {
        node = node.ne;
      } else if (rectangleFullyContainsRectangle(node.sw.extent, rectangle)) {
        node = node.sw;
      } else if (rectangleFullyContainsRectangle(node.se.extent, rectangle)) {
        node = node.se;
      } else {
        break;
      }
    }
  
    if (
      node.rectangles.length === 0 ||
      node.rectangles[node.rectangles.length - 1].level <= rectangle.level
    ) {
      node.rectangles.push(rectangle);
    } else {
      // Maintain ordering by level when inserting.
      var index = binarySearch(
        node.rectangles,
        rectangle.level,
        rectangleLevelComparator
      );
      if (index < 0) {
        index = ~index;
      }
      node.rectangles.splice(index, 0, rectangle);
    }
  }
  
  function rectangleLevelComparator(a, b) {
    return a.level - b;
  }
  
  function rectangleFullyContainsRectangle(potentialContainer, rectangleToTest) {
    return (
      rectangleToTest.west >= potentialContainer.west &&
      rectangleToTest.east <= potentialContainer.east &&
      rectangleToTest.south >= potentialContainer.south &&
      rectangleToTest.north <= potentialContainer.north
    );
  }
  
  function rectangleContainsPosition(potentialContainer, positionToTest) {
    return (
      positionToTest.longitude >= potentialContainer.west &&
      positionToTest.longitude <= potentialContainer.east &&
      positionToTest.latitude >= potentialContainer.south &&
      positionToTest.latitude <= potentialContainer.north
    );
  }
  
  function findMaxLevelFromNode(stopNode, node, position) {
    var maxLevel = 0;
  
    // Find the deepest quadtree node containing this point.
    var found = false;
    while (!found) {
      var nw = node._nw && rectangleContainsPosition(node._nw.extent, position);
      var ne = node._ne && rectangleContainsPosition(node._ne.extent, position);
      var sw = node._sw && rectangleContainsPosition(node._sw.extent, position);
      var se = node._se && rectangleContainsPosition(node._se.extent, position);
  
      // The common scenario is that the point is in only one quadrant and we can simply
      // iterate down the tree.  But if the point is on a boundary between tiles, it is
      // in multiple tiles and we need to check all of them, so use recursion.
      if (nw + ne + sw + se > 1) {
        if (nw) {
          maxLevel = Math.max(
            maxLevel,
            findMaxLevelFromNode(node, node._nw, position)
          );
        }
        if (ne) {
          maxLevel = Math.max(
            maxLevel,
            findMaxLevelFromNode(node, node._ne, position)
          );
        }
        if (sw) {
          maxLevel = Math.max(
            maxLevel,
            findMaxLevelFromNode(node, node._sw, position)
          );
        }
        if (se) {
          maxLevel = Math.max(
            maxLevel,
            findMaxLevelFromNode(node, node._se, position)
          );
        }
        break;
      } else if (nw) {
        node = node._nw;
      } else if (ne) {
        node = node._ne;
      } else if (sw) {
        node = node._sw;
      } else if (se) {
        node = node._se;
      } else {
        found = true;
      }
    }
  
    // Work up the tree until we find a rectangle that contains this point.
    while (node !== stopNode) {
      var rectangles = node.rectangles;
  
      // Rectangles are sorted by level, lowest first.
      for (
        var i = rectangles.length - 1;
        i >= 0 && rectangles[i].level > maxLevel;
        --i
      ) {
        var rectangle = rectangles[i];
        if (rectangleContainsPosition(rectangle, position)) {
          maxLevel = rectangle.level;
        }
      }
  
      node = node.parent;
    }
  
    return maxLevel;
  }
  
  function updateCoverageWithNode(
    remainingToCoverByLevel,
    node,
    rectanglesToCover
  ) {
    if (!node) {
      return;
    }
  
    var i;
    var anyOverlap = false;
    for (i = 0; i < rectanglesToCover.length; ++i) {
      anyOverlap =
        anyOverlap || rectanglesOverlap(node.extent, rectanglesToCover[i]);
    }
  
    if (!anyOverlap) {
      // This node is not applicable to the rectangle(s).
      return;
    }
  
    var rectangles = node.rectangles;
    for (i = 0; i < rectangles.length; ++i) {
      var rectangle = rectangles[i];
  
      if (!remainingToCoverByLevel[rectangle.level]) {
        remainingToCoverByLevel[rectangle.level] = rectanglesToCover;
      }
  
      remainingToCoverByLevel[rectangle.level] = subtractRectangle(
        remainingToCoverByLevel[rectangle.level],
        rectangle
      );
    }
  
    // Update with child nodes.
    updateCoverageWithNode(remainingToCoverByLevel, node._nw, rectanglesToCover);
    updateCoverageWithNode(remainingToCoverByLevel, node._ne, rectanglesToCover);
    updateCoverageWithNode(remainingToCoverByLevel, node._sw, rectanglesToCover);
    updateCoverageWithNode(remainingToCoverByLevel, node._se, rectanglesToCover);
  }
  
  function subtractRectangle(rectangleList, rectangleToSubtract) {
    var result = [];
    for (var i = 0; i < rectangleList.length; ++i) {
      var rectangle = rectangleList[i];
      if (!rectanglesOverlap(rectangle, rectangleToSubtract)) {
        // Disjoint rectangles.  Original rectangle is unmodified.
        result.push(rectangle);
      } else {
        // rectangleToSubtract partially or completely overlaps rectangle.
        if (rectangle.west < rectangleToSubtract.west) {
          result.push(
            new Rectangle(
              rectangle.west,
              rectangle.south,
              rectangleToSubtract.west,
              rectangle.north
            )
          );
        }
        if (rectangle.east > rectangleToSubtract.east) {
          result.push(
            new Rectangle(
              rectangleToSubtract.east,
              rectangle.south,
              rectangle.east,
              rectangle.north
            )
          );
        }
        if (rectangle.south < rectangleToSubtract.south) {
          result.push(
            new Rectangle(
              Math.max(rectangleToSubtract.west, rectangle.west),
              rectangle.south,
              Math.min(rectangleToSubtract.east, rectangle.east),
              rectangleToSubtract.south
            )
          );
        }
        if (rectangle.north > rectangleToSubtract.north) {
          result.push(
            new Rectangle(
              Math.max(rectangleToSubtract.west, rectangle.west),
              rectangleToSubtract.north,
              Math.min(rectangleToSubtract.east, rectangle.east),
              rectangle.north
            )
          );
        }
      }
    }
  
    return result;
  }
  export default TileAvailability;
  