JavaStringUtils.java

Go to the documentation of this file.

// -*- mode: java; c-basic-offset: 2; -*-
// Copyright 2017-2020  MIT, All rights reserve
// Released under the Apache License, Version 2.0
// http://www.apache.org/licenses/LICENSE-2.0
 
package com.google.appinventor.components.runtime.util;
 
import android.util.Log;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class JavaStringUtils {
  private static class MappingOrder {
    public void changeOrder(List<String> keys, String text) {
      // Default option: Do nothing (dictionary order)
    }
  }
 
  private static class MappingLongestStringFirstOrder extends MappingOrder {
    @Override
    public void changeOrder(List<String> keys, String text) {
      Collections.sort(keys, new Comparator<String>() {
        @Override
        public int compare(String s, String t1) {
          // Sort in descending order of string length
          return Integer.compare(t1.length(), s.length());
        }
      });
    }
  }
 
  private static class MappingEarliestOccurrenceFirstOrder extends MappingOrder {
    @Override
    public void changeOrder(List<String> keys, String text) {
      // Construct a map for first index of occurrence for String
      final Map<String, Integer> occurrenceIndices = new HashMap<>();
 
      // TODO: Can we optimize the O(mn) loop with m = length of text,
      // TODO: n = number of keys?
      for (String key : keys) {
        int firstIndex = text.indexOf(key);
 
        // No first index; Key should gain less priority than
        // other occurrences (this value can be arbitrary)
        if (firstIndex == -1) {
          firstIndex = text.length() + occurrenceIndices.size();
        }
 
        // Map key to first index of occurrence
        occurrenceIndices.put(key, firstIndex);
      }
 
      Collections.sort(keys, new Comparator<String>() {
        @Override
        public int compare(String s, String t1) {
          // Sort in ascending order by first index in String
          int id1 = occurrenceIndices.get(s);
          int id2 = occurrenceIndices.get(t1);
 
          if (id1 == id2) {
            // Use longer string instead if indices equal
            return Integer.compare(t1.length(), s.length());
          } else {
            // Take smaller index first
            return Integer.compare(id1, id2);
          }
        }
      });
    }
  }
 
  private static class Range {
    int start;   // Inclusive start index
    int end;     // Exclusive end index
    String text; // Replacement text
 
    public Range(int start, int end, String text) {
      this.start = start;
      this.end = end;
      this.text = text;
    }
  }
  /*
   * Range comparator that sorts ranges in descending order of range
   * end times. Overlapping ranges are considered equal by the comparator.
   */
  private static class RangeComparator implements Comparator<Range> {
    @Override
    public int compare(Range r1, Range r2) {
      // First, test for overlap. We do this by taking the maximum
      // start point of a range, and the minimum end point of a range.
      int maxStart = Math.max(r1.start, r2.start);
      int minEnd = Math.min(r1.end, r2.end);
 
      // If maxStart <= minEnd, the ranges overlap (or touch). Since the
      // min end index is exclusive, we take the strictly less < instead,
      // since the ranges could touch (due to the end ID being overlapping)
      if (maxStart < minEnd) {
        // Ranges overlap. Consider them equal, thus not inserting a new range.
        return 0;
      } else {
        // Ranges unequal. Sort by endpoint in descending order to get the last
        // range first in the TreeSet.
        return Integer.compare(r2.end, r1.end);
      }
    }
  }
 
  public static final String LOG_TAG_JOIN_STRINGS = "JavaJoinListOfStrings";
  private static final boolean DEBUG = false;
 
  private static final MappingOrder mappingOrderDictionary = new MappingOrder();
  private static final MappingOrder mappingOrderLongestStringFirst = new MappingLongestStringFirstOrder();
  private static final MappingOrder mappingOrderEarliestOccurrence = new MappingEarliestOccurrenceFirstOrder();
  private static final Comparator<Range> rangeComparator = new RangeComparator();
 
  public static String joinStrings(List<Object> listOfStrings, String separator) {
    // We would use String.join, but that is Java 8
    if (DEBUG) {
      Log.i(LOG_TAG_JOIN_STRINGS, "calling joinStrings");
    }
    return join(listOfStrings, separator);
  }
 
  private static String join(List<Object> list, String separator)
  {
    StringBuilder sb = new StringBuilder();
    boolean first = true;
    for (Object item : list)
    {
      if (first)
        first = false;
      else
        sb.append(separator);
      sb.append(item.toString());
    }
    return sb.toString();
  }
 
  public static String replaceAllMappingsDictionaryOrder(String text, Map<Object, Object> mappings) {
    return replaceAllMappings(text, mappings, mappingOrderDictionary);
  }
 
  public static String replaceAllMappingsLongestStringOrder(String text, Map<Object, Object> mappings) {
    return replaceAllMappings(text, mappings, mappingOrderLongestStringFirst);
  }
 
  public static String replaceAllMappingsEarliestOccurrenceOrder(String text, Map<Object, Object> mappings) {
    return replaceAllMappings(text, mappings, mappingOrderEarliestOccurrence);
  }
 
  public static String replaceAllMappings(String text, Map<Object, Object> mappings, MappingOrder order) {
    // Iterate over all the mappings
    Iterator<Map.Entry<Object, Object>> it = mappings.entrySet().iterator();
 
    // Construct a new map for <String, String> mappings in order to support
    // look-ups for non-pure String values (e.g. numbers)
    Map<String, String> stringMappings = new HashMap<>();
 
    // Construct a new List to store the Map's keys
    List<String> keys = new ArrayList<>();
 
    while (it.hasNext()) {
      Map.Entry<Object, Object> current = it.next();
 
      // Get Key & Value as strings
      // This is needed to convert any non-String values to a String,
      // e.g. numbers to String literals
      String key = current.getKey().toString();
      String value = current.getValue().toString();
 
      // Add key only if it was not added before (to reduce potential
      // redundancy on potentially duplicate keys)
      if (!stringMappings.containsKey(key)) {
        keys.add(key);
      }
 
      // Update map
      stringMappings.put(key, value);
    }
 
    // Change the order of the keys based on the given Order object
    // TODO: If we have stream support, we can sort the stringMappings map
    // TODO: directly provided we initialize it to a LinkedHashMap.
    // TODO: It could save some memory in the long run.
    order.changeOrder(keys, text);
 
    // Apply mappings owith re-ordered keys and mappings
    return applyMappings(text, stringMappings, keys);
  }
 
  private static String applyMappings(String text, Map<String, String> mappings, List<String> keys) {
    // Create a set of ranges to keep track of which index ranges in the
    // original text string are already set for replacement, together with the
    // text to replace with. We sort this TreeSet in descending order to preserve
    // indices of all ranges after replacement.
    TreeSet<Range> ranges = new TreeSet<Range>(rangeComparator);
 
    // Range construction step: Iterate through all the keys,
    // and fill in ranges set & replacements map.
    for (String key : keys) {
      // Convert key to pattern, and create a matcher to find all
      // occurrences of the current string.
      Pattern keyPattern = Pattern.compile(Pattern.quote(key));
      Matcher matcher =  keyPattern.matcher(text);
 
      // Keep track of the String to replace key with
      String replacement = mappings.get(key);
 
      // Iterate until the key can no longer be found in text.
      while (matcher.find()) {
        // Get start & end indices of the string to be replaced.
        int startId = matcher.start();
        int endId = matcher.end();
 
        // Create a closed open range (closed since startId is inclusive,
        // and open because endId is exclusive), and add the range
        // to our TreeSet of ranges. If the range is already covered (i.e.
        // there exists an overlapping range), it is simply not added.
        Range range = new Range(startId, endId, replacement);
        ranges.add(range);
      }
    }
 
    // Go through each entry that we want to replace. Since we used
    // a TreeSet, we have an order that will not break things;
    // We first replace the substring with the largest end index, which,
    // because of overlap, will not affect the previous range indices
    // because no ranges overlap in our range set.
    // If we did not have this order, then we would have to update all indices
    // of all ranges upon replacement.
    for (Range range : ranges) {
      // Combine strings: L + M + R, where:
      // L - substring from start of string until endpoint
      // M - middle string (the one that we use as replacement)
      // R - remainder of the string after replacement
      String left = text.substring(0, range.start);
      String middle = range.text;
      String end = text.substring(range.end);
      text = left + middle + end;
    }
 
    return text;
  }
}