private Multimap<Scope, String> getClassnames(final ASTNode node) {
	final ClassnameFinder cf = new ClassnameFinder(methodsAsRoots);
	node.accept(cf);

	final Multimap<Scope, String> classnames = TreeMultimap.create();

	for (final Entry<ASTNode, String> classname : cf.types.entries()) {
		final ASTNode parentNode = classname.getKey();
		final Scope sc = new Scope(
				classname.getKey().toString(),
				parentNode.getNodeType() == ASTNode.METHOD_DECLARATION ? ScopeType.SCOPE_METHOD
						: ScopeType.SCOPE_CLASS, TYPENAME,
				parentNode.getNodeType(), -1);
		classnames.put(sc, classname.getValue());
	}
	return classnames;
}
 

/**
 * Return a multimap containing all the (local) variables of the given
 * scope.
 * 
 * @param cu
 * @return Multimap<Snippet, VariableName>
 */
public static Multimap<Scope, String> getScopeSnippets(final ASTNode cu) {
	final VariableScopeFinder scopeFinder = new VariableScopeFinder();
	cu.accept(scopeFinder);

	final Multimap<Scope, String> scopes = TreeMultimap.create();
	for (final Entry<ASTNode, Variable> variable : scopeFinder.variableScopes
			.entries()) {
		final int astNodeType = variable.getKey().getNodeType();
		final int astNodeParentType;
		if (variable.getKey().getParent() == null) {
			astNodeParentType = -1;
		} else {
			astNodeParentType = variable.getKey().getParent().getNodeType();
		}
		scopes.put(
				new Scope(variable.getKey().toString(),
						variable.getValue().scope,
						variable.getValue().type, astNodeType,
						astNodeParentType), variable.getValue().name);
	}

	return scopes;

}
 

static TreeMultimap<String,IndexStream> nextAll(String key, Collection<IndexStream> streams) {
    TreeMultimap<String,IndexStream> newChildren = TreeMultimap.create(Ordering.natural(), Ordering.arbitrary());
    for (IndexStream itr : streams) {
        if (!isDay(key) && isDay(key(itr.peek()))) {
            newChildren.put(itr.peek().first(), itr);
        } else {
            itr.next();
            if (itr.hasNext()) {
                newChildren.put(itr.peek().first(), itr);
            } else {
                return TreeMultimap.create(Ordering.natural(), Ordering.arbitrary());
            }
        }
    }
    return newChildren;
}
 

public static Multimap<Scope, String> getScopeSnippets(final ASTNode node,
		final boolean methodAsRoots) {
	final ScopeFinder scopeFinder = new ScopeFinder(methodAsRoots);
	node.accept(scopeFinder);

	final Multimap<Scope, String> scopes = TreeMultimap.create();
	for (final Entry<ASTNode, Method> method : scopeFinder.methods
			.entries()) {
		scopes.put(new Scope(method.getKey().toString(),
				method.getValue().type, METHOD_CALL, 0, 0), method
				.getValue().name);
	}

	return scopes;

}
 

public void build() {
    groups = TreeMultimap.create(new Comparator<String>() {
        public int compare(String string1, String string2) {
            return string1.compareToIgnoreCase(string2);
        }
    }, new Comparator<TaskDetails>() {
        public int compare(TaskDetails task1, TaskDetails task2) {
            return task1.getPath().compareTo(task2.getPath());
        }
    });
    for (TaskReportModel project : projects) {
        for (String group : project.getGroups()) {
            for (final TaskDetails task : project.getTasksForGroup(group)) {
                groups.put(group, mergeTasksWithSameName ? new MergedTaskDetails(task) : task);
            }
        }
    }
}
 

/**
 * Allows creators of this iterator to defer creating the sorted mapping of values to iterators until some condition is met. This is intended to let us
 * build the tree of iterators in <code>init()</code> and defer sorting the iterators until after <code>seek()</code> is called.
 */
