/*
    * Copyright (c) 2002-2026 Gargoyle Software Inc.
    *
    * Licensed 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
    * https://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.htmlunit.html.impl;
  
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Objects;
  
  import org.apache.commons.lang3.builder.EqualsBuilder;
  import org.htmlunit.SgmlPage;
  import org.htmlunit.html.DomDocumentFragment;
  import org.htmlunit.html.DomNode;
  import org.htmlunit.html.DomNodeList;
  import org.htmlunit.html.DomText;
  import org.w3c.dom.DOMException;
  import org.w3c.dom.DocumentFragment;
  import org.w3c.dom.Node;
  import org.w3c.dom.NodeList;
  
  /**
   * Simple implementation of a DOM Range.
   *
   * @author Marc Guillemot
   * @author Daniel Gredler
   * @author James Phillpotts
   * @author Ahmed Ashour
   * @author Ronald Brill
   */
  public class SimpleRange implements Serializable {
  
      /** The start (anchor) container. */
      private DomNode startContainer_;
  
      /** The end (focus) container. */
      private DomNode endContainer_;
  
      /**
       * The start (anchor) offset; units are chars if the start container is a text node or an
       * input element, DOM nodes otherwise.
       */
      private int startOffset_;
  
      /**
       * The end (focus) offset; units are chars if the end container is a text node or an input
       * element, DOM nodes otherwise.
       */
      private int endOffset_;
  
      /**
       * Constructs an empty range without boundary points.
       */
      public SimpleRange() {
          // Empty.
      }
  
      /**
       * Constructs a range enclosing the contents of the specified node.
       *
       * @param node the node whose contents will be enclosed by this range
       */
      public SimpleRange(final DomNode node) {
          startContainer_ = node;
          endContainer_ = node;
          startOffset_ = 0;
          endOffset_ = getMaxOffset(node);
      }
  
      /**
       * Constructs a collapsed range at the specified offset within a node.
       *
       * @param node the container node for start and end boundaries
       * @param offset the character or node index for both start and end boundaries
       */
      public SimpleRange(final DomNode node, final int offset) {
          startContainer_ = node;
          endContainer_ = node;
          startOffset_ = offset;
          endOffset_ = offset;
      }
  
      /**
       * Constructs a range with the specified start and end boundary points.
       *
       * @param startNode the start container node
      * @param startOffset the start offset within the start node
      * @param endNode the end container node
      * @param endOffset the end offset within the end node
      */
     public SimpleRange(final DomNode startNode, final int startOffset, final DomNode endNode, final int endOffset) {
         startContainer_ = startNode;
         endContainer_ = endNode;
         startOffset_ = startOffset;
         endOffset_ = endOffset;
         if (startNode == endNode && startOffset > endOffset) {
             endOffset_ = startOffset;
         }
     }
 
     /**
      * Duplicates the contents of this range into a document fragment.
      *
      * @return a {@link DomDocumentFragment} containing cloned contents of this range
      */
     public DomDocumentFragment cloneContents() {
         if (isCollapsed()) {
             final SgmlPage page = startContainer_ != null ? startContainer_.getPage() : null;
             return new DomDocumentFragment(page);
         }
 
         // Clone the common ancestor.
         final DomNode ancestor = getCommonAncestorContainer();
         if (ancestor == null) {
             return new DomDocumentFragment(null);
         }
         final DomNode ancestorClone = ancestor.cloneNode(true);
 
         // Find the start container and end container clones.
         DomNode startClone = null;
         DomNode endClone = null;
         final DomNode start = startContainer_;
         final DomNode end = endContainer_;
         if (start == ancestor) {
             startClone = ancestorClone;
         }
         if (end == ancestor) {
             endClone = ancestorClone;
         }
         final Iterable<DomNode> descendants = ancestor.getDescendants();
         if (startClone == null || endClone == null) {
             final Iterator<DomNode> i = descendants.iterator();
             final Iterator<DomNode> ci = ancestorClone.getDescendants().iterator();
             while (i.hasNext()) {
                 final DomNode e = i.next();
                 final DomNode ce = ci.next();
                 if (start == e) {
                     startClone = ce;
                 }
                 if (end == e) {
                     endClone = ce;
                 }
                 if (startClone != null && endClone != null) {
                     break;
                 }
             }
         }
 
         // Do remove from end first so that it can't affect the offset values
 
         // Remove everything following the selection end from the clones.
         if (endClone == null) {
             throw new IllegalStateException("Unable to find end node clone.");
         }
         deleteAfter(endClone, endOffset_);
         for (DomNode n = endClone; n != null && n != ancestorClone; n = n.getParentNode()) {
             while (n.getNextSibling() != null) {
                 n.getNextSibling().remove();
             }
         }
 
         // Remove everything prior to the selection start from the clones.
         if (startClone == null) {
             throw new IllegalStateException("Unable to find start node clone.");
         }
         deleteBefore(startClone, startOffset_);
         for (DomNode n = startClone; n != null && n != ancestorClone; n = n.getParentNode()) {
             while (n.getPreviousSibling() != null) {
                 n.getPreviousSibling().remove();
             }
         }
 
         final SgmlPage page = ancestor.getPage();
         final DomDocumentFragment fragment = new DomDocumentFragment(page);
 
         // Append text node clone directly, or append child nodes for element containers
         if (start == end && isOffsetChars(start)) {
             fragment.appendChild(ancestorClone);
         }
         else {
             for (final DomNode n : new ArrayList<>(ancestorClone.getChildNodes())) {
                 fragment.appendChild(n);
             }
         }
         return fragment;
     }
 
     /**
      * Produces a new {@code SimpleRange} with boundary points identical to this range.
      *
      * @return a cloned instance of this range
      */
     public SimpleRange cloneRange() {
         return new SimpleRange(startContainer_, startOffset_, endContainer_, endOffset_);
     }
 
     /**
      * Collapses this range onto one of its boundary points.
      *
      * @param toStart if {@code true}, collapses the range to its start boundary;
      *                otherwise collapses it to its end boundary
      */
     public void collapse(final boolean toStart) {
         if (toStart) {
             endContainer_ = startContainer_;
             endOffset_ = startOffset_;
         }
         else {
             startContainer_ = endContainer_;
             startOffset_ = endOffset_;
         }
     }
 
     /**
      * Removes the contents of this range from the document tree.
      */
     public void deleteContents() {
         final DomNode ancestor = getCommonAncestorContainer();
         if (ancestor != null) {
             deleteContents(ancestor);
         }
     }
 
     private void deleteContents(final DomNode ancestor) {
         // Handle single text/input node deletion separately
         if (startContainer_ == endContainer_ && isOffsetChars(startContainer_)) {
             final String text = getText(startContainer_);
             if (startOffset_ < text.length() && endOffset_ <= text.length()) {
                 final String newText = text.substring(0, startOffset_) + text.substring(endOffset_);
                 setText(startContainer_, newText);
             }
             return;
         }
 
         final DomNode start;
         if (isOffsetChars(startContainer_)) {
             start = startContainer_;
             String text = getText(start);
             if (startOffset_ > -1 && startOffset_ < text.length()) {
                 text = text.substring(0, startOffset_);
             }
             setText(start, text);
         }
         else if (startContainer_.getChildNodes().getLength() > startOffset_) {
             start = (DomNode) startContainer_.getChildNodes().item(startOffset_);
         }
         else {
             start = startContainer_.getNextSibling();
         }
 
         final DomNode end;
         if (isOffsetChars(endContainer_)) {
             end = endContainer_;
             String text = getText(end);
             if (endOffset_ > -1 && endOffset_ <= text.length()) {
                 text = text.substring(endOffset_);
             }
             setText(end, text);
         }
         else if (endContainer_.getChildNodes().getLength() > endOffset_) {
             end = (DomNode) endContainer_.getChildNodes().item(endOffset_);
         }
         else {
             end = endContainer_.getNextSibling();
         }
 
         boolean foundStart = false;
         boolean started = false;
         final Iterator<DomNode> i = ancestor.getDescendants().iterator();
         while (i.hasNext()) {
             final DomNode n = i.next();
             if (n == end) {
                 break;
             }
             if (n == start) {
                 foundStart = true;
             }
             if (foundStart && (n != start || !isOffsetChars(startContainer_))) {
                 started = true;
             }
             if (started
                     && !n.isAncestorOf(end)
                     && n != endContainer_
                     && !n.isAncestorOf(endContainer_)
                     && n != startContainer_
                     && !n.isAncestorOf(startContainer_)) {
                 i.remove();
             }
         }
     }
 
     /**
      * Moves the contents of this range from the document tree into a new DocumentFragment.
      *
      * @return a {@link DomDocumentFragment} containing the extracted contents
      */
     public DomDocumentFragment extractContents() throws DOMException {
         final DomDocumentFragment fragment = cloneContents();
 
         // Remove everything inside the range from the original nodes.
         deleteContents();
 
         // Build the document fragment using the cloned nodes, and return it.
         return fragment;
     }
 
     /**
      * Indicates whether this range is collapsed (start boundary equals end boundary).
      *
      * @return {@code true} if start container equals end container and start offset equals end offset
      */
     public boolean isCollapsed() {
         return startContainer_ != null
                 && startContainer_ == endContainer_
                 && startOffset_ == endOffset_;
     }
 
     /**
      * Returns the deepest common ancestor container of this range's boundary points.
      * <p>
      * Uses a two-pointer algorithm that requires O(1) memory by avoiding collections
      * like {@code HashSet}. If the two boundary nodes are at different depths in the tree,
      * switching pointers to the opposite starting node when hitting {@code null} aligns
      * their paths so both pointers travel the exact same total distance
      * ({@code depth(start) + depth(end)}).
      * </p>
      *
      * @return the lowest common ancestor {@link DomNode}, or {@code null} if either
      *         boundary point is {@code null} or they belong to disconnected trees
      */
     public DomNode getCommonAncestorContainer() {
         if (startContainer_ == null || endContainer_ == null) {
             return null;
         }
 
         DomNode n1 = startContainer_;
         DomNode n2 = endContainer_;
 
         // Traverse upwards towards root. When a pointer reaches null (root's parent),
         // redirect it to the other node's start container.
         //
         // Path length for n1: startContainer -> root -> endContainer -> LCA
         // Path length for n2: endContainer   -> root -> startContainer -> LCA
         //
         // Because addition is commutative, both pointers cover equal total steps
         // and will land on the common ancestor (or null, if disconnected) at the same time.
         while (n1 != n2) {
             n1 = (n1 == null) ? endContainer_ : n1.getParentNode();
             n2 = (n2 == null) ? startContainer_ : n2.getParentNode();
         }
 
         return n1;
     }
 
     /**
      * Returns the node within which this range ends.
      *
      * @return the Node within which this range ends
      */
     public DomNode getEndContainer() {
         return endContainer_;
     }
 
     /**
      * Returns the offset within the end container.
      *
      * @return offset within the ending node of this
      */
     public int getEndOffset() {
         return endOffset_;
     }
 
     /**
      * Returns the node within which this range begins.
      *
      * @return the Node within which this range begins
      */
     public DomNode getStartContainer() {
         return startContainer_;
     }
 
     /**
      * Returns the offset within the start container.
      *
      * @return offset within the starting node of this
      */
     public int getStartOffset() {
         return startOffset_;
     }
 
     /**
      * Inserts a node into the Document or DocumentFragment at the start of
      * the Range. If the container is a Text node, this will be split at the
      * start of the Range (as if the Text node's splitText method was
      * performed at the insertion point) and the insertion will occur
      * between the two resulting Text nodes. Adjacent Text nodes will not be
      * automatically merged. If the node to be inserted is a
      * DocumentFragment node, the children will be inserted rather than the
      * DocumentFragment node itself.
      * @param newNode The node to insert at the start of the Range
      */
     public void insertNode(final DomNode newNode) {
         if (startContainer_ instanceof DomText textNode) {
             final DomText secondPart = textNode.splitText(startOffset_);
             final DomNode parent = textNode.getParentNode();
             insertNodeOrDocFragment(parent, newNode, secondPart);
         }
         else if (isOffsetChars(startContainer_)) {
             final DomNode split = startContainer_.cloneNode(false);
             String text = getText(startContainer_);
             if (startOffset_ > -1 && startOffset_ < text.length()) {
                 text = text.substring(0, startOffset_);
             }
             setText(startContainer_, text);
             text = getText(split);
             if (startOffset_ > -1 && startOffset_ <= text.length()) {
                 text = text.substring(startOffset_);
             }
             setText(split, text);
             insertNodeOrDocFragment(startContainer_.getParentNode(), split, startContainer_.getNextSibling());
             insertNodeOrDocFragment(startContainer_.getParentNode(), newNode, split);
         }
         else {
             insertNodeOrDocFragment(startContainer_, newNode,
                     (DomNode) startContainer_.getChildNodes().item(startOffset_));
         }
 
         setStart(newNode, 0);
     }
 
     private static void insertNodeOrDocFragment(final DomNode parent, final DomNode newNode, final DomNode refNode) {
         if (newNode instanceof DocumentFragment fragment) {
 
             final NodeList childNodes = fragment.getChildNodes();
             while (childNodes.getLength() > 0) {
                 final Node item = childNodes.item(0);
                 parent.insertBefore(item, refNode);
             }
         }
         else {
             parent.insertBefore(newNode, refNode);
         }
     }
 
     /**
      * Select a node and its contents.
      * @param node The node to select.
      */
     public void selectNode(final DomNode node) {
         final DomNode parent = node.getParentNode();
         startContainer_ = parent;
         endContainer_ = parent;
         // find node's index among parent's children
         int index = 0;
         DomNode sibling = node.getPreviousSibling();
         while (sibling != null) {
             index++;
             sibling = sibling.getPreviousSibling();
         }
         startOffset_ = index;
         endOffset_ = index + 1;
     }
 
     /**
      * Select the contents within a node.
      * @param node Node to select from
      */
     public void selectNodeContents(final DomNode node) {
         startContainer_ = node;
         startOffset_ = 0;
         endContainer_ = node;
         endOffset_ = getMaxOffset(node);
     }
 
     /**
      * Sets the end boundary point of this range.
      *
      * @param refNode the end container node
      * @param offset the offset within the end node
      */
     public void setEnd(final DomNode refNode, final int offset) {
         endContainer_ = refNode;
         endOffset_ = offset;
     }
 
     /**
      * Sets the start boundary point of this range.
      *
      * @param refNode the start container node
      * @param offset the offset within the start node
      */
     public void setStart(final DomNode refNode, final int offset) {
         startContainer_ = refNode;
         startOffset_ = offset;
     }
 
     /**
      * Reparents the contents of the Range to the given node and inserts the
      * node at the position of the start of the Range.
      * <p>
      * Per the DOM spec, throws an {@code InvalidStateError} if any non-Text
      * node is only partially contained by the range (i.e. the range's start
      * or end boundary splits an element, leaving one boundary tag inside the
      * range and the other outside). A range that spans only Text nodes, or
      * that fully encloses every element it touches, is always valid.
      * </p>
      *
      * @param newParent the node to surround the contents with
      * @throws DOMException {@code INVALID_STATE_ERR} if any non-Text node is
      *     partially contained in this range
      */
     public void surroundContents(final DomNode newParent) {
         if (hasPartiallyContainedNonTextNode()) {
             throw new DOMException(DOMException.INVALID_STATE_ERR, "The range partially contains a non-Text node.");
         }
 
         newParent.appendChild(extractContents());
         insertNode(newParent);
         setStart(newParent, 0);
         setEnd(newParent, getMaxOffset(newParent));
     }
 
     /**
      * Returns whether any non-Text node in the tree is "partially contained"
      * by this range -- meaning it is an ancestor of exactly one boundary
      * container, not both. Text nodes are explicitly exempted by the spec.
      */
     private boolean hasPartiallyContainedNonTextNode() {
         if (startContainer_ == null || endContainer_ == null) {
             return false;
         }
         if (startContainer_ == endContainer_) {
             return false;
         }
 
         // Collect all ancestors of the start container (excluding the common
         // ancestor itself, which by definition contains both sides)
         final DomNode common = getCommonAncestorContainer();
 
         // walk up from start -- any non-Text ancestor that is NOT also an
         // ancestor of end (i.e. stops at or before the common ancestor) is
         // partially contained
         DomNode n = startContainer_.getParentNode();
         while (n != null && n != common) {
             if (!(n instanceof DomText)) {
                 return true;
             }
             n = n.getParentNode();
         }
 
         // walk up from end -- same check from the other side
         n = endContainer_.getParentNode();
         while (n != null && n != common) {
             if (!(n instanceof DomText)) {
                 return true;
             }
             n = n.getParentNode();
         }
 
         return false;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public boolean equals(final Object obj) {
         if (!(obj instanceof SimpleRange other)) {
             return false;
         }
         return new EqualsBuilder()
             .append(startContainer_, other.startContainer_)
             .append(endContainer_, other.endContainer_)
             .append(startOffset_, other.startOffset_)
             .append(endOffset_, other.endOffset_).isEquals();
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public int hashCode() {
         return Objects.hash(startContainer_, endContainer_, startOffset_, endOffset_);
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public String toString() {
         final DomDocumentFragment fragment = cloneContents();
         if (fragment.getPage() != null) {
             return fragment.asNormalizedText();
         }
         return "";
     }
 
     private static boolean isOffsetChars(final DomNode node) {
         return node instanceof DomText || node instanceof SelectableTextInput;
     }
 
     private static String getText(final DomNode node) {
         if (node instanceof SelectableTextInput input) {
             return input.getText();
         }
         return node.getTextContent();
     }
 
     private static void setText(final DomNode node, final String text) {
         if (node instanceof SelectableTextInput input) {
             input.setText(text);
         }
         else {
             node.setTextContent(text);
         }
     }
 
     private static void deleteBefore(final DomNode node, int offset) {
         if (isOffsetChars(node)) {
             String text = getText(node);
             if (offset > -1 && offset < text.length()) {
                 text = text.substring(offset);
             }
             else {
                 text = "";
             }
             setText(node, text);
         }
         else {
             final DomNodeList<DomNode> children = node.getChildNodes();
             for (int i = 0; i < offset && i < children.getLength(); i++) {
                 final DomNode child = children.get(i);
 
                 child.remove();
                 // Removing item at index i shifts the live list left; decrement both
                 // i and offset so the loop re-examines the new item at this position
                 // rather than skipping it.
                 i--;
                 offset--;
             }
         }
     }
 
     private static void deleteAfter(final DomNode node, final int offset) {
         if (isOffsetChars(node)) {
             String text = getText(node);
             if (offset > -1 && offset < text.length()) {
                 text = text.substring(0, offset);
                 setText(node, text);
             }
         }
         else {
             final DomNodeList<DomNode> children = node.getChildNodes();
             for (int i = offset; i < children.getLength(); i++) {
                 final DomNode child = children.get(i);
                 child.remove();
                 i--;
             }
         }
     }
 
     private static int getMaxOffset(final DomNode node) {
         return isOffsetChars(node) ? getText(node).length() : node.getChildNodes().getLength();
     }
 
     /**
      * Returns the nodes fully contained within this range in document order.
      *
      * @return a list with all nodes contained in this range
      */
     public List<DomNode> containedNodes() {
         final DomNode ancestor = getCommonAncestorContainer();
         if (ancestor == null) {
             return Collections.emptyList();
         }
 
         if (startContainer_ == endContainer_ && isOffsetChars(startContainer_)) {
             return Collections.singletonList(startContainer_);
         }
 
         final DomNode start;
         if (isOffsetChars(startContainer_)) {
             start = startContainer_;
         }
         else if (startContainer_.getChildNodes().getLength() > startOffset_) {
             start = (DomNode) startContainer_.getChildNodes().item(startOffset_);
         }
         else {
             start = startContainer_.getNextSibling();
         }
 
         final DomNode end;
         if (isOffsetChars(endContainer_)) {
             end = endContainer_;
         }
         else if (endContainer_.getChildNodes().getLength() > endOffset_) {
             end = (DomNode) endContainer_.getChildNodes().item(endOffset_);
         }
         else {
             end = endContainer_.getNextSibling();
         }
 
         boolean foundStart = false;
         boolean started = false;
         final List<DomNode> nodes = new ArrayList<>();
         for (final DomNode n : ancestor.getDescendants()) {
             if (n == end) {
                 break;
             }
             if (n == start) {
                 foundStart = true;
             }
             if (foundStart && (n != start || !isOffsetChars(startContainer_))) {
                 started = true;
             }
             if (started
                     && !n.isAncestorOf(end)
                     && n != endContainer_
                     && !n.isAncestorOf(endContainer_)
                     && n != startContainer_
                     && !n.isAncestorOf(startContainer_)) {
                 nodes.add(n);
             }
         }
         return nodes;
     }
 }