@Test
public void testSetCopy() {
    Set<Integer> set = InsertionOrderUtil.newSet();
    set.add(4);
    set.add(2);
    set.add(5);
    set.add(1);
    set.add(3);
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(set));

    Set<Integer> set2 = InsertionOrderUtil.newSet(set);
    set2.add(6);
    set2.add(1);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3, 6),
                        ImmutableList.copyOf(set2));
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(set));
}
 

@Test
public void testListCopy() {
    List<Integer> list = InsertionOrderUtil.newList();
    list.add(4);
    list.add(2);
    list.add(5);
    list.add(1);
    list.add(3);
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(list));

    List<Integer> list2 = InsertionOrderUtil.newList(list);
    list2.add(6);
    list2.add(1);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3, 6, 1),
                        ImmutableList.copyOf(list2));
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(list));
}
 

@Test
public void testMapCopy() {
    Map<Integer, Integer> map = InsertionOrderUtil.newMap(3);
    map.put(4, 4);
    map.put(2, 2);
    map.put(5, 5);
    map.put(1, 1);
    map.put(3, 3);
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(map.keySet()));

    Map<Integer, Integer> map2 = InsertionOrderUtil.newMap(map);
    map2.put(6, 6);
    map2.put(1, 7);
    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3, 6),
                        ImmutableList.copyOf(map2.keySet()));

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(map.keySet()));
}
 

public static <K, V extends Comparable<? super V>> Map<K, V> topN(
                                                             Map<K, V> map,
                                                             boolean sorted,
                                                             long limit) {
    if (sorted) {
        map = CollectionUtil.sortByValue(map, false);
    }
    if (limit == NO_LIMIT || map.size() <= limit) {
        return map;
    }
    Map<K, V> results = InsertionOrderUtil.newMap();
    long count = 0L;
    for (Map.Entry<K, V> entry : map.entrySet()) {
        results.put(entry.getKey(), entry.getValue());
        if (++count >= limit) {
            break;
        }
    }
    return results;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    IKSegmenter ik = new IKSegmenter(new StringReader(text),
                                     this.smartSegMode);
    try {
        Lexeme word = null;
        while ((word = ik.next()) != null) {
            result.add(word.getLexemeText());
        }
    } catch (Exception e) {
        throw new HugeException("IKAnalyzer segment text '%s' failed",
                                e, text);
    }
    return result;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    Reader reader = new StringReader(text);
    try (TokenStream tokenStream = ANALYZER.tokenStream("text", reader)) {
        tokenStream.reset();
        CharTermAttribute term = null;
        while (tokenStream.incrementToken()) {
            term = tokenStream.getAttribute(CharTermAttribute.class);
            result.add(term.toString());
        }
    } catch (Exception e) {
        throw new HugeException("SmartCN segment text '%s' failed",
                                e, text);
    }
    return result;
}
 

private static Set<Relations> flattenAndOr(Condition condition) {
    Set<Relations> result = InsertionOrderUtil.newSet();
    switch (condition.type()) {
        case RELATION:
            Relation relation = (Relation) condition;
            result.add(Relations.of(relation));
            break;
        case AND:
            Condition.And and = (Condition.And) condition;
            result = and(flattenAndOr(and.left()),
                         flattenAndOr(and.right()));
            break;
        case OR:
            Condition.Or or = (Condition.Or) condition;
            result = or(flattenAndOr(or.left()),
                        flattenAndOr(or.right()));
            break;
        default:
            throw new AssertionError(String.format(
                      "Wrong condition type: '%s'", condition.type()));
    }
    return result;
}
 

@GET
@Timed
@Path("backend")
@Produces(APPLICATION_JSON_WITH_CHARSET)
@RolesAllowed("admin")
public String backend(@Context GraphManager manager) {
    Map<String, Map<String, Object>> results = InsertionOrderUtil.newMap();
    for (String graph : manager.graphs()) {
        HugeGraph g = manager.graph(graph);
        Map<String, Object> metrics = InsertionOrderUtil.newMap();
        metrics.put(BackendMetrics.BACKEND, g.backend());
        try {
            metrics.putAll(g.metadata(null, "metrics"));
        } catch (Throwable e) {
            metrics.put(BackendMetrics.EXCEPTION, e.toString());
            LOG.debug("Failed to get backend metrics", e);
        }
        results.put(graph, metrics);
    }
    return JsonUtil.toJson(results);
}
 