public void initialize() {
    Comparator<T> keyComp = Util.keyComparator();
    // nestedIteratorComparator will keep a deterministic ordering, unlike hashCodeComparator
    Comparator<NestedIterator<T>> itrComp = Util.nestedIteratorComparator();
    
    transformer = Util.keyTransformer();
    transforms = new HashMap<>();
    
    includeHeads = TreeMultimap.create(keyComp, itrComp);
    initSubtree(includeHeads, includes, transformer, transforms, false);
    
    if (contextIncludes.size() > 0) {
        contextIncludeHeads = TreeMultimap.create(keyComp, itrComp);
        contextIncludeNullHeads = TreeMultimap.create(keyComp, itrComp);
    }
    
    if (contextExcludes.size() > 0) {
        contextExcludeHeads = TreeMultimap.create(keyComp, itrComp);
        contextExcludeNullHeads = TreeMultimap.create(keyComp, itrComp);
    }
    
    next();
}
 

/**
 * Process moves against the set of sources. Set the context and move each. Will update the headMap with new references except for null responses. A null
 * response indicates that the iterator had no key's left when moving to context
 * 
 * @param context
 * @param sourcesToMove
 * @param headMap
 * @param transformer
 * @param <T>
 * @return non-null Set of null response iterators
 */
private static <T> Set<NestedIterator<T>> processMoves(T context, Set<NestedIterator<T>> sourcesToMove, TreeMultimap<T,NestedIterator<T>> headMap,
                Util.Transformer<T> transformer) {
    Set<NestedIterator<T>> nullSources = new HashSet<>();
    for (NestedIterator<T> contextRequiredIterator : sourcesToMove) {
        contextRequiredIterator.setContext(context);
        T result = contextRequiredIterator.move(context);
        if (result == null) {
            // beyond the end of the iterator
            nullSources.add(contextRequiredIterator);
        } else {
            T transformed = transformer.transform(result);
            headMap.put(transformed, contextRequiredIterator);
        }
    }
    
    return nullSources;
}
 

@Test
public void test() throws Throwable {
    List<String> filterSet1 = Lists.newArrayList("a", "b", "c", "q", "r", "s");
    Itr<String> f1 = new Itr<>(filterSet1);
    List<String> filterSet2 = Lists.newArrayList("a", "b", "c", "d", "e", "f");
    Itr<String> f2 = new Itr<>(filterSet2);
    TreeMultimap<String,NestedIterator<String>> mmap = TreeMultimap.create(Util.keyComparator(), Util.hashComparator());
    mmap.put(f1.next(), f1);
    mmap.put(f2.next(), f2);
    
    assertTrue(NegationFilter.isFiltered("e", mmap, Util.keyTransformer()));
    assertEquals(2, mmap.keySet().size());
    assertNotEquals(null, mmap.get("e"));
    assertNotEquals(null, mmap.get("q"));
    assertEquals(2, mmap.values().size());
}
 

public static void main(String... args) {
  // Clear saved state for new calls.
  tree = TreeMultimap.create();
  astLookup = Sets.newHashSet();
  ClassPath cp = null;
  try {
    cp = ClassPath.from(ClassLoader.getSystemClassLoader());
  } catch (IOException e) {
    ErrorUtil.error(e.getMessage());
    System.exit(1);
  }
  for (ClassInfo c : cp.getTopLevelClasses("org.eclipse.jdt.core.dom")){
    astLookup.add(c.getSimpleName());
  }
  for (ClassInfo ci : cp.getTopLevelClasses("com.google.devtools.j2objc.ast")) {
    // Ignore package-info and JUnit tests.
    if (ci.getSimpleName().equals("package-info") || TestCase.class.isAssignableFrom(ci.load())) {
      continue;
    }
    walkSuperclassHierarchy(ci.load());
  }
  // Print hierarchy descending from Object.
  printClassHierarchy("Object", "");
}
 

