/*-------------------------------------------------------------------------+
|                                                                          |
| Copyright 2005-2011 the ConQAT Project                                   |
|                                                                          |
| 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                                  |
|                                                                          |
|    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 eu.cqse.check.framework.shallowparser;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.EnumSet;
import java.util.List;
import java.util.Set;
import java.util.function.BiPredicate;
import java.util.function.Predicate;

import org.conqat.lib.commons.assertion.CCSMAssert;
import org.conqat.lib.commons.collections.CollectionUtils;

import com.google.common.base.Preconditions;

import eu.cqse.check.framework.scanner.ELanguage;
import eu.cqse.check.framework.scanner.ETokenType;
import eu.cqse.check.framework.scanner.ETokenType.ETokenClass;
import eu.cqse.check.framework.scanner.IToken;

/**
 * Utility methods for {@link IToken} lists.
 */
public class TokenStreamUtils {

        /** The value returned if nothing was found in the various find methods. */
        public static final int NOT_FOUND = -1;

        /**
         * Finds the index of the first token in the token list that has any of the of
         * given token types.
         * 
         * <p>
         * For finding sequences, see this method:
         * {@link #firstTokenOfTypeSequence(List, int, int, ETokenType...)}
         * 
         * @return integer index (or {@link #NOT_FOUND}).
         */
        public static int firstTokenOfType(List<IToken> tokens, ETokenType... tokenTypes) {
                return firstTokenOfType(tokens, 0, tokenTypes);
        }

        /**
         * Finds the index of the first token in the token list after startIndex that
         * has any of the of given token types.
         * 
         * <p>
         * For finding sequences, see this method:
         * {@link #firstTokenOfTypeSequence(List, int, int, ETokenType...)}
         * 
         * @return integer index (or {@link #NOT_FOUND}).
         */
        public static int firstTokenOfType(List<IToken> tokens, int startIndex, ETokenType... tokenTypes) {
                return firstTokenOfType(tokens, startIndex, tokens.size(), tokenTypes);
        }

        /**
         * Finds the index of the first token in the token list (not before startIndex
         * and before endIndex) that has any of the of given token types.
         * <p>
         * For finding sequences, see this method:
         * {@link #firstTokenOfTypeSequence(List, int, int, ETokenType...)}
         * 
         * @return integer index (or {@link #NOT_FOUND}).
         */
        public static int firstTokenOfType(List<IToken> tokens, int startIndex, int endIndex, ETokenType... tokenTypes) {
                EnumSet<ETokenType> set = toEnumSet(tokenTypes);
                return firstTokenOfType(tokens, startIndex, endIndex, set);
        }

