001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.text.diff;
018
019import java.util.ArrayList;
020import java.util.List;
021
022/**
023 * This class handles sequences of replacements resulting from a comparison.
024 * <p>
025 * The comparison of two objects sequences leads to the identification of common
026 * parts and parts which only belong to the first or to the second sequence. The
027 * common parts appear in the edit script in the form of <em>keep</em> commands,
028 * they can be considered as synchronization objects between the two sequences.
029 * These synchronization objects split the two sequences in synchronized
030 * sub-sequences. The first sequence can be transformed into the second one by
031 * replacing each synchronized sub-sequence of the first sequence by the
032 * corresponding sub-sequence of the second sequence. This is a synthetic way to
033 * see an {@link EditScript edit script}, replacing individual
034 * {@link DeleteCommand delete}, {@link KeepCommand keep} and
035 * {@link InsertCommand insert} commands by fewer replacements acting on
036 * complete sub-sequences.
037 * </p>
038 * <p>
039 * This class is devoted to perform this interpretation. It visits an
040 * {@link EditScript edit script} (because it implements the
041 * {@link CommandVisitor CommandVisitor} interface) and calls a user-supplied
042 * handler implementing the {@link ReplacementsHandler ReplacementsHandler}
043 * interface to process the sub-sequences.
044 * </p>
045 *
046 * @see ReplacementsHandler
047 * @see EditScript
048 * @see StringsComparator
049 *
050 * @param <T> object type
051 * @since 1.0
052 */
053public class ReplacementsFinder<T> implements CommandVisitor<T> {
054
055    /**
056     * List of pending insertions.
057     */
058    private final List<T> pendingInsertions;
059
060    /**
061     * List of pending deletions.
062     */
063    private final List<T> pendingDeletions;
064
065    /**
066     * Count of elements skipped.
067     */
068    private int skipped;
069
070    /** Handler to call when synchronized sequences are found. */
071    private final ReplacementsHandler<T> handler;
072
073    /**
074     * Constructs a new instance of {@link ReplacementsFinder}.
075     *
076     * @param handler  handler to call when synchronized sequences are found
077     */
078    public ReplacementsFinder(final ReplacementsHandler<T> handler) {
079        pendingInsertions = new ArrayList<>();
080        pendingDeletions  = new ArrayList<>();
081        skipped           = 0;
082        this.handler      = handler;
083    }
084
085    /**
086     * Add an object to the pending deletions set.
087     *
088     * @param object  object to delete
089     */
090    @Override
091    public void visitDeleteCommand(final T object) {
092        pendingDeletions.add(object);
093    }
094
095    /**
096     * Add an object to the pending insertions set.
097     *
098     * @param object  object to insert
099     */
100    @Override
101    public void visitInsertCommand(final T object) {
102        pendingInsertions.add(object);
103    }
104
105    /**
106     * Handle a synchronization object.
107     * <p>
108     * When a synchronization object is identified, the pending insertions and
109     * pending deletions sets are provided to the user handler as subsequences.
110     * </p>
111     *
112     * @param object  synchronization object detected
113     */
114    @Override
115    public void visitKeepCommand(final T object) {
116        if (pendingDeletions.isEmpty() && pendingInsertions.isEmpty()) {
117            ++skipped;
118        } else {
119            handler.handleReplacement(skipped, pendingDeletions, pendingInsertions);
120            pendingDeletions.clear();
121            pendingInsertions.clear();
122            skipped = 1;
123        }
124    }
125
126}