@Test
public void testContains() throws Throwable {
    List<String> filterSet1 = Lists.newArrayList("a", "b");
    Itr<String> f1 = new Itr<>(filterSet1);
    List<String> filterSet2 = Lists.newArrayList("a", "b", "c", "d", "e", "f");
    Itr<String> f2 = new Itr<>(filterSet2);
    TreeMultimap<String,NestedIterator<String>> mmap = TreeMultimap.create(Util.keyComparator(), Util.hashComparator());
    mmap.put(f1.next(), f1);
    mmap.put("c", f2);
    
    assertTrue(NegationFilter.isFiltered("c", mmap, Util.keyTransformer()));
    // even though filterSet1 is outside the bounds, the contains check doesn't move anything, this is expected and good
    assertEquals(2, mmap.keySet().size());
    Iterator<String> i = mmap.keySet().iterator();
    assertEquals("a", i.next());
    assertEquals("c", i.next());
    assertFalse(i.hasNext());
    assertEquals(2, mmap.values().size());
}
 

public static Collection<AddressSpecHash> getAddressesByAge(WalletDatabase db, NetworkParams params)
{
  TreeMultimap<Long, AddressSpecHash> age_map = TreeMultimap.create();
  for(AddressSpec spec : db.getAddressesList())
  {
    String addr = AddressUtil.getAddressString(spec, params);
    long tm = 0;
    if (db.getAddressCreateTimeMap().containsKey(addr))
    {
      tm = db.getAddressCreateTimeMap().get(addr);
    }
    age_map.put(tm, AddressUtil.getHashForSpec(spec));

  }

  return age_map.values();

}
 

/**
 * Encodes dimensions multimap to filter strings.
 *
 * @param filters dimensions multimap
 * @return filter string fragments
 */
public static List<String> encodeDimensions(Multimap<String, String> filters) {
  List<String> output = new ArrayList<>();

  Multimap<String, String> sorted = TreeMultimap.create(filters);
  for(Map.Entry<String, String> entry : sorted.entries()) {
    String operator = "=";
    String value = entry.getValue();

    // check for exclusion case
    for (Map.Entry<String, String> prefix : FILTER_TO_OPERATOR.entrySet()) {
      if (entry.getValue().startsWith(prefix.getKey())) {
        operator = prefix.getValue();
        value = entry.getValue().substring(prefix.getKey().length());
        break;
      }
    }

    output.add(EntityUtils.encodeURNComponent(String.format("%s%s%s", entry.getKey(), operator, value)));
  }

  return output;
}
 

@Override
public void addAll(TreeMultimap<ByteString, ByteString> map)
{
  try(WriteBatch batch = new WriteBatch())
  {
    byte b[]=new byte[0];

    for(Map.Entry<ByteString, ByteString> me : map.entries())
    {
      ByteString w = getDBKey(me.getKey(), me.getValue());
      batch.put(w.toByteArray(), b);
    }

    db.write(jdb.getWriteOption(), batch);
  }
  catch(RocksDBException e)
  {
    throw new RuntimeException(e);
  }

}
 

/**
 * Read each line of input, tokenize them into key/value pairs, perform a lookup/transformation of the keys via the
 * MetadataDictionary where applicable, and return the results as a map.
 * 
 * @param input the bytes to convert
 * @param output a ByteArrayOutputStream to write failed parse attempts to
 * @return a Map containing each line converted to a key/value pair and sorted alphabetically by key
 * @throws IOException If there is some I/O problem.
 */
public Map<String, Collection<String>> convertLinesToMap(final byte[] input, final ByteArrayOutputStream output) throws IOException {
    final TreeMultimap<String, String> kv = TreeMultimap.create();
    final LineTokenizer ltok = new LineTokenizer(input, this.charset);

    // Look at each line for a key value and run it through the dictionary
    while (ltok.hasMoreTokens()) {
        final String line = ltok.nextToken();
        final int pos = line.indexOf(SEP);
        if (pos == -1) {
            output.write(line.getBytes());
            output.write('\n');
            this.logger.debug("Found no key/value pair on line " + line);
        } else {
            final String key = line.substring(0, pos);
            final String value = line.substring(pos + 1);
            final String nkey = this.dict.map(this.servicePrefix + key);
            kv.put(nkey, value.trim());
            this.logger.debug("Mapped key " + key + " to " + nkey + ": " + value);
        }
    }
    return new TreeMap<>(kv.asMap());
}
 

