hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements. See the NOTICE file distributed with this
 * work for additional information regarding copyright ownership. The ASF
 * licenses this file to You 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 org.apache.hugegraph.traversal.algorithm.records;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.function.Function;

import org.apache.hugegraph.HugeException;
import org.apache.hugegraph.backend.id.Id;
import org.apache.hugegraph.perf.PerfUtil.Watched;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.EdgeRecord;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.Path;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.PathSet;
import org.apache.hugegraph.traversal.algorithm.records.record.Int2IntRecord;
import org.apache.hugegraph.traversal.algorithm.records.record.Record;
import org.apache.hugegraph.traversal.algorithm.records.record.RecordType;
import org.apache.hugegraph.type.define.CollectionType;
import org.apache.hugegraph.util.collection.CollectionFactory;
import org.apache.hugegraph.util.collection.IntIterator;
import org.apache.hugegraph.util.collection.IntMap;
import org.apache.hugegraph.util.collection.IntSet;

public abstract class SingleWayMultiPathsRecords extends AbstractRecords {

    protected final int sourceCode;
    private final Stack<Record> records;
    private final boolean nearest;
    private final IntSet accessedVertices;
    private final EdgeRecord edgeResults;
    private IntIterator parentRecordKeys;

    public SingleWayMultiPathsRecords(RecordType type, boolean concurrent,
                                      Id source, boolean nearest) {
        super(type, concurrent);

        this.nearest = nearest;

        this.sourceCode = this.code(source);
        Record firstRecord = this.newRecord();
        firstRecord.addPath(this.sourceCode, 0);
        this.records = new Stack<>();
        this.records.push(firstRecord);
        this.edgeResults = new EdgeRecord(concurrent);

        this.accessedVertices = CollectionFactory.newIntSet();
    }

    @Override
    public void startOneLayer(boolean forward) {
        Record parentRecord = this.records.peek();
        this.currentRecord(this.newRecord(), parentRecord);
        this.parentRecordKeys = parentRecord.keys();
    }

    @Override
    public void finishOneLayer() {
        this.records.push(this.currentRecord());
    }

    @Override
    public boolean hasNextKey() {
        return this.parentRecordKeys.hasNext();
    }

    @Override
    public Id nextKey() {
        return this.id(this.parentRecordKeys.next());
    }

    @Override
    public PathSet findPath(Id target, Function<Id, Boolean> filter,
                            boolean all, boolean ring) {
        PathSet paths = new PathSet();
        for (int i = 1; i < this.records.size(); i++) {
            IntIterator iterator = this.records.get(i).keys();
            while (iterator.hasNext()) {
                paths.add(this.linkPath(i, iterator.next()));
            }
        }
        return paths;
    }

    @Override
    public long accessed() {
        return this.accessedVertices.size();
    }

    public Iterator<Id> keys() {
        return new IntIterator.MapperInt2ObjectIterator<>(this.parentRecordKeys, this::id);
    }

    @Watched
    public void addPath(Id source, Id target) {
        this.addPathToRecord(this.code(source), this.code(target), this.currentRecord());
    }

    public void addPathToRecord(int sourceCode, int targetCode, Record record) {
        if (this.nearest && this.accessedVertices.contains(targetCode) ||
            !this.nearest && record.containsKey(targetCode) ||
            targetCode == this.sourceCode) {
            return;
        }
        record.addPath(targetCode, sourceCode);
        this.accessedVertices.add(targetCode);
    }

    protected final Path linkPath(int target) {
        List<Id> ids = CollectionFactory.newList(CollectionType.EC);
        // Find the layer where the target is located
        int foundLayer = -1;
        for (int i = 0; i < this.records.size(); i++) {
            IntMap layer = this.layer(i);
            if (!layer.containsKey(target)) {
                continue;
            }

            foundLayer = i;
            // Collect self node
            ids.add(this.id(target));
            break;
        }
        // If a layer found, then concat parents
        if (foundLayer > 0) {
            for (int i = foundLayer; i > 0; i--) {
                IntMap layer = this.layer(i);
                // Uptrack parents
                target = layer.get(target);
                ids.add(this.id(target));
            }
        }
        return new Path(ids);
    }

    protected final Path linkPath(int layerIndex, int target) {
        List<Id> ids = CollectionFactory.newList(CollectionType.EC);
        IntMap layer = this.layer(layerIndex);
        if (!layer.containsKey(target)) {
            throw new HugeException("Failed to get path for %s",
                                    this.id(target));
        }
        // Collect self node
        ids.add(this.id(target));
        // Concat parents
        for (int i = layerIndex; i > 0; i--) {
            layer = this.layer(i);
            // Uptrack parents
            target = layer.get(target);
            ids.add(this.id(target));
        }
        Collections.reverse(ids);
        return new Path(ids);
    }

    protected final IntMap layer(int layerIndex) {
        Record record = this.records.elementAt(layerIndex);
        return ((Int2IntRecord) record).layer();
    }

    protected final Stack<Record> records() {
        return this.records;
    }

    public EdgeRecord edgeResults() {
        return edgeResults;
    }

    public abstract int size();

    public abstract List<Id> ids(long limit);

    public abstract PathSet paths(long limit);
}