fork download
copy 
  1. import java.util.Arrays;
  2. import java.util.Optional;
  3. import java.util.SortedSet;
  4. import java.util.TreeSet;
  5.  
  6. public class Main {
  7.  
  8.     public static void main(final String[] args) {
  9.         final SortedSet<String> set = new TreeSet<>();
  10.         set.addAll(Arrays.asList("foo", "bar", "baz", "bip"));
  11.  
  12.         for (int i = 0; i <= 4; ++i) {
  13.             final String prefix = "bark".substring(0, i);
  14.             System.out.printf("Strings starting with %-7s %s%n", "\"" + prefix + "\":",
  15.                     getElementsWithPrefix(set, prefix));
  16.         }
  17.     }
  18.  
  19.     /**
  20.      * @param prefix
  21.      * @return The least string that's greater than all strings starting with
  22.      *         prefix, if one exists. Otherwise, returns Optional.empty().
  23.      *         (Specifically, returns Optional.empty() if the prefix is the
  24.      *         empty string, or is just a sequence of Character.MAX_VALUE-s.)
  25.      */
  26.     private static Optional<String> incrementPrefix(final String prefix) {
  27.         final StringBuilder sb = new StringBuilder(prefix);
  28.  
  29.         // remove any trailing occurrences of Character.MAX_VALUE:
  30.         while (sb.length() > 0 && sb.charAt(sb.length() - 1) == Character.MAX_VALUE) {
  31.             sb.setLength(sb.length() - 1);
  32.         }
  33.  
  34.         // if the prefix is empty, then there's no upper bound:
  35.         if (sb.length() == 0) {
  36.             return Optional.empty();
  37.         }
  38.  
  39.         // otherwise, increment the last character and return the result:
  40.         sb.setCharAt(sb.length() - 1, (char) (sb.charAt(sb.length() - 1) + 1));
  41.         return Optional.of(sb.toString());
  42.     }
  43.  
  44.     /**
  45.      * @param allElements - a SortedSet of strings. This set must use the
  46.      *                      natural string ordering; otherwise this method
  47.      *                      may not behave as intended.
  48.      * @param prefix
  49.      * @return The subset of allElements containing the strings that start
  50.      *         with prefix.
  51.      */
  52.     private static SortedSet<String> getElementsWithPrefix(
  53.             final SortedSet<String> allElements, final String prefix) {
  54.  
  55.         final Optional<String> endpoint = incrementPrefix(prefix);
  56.  
  57.         if (endpoint.isPresent()) {
  58.             return allElements.subSet(prefix, endpoint.get());
  59.         } else {
  60.             return allElements.tailSet(prefix);
  61.         }
  62.     }
  63. }
Success #stdin #stdout 0.05s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Strings starting with "":     [bar, baz, bip, foo]
Strings starting with "b":    [bar, baz, bip]
Strings starting with "ba":   [bar, baz]
Strings starting with "bar":  [bar]
Strings starting with "bark": []
https://ideone.com/YvO4b3
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!