@Override
public String visitObjectLiteral(ObjectLiteral node, Void context) {
    StringBuilder builder = new StringBuilder("{");
    boolean first = true;
    TreeMultimap<String, Expression> sorted = TreeMultimap.create(
            Ordering.natural().nullsLast(),
            Ordering.usingToString().nullsLast()
    );
    sorted.putAll(node.values());
    for (Map.Entry<String, Expression> entry : sorted.entries()) {
        if (!first) {
            builder.append(", ");
        } else {
            first = false;
        }
        builder.append(formatIdentifier(entry.getKey()))
               .append("= ")
               .append(entry.getValue().accept(this, context));

    }
    return builder.append("}").toString();
}
 

public static Multimap<Scope, String> getScopeSnippets(final ASTNode node,
		final boolean methodAsRoots) {
	final ScopeFinder scopeFinder = new ScopeFinder(methodAsRoots);
	node.accept(scopeFinder);

	final Multimap<Scope, String> scopes = TreeMultimap.create();
	for (final Entry<ASTNode, Method> method : scopeFinder.methods
			.entries()) {
		scopes.put(new Scope(method.getKey().toString(),
				method.getValue().type, METHOD_CALL, 0, 0), method
				.getValue().name);
	}

	return scopes;

}
 

/**
 * Return a multimap containing all the (local) variables of the given
 * scope.
 * 
 * @param cu
 * @return Multimap<Snippet, VariableName>
 */
public static Multimap<Scope, String> getScopeSnippets(final ASTNode cu) {
	final VariableScopeFinder scopeFinder = new VariableScopeFinder();
	cu.accept(scopeFinder);

	final Multimap<Scope, String> scopes = TreeMultimap.create();
	for (final Entry<ASTNode, Variable> variable : scopeFinder.variableScopes
			.entries()) {
		final int astNodeType = variable.getKey().getNodeType();
		final int astNodeParentType;
		if (variable.getKey().getParent() == null) {
			astNodeParentType = -1;
		} else {
			astNodeParentType = variable.getKey().getParent().getNodeType();
		}
		scopes.put(
				new Scope(variable.getKey().toString(),
						variable.getValue().scope,
						variable.getValue().type, astNodeType,
						astNodeParentType), variable.getValue().name);
	}

	return scopes;

}
 

/**
 * Constructor
 */
public TreeMapStore() {
    /*
     * For the start times index, the "key comparator" will compare the
     * start times as longs directly. This is the primary comparator for its
     * tree map.
     *
     * The secondary "value" comparator will check the end times first, and
     * in the event of a tie, defer to the ISegment's Comparable
     * implementation, a.k.a. its natural ordering.
     */
    fStartTimesIndex = TreeMultimap.create(Comparator.<Long>naturalOrder(),
            Comparator.comparingLong(E::getEnd).thenComparing(Function.identity()));

    fSize = 0;
}
 

public static <T extends Comparable, E extends Comparable> Iterator<T> extractAndSort(Iterator<T> input, Function<T, E> extractor) {
    TreeMultimap<E, T> reorgnized = TreeMultimap.create();
    while (input.hasNext()) {
        T t = input.next();
        E e = extractor.apply(t);
        reorgnized.put(e, t);
    }
    return reorgnized.values().iterator();
}
 

@Override
protected void doExecute() {
    MetricsService metricsService = get(MetricsService.class);

    MetricFilter filter = metricName != null ? (name, metric) -> name.equals(metricName) : MetricFilter.ALL;

    TreeMultimap<String, Metric> matched = listMetrics(metricsService, filter);
    matched.asMap().forEach((name, metrics) -> {
        if (outputJson()) {
            metrics.forEach(metric -> print("%s", json(metric)));
        } else {
            metrics.forEach(metric -> printMetric(name, metric));
        }
    });
}
 

