blob: d49aab263f223315a09249c6c48ad91105b7ba6b [file] [log] [blame]
/*
* 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.ArrayList;
import java.util.List;
import java.util.Stack;
import org.apache.commons.collections.CollectionUtils;
import org.apache.hugegraph.backend.id.Id;
import org.apache.hugegraph.util.collection.IntIterator;
import org.apache.hugegraph.perf.PerfUtil.Watched;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.Path;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.PathSet;
import org.apache.hugegraph.traversal.algorithm.records.record.Record;
import org.apache.hugegraph.traversal.algorithm.records.record.RecordType;
import com.google.common.collect.Lists;
public abstract class DoubleWayMultiPathsRecords extends AbstractRecords {
private final Stack<Record> sourceRecords;
private final Stack<Record> targetRecords;
private IntIterator parentRecordKeys;
private int currentKey;
private boolean movingForward;
private long accessed;
public DoubleWayMultiPathsRecords(RecordType type, boolean concurrent,
Id sourceV, Id targetV) {
super(type, concurrent);
int sourceCode = this.code(sourceV);
int targetCode = this.code(targetV);
Record firstSourceRecord = this.newRecord();
Record firstTargetRecord = this.newRecord();
firstSourceRecord.addPath(sourceCode, 0);
firstTargetRecord.addPath(targetCode, 0);
this.sourceRecords = new Stack<>();
this.targetRecords = new Stack<>();
this.sourceRecords.push(firstSourceRecord);
this.targetRecords.push(firstTargetRecord);
this.accessed = 2L;
}
@Override
public void startOneLayer(boolean forward) {
this.movingForward = forward;
Record parentRecord = this.movingForward ?
this.sourceRecords.peek() :
this.targetRecords.peek();
this.currentRecord(this.newRecord(), parentRecord);
this.parentRecordKeys = parentRecord.keys();
}
@Override
public void finishOneLayer() {
Record record = this.currentRecord();
if (this.movingForward) {
this.sourceRecords.push(record);
} else {
this.targetRecords.push(record);
}
this.accessed += record.size();
}
@Watched
@Override
public boolean hasNextKey() {
return this.parentRecordKeys.hasNext();
}
@Watched
@Override
public Id nextKey() {
this.currentKey = this.parentRecordKeys.next();
return this.id(this.currentKey);
}
public boolean parentsContain(int id) {
Record parentRecord = this.parentRecord();
if (parentRecord == null) {
return false;
}
IntIterator parents = parentRecord.get(this.currentKey);
while (parents.hasNext()) {
int parent = parents.next();
if (parent == id) {
// Find backtrace path, stop
return true;
}
}
return false;
}
@Override
public long accessed() {
return this.accessed;
}
public boolean sourcesLessThanTargets() {
return this.sourceRecords.peek().size() <=
this.targetRecords.peek().size();
}
@Watched
protected final PathSet linkPath(int source, int target, boolean ring) {
PathSet paths = new PathSet();
PathSet sources = this.linkSourcePath(source);
PathSet targets = this.linkTargetPath(target);
for (Path tpath : targets) {
tpath.reverse();
for (Path spath : sources) {
if (!ring) {
// Avoid loop in path
if (CollectionUtils.containsAny(spath.vertices(),
tpath.vertices())) {
continue;
}
}
List<Id> ids = new ArrayList<>(spath.vertices());
ids.addAll(tpath.vertices());
Id crosspoint = this.id(this.movingForward ? target : source);
paths.add(new Path(crosspoint, ids));
}
}
return paths;
}
private PathSet linkSourcePath(int source) {
return this.linkPathLayer(this.sourceRecords, source,
this.sourceRecords.size() - 1);
}
private PathSet linkTargetPath(int target) {
return this.linkPathLayer(this.targetRecords, target,
this.targetRecords.size() - 1);
}
private PathSet linkPathLayer(Stack<Record> all, int id, int layerIndex) {
PathSet results = new PathSet();
if (layerIndex == 0) {
Id sid = this.id(id);
results.add(new Path(Lists.newArrayList(sid)));
return results;
}
Id current = this.id(id);
Record layer = all.elementAt(layerIndex);
IntIterator iterator = layer.get(id);
while (iterator.hasNext()) {
int parent = iterator.next();
PathSet paths = this.linkPathLayer(all, parent, layerIndex - 1);
paths.append(current);
results.addAll(paths);
}
return results;
}
@Watched
protected final void addPath(int current, int parent) {
this.currentRecord().addPath(current, parent);
}
protected final boolean sourceContains(int node) {
return this.sourceRecords.peek().containsKey(node);
}
protected final boolean targetContains(int node) {
return this.targetRecords.peek().containsKey(node);
}
protected final Stack<Record> sourceRecords() {
return this.sourceRecords;
}
protected final Stack<Record> targetRecords() {
return this.targetRecords;
}
protected final boolean movingForward() {
return this.movingForward;
}
protected final int current() {
return this.currentKey;
}
}