@Override
public Map<String, Object> getMetrics() {
    Map<String, Object> metrics = InsertionOrderUtil.newMap();
    metrics.put(NODES, 1);
    // NOTE: the unit of rocksdb mem property is bytes
    metrics.put(MEM_USED, this.getMemUsed() / Bytes.MB);
    metrics.put(MEM_UNIT, "MB");

    putMetrics(metrics, BLOCK_CACHE);
    putMetrics(metrics, BLOCK_CACHE_PINNED);
    putMetrics(metrics, BLOCK_CACHE_CAPACITY);
    putMetrics(metrics, INDEX_FILTER);
    putMetrics(metrics, ALL_MEM_TABLE);
    putMetrics(metrics, MEM_TABLE);
    putMetrics(metrics, MEM_TABLE_FLUSH_PENDINF);

    String size = FileUtils.byteCountToDisplaySize(this.getDataSize());
    metrics.put(DATA_SIZE, size);

    return metrics;
}
 

public ListIterator(long capacity, Iterator<T> origin) {
    List<T> results = InsertionOrderUtil.newList();
    while (origin.hasNext()) {
        if (capacity >= 0L && results.size() >= capacity) {
            throw new IllegalArgumentException(
                      "The iterator exceeded capacity " + capacity);
        }
        results.add(origin.next());
    }
    this.originIterator = origin;
    this.results = Collections.unmodifiableList(results);
    this.resultsIterator = this.results.iterator();
}
 

protected final List<T> nextBatch() {
    if (!this.originIterator.hasNext()) {
        return ImmutableList.of();
    }
    List<T> list = InsertionOrderUtil.newList();
    for (int i = 0; i < this.batch && this.originIterator.hasNext(); i++) {
        T next = this.originIterator.next();
        list.add(next);
    }
    return list;
}
 

@Test
public void testSet() {
    Set<Integer> set = InsertionOrderUtil.newSet();
    set.add(4);
    set.add(2);
    set.add(5);
    set.add(1);
    set.add(3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(set));
}
 

@Test
public void testSetWithInitialCapacity() {
    Set<Integer> set = InsertionOrderUtil.newSet(3);
    set.add(4);
    set.add(2);
    set.add(5);
    set.add(1);
    set.add(3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(set));
}
 

@Test
public void testList() {
    List<Integer> list = InsertionOrderUtil.newList();
    list.add(4);
    list.add(2);
    list.add(5);
    list.add(1);
    list.add(3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(list));
}
 

@Test
public void testListWithInitialCapacity() {
    List<Integer> list = InsertionOrderUtil.newList(3);
    list.add(4);
    list.add(2);
    list.add(5);
    list.add(1);
    list.add(3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(list));
}
 

@Test
public void testMap() {
    Map<Integer, Integer> map = InsertionOrderUtil.newMap();
    map.put(4, 4);
    map.put(2, 2);
    map.put(5, 5);
    map.put(1, 1);
    map.put(3, 3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(map.keySet()));
}
 

@Test
public void testMapWithInitialCapacity() {
    Map<Integer, Integer> map = InsertionOrderUtil.newMap(3);
    map.put(4, 4);
    map.put(2, 2);
    map.put(5, 5);
    map.put(1, 1);
    map.put(3, 3);

    Assert.assertEquals(ImmutableList.of(4, 2, 5, 1, 3),
                        ImmutableList.copyOf(map.keySet()));
}
 

public Set<Id> elementIds() {
    Set<Id> ids = InsertionOrderUtil.newSet(this.elementIds.size());
    for (IdWithExpiredTime idWithExpiredTime : this.elementIds) {
        ids.add(idWithExpiredTime.id());
    }
    return Collections.unmodifiableSet(ids);
}
 