public void build(TaskReportModel model) {
    Comparator<String> keyComparator = GUtil.last(GUtil.last(STRING_COMPARATOR, OTHER_GROUP), DEFAULT_GROUP);
    Comparator<TaskDetails> taskComparator = new Comparator<TaskDetails>() {
        public int compare(TaskDetails task1, TaskDetails task2) {
            int diff = STRING_COMPARATOR.compare(task1.getPath().getName(), task2.getPath().getName());
            if (diff != 0) {
                return diff;
            }
            Path parent1 = task1.getPath().getParent();
            Path parent2 = task2.getPath().getParent();
            if (parent1 == null && parent2 != null) {
                return -1;
            }
            if (parent1 != null && parent2 == null) {
                return 1;
            }
            if (parent1 == null) {
                return 0;
            }
            return parent1.compareTo(parent2);
        }
    };
    groups = TreeMultimap.create(keyComparator, taskComparator);
    for (String group : model.getGroups()) {
        groups.putAll(group, model.getTasksForGroup(group));
    }
    String otherGroupName = findOtherGroup(groups.keySet());
    if (otherGroupName != null && groups.keySet().contains(DEFAULT_GROUP)) {
        groups.putAll(otherGroupName, groups.removeAll(DEFAULT_GROUP));
    }
    if (groups.keySet().contains(DEFAULT_GROUP) && groups.keySet().size() > 1) {
        groups.putAll(OTHER_GROUP, groups.removeAll(DEFAULT_GROUP));
    }
}
 

@VisibleForTesting
@JsonCreator
ConvertConfigurationAnswerElement(
    @JsonProperty(PROP_DEFINED_STRUCTURES)
        SortedMap<String, SortedMap<String, SortedMap<String, DefinedStructureInfo>>>
            definedStructures,
    @JsonProperty(PROP_REFERENCED_STRUCTURES)
        SortedMap<
                String,
                SortedMap<String, SortedMap<String, SortedMap<String, SortedSet<Integer>>>>>
            referencedstructures,
    @JsonProperty(PROP_CONVERT_STATUS) SortedMap<String, ConvertStatus> convertStatus,
    @JsonProperty(PROP_ERRORS) SortedMap<String, BatfishException.BatfishStackTrace> errors,
    @JsonProperty(PROP_ERROR_DETAILS) SortedMap<String, ErrorDetails> errorDetails,
    @JsonProperty(PROP_UNDEFINED_REFERENCES)
        SortedMap<
                String,
                SortedMap<String, SortedMap<String, SortedMap<String, SortedSet<Integer>>>>>
            undefinedReferences,
    @JsonProperty(PROP_VERSION) String version,
    @JsonProperty(PROP_WARNINGS) SortedMap<String, Warnings> warnings,
    @JsonProperty(PROP_FILE_MAP) @Nullable Multimap<String, String> fileMap) {
  _definedStructures = firstNonNull(definedStructures, new TreeMap<>());
  _errors = firstNonNull(errors, new TreeMap<>());
  _errorDetails = firstNonNull(errorDetails, new TreeMap<>());
  _fileMap = firstNonNull(fileMap, TreeMultimap.create());
  _convertStatus = firstNonNull(convertStatus, new TreeMap<>());

  _referencedStructures = firstNonNull(referencedstructures, new TreeMap<>());
  _undefinedReferences = firstNonNull(undefinedReferences, new TreeMap<>());
  _version = firstNonNull(version, BatfishVersion.getVersionStatic());
  _warnings = firstNonNull(warnings, new TreeMap<>());
}
 

private SortedMultiMapIterator createSourceWithTestData() {
    TreeMultimap<Key,Value> map = TreeMultimap.create();
    
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc", true), new Value(createValueWithUid("abc.0").build().toByteArray()));
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithUid("abc.1").build().toByteArray()));
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithUid("abc.2").build().toByteArray()));
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithUid("abc.3").build().toByteArray()));
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithUid("abc.4").build().toByteArray()));
    
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abd"), new Value(createValueWithUid("abc.3").build().toByteArray()));
    
    return new SortedMultiMapIterator(map);
}
 

private static Map<CukesComponent, Multimap<StepType, StepDefinition>> createStepsStubs() {
    Map<CukesComponent, Multimap<StepType, StepDefinition>> steps = new LinkedHashMap<>();
    for (CukesComponent component : CukesComponent.values()) {
        Multimap<StepType, StepDefinition> stepsMap = TreeMultimap.create(StepType.comparator, StepDefinition.comparator);
        steps.put(component, stepsMap);
    }
    return steps;
}
 