        /**
         * Finds the index of the first token in the token list (not before startIndex
         * and before endIndex) that has any of the of given token types.
         * <p>
         * For finding sequences, see this method:
         * {@link #firstTokenOfTypeSequence(List, int, int, ETokenType...)}
         *
         * @return integer index (or {@link #NOT_FOUND}).
         */
        public static int firstTokenOfType(List<IToken> tokens, int startIndex, int endIndex, EnumSet<ETokenType> set) {
                assertListRange(tokens, startIndex, endIndex);
                for (int i = startIndex; i < endIndex; ++i) {
                        if (set.contains(tokens.get(i).getType())) {
                                return i;
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Converts the given token types array into an enum set.
         */
        private static EnumSet<ETokenType> toEnumSet(ETokenType... tokenTypes) {
                EnumSet<ETokenType> set = EnumSet.noneOf(ETokenType.class);
                set.addAll(Arrays.asList(tokenTypes));
                return set;
        }

        /**
         * Returns the index of the last token that has any of the given token types (or
         * {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, ETokenType... tokenTypes) {
                return lastTokenOfType(tokens, 0, tokenTypes);
        }

        /**
         * Returns the index of the last token that has any of the given token types (or
         * {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, EnumSet<ETokenType> tokenTypes) {
                return lastTokenOfType(tokens, 0, tokenTypes);
        }

        /**
         * Returns the index of the last token that has any of the given token types not
         * before the start index (or {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, int startIndex, ETokenType... tokenTypes) {
                return lastTokenOfType(tokens, startIndex, tokens.size(), tokenTypes);
        }

        /**
         * Returns the index of the last token that has any of the given token types not
         * before the start index (or {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, int startIndex, EnumSet<ETokenType> tokenTypes) {
                return lastTokenOfType(tokens, startIndex, tokens.size(), tokenTypes);
        }

        /**
         * Returns the index of the last token that has any of the given token types not
         * before the start index and before the end index (or {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, int startIndex, int endIndex, ETokenType... tokenTypes) {
                return lastTokenOfType(tokens, startIndex, endIndex, toEnumSet(tokenTypes));
        }

        /**
         * Returns the index of the last token that has any of the given token types not
         * before the start index and before the end index (or {@link #NOT_FOUND}).
         */
        public static int lastTokenOfType(List<IToken> tokens, int startIndex, int endIndex,
                        EnumSet<ETokenType> tokenTypes) {
                assertListRange(tokens, startIndex, endIndex);

                for (int i = endIndex - 1; i >= startIndex; --i) {
                        if (tokenTypes.contains(tokens.get(i).getType())) {
                                return i;
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the starting index of a element - separator - element type token
         * sequence ending at {@code endOffset} with type {@code element}. Returns
         * {@link #NOT_FOUND} if no such sequence is found. Useful for example for
         * matching qualified names (element=IDENTIFIER, separator=DOT)
         */
        public static int firstTokenOfAlternatingTypes(List<IToken> tokens, int endOffset, ETokenType element,
                        ETokenType separator) {
                Preconditions.checkArgument(endOffset >= 0 && endOffset < tokens.size());
                if (tokens.get(endOffset).getType() != element) {
                        return NOT_FOUND;
                }
                for (int i = endOffset; i >= 0; i -= 2) {
                        if (i >= 1 && TokenStreamUtils.hasTokenTypeSequence(tokens, i - 1, separator, element)) {
                                continue;
                        } else if (tokens.get(i).getType() == element) {
                                return i;
                        }
                        return NOT_FOUND;
                }
                return NOT_FOUND;
        }

        /**
         * Asserts that the given start and end indices lie in between the list range
         * and that the end index is not smaller than the start index.
         */
        private static void assertListRange(List<IToken> tokens, int startIndex, int endIndex) throws AssertionError {
                CCSMAssert.isTrue(startIndex >= 0, "startIndex must be greater or equal to zero");
                CCSMAssert.isTrue(endIndex <= tokens.size(), "endIndex must be less or equal to tokens.size()");
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a token of
         * <code>tokenType<code>, false otherwise.
         */
        public static boolean contains(List<IToken> tokens, ETokenType tokenType) {
                return contains(tokens, 0, tokens.size(), tokenType);
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a token of
         * <code>tokenType<code> in the given range, false otherwise.
         */
        public static boolean contains(List<IToken> tokens, int startIndex, int endIndex, ETokenType tokenType) {
                return firstTokenOfType(tokens, startIndex, endIndex, tokenType) != NOT_FOUND;
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a token of
         * <code>tokenClass<code>, false otherwise.
         */
        public static boolean contains(List<IToken> tokens, ETokenClass tokenClass) {
                for (IToken token : tokens) {
                        if (token.getType().getTokenClass() == tokenClass) {
                                return true;
                        }
                }
                return false;
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a any token of given
         * <code>tokenTypes<code>, false otherwise.
         */
        public static boolean containsAny(List<IToken> tokens, ETokenType... tokenTypes) {
                return containsAny(tokens, 0, tokens.size(), tokenTypes);
        }

        /**
         * Returns <code>true</code> if the given token stream contains one of the
         * tokens in the given set.
         */
        public static boolean containsAny(List<IToken> tokens, EnumSet<ETokenType> tokenTypeSet) {
                return containsAny(tokens, 0, tokens.size(), tokenTypeSet);
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a any token of given
         * <code>tokenTypes<code> in the given range, false otherwise.
         */
        public static boolean containsAny(List<IToken> tokens, int startIndex, int endIndex, ETokenType... tokenTypes) {
                return containsAny(tokens, startIndex, endIndex, toEnumSet(tokenTypes));
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a any token of given
         * <code>tokenTypes<code> in the given range, false otherwise.
         */
        public static boolean containsAny(List<IToken> tokens, int startIndex, int endIndex,
                        EnumSet<ETokenType> tokenTypes) {
                assertListRange(tokens, startIndex, endIndex);
                if (tokenTypes.isEmpty()) {
                        return false;
                }

                for (int i = startIndex; i < endIndex; ++i) {
                        if (tokenTypes.contains(tokens.get(i).getType())) {
                                return true;
                        }
                }
                return false;
        }

        /**
         * Returns <code>true</code> if the list of tokens contains at least one token
         * of each of the given <code>tokenTypes<code>, false otherwise.
         */
        public static boolean containsAll(List<IToken> tokens, ETokenType... tokenTypes) {
                return containsAll(tokens, 0, tokens.size(), tokenTypes);
        }

        /**
         * Returns <code>true</code> if the list of tokens contains at least one token
         * of each of the given <code>tokenTypes<code> in the given range, false
         * otherwise.
         */
        public static boolean containsAll(List<IToken> tokens, int startIndex, int endIndex, ETokenType... tokenTypes) {
                assertListRange(tokens, startIndex, endIndex);

                if (tokenTypes.length == 0) {
                        return true;
                }

                EnumSet<ETokenType> types = toEnumSet(tokenTypes);
                for (int i = startIndex; i < endIndex; ++i) {
                        types.remove(tokens.get(i).getType());
                        if (types.isEmpty()) {
                                return true;
                        }
                }
                return false;
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a consecutive
         * subsequence of tokens that match the sequence of token types., false
         * otherwise.
         */
        public static boolean containsSequence(List<IToken> tokens, int startIndex, int endIndex,
                        ETokenType... tokenTypes) {
                assertListRange(tokens, startIndex, endIndex);

                OUTER: for (int i = startIndex; i <= endIndex - tokenTypes.length; ++i) {
                        for (int j = 0; j < tokenTypes.length; ++j) {
                                if (tokens.get(i + j).getType() != tokenTypes[j]) {
                                        continue OUTER;
                                }
                        }
                        return true;
                }
                return false;
        }

        /**
         * Returns <code>true</code> if the list of tokens contains a consecutive
         * subsequence of tokens that match the sequence of token types., false
         * otherwise.
         */
        public static boolean containsSequence(List<IToken> tokens, ETokenType... tokenTypes) {
                return containsSequence(tokens, 0, tokens.size(), tokenTypes);
        }

        /**
         * Returns the sublist of tokens between the first occurrence of given start
         * token type and the first occurrence of end token type (after start). If one
         * of them is not found, an empty list is returned. The tokens for the start and
         * end are not included in the returned sub list.
         */
        public static List<IToken> tokensBetween(List<IToken> tokens, ETokenType startType, ETokenType endType) {
                return tokensBetween(tokens, EnumSet.of(startType), EnumSet.of(endType));
        }

        /**
         * Returns the sublist of tokens between the first occurrence of some given
         * start token types and the first occurrence of any of the given end token
         * types (after start). If no matches are found, an empty list is returned. The
         * tokens for the start and end are not included in the returned sub list.
         */
        public static List<IToken> tokensBetween(List<IToken> tokens, EnumSet<ETokenType> startTypes,
                        EnumSet<ETokenType> endTypes) {
                int start = TokenStreamUtils.firstTokenOfType(tokens, startTypes.toArray(new ETokenType[0]));
                if (start == NOT_FOUND) {
                        return CollectionUtils.emptyList();
                }
                start += 1;

                int end = TokenStreamUtils.firstTokenOfType(tokens, start, endTypes.toArray(new ETokenType[0]));
                if (end == NOT_FOUND) {
                        return CollectionUtils.emptyList();
                }

                return tokens.subList(start, end);
        }

        /**
         * Returns the offset of the first token of closingType, thereby counting
         * nesting occurrences of openingType and closingType. Returns
         * {@link #NOT_FOUND} if the token before currentOffset isn't equal to the
         * openingType or if no token with closingType was found.
         * 
         * @param currentOffset
         *            this is the offset to start the search and must be one token
         *            <b>after</b> the opening token for which the closing token shall
         *            be found.
         */
        public static int findMatchingClosingToken(List<IToken> tokens, int currentOffset, ETokenType openingType,
                        ETokenType closingType) {
                int nesting = 1;
                for (; currentOffset < tokens.size(); ++currentOffset) {
                        ETokenType tokenType = tokens.get(currentOffset).getType();
                        if (tokenType == openingType) {
                                nesting += 1;
                        } else if (tokenType == closingType) {
                                nesting -= 1;
                                if (nesting == 0) {
                                        return currentOffset;
                                }
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the offset of the first token of closingType, thereby counting
         * nesting occurrences of openingType and closingType. Returns
         * {@link #NOT_FOUND} if none was found.
         * 
         * @param currentOffset
         *            this is the offset to start the search and must be one token
         *            <b>after</b> the opening token for which the closing token shall
         *            be found.
         */
        public static int findMatchingClosingToken(List<IToken> tokens, int currentOffset, EnumSet<ETokenType> openingTypes,
                        EnumSet<ETokenType> closingTypes) {
                int nesting = 1;
                for (; currentOffset < tokens.size(); ++currentOffset) {
                        ETokenType tokenType = tokens.get(currentOffset).getType();
                        if (openingTypes.contains(tokenType)) {
                                nesting += 1;
                        } else if (closingTypes.contains(tokenType)) {
                                nesting -= 1;
                                if (nesting == 0) {
                                        return currentOffset;
                                }
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the offset of the first token of openingType, thereby counting
         * nesting occurrences of openingType and closingType. Returns
         * {@link #NOT_FOUND} if none was found.
         * 
         * @param currentOffset
         *            this is the offset to start the search and must be one token
         *            <b>before</b> the closing token for which the opening token shall
         *            be found.
         */
        public static int findMatchingOpeningToken(List<IToken> tokens, int currentOffset, ETokenType openingType,
                        ETokenType closingType) {
                int openBraces = 1;
                for (; currentOffset >= 0; currentOffset--) {
                        ETokenType currentTokenType = tokens.get(currentOffset).getType();
                        if (currentTokenType.equals(openingType)) {
                                openBraces--;
                        } else if (currentTokenType.equals(closingType)) {
                                openBraces++;
                        }
                        if (openBraces == 0) {
                                return currentOffset;
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the index of the first top-level token that has the given search type
         * regarding the nesting introduced by the opening and closing types. If no such
         * token is found {@link #NOT_FOUND} is returned.
         */
        public static int findFirstTopLevel(List<IToken> tokens, ETokenType searchType, List<ETokenType> openingTypes,
                        List<ETokenType> closingTypes) {
                return findFirstTopLevel(tokens, EnumSet.of(searchType), openingTypes, closingTypes);
        }

        /**
         * Returns the index of the first top-level token that has one of the given
         * search types regarding the nesting introduced by the opening and closing
         * types. If no such token is found {@link #NOT_FOUND} is returned.
         */
        public static int findFirstTopLevel(List<IToken> tokens, EnumSet<ETokenType> searchTypes,
                        List<ETokenType> openingTypes, List<ETokenType> closingTypes) {
                return findFirstTopLevel(tokens, 0, searchTypes, openingTypes, closingTypes);
        }

        /**
         * Returns the index of the first top-level token starting at the given index
         * that has one of the given search types regarding the nesting introduced by
         * the opening and closing types. If no such token is found {@link #NOT_FOUND}
         * is returned.
         */
        public static int findFirstTopLevel(List<IToken> tokens, int startIndex, EnumSet<ETokenType> searchTypes,
                        List<ETokenType> openingTypes, List<ETokenType> closingTypes) {
                return findFirstTopLevel(tokens, startIndex, token -> searchTypes.contains(token.getType()), openingTypes,
                                closingTypes);
        }

        /**
         * Returns the index of the first top-level token starting at the given index
         * that matches the given token predicate regarding the nesting introduced by
         * the opening and closing types. If no such token is found {@link #NOT_FOUND}
         * is returned.
         */
        public static int findFirstTopLevel(List<IToken> tokens, int startIndex, Predicate<IToken> searchPredicate,
                        List<ETokenType> openingTypes, List<ETokenType> closingTypes) {
                CCSMAssert.isTrue(startIndex >= 0, "startIndex must be greater or equal to zero");

                for (NestingAwareTokenIterator iterator = new NestingAwareTokenIterator(tokens, startIndex, openingTypes,
                                closingTypes); iterator.hasNext();) {
                        IToken token = iterator.next();
                        if (iterator.isTopLevel() && searchPredicate.test(token)) {
                                return iterator.getCurrentIndex();
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the index of the first top-level token starting at the given index
         * that matches the given token predicate regarding the nesting introduced by
         * the opening and closing types. If no such token is found {@link #NOT_FOUND}
         * is returned.
         */
        public static int findFirstTopLevelWithIndexPredicate(List<IToken> tokens, int startIndex,
                        Predicate<Integer> searchPredicate, List<ETokenType> openingTypes, List<ETokenType> closingTypes) {
                CCSMAssert.isTrue(startIndex >= 0, "startIndex must be greater or equal to zero");

                for (NestingAwareTokenIterator iterator = new NestingAwareTokenIterator(tokens, startIndex, openingTypes,
                                closingTypes); iterator.hasNext();) {
                        iterator.next();
                        if (iterator.isTopLevel() && searchPredicate.test(iterator.getCurrentIndex())) {
                                return iterator.getCurrentIndex();
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns whether the next tokens starting at the given offset are of given
         * type.
         * 
         * @deprecated use {@link #hasTokenTypeSequence(List, int, ETokenType...)}
         *             instead. I leave the method here to avoid hidden merge conflicts.
         *             Can be removed after some releases.
         */
        @Deprecated
        public static boolean tokenTypesAt(List<IToken> tokens, int startOffset, ETokenType... tokenTypes) {
                return hasTokenTypeSequence(tokens, startOffset, tokenTypes);
        }

        /**
         * Returns whether the given token list starts with given token type sequence.
         */
        public static boolean startsWith(List<IToken> tokens, ETokenType... sequence) {
                return hasTokenTypeSequence(tokens, 0, sequence);
        }

        /**
         * Returns whether the given token list ends with given token type sequence.
         */
        public static boolean endsWith(List<IToken> tokens, ETokenType... sequence) {
                return hasTokenTypeSequence(tokens, tokens.size() - sequence.length, sequence);
        }

        /** Counts the number of tokens of a given type in the list of tokens */
        public static int count(List<IToken> tokens, ETokenType tokenType) {
                int counter = 0;
                for (IToken token : tokens) {
                        if (token.getType().equals(tokenType)) {
                                counter++;
                        }
                }
                return counter;
        }

        /**
         * Counts the number of tokens of a given type in the list of tokens that are
         * not nested between the given nesting tokens.
         */
        public static int countWithoutNesting(List<IToken> tokens, ETokenType tokenType, ETokenType openingType,
                        ETokenType closingType) {
                return countWithoutNesting(tokens, tokenType, Arrays.asList(openingType), Arrays.asList(closingType));
        }

        /**
         * Counts the number of tokens of a given type in the list of tokens that are
         * not nested between the given nesting tokens.
         */
        public static int countWithoutNesting(List<IToken> tokens, ETokenType tokenType, List<ETokenType> openingType,
                        List<ETokenType> closingType) {
                int counter = 0;
                for (NestingAwareTokenIterator iterator = new NestingAwareTokenIterator(tokens, 0, openingType,
                                closingType); iterator.hasNext();) {
                        IToken token = iterator.next();
                        if (iterator.isTopLevel() && token.getType().equals(tokenType)) {
                                counter++;
                        }
                }
                return counter;
        }

        /**
         * Returns all tokens of the given token types in the given token list.
         */
        public static List<IToken> findAllTokens(List<IToken> tokens, EnumSet<ETokenType> types) {
                List<IToken> result = new ArrayList<>();
                for (Integer index : findAll(tokens, 0, tokens.size(), types)) {
                        result.add(tokens.get(index));
                }
                return result;
        }

        /**
         * Returns all indices of the given token types in the given token list.
         */
        public static List<Integer> findAll(List<IToken> tokens, EnumSet<ETokenType> types) {
                return findAll(tokens, 0, tokens.size(), types);
        }

        /**
         * Returns all indices of the given token types in the given token list,
         * beginning from startOffset (inclusive) to endOffset (exclusive).
         */
        public static List<Integer> findAll(List<IToken> tokens, int startOffset, int endOffset,
                        EnumSet<ETokenType> types) {
                CCSMAssert.isTrue(startOffset >= 0, "startOffset must be greater or equal to zero");
                CCSMAssert.isTrue(endOffset <= tokens.size(), "endOffset must be less or equal to tokens.size()");

                List<Integer> indices = new ArrayList<>();
                for (int i = startOffset; i < endOffset; i++) {
                        if (types.contains(tokens.get(i).getType())) {
                                indices.add(i);
                        }
                }
                return indices;
        }

        /** Splits the given token stream at the tokens of the given types. */
        public static List<List<IToken>> split(List<IToken> tokens, EnumSet<ETokenType> splitTypes) {
                return split(tokens, splitTypes, Integer.MAX_VALUE);
        }

        /** Splits the given token stream at the tokens of the given types. */
        public static List<List<IToken>> split(List<IToken> tokens, ETokenType... splitTypes) {
                return split(tokens, toEnumSet(splitTypes), Integer.MAX_VALUE);
        }

        /**
         * Splits the given token stream at the tokens of the given types, but at most
         * as often as given in the limit parameter. The resulting list will have at
         * most <code>limit</code> entries). The limit must be bigger than 0.
         */
        public static List<List<IToken>> split(List<IToken> tokens, EnumSet<ETokenType> splitTypes, int limit) {
                Predicate<IToken> splitTokenMatcher = token -> splitTypes.contains(token.getType());
                return split(tokens, splitTokenMatcher, limit);
        }

        /**
         * Splits the given token stream at the tokens matching the given predicate, but
         * at most as often as given in the limit parameter. The resulting list will
         * have at most <code>limit</code> entries). The limit must be bigger than 0.
         */
        public static List<List<IToken>> split(List<IToken> tokens, Predicate<IToken> splitTokenMatcher, int limit)
                        throws AssertionError {
                CCSMAssert.isTrue(limit > 0, "The limit must be greater than zero");
                List<List<IToken>> parts = new ArrayList<>();
                int start = 0;

                for (int i = 0; i < tokens.size(); i++) {
                        if (parts.size() == limit - 1) {
                                break;
                        }
                        if (splitTokenMatcher.test(tokens.get(i))) {
                                List<IToken> part = tokens.subList(start, i);
                                parts.add(part);
                                start = i + 1;
                        }
                }
                parts.add(tokens.subList(start, tokens.size()));
                return parts;
        }

        /**
         * Returns whether the given token list contains tokens with the given types in
         * that order starting at the given start offset.
         * 
         * This method returns false when called with invalid offsets.
         */
        public static boolean hasTokenTypeSequence(List<IToken> tokens, int startOffset, ETokenType... sequence) {
                if (startOffset + sequence.length > tokens.size() || startOffset < 0) {
                        return false;
                }

                for (int i = 0; i < sequence.length; i++) {
                        if (!tokens.get(i + startOffset).getType().equals(sequence[i])) {
                                return false;
                        }
                }
                return true;
        }

        /**
         * Returns whether an index of the given token list matches the given
         * {@link BiPredicate} (which gets the token index and the given token list).
         */
        public static boolean containsTokenIndexPredicate(List<IToken> tokens,
                        BiPredicate<Integer, List<IToken>> predicate) {
                return firstTokenMatchingIndexPredicate(tokens, 0, predicate) != NOT_FOUND;
        }

        /**
         * Returns the first index of the given token list that matches the given
         * {@link BiPredicate} (which gets the token index and the given token list).
         * This method iterates over the indices starting with the given startIndex.
         */
        public static int firstTokenMatchingIndexPredicate(List<IToken> tokens, int startIndex,
                        BiPredicate<Integer, List<IToken>> predicate) {
                for (int i = startIndex; i < tokens.size(); i++) {
                        if (predicate.test(i, tokens)) {
                                return i;
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the index (between the given start and end indices) of the first
         * token that starts a sequence of the given token types. If no such token is
         * found {@link #NOT_FOUND} is returned.
         */
        public static int firstTokenOfTypeSequence(List<IToken> tokens, int startOffset, int endIndex,
                        ETokenType... sequence) {
                for (int i = startOffset; i < endIndex; i++) {
                        if (hasTokenTypeSequence(tokens, i, sequence)) {
                                return i;
                        }
                }
                return NOT_FOUND;
        }

        /**
         * Returns the indices of all tokens that starts a sequence of the given token
         * types (and are between startOffset and endIndex). If no such token is found,
         * an empty List is returned.
         */
        public static List<Integer> allStartingIndicesOfTypeSequence(List<IToken> tokens, int startOffset, int endIndex,
                        ETokenType... sequence) {
                List<Integer> startingIndices = new ArrayList<>();
                for (int i = startOffset; i < endIndex; i++) {
                        if (hasTokenTypeSequence(tokens, i, sequence)) {
                                startingIndices.add(i);
                        }
                }
                return startingIndices;
        }

        /**
         * Returns the index of the first occurrence of the given sequence of token
         * types in the given token list, beginning from the given start offset. If the
         * sequence if not found, {@link #NOT_FOUND} is returned.
         */
        public static int firstTokenOfTypeSequence(List<IToken> tokens, int startOffset, ETokenType... sequence) {
                return firstTokenOfTypeSequence(tokens, startOffset, tokens.size() - sequence.length + 1, sequence);
        }

        /**
         * Returns all indices of occurrences of the given sequence of token types in
         * the given token list, beginning from the given offset. If the sequence is not
         * found, an empty list is returned.
         */
        public static List<Integer> firstTokenOfTypeSequences(List<IToken> tokens, int offset, ETokenType... sequence) {
                List<Integer> indices = new ArrayList<>();

                while (offset < tokens.size() - sequence.length + 1) {
                        offset = firstTokenOfTypeSequence(tokens, offset, sequence);
                        if (offset == NOT_FOUND) {
                                break;
                        }
                        indices.add(offset);
                        offset++;
                }

                return indices;
        }

        /**
         * Returns whether the given list's token types equal the given token types.
         */
        public static boolean hasTypes(List<IToken> tokens, ETokenType... types) {
                if (tokens.size() != types.length) {
                        return false;
                }

                return hasTokenTypeSequence(tokens, 0, types);
        }

        /**
         * Returns all tokens between the tokens of the opening and closing types
         * regarding nesting.
         */
        public static List<IToken> tokensBetweenWithNesting(List<IToken> tokens, ETokenType openingType,
                        ETokenType closingType) {
                return tokensBetweenWithNesting(tokens, 0, openingType, closingType);
        }

        /**
         * Returns all tokens between the tokens of the opening and closing types
         * regarding nesting beginning from the given start offset.
         */
        public static List<IToken> tokensBetweenWithNesting(List<IToken> tokens, int startOffset, ETokenType openingType,
                        ETokenType closingType) {
                int openingIndex = firstTokenOfType(tokens, startOffset, openingType);
                if (openingIndex == NOT_FOUND) {
                        return CollectionUtils.emptyList();
                }

                openingIndex += 1;
                int closingIndex = findMatchingClosingToken(tokens, openingIndex, openingType, closingType);
                if (closingIndex == NOT_FOUND) {
                        return CollectionUtils.emptyList();
                }

                return tokens.subList(openingIndex, closingIndex);
        }

        /**
         * Splits the given token list at the tokens of the given split type. If the
         * split type is nested between the open and close tokens, it is ignored.
         */
        public static List<List<IToken>> splitWithNesting(List<IToken> tokens, ETokenType splitType, ETokenType openingType,
                        ETokenType closingType) {
                return splitWithNesting(tokens, splitType, Arrays.asList(openingType), Arrays.asList(closingType));
        }

        /**
         * Splits the given token list at the tokens of the given split type. If the
         * split type is nested between one of the open and close tokens, it is ignored.
         * The open and close token type lists must have the same size. None of both
         * must contain duplicates.
         */
        public static List<List<IToken>> splitWithNesting(List<IToken> tokens, ETokenType splitType,
                        List<ETokenType> openingTypes, List<ETokenType> closingTypes) {
                return splitWithNesting(tokens, EnumSet.of(splitType), openingTypes, closingTypes, Integer.MAX_VALUE);
        }

        /**
         * Splits the given token list at the tokens of the given split types. If one of
         * the split types is nested between one of the open and close tokens, it is
         * ignored. The resulting list will have at most limit entries. Limit must be
         * greater zero. The open and close token type lists must have the same size.
         * None of both must contain duplicates.
         */
        public static List<List<IToken>> splitWithNesting(List<IToken> tokens, EnumSet<ETokenType> splitTypes,
                        List<ETokenType> openingTypes, List<ETokenType> closingTypes, int limit) {
                CCSMAssert.isTrue(limit > 0, "The limit must be greater than zero");

                List<List<IToken>> parts = new ArrayList<>();
                int start = 0;
                for (NestingAwareTokenIterator iterator = new NestingAwareTokenIterator(tokens, 0, openingTypes,
                                closingTypes); iterator.hasNext();) {
                        IToken token = iterator.next();
                        if (parts.size() == limit - 1) {
                                break;
                        }
                        if (iterator.isTopLevel() && splitTypes.contains(token.getType())) {
                                List<IToken> part = tokens.subList(start, iterator.getCurrentIndex());
                                parts.add(part);
                                start = iterator.getCurrentIndex() + 1;
                        }
                }

                parts.add(tokens.subList(start, tokens.size()));
                return parts;
        }

        /**
         * Creates a new token from the given referenceToken.
         * 
         * @param referenceToken
         *            Reference token, whose offset, line number and origin id will be
         *            copied to the new token.
         * @param text
         *            Text of the newly created token.
         * @param type
         *            Type of the newly created token.
         * @return New token with the given text and type.
         */
        public static IToken createToken(IToken referenceToken, String text, ETokenType type) {
                return referenceToken.newToken(type, referenceToken.getOffset(), referenceToken.getLineNumber(), text,
                                referenceToken.getOriginId());
        }

        /**
         * Creates a new token list copying the given list and using the given reference
         * token.
         * 
         * @param referenceToken
         *            Reference token, whose offset, line number and origin id will be
         *            copied to the new tokens.
         * @param tokens
         *            List of tokens to be duplicated.
         */
        public static List<IToken> copyTokens(IToken referenceToken, List<IToken> tokens) {
                return CollectionUtils.map(tokens,
                                token -> TokenStreamUtils.createToken(referenceToken, token.getText(), token.getType()));
        }

        /**
         * Adds a new token to the given token list at the given position with the given
         * type and text. The token that is at that position currently is taken as a
         * reference. The new token will have the same offset, origin ID and line number
         * as the reference token.
         * 
         * @param tokens
         *            The token list to modify. Must not be unmodifiable or empty.
         * @param position
         *            The position at which to insert the new token. Also the position
         *            of the reference token. If this is equal to the size of the token
         *            list, the new token will be appended at the end and the last token
         *            will be taken as the reference token.
         * @param type
         *            The token type of the new token.
         * @param text
         *            The text of the new token.
         */
        public static void addToken(List<IToken> tokens, int position, ETokenType type, String text) {
                CCSMAssert.isFalse(tokens.isEmpty(),
                                "Cannot create new tokens without at least one existing token as a reference");
                int referencePosition = position;
                if (position == tokens.size()) {
                        referencePosition--;
                }
                IToken referenceToken = tokens.get(referencePosition);
                IToken newToken = createToken(referenceToken, text, type);
                tokens.add(position, newToken);
        }

        /**
         * Removes the last token of the given token list if it matches the specified
         * token type.
         * 
         * @param tokens
         *            The token list to modify.
         * @param type
         *            Token type, which should be removed.
         * @return The token list without the given token type at the end.
         */
        public static List<IToken> removeAtEnd(List<IToken> tokens, ETokenType type) {
                if (endsWith(tokens, type)) {
                        tokens = tokens.subList(0, tokens.size() - 1);
                }
                return tokens;
        }

        /**
         * Removes the first token of the given token list if it matches the specified
         * token type.
         * 
         * @param tokens
         *            The token list to modify.
         * @param type
         *            Token type, which should be removed.
         * @return The token list without the given token type at the beginning.
         */
        public static List<IToken> removeAtFront(List<IToken> tokens, ETokenType type) {
                if (startsWith(tokens, type)) {
                        tokens = CollectionUtils.getRest(tokens);
                }
                return tokens;
        }

        /**
         * Searches for the first token with the given type and text (ignoring case).
         * 
         * @param tokens
         *            The list of tokens to be searched.
         * @param tokenText
         *            The searched token should have this text (ignoring case).
         * @param tokenTypes
         *            The searched token should have one of these types.
         * @return The first token that matches, null if none is found.
         */
        public static IToken getTokenByTypeAndText(List<IToken> tokens, String tokenText, Set<ETokenType> tokenTypes) {
                for (IToken token : tokens) {
                        if (tokenTypes.contains(token.getType()) && token.getText().equalsIgnoreCase(tokenText)) {
                                return token;
                        }
                }
                return null;
        }

        /**
         * Filters the tokens by type and returns the text of each filtered token.
         * 
         * @param tokens
         *            The list of tokens to be searched.
         * @param tokenType
         *            The type for which filtering is performed.
         * @return A list containing the texts of all tokens of the passed type. Empty
         *         list if no token was found.
         */
        public static List<String> getTokenTextsByType(List<IToken> tokens, ETokenType tokenType) {
                List<String> result = new ArrayList<>();
                for (IToken token : tokens) {
                        if (token.getType() == tokenType) {
                                result.add(token.getText());
                        }
                }
                return result;
        }

        /**
         * Binary search for an {@link IToken} in the given list that has exactly the
         * given offset ({@link IToken#getOffset()}). Assumes that the tokens in the
         * given list are ordered by offset. Returns the index of the found token in the
         * given list or {@value #NOT_FOUND} if no such token is found.
         * 
         * This also works on token lists where offsets are not *strictly* increasing
         * (e.g., due to preprocessor expansions). In this case, returns the index of
         * the first token that has the given offset.
         * 
         * @param tokens
         *            The list of tokens in which to search
         * @param offset
         *            The offset for which the token is to find
         * @return index of the token in the list or {@value #NOT_FOUND}
         */
        public static int indexOfByOffset(List<IToken> tokens, int offset) {
                int leftSearchBoundary = 0;
                int rightSearchBoundary = tokens.size() - 1;
                int matchingIndex = NOT_FOUND;
                while (leftSearchBoundary <= rightSearchBoundary) {
                        int currentIndex = (leftSearchBoundary + rightSearchBoundary) / 2;
                        if (tokens.get(currentIndex).getOffset() < offset) {
                                leftSearchBoundary = currentIndex + 1;
                        } else if (tokens.get(currentIndex).getOffset() > offset) {
                                rightSearchBoundary = currentIndex - 1;
                        } else {
                                matchingIndex = currentIndex;
                                break;
                        }
                }
                if (matchingIndex == NOT_FOUND) {
                        return NOT_FOUND;
                }
                // backtrack to first index that matches the offset (might be more than one
                // consecutive token in presence of preprocessor expansions).
                while (matchingIndex > 0 && tokens.get(matchingIndex - 1).getOffset() == offset) {
                        matchingIndex--;
                }
                return matchingIndex;
        }

        /**
         * Returns the indices of the tokens in the given list that satisfy the given
         * predicate.
         */
        public static List<Integer> indicesOfByPredicate(List<IToken> tokens, Predicate<IToken> includeToken) {
                List<Integer> indices = new ArrayList<>();
                for (int i = 0; i < tokens.size(); i++) {
                        if (includeToken.test(tokens.get(i))) {
                                indices.add(i);
                        }
                }
                return indices;
        }

        /**
         * Returns the {@link ELanguage} of the given tokens (assuming all tokens have
         * the same language). Returns <code>null</code> if the given collection is
         * empty.
         */
        public static ELanguage getLanguage(Collection<IToken> tokens) {
                if (tokens.isEmpty()) {
                        return null;
                }
                return CollectionUtils.getAny(tokens).getLanguage();
        }

        /**
         * Returns a list of tokens existing in the same line of a given token, which
         * specified by its index.
         */
        public static List<IToken> getTokensInSameLine(List<IToken> tokens, int index) {
                int tokenLineNumber = tokens.get(index).getLineNumber();
                int leftIndex = index, rightIndex = index;
                int size = tokens.size() - 1;
                while (leftIndex > 0 && tokens.get(leftIndex - 1).getLineNumber() == tokenLineNumber) {
                        leftIndex--;
                }
                while (rightIndex < size && tokens.get(rightIndex + 1).getLineNumber() == tokenLineNumber) {
                        rightIndex++;
                }
                return tokens.subList(leftIndex, rightIndex + 1);
        }

        /**
         * Checks if the token is the start of a new statement.
         *
         * @param token
         *            The current token.
         * @param lastToken
         *            The previous token.
         * @param continueTokens
         *            Token types that force a statement to continue even in a new line.
         * @param nonContinuationTokens
         *            Token types of class OPERATOR that do not force a statement
         *            continuation.
         * @param newStatementToken
         *            Token that indicates the start of a new statement.
         * @return True if it is the start of a new statement otherwise false.
         */
        public static boolean startsNewStatement(IToken token, IToken lastToken, EnumSet<ETokenType> continueTokens,
                        EnumSet<ETokenType> nonContinuationTokens, ETokenType newStatementToken) {

                if (lastToken == null) {
                        return false;
                }

                if (token == null) {
                        return true;
                }

                ETokenType tokenType = token.getType();
                ETokenType lastTokenType = lastToken.getType();

                if (tokenType == newStatementToken) {
                        return true;
                }

                // E.g.
                // a++
                // b
                // should be treated as two statements.
                // a &&
                // b
                // should be treated as one statement.

                if (!nonContinuationTokens.contains(lastTokenType) && lastTokenType.getTokenClass() == ETokenClass.OPERATOR) {
                        return false;
                }

                if (continueTokens.contains(tokenType) || continueTokens.contains(lastTokenType)) {
                        return false;
                }

                /*
                 * If there is no reason to continue the statement in the next line, end the
                 * statement once the new token is on a new line.
                 */
                return lastToken.getLineNumber() < token.getLineNumber();
        }

}