public Set<IdWithExpiredTime> expiredElementIds() {
    long now = this.graph.now();
    Set<IdWithExpiredTime> expired = InsertionOrderUtil.newSet(
                                     this.elementIds.size());
    for (IdWithExpiredTime id : this.elementIds) {
        if (0L < id.expiredTime && id.expiredTime < now) {
            expired.add(id);
        }
    }
    this.elementIds.removeAll(expired);
    return expired;
}
 

public HugeVertex(final HugeGraph graph, Id id, VertexLabel label) {
    super(graph, id);

    this.tx = null;
    this.vertexLabel(label);
    this.edges = InsertionOrderUtil.newSet();
    this.name = null;
    if (this.id != null) {
        if (label.idStrategy() == IdStrategy.CUSTOMIZE_UUID) {
            this.assignId(id);
        } else {
            this.checkIdLength();
        }
    }
}
 

public Map<Id, Set<Map<String, Object>>> toMap() {
    Map<Id, Set<Map<String, Object>>> results = new HashMap<>();
    for (Map.Entry<Id, Set<Similar>> entry : this.entrySet()) {
        Id source = entry.getKey();
        Set<Similar> similars = entry.getValue();
        Set<Map<String, Object>> result = InsertionOrderUtil.newSet();
        for (Similar similar : similars) {
            result.add(similar.toMap());
        }
        results.put(source, result);
    }
    return results;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    for (SegToken token : JIEBA_SEGMENTER.process(text, this.segMode)) {
        result.add(token.word);
    }
    return result;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    MMSeg mmSeg = new MMSeg(new StringReader(text), this.seg);
    try {
        Word word = null;
        while ((word = mmSeg.next()) != null) {
            result.add(word.getString());
        }
    } catch (Exception e) {
        throw new HugeException("MMSeg4j segment text '%s' failed",
                                e, text);
    }
    return result;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    try {
        Object[] args = new Object[]{new StringReader(text), CONFIG, DIC};
        ISegment seg = SegmentFactory.createJcseg(this.segMode, args);
        IWord word = null;
        while ((word = seg.next()) != null) {
            result.add(word.getValue());
        }
    } catch (Exception e) {
        throw new HugeException("Jcseg segment text '%s' failed", e, text);
    }
    return result;
}
 

@Override
public Set<String> segment(String text) {
    Set<String> result = InsertionOrderUtil.newSet();
    List<Word> words = WordSegmenter.segWithStopWords(text, this.algorithm);
    for (Word word : words) {
        result.add(word.getText());
    }
    return result;
}
 

public void depends(Id id) {
    E.checkState(this.status == TaskStatus.NEW,
                 "Can't add dependency in status '%s'", this.status);
    if (this.dependencies == null) {
        this.dependencies = InsertionOrderUtil.newSet();
    }
    this.dependencies.add(id);
}
 

@Watched(prefix = "index")
private IdHolder doIndexQueryBatch(IndexLabel indexLabel,
                                   ConditionQuery query) {
    Iterator<BackendEntry> entries = super.query(query).iterator();
    return new BatchIdHolder(query, entries, batch -> {
        LockUtil.Locks locks = new LockUtil.Locks(this.graphName());
        try {
            // Catch lock every batch
            locks.lockReads(LockUtil.INDEX_LABEL_DELETE, indexLabel.id());
            locks.lockReads(LockUtil.INDEX_LABEL_REBUILD, indexLabel.id());
            if (!indexLabel.system()) {
                /*
                 * Check exist because it may be deleted after some batches
                 * throw exception if the index label not exists
                 * NOTE: graph() will return null with system index label
                 */
                graph().indexLabel(indexLabel.id());
            }

            // Iterate one batch, and keep iterator position
            Set<Id> ids = InsertionOrderUtil.newSet();
            while ((ids.size() < batch || batch == Query.NO_LIMIT) &&
                   entries.hasNext()) {
                HugeIndex index = this.serializer.readIndex(graph(), query,
                                                            entries.next());
                this.removeExpiredIndexIfNeeded(index, query.showExpired());
                ids.addAll(index.elementIds());
                Query.checkForceCapacity(ids.size());
            }
            return ids;
        } finally {
            locks.unlock();
        }
    });
}
 