@Test
public void testNoAggregatorWithDeepCopy() throws IOException {
    TreeMultimap<Key,Value> map = TreeMultimap.create();
    
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithUid("abc.0").build().toByteArray()));
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), new Value(createValueWithRemoveUid("abc.0").build().toByteArray()));
    
    map.put(newKey(SHARD, FIELD_TO_AGGREGATE, "abd"), new Value(createValueWithUid("abc.3").build().toByteArray()));
    
    SortedMultiMapIterator data = new SortedMultiMapIterator(map);
    
    PropogatingIterator iter = new PropogatingIterator();
    Map<String,String> options = Maps.newHashMap();
    
    IteratorEnvironment env = new MockIteratorEnvironment(false);
    
    iter.init(data, options, env);
    iter = iter.deepCopy(env);
    
    iter.seek(new Range(), Collections.emptyList(), false);
    
    Assert.assertTrue(iter.hasTop());
    
    Key topKey = iter.getTopKey();
    
    Assert.assertEquals(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), topKey);
    validateUids(iter.getTopValue(), "abc.0");
    iter.next();
    Assert.assertEquals(newKey(SHARD, FIELD_TO_AGGREGATE, "abc"), topKey);
    validateRemoval(iter.getTopValue(), "abc.0");
    iter.next();
    topKey = iter.getTopKey();
    Assert.assertEquals(newKey(SHARD, FIELD_TO_AGGREGATE, "abd"), topKey);
    
}
 

@Override
public Multimap<Scope, String> getFromNode(ASTNode node) {
	final Multimap<Scope, String> scopes = TreeMultimap.create();
	for (final IScopeExtractor extractor : allExtractors) {
		scopes.putAll(extractor.getFromNode(node));
	}
	return scopes;
}
 

private void printMap(Multimap<String,String> fieldMap) {
    TreeMultimap<String,String> sorted = TreeMultimap.create(fieldMap);
    for (String key : sorted.keySet()) {
        System.out.print(key + ": ");
        Collection<String> values = fieldMap.get(key);
        for (String value : values) {
            System.out.print("[" + value + "]");
        }
        System.out.print("\n");
    }
    System.out.println();
}
 

static TreeMultimap<String,IndexStream> pivot(TreeMultimap<String,IndexStream> children) {
    TreeMultimap<String,IndexStream> newChildren = TreeMultimap.create(Ordering.natural(), Ordering.arbitrary());
    final String max = children.keySet().last();
    newChildren.putAll(max, children.removeAll(max));
    for (IndexStream itr : children.values()) {
        // move this iterator forward until we get to a key past the max processed thus far
        String dayOrShard = null;
        while (itr.hasNext()) {
            
            dayOrShard = key(itr.peek());
            if (dayOrShard.compareTo(max) >= 0) {
                break;
            }
            if (isDay(dayOrShard) && max.startsWith(dayOrShard)) {
                // use the existing max instead of the day to add to the list
                dayOrShard = max;
                break;
            }
            itr.next();
        }
        // add the item into our map
        if (itr.hasNext()) {
            newChildren.put(dayOrShard, itr);
        } else {
            // nobody has anything past max, so no intersection
            return TreeMultimap.create(Ordering.natural(), Ordering.arbitrary());
        }
    }
    return newChildren;
}
 

private SubscriberCoordinator( final Comparator<T> comparator, final Subscriber<? super T> subscriber,
                               final int innerSize ) {
    //we only want to emit events serially
    this.subscriber = new SerializedSubscriber( subscriber );
    this.innerSubscribers = new ArrayList<>( innerSize );
    this.nextValues = TreeMultimap.create( comparator, InnerObserverComparator.INSTANCE );
    this.toProduce = new ArrayDeque<>( innerSize );
}
 

public ParseVendorConfigurationAnswerElement() {
  _fileMap = TreeMultimap.create();
  _parseStatus = new TreeMap<>();
  _parseTrees = new TreeMap<>();
  _warnings = new TreeMap<>();
  _errors = new TreeMap<>();
  _errorDetails = new TreeMap<>();
}