@Watched(prefix = "index")
private PageIds doIndexQueryOnce(IndexLabel indexLabel,
                                 ConditionQuery query) {
    // Query all or one page
    Iterator<BackendEntry> entries = null;
    LockUtil.Locks locks = new LockUtil.Locks(this.graphName());
    try {
        locks.lockReads(LockUtil.INDEX_LABEL_DELETE, indexLabel.id());
        locks.lockReads(LockUtil.INDEX_LABEL_REBUILD, indexLabel.id());

        Set<Id> ids = InsertionOrderUtil.newSet();
        entries = super.query(query).iterator();
        while (entries.hasNext()) {
            HugeIndex index = this.serializer.readIndex(graph(), query,
                                                        entries.next());
            this.removeExpiredIndexIfNeeded(index, query.showExpired());
            ids.addAll(index.elementIds());
            if (query.reachLimit(ids.size())) {
                break;
            }
            Query.checkForceCapacity(ids.size());
        }
        // If there is no data, the entries is not a Metadatable object
        if (ids.isEmpty()) {
            return PageIds.EMPTY;
        }
        // NOTE: Memory backend's iterator is not Metadatable
        if (!query.paging()) {
            return new PageIds(ids, PageState.EMPTY);
        }
        E.checkState(entries instanceof Metadatable,
                     "The entries must be Metadatable when query " +
                     "in paging, but got '%s'",
                     entries.getClass().getName());
        return new PageIds(ids, PageInfo.pageState(entries));
    } finally {
        locks.unlock();
        CloseableIterator.closeIterator(entries);
    }
}
 

/**
 * Collect matched IndexLabel(s) in a SchemaLabel for a query
 * @param schemaLabel find indexLabels of this schemaLabel
 * @param query conditions container
 * @return MatchedLabel object contains schemaLabel and matched indexLabels
 */
@Watched(prefix = "index")
private MatchedIndex collectMatchedIndex(SchemaLabel schemaLabel,
                                         ConditionQuery query) {
    SchemaTransaction schema = this.params().schemaTransaction();
    Set<IndexLabel> ils = InsertionOrderUtil.newSet();
    for (Id il : schemaLabel.indexLabels()) {
        IndexLabel indexLabel = schema.getIndexLabel(il);
        if (indexLabel.indexType().isUnique()) {
            continue;
        }
        ils.add(indexLabel);
    }
    if (ils.isEmpty()) {
        return null;
    }
    // Try to match single or composite index
    Set<IndexLabel> matchedILs = matchSingleOrCompositeIndex(query, ils);
    if (matchedILs.isEmpty()) {
        // Try joint indexes
        matchedILs = matchJointIndexes(query, ils);
    }

    if (!matchedILs.isEmpty()) {
        return new MatchedIndex(schemaLabel, matchedILs);
    }
    return null;
}
 

private static Set<IndexLabel> matchRangeOrSearchIndexLabels(
                               ConditionQuery query,
                               Set<IndexLabel> indexLabels) {
    Set<IndexLabel> matchedIndexLabels = InsertionOrderUtil.newSet();
    for (Condition.Relation relation : query.userpropRelations()) {
        if (!relation.relation().isRangeType() &&
            !relation.relation().isSearchType()) {
            continue;
        }
        Id key = (Id) relation.key();
        boolean matched = false;
        for (IndexLabel indexLabel : indexLabels) {
            if (indexLabel.indexType().isRange() ||
                indexLabel.indexType().isSearch()) {
                if (indexLabel.indexField().equals(key)) {
                    matched = true;
                    matchedIndexLabels.add(indexLabel);
                    break;
                }
            }
        }
        if (!matched) {
            return ImmutableSet.of();
        }
    }
    return matchedIndexLabels;
}