Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphMatcher.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphMatcher.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphMatcher.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphMatcher.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,141 @@ +/* + * 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.commons.rdf.impl.utils.graphmatching; + + + +import java.util.Iterator; +import java.util.Map; +import java.util.Set; +import org.apache.commons.rdf.BlankNode; +import org.apache.commons.rdf.BlankNodeOrIri; +import org.apache.commons.rdf.Graph; +import org.apache.commons.rdf.RdfTerm; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.impl.utils.TripleImpl; +import org.apache.commons.rdf.impl.utils.simple.SimpleMGraph; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * @author reto + * + */ +public class GraphMatcher { + + + private final static Logger log = LoggerFactory.getLogger(GraphMatcher.class); + + /** + * get a mapping from g1 to g2 or null if the graphs are not isomorphic. The + * returned map maps each <code>BNode</code>s from g1 to one + * of g2. If the graphs are ground graphs the method return an empty map if + * the ImmutableGraph are equals and null otherwise. + * <p/> + * NOTE: This method does not returned mapping from blank nodes to grounded + * nodes, a bnode in g1 is not a vraiable that may match any node, but must + * match a bnode in g2. + * <p/> + * + * On the algorithm:<br/> + * - In a first step it checked if every grounded triple in g1 matches one + * in g2<br/> + * - [optional] blank node blind matching</br> + * - in a map mbng1 bnode of g1 is mapped to a set of of its + * properties and inverse properties, this is the predicate and the object + * or subject respectively, analoguosly in mbgn2 every bnode of g2<br/> + * - based on the incoming and outgoing properties a hash is calculated for + * each bnode, in the first step when calculating the hash aconstant value + * is taken for the bnodes that might be subject or object in the (inverse properties) + * - hash-classes: + * + * @param g1 + * @param g2 + * @return a Set of NodePairs + */ + public static Map<BlankNode, BlankNode> getValidMapping(Graph og1, Graph og2) { + Graph g1 = new SimpleMGraph(og1); + Graph g2 = new SimpleMGraph(og2); + if (!Utils.removeGrounded(g1,g2)) { + return null; + } + final HashMatching hashMatching; + try { + hashMatching = new HashMatching(g1, g2); + } catch (GraphNotIsomorphicException ex) { + return null; + } + Map<BlankNode, BlankNode> matchings = hashMatching.getMatchings(); + if (g1.size() > 0) { + //start trial an error matching + //TODO (CLEREZZA-81) at least in the situation where one matching + //group is big (approx > 5) we should switch back to hash-based matching + //after a first guessed matching, rather than try all permutations + Map<BlankNode, BlankNode> remainingMappings = trialAndErrorMatching(g1, g2, hashMatching.getMatchingGroups()); + if (remainingMappings == null) { + return null; + } else { + matchings.putAll(remainingMappings); + } + } + return matchings; + } + + private static Map<BlankNode, BlankNode> trialAndErrorMatching(Graph g1, Graph g2, + Map<Set<BlankNode>, Set<BlankNode>> matchingGroups) { + if (log.isDebugEnabled()) { + Set<BlankNode> bn1 = Utils.getBNodes(g1); + log.debug("doing trial and error matching for {} bnodes, " + + "in graphs of size: {}.", bn1.size(), g1.size()); + } + Iterator<Map<BlankNode, BlankNode>> mappingIter + = GroupMappingIterator.create(matchingGroups); + while (mappingIter.hasNext()) { + Map<BlankNode, BlankNode> map = mappingIter.next(); + if (checkMapping(g1, g2, map)) { + return map; + } + } + return null; + } + + private static boolean checkMapping(Graph g1, Graph g2, Map<BlankNode, BlankNode> map) { + for (Triple triple : g1) { + if (!g2.contains(map(triple, map))) { + return false; + } + } + return true; + } + + private static Triple map(Triple triple, Map<BlankNode, BlankNode> map) { + final BlankNodeOrIri oSubject = triple.getSubject(); + + BlankNodeOrIri subject = oSubject instanceof BlankNode ? + map.get((BlankNode)oSubject) : oSubject; + + RdfTerm oObject = triple.getObject(); + RdfTerm object = oObject instanceof BlankNode ? + map.get((BlankNode)oObject) : oObject; + return new TripleImpl(subject, triple.getPredicate(), object); + } + + +}
Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphNotIsomorphicException.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphNotIsomorphicException.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphNotIsomorphicException.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GraphNotIsomorphicException.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,28 @@ +/* + * 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.commons.rdf.impl.utils.graphmatching; + +/** + * + * @author reto + */ +class GraphNotIsomorphicException extends Exception { + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GroupMappingIterator.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GroupMappingIterator.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GroupMappingIterator.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/GroupMappingIterator.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,102 @@ +/* + * Copyright 2010 reto. + * + * Licensed 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. + * under the License. + */ + +package org.apache.commons.rdf.impl.utils.graphmatching; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Set; + +/** + * Iterates over all mappings from each element of every Set<T> to each + * elemenent of their corresponding Set<U>. + * + * @author reto + */ +class GroupMappingIterator<T,U> implements Iterator<Map<T, U>> { + + private Iterator<Map<T, U>> firstPartIter; + private Map<T, U> currentFirstPart; + final private Map<Set<T>, Set<U>> restMap; + private Iterator<Map<T, U>> currentRestPartIter; + + static <T,U> Iterator<Map<T, U>> create(Map<Set<T>, Set<U>> matchingGroups) { + if (matchingGroups.size() > 1) { + return new GroupMappingIterator<T, U>(matchingGroups); + } else { + if (matchingGroups.size() == 0) { + return new ArrayList<Map<T, U>>(0).iterator(); + } + Map.Entry<Set<T>, Set<U>> entry = matchingGroups.entrySet().iterator().next(); + return new MappingIterator<T,U>(entry.getKey(), + entry.getValue()); + } + } + + private GroupMappingIterator(Map<Set<T>, Set<U>> matchingGroups) { + if (matchingGroups.size() == 0) { + throw new IllegalArgumentException("matchingGroups must not be empty"); + } + restMap = new HashMap<Set<T>, Set<U>>(); + boolean first = true; + for (Map.Entry<Set<T>, Set<U>> entry : matchingGroups.entrySet()) { + if (first) { + firstPartIter = new MappingIterator<T,U>(entry.getKey(), + entry.getValue()); + first = false; + } else { + restMap.put(entry.getKey(), entry.getValue()); + } + } + currentRestPartIter = create(restMap); + currentFirstPart = firstPartIter.next(); + } + + @Override + public boolean hasNext() { + return firstPartIter.hasNext() || currentRestPartIter.hasNext(); + } + + @Override + public Map<T, U> next() { + Map<T, U> restPart; + if (currentRestPartIter.hasNext()) { + restPart = currentRestPartIter.next(); + } else { + if (firstPartIter.hasNext()) { + currentFirstPart = firstPartIter.next(); + currentRestPartIter = create(restMap); + restPart = currentRestPartIter.next(); + } else { + throw new NoSuchElementException(); + } + } + Map<T, U> result = new HashMap<T, U>(restPart); + result.putAll(currentFirstPart); + return result; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Not supported."); + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/HashMatching.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/HashMatching.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/HashMatching.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/HashMatching.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,268 @@ +/* + * 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.commons.rdf.impl.utils.graphmatching; + + +import org.apache.commons.rdf.impl.utils.graphmatching.collections.IntHashMap; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; +import org.apache.commons.rdf.BlankNode; +import org.apache.commons.rdf.Graph; +import org.apache.commons.rdf.BlankNodeOrIri; +import org.apache.commons.rdf.RdfTerm; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.Graph; +import org.apache.commons.rdf.Iri; +import org.apache.commons.rdf.impl.utils.TripleImpl; +import org.apache.commons.rdf.impl.utils.graphmatching.collections.IntIterator; + +/** + * + * @author reto + */ +public class HashMatching { + + private Map<BlankNode, BlankNode> matchings = new HashMap<BlankNode, BlankNode>(); + private Map<Set<BlankNode>, Set<BlankNode>> matchingGroups; + + /** + * tc1 and tc2 will be modified: the triples containing no unmatched bnode + * will be removed + * + * @param tc1 + * @param tc2 + * @throws GraphNotIsomorphicException + */ + HashMatching(Graph tc1, Graph tc2) throws GraphNotIsomorphicException { + int foundMatchings = 0; + int foundMatchingGroups = 0; + Map<BlankNode, Integer> bNodeHashMap = new HashMap<BlankNode, Integer>(); + while (true) { + bNodeHashMap = matchByHashes(tc1, tc2, bNodeHashMap); + if (bNodeHashMap == null) { + throw new GraphNotIsomorphicException(); + } + if (matchings.size() == foundMatchings) { + if (!(matchingGroups.size() > foundMatchingGroups)) { + break; + } + } + foundMatchings = matchings.size(); + foundMatchingGroups = matchingGroups.size(); + } + } + + /** + * + * @return a map containing set of which each bnodes mappes one of the other set + */ + public Map<Set<BlankNode>, Set<BlankNode>> getMatchingGroups() { + return matchingGroups; + } + + public Map<BlankNode, BlankNode> getMatchings() { + return matchings; + } + + + private static IntHashMap<Set<BlankNode>> getHashNodes(Map<BlankNode, + Set<Property>> bNodePropMap, Map<BlankNode, Integer> bNodeHashMap) { + IntHashMap<Set<BlankNode>> result = new IntHashMap<Set<BlankNode>>(); + for (Map.Entry<BlankNode, Set<Property>> entry : bNodePropMap.entrySet()) { + int hash = computeHash(entry.getValue(), bNodeHashMap); + Set<BlankNode> bNodeSet = result.get(hash); + if (bNodeSet == null) { + bNodeSet = new HashSet<BlankNode>(); + result.put(hash,bNodeSet); + } + bNodeSet.add(entry.getKey()); + } + return result; + } + /* + * returns a Map from bnodes to hash that can be used for future + * refinements, this could be separate for each ImmutableGraph. + * + * triples no longer containing an unmatched bnodes ae removed. + * + * Note that the matched node are not guaranteed to be equals, but only to + * be the correct if the graphs are isomorphic. + */ + private Map<BlankNode, Integer> matchByHashes(Graph g1, Graph g2, + Map<BlankNode, Integer> bNodeHashMap) { + Map<BlankNode, Set<Property>> bNodePropMap1 = getBNodePropMap(g1); + Map<BlankNode, Set<Property>> bNodePropMap2 = getBNodePropMap(g2); + IntHashMap<Set<BlankNode>> hashNodeMap1 = getHashNodes(bNodePropMap1, bNodeHashMap); + IntHashMap<Set<BlankNode>> hashNodeMap2 = getHashNodes(bNodePropMap2, bNodeHashMap); + if (!hashNodeMap1.keySet().equals(hashNodeMap2.keySet())) { + return null; + } + + matchingGroups = new HashMap<Set<BlankNode>, Set<BlankNode>>(); + IntIterator hashIter = hashNodeMap1.keySet().intIterator(); + while (hashIter.hasNext()) { + int hash = hashIter.next(); + Set<BlankNode> nodes1 = hashNodeMap1.get(hash); + Set<BlankNode> nodes2 = hashNodeMap2.get(hash); + if (nodes1.size() != nodes2.size()) { + return null; + } + if (nodes1.size() != 1) { + matchingGroups.put(nodes1, nodes2); + continue; + } + final BlankNode bNode1 = nodes1.iterator().next(); + final BlankNode bNode2 = nodes2.iterator().next(); + matchings.put(bNode1,bNode2); + //in the graphs replace node occurences with grounded node, + BlankNodeOrIri mappedNode = new MappedNode(bNode1, bNode2); + replaceNode(g1,bNode1, mappedNode); + replaceNode(g2, bNode2, mappedNode); + //remove grounded triples + if (!Utils.removeGrounded(g1,g2)) { + return null; + } + } + Map<BlankNode, Integer> result = new HashMap<BlankNode, Integer>(); + addInverted(result, hashNodeMap1); + addInverted(result, hashNodeMap2); + return result; + } + private static int computeHash(Set<Property> propertySet, Map<BlankNode, Integer> bNodeHashMap) { + int result = 0; + for (Property property : propertySet) { + result += property.hashCode(bNodeHashMap); + } + return result; + } + private static Map<BlankNode, Set<Property>> getBNodePropMap(Graph g) { + Set<BlankNode> bNodes = Utils.getBNodes(g); + Map<BlankNode, Set<Property>> result = new HashMap<BlankNode, Set<Property>>(); + for (BlankNode bNode : bNodes) { + result.put(bNode, getProperties(bNode, g)); + } + return result; + } + private static Set<Property> getProperties(BlankNode bNode, Graph g) { + Set<Property> result = new HashSet<Property>(); + Iterator<Triple> ti = g.filter(bNode, null, null); + while (ti.hasNext()) { + Triple triple = ti.next(); + result.add(new ForwardProperty(triple.getPredicate(), triple.getObject())); + } + ti = g.filter(null, null, bNode); + while (ti.hasNext()) { + Triple triple = ti.next(); + result.add(new BackwardProperty(triple.getSubject(), triple.getPredicate())); + } + return result; + } + private static int nodeHash(RdfTerm resource, Map<BlankNode, Integer> bNodeHashMap) { + if (resource instanceof BlankNode) { + Integer mapValue = bNodeHashMap.get((BlankNode)resource); + if (mapValue == null) { + return 0; + } else { + return mapValue; + } + } else { + return resource.hashCode(); + } + } + private static void replaceNode(Graph graph, BlankNode bNode, BlankNodeOrIri replacementNode) { + Set<Triple> triplesToRemove = new HashSet<Triple>(); + for (Triple triple : graph) { + Triple replacementTriple = getReplacement(triple, bNode, replacementNode); + if (replacementTriple != null) { + triplesToRemove.add(triple); + graph.add(replacementTriple); + } + } + graph.removeAll(triplesToRemove); + } + private static Triple getReplacement(Triple triple, BlankNode bNode, BlankNodeOrIri replacementNode) { + if (triple.getSubject().equals(bNode)) { + if (triple.getObject().equals(bNode)) { + return new TripleImpl(replacementNode, triple.getPredicate(), replacementNode); + } else { + return new TripleImpl(replacementNode, triple.getPredicate(), triple.getObject()); + } + } else { + if (triple.getObject().equals(bNode)) { + return new TripleImpl(triple.getSubject(), triple.getPredicate(), replacementNode); + } else { + return null; + } + } + } + private static void addInverted(Map<BlankNode, Integer> result, IntHashMap<Set<BlankNode>> hashNodeMap) { + for (int hash : hashNodeMap.keySet()) { + Set<BlankNode> bNodes = hashNodeMap.get(hash); + for (BlankNode bNode : bNodes) { + result.put(bNode, hash); + } + } + } + + private static class BackwardProperty implements Property { + private BlankNodeOrIri subject; + private Iri predicate; + + public BackwardProperty(BlankNodeOrIri subject, Iri predicate) { + this.subject = subject; + this.predicate = predicate; + } + + @Override + public int hashCode(Map<BlankNode, Integer> bNodeHashMap) { + return 0xFF ^ predicate.hashCode() ^ nodeHash(subject, bNodeHashMap); + } + + } + private static class ForwardProperty implements Property { + private Iri predicate; + private RdfTerm object; + + public ForwardProperty(Iri predicate, RdfTerm object) { + this.predicate = predicate; + this.object = object; + } + + @Override + public int hashCode(Map<BlankNode, Integer> bNodeHashMap) { + return predicate.hashCode() ^ nodeHash(object, bNodeHashMap); + } + } + private static class MappedNode implements BlankNodeOrIri { + private BlankNode bNode1, bNode2; + + public MappedNode(BlankNode bNode1, BlankNode bNode2) { + this.bNode1 = bNode1; + this.bNode2 = bNode2; + } + + } + private static interface Property { + public int hashCode(Map<BlankNode, Integer> bNodeHashMap); + } +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/MappingIterator.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/MappingIterator.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/MappingIterator.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/MappingIterator.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,76 @@ +package org.apache.commons.rdf.impl.utils.graphmatching; + +/* + * 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. + */ + + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * An iterator over all possible mapping beetween the elemnets of two sets of + * the same size, each mapping maps each element from set1 to a disctinct one of + * set2. + * + * + * + * @author reto + */ +class MappingIterator<T,U> implements Iterator<Map<T, U>> { + + private List<T> list1; + private Iterator<List<U>> permutationList2Iterator; + + + public MappingIterator(Set<T> set1, Set<U> set2) { + if (set1.size() != set2.size()) { + throw new IllegalArgumentException(); + } + this.list1 = new ArrayList<T>(set1); + permutationList2Iterator = new PermutationIterator<U>( + new ArrayList<U>(set2)); + } + + @Override + public boolean hasNext() { + return permutationList2Iterator.hasNext(); + } + + @Override + public Map<T, U> next() { + List<U> list2 = permutationList2Iterator.next(); + Map<T, U> result = new HashMap<T, U>(list1.size()); + for (int i = 0; i < list1.size(); i++) { + result.put(list1.get(i), list2.get(i)); + } + return result; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Not supported."); + } + + + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/PermutationIterator.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/PermutationIterator.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/PermutationIterator.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/PermutationIterator.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,107 @@ +/* + * 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.commons.rdf.impl.utils.graphmatching; + + + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +/** + * + * An Iterator over all permuations of a list. + * + * @author reto + */ +class PermutationIterator<T> implements Iterator<List<T>> { + + private Iterator<List<T>> restIterator; + private List<T> list; + private List<T> next; + int posInList = 0; //the position of the last element of next returned list + //with list, this is the one excluded from restIterator + + PermutationIterator(List<T> list) { + this.list = Collections.unmodifiableList(list); + if (list.size() > 1) { + createRestList(); + } + prepareNext(); + } + + @Override + public boolean hasNext() { + return next != null; + } + + @Override + public List<T> next() { + List<T> result = next; + if (result == null) { + throw new NoSuchElementException(); + } + prepareNext(); + return result; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Not supported"); + } + + private void createRestList() { + List<T> restList = new ArrayList<T>(list); + restList.remove(posInList); + restIterator = new PermutationIterator<T>(restList); + } + + private void prepareNext() { + next = getNext(); + + } + private List<T> getNext() { + if (list.size() == 0) { + return null; + } + if (list.size() == 1) { + if (posInList++ == 0) { + return new ArrayList<T>(list); + } else { + return null; + } + } else { + if (!restIterator.hasNext()) { + if (posInList < (list.size()-1)) { + posInList++; + createRestList(); + } else { + return null; + } + } + List<T> result = restIterator.next(); + result.add(list.get(posInList)); + return result; + } + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/Utils.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/Utils.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/Utils.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/Utils.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,82 @@ +package org.apache.commons.rdf.impl.utils.graphmatching; +/* + * + * 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. + * +*/ + + +import java.util.Collection; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; + +import org.apache.commons.rdf.BlankNode; +import org.apache.commons.rdf.Triple; + +public class Utils { + + static Set<BlankNode> getBNodes(Collection<Triple> s) { + Set<BlankNode> result = new HashSet<BlankNode>(); + for (Triple triple : s) { + if (triple.getSubject() instanceof BlankNode) { + result.add((BlankNode) triple.getSubject()); + } + if (triple.getObject() instanceof BlankNode) { + result.add((BlankNode) triple.getObject()); + } + } + return result; + } + + /** + * removes the common grounded triples from s1 and s2. returns false if + * a grounded triple is not in both sets, true otherwise + */ + static boolean removeGrounded(Collection<Triple> s1, Collection<Triple> s2) { + Iterator<Triple> triplesIter = s1.iterator(); + while (triplesIter.hasNext()) { + Triple triple = triplesIter.next(); + if (!isGrounded(triple)) { + continue; + } + if (!s2.remove(triple)) { + return false; + } + triplesIter.remove(); + } + //for efficiency we might skip this (redefine method) + for (Triple triple : s2) { + if (isGrounded(triple)) { + return false; + } + } + return true; + } + + private static boolean isGrounded(Triple triple) { + if (triple.getSubject() instanceof BlankNode) { + return false; + } + if (triple.getObject() instanceof BlankNode) { + return false; + } + return true; + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashMap.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashMap.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashMap.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashMap.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,377 @@ +/* + * Copyright 2002-2004 The Apache Software Foundation. + * + * Licensed 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. + */ + +/* + * Note: originally released under the GNU LGPL v2.1, + * but rereleased by the original author under the ASF license (above). + */ + +package org.apache.commons.rdf.impl.utils.graphmatching.collections; + + + +/** + * <p>A hash map that uses primitive ints for the key rather than objects.</p> + * + * <p>Note that this class is for internal optimization purposes only, and may + * not be supported in future releases of Jakarta Commons Lang. Utilities of + * this sort may be included in future releases of Jakarta Commons Collections.</p> + * + * @author Justin Couch + * @author Alex Chaffee ([email protected]) + * @author Stephen Colebourne + * @since 2.0 + * @version $Revision: 1.2 $ + * @see java.util.HashMap + */ +public class IntHashMap<T> { + + + private IntSet keySet = new IntHashSet(); + + /** + * The hash table data. + */ + private transient Entry<T> table[]; + + /** + * The total number of entries in the hash table. + */ + private transient int count; + + /** + * The table is rehashed when its size exceeds this threshold. (The + * value of this field is (int)(capacity * loadFactor).) + * + * @serial + */ + private int threshold; + + /** + * The load factor for the hashtable. + * + * @serial + */ + private float loadFactor; + + /** + * <p>Innerclass that acts as a datastructure to create a new entry in the + * table.</p> + */ + private static class Entry<T> { + int hash; + int key; + T value; + Entry<T> next; + + /** + * <p>Create a new entry with the given values.</p> + * + * @param hash The code used to hash the object with + * @param key The key used to enter this in the table + * @param value The value for this key + * @param next A reference to the next entry in the table + */ + protected Entry(int hash, int key, T value, Entry<T> next) { + this.hash = hash; + this.key = key; + this.value = value; + this.next = next; + } + } + + /** + * <p>Constructs a new, empty hashtable with a default capacity and load + * factor, which is <code>20</code> and <code>0.75</code> respectively.</p> + */ + public IntHashMap() { + this(20, 0.75f); + } + + /** + * <p>Constructs a new, empty hashtable with the specified initial capacity + * and default load factor, which is <code>0.75</code>.</p> + * + * @param initialCapacity the initial capacity of the hashtable. + * @throws IllegalArgumentException if the initial capacity is less + * than zero. + */ + public IntHashMap(int initialCapacity) { + this(initialCapacity, 0.75f); + } + + /** + * <p>Constructs a new, empty hashtable with the specified initial + * capacity and the specified load factor.</p> + * + * @param initialCapacity the initial capacity of the hashtable. + * @param loadFactor the load factor of the hashtable. + * @throws IllegalArgumentException if the initial capacity is less + * than zero, or if the load factor is nonpositive. + */ + public IntHashMap(int initialCapacity, float loadFactor) { + super(); + if (initialCapacity < 0) { + throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); + } + if (loadFactor <= 0) { + throw new IllegalArgumentException("Illegal Load: " + loadFactor); + } + if (initialCapacity == 0) { + initialCapacity = 1; + } + + this.loadFactor = loadFactor; + table = new Entry[initialCapacity]; + threshold = (int) (initialCapacity * loadFactor); + } + + /** + * <p>Returns the number of keys in this hashtable.</p> + * + * @return the number of keys in this hashtable. + */ + public int size() { + return count; + } + + /** + * <p>Tests if this hashtable maps no keys to values.</p> + * + * @return <code>true</code> if this hashtable maps no keys to values; + * <code>false</code> otherwise. + */ + public boolean isEmpty() { + return count == 0; + } + + /** + * <p>Tests if some key maps into the specified value in this hashtable. + * This operation is more expensive than the <code>containsKey</code> + * method.</p> + * + * <p>Note that this method is identical in functionality to containsValue, + * (which is part of the Map interface in the collections framework).</p> + * + * @param value a value to search for. + * @return <code>true</code> if and only if some key maps to the + * <code>value</code> argument in this hashtable as + * determined by the <tt>equals</tt> method; + * <code>false</code> otherwise. + * @throws NullPointerException if the value is <code>null</code>. + * @see #containsKey(int) + * @see #containsValue(Object) + * @see java.util.Map + */ + public boolean contains(Object value) { + if (value == null) { + throw new NullPointerException(); + } + + Entry tab[] = table; + for (int i = tab.length; i-- > 0;) { + for (Entry e = tab[i]; e != null; e = e.next) { + if (e.value.equals(value)) { + return true; + } + } + } + return false; + } + + /** + * <p>Returns <code>true</code> if this HashMap maps one or more keys + * to this value.</p> + * + * <p>Note that this method is identical in functionality to contains + * (which predates the Map interface).</p> + * + * @param value value whose presence in this HashMap is to be tested. + * @see java.util.Map + * @since JDK1.2 + */ + public boolean containsValue(Object value) { + return contains(value); + } + + /** + * <p>Tests if the specified object is a key in this hashtable.</p> + * + * @param key possible key. + * @return <code>true</code> if and only if the specified object is a + * key in this hashtable, as determined by the <tt>equals</tt> + * method; <code>false</code> otherwise. + * @see #contains(Object) + */ + public boolean containsKey(int key) { + Entry tab[] = table; + int hash = key; + int index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry e = tab[index]; e != null; e = e.next) { + if (e.hash == hash) { + return true; + } + } + return false; + } + + /** + * <p>Returns the value to which the specified key is mapped in this map.</p> + * + * @param key a key in the hashtable. + * @return the value to which the key is mapped in this hashtable; + * <code>null</code> if the key is not mapped to any value in + * this hashtable. + * @see #put(int, Object) + */ + public T get(int key) { + Entry<T> tab[] = table; + int hash = key; + int index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry<T> e = tab[index]; e != null; e = e.next) { + if (e.hash == hash) { + return e.value; + } + } + return null; + } + + /** + * <p>Increases the capacity of and internally reorganizes this + * hashtable, in order to accommodate and access its entries more + * efficiently.</p> + * + * <p>This method is called automatically when the number of keys + * in the hashtable exceeds this hashtable's capacity and load + * factor.</p> + */ + protected void rehash() { + int oldCapacity = table.length; + Entry<T> oldMap[] = table; + + int newCapacity = oldCapacity * 2 + 1; + Entry<T> newMap[] = new Entry[newCapacity]; + + threshold = (int) (newCapacity * loadFactor); + table = newMap; + + for (int i = oldCapacity; i-- > 0;) { + for (Entry<T> old = oldMap[i]; old != null;) { + Entry<T> e = old; + old = old.next; + + int index = (e.hash & 0x7FFFFFFF) % newCapacity; + e.next = newMap[index]; + newMap[index] = e; + } + } + } + + /** + * <p>Maps the specified <code>key</code> to the specified + * <code>value</code> in this hashtable. The key cannot be + * <code>null</code>. </p> + * + * <p>The value can be retrieved by calling the <code>get</code> method + * with a key that is equal to the original key.</p> + * + * @param key the hashtable key. + * @param value the value. + * @return the previous value of the specified key in this hashtable, + * or <code>null</code> if it did not have one. + * @throws NullPointerException if the key is <code>null</code>. + * @see #get(int) + */ + public Object put(int key, T value) { + keySet.add(key); + // Makes sure the key is not already in the hashtable. + Entry<T> tab[] = table; + int hash = key; + int index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry<T> e = tab[index]; e != null; e = e.next) { + if (e.hash == hash) { + T old = e.value; + e.value = value; + return old; + } + } + + if (count >= threshold) { + // Rehash the table if the threshold is exceeded + rehash(); + + tab = table; + index = (hash & 0x7FFFFFFF) % tab.length; + } + + // Creates the new entry. + Entry<T> e = new Entry<T>(hash, key, value, tab[index]); + tab[index] = e; + count++; + return null; + } + + /** + * <p>Removes the key (and its corresponding value) from this + * hashtable.</p> + * + * <p>This method does nothing if the key is not present in the + * hashtable.</p> + * + * @param key the key that needs to be removed. + * @return the value to which the key had been mapped in this hashtable, + * or <code>null</code> if the key did not have a mapping. + */ + /*public Object remove(int key) { + Entry tab[] = table; + int hash = key; + int index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { + if (e.hash == hash) { + if (prev != null) { + prev.next = e.next; + } else { + tab[index] = e.next; + } + count--; + Object oldValue = e.value; + e.value = null; + return oldValue; + } + } + return null; + }*/ + + /** + * <p>Clears this hashtable so that it contains no keys.</p> + */ + public synchronized void clear() { + keySet.clear(); + Entry tab[] = table; + for (int index = tab.length; --index >= 0;) { + tab[index] = null; + } + count = 0; + } + + public IntSet keySet() { + return keySet; + } + + + +} + Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashSet.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashSet.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashSet.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntHashSet.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,62 @@ +/* + * Copyright 2002-2004 The Apache Software Foundation. + * + * Licensed 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.commons.rdf.impl.utils.graphmatching.collections; + +import java.util.HashSet; +import java.util.Iterator; + +/** + * This is currently just a placeholder implementation based onm HashSet<Integer> + * an efficient implementation is to store the primitives directly. + * + * @author reto + */ +public class IntHashSet extends HashSet<Integer> implements IntSet { + + @Override + public IntIterator intIterator() { + final Iterator<Integer> base = iterator(); + return new IntIterator() { + + @Override + public int nextInt() { + return base.next(); + } + + @Override + public boolean hasNext() { + return base.hasNext(); + } + + @Override + public Integer next() { + return base.next(); + } + + @Override + public void remove() { + base.remove(); + } + }; + } + + @Override + public void add(int i) { + super.add((Integer)i); + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntIterator.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntIterator.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntIterator.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntIterator.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,30 @@ +/* + * Copyright 2002-2004 The Apache Software Foundation. + * + * Licensed 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.commons.rdf.impl.utils.graphmatching.collections; + +import java.util.Iterator; + + +/** + * An iterator allowing to iterate over ints, Iterator<Integer> is extended for + * compatibility, however accessing nextInt allows faster implementations. + * + * @author reto + */ +public interface IntIterator extends Iterator<Integer> { + public int nextInt(); +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntSet.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntSet.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntSet.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/graphmatching/collections/IntSet.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,35 @@ +/* + * Copyright 2002-2004 The Apache Software Foundation. + * + * Licensed 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.commons.rdf.impl.utils.graphmatching.collections; + +import java.util.Set; + +/** + * A IntSet allows directly adding primitive ints to a set, Set<Integer> is + * extended, but accessingt he respective methods is less efficient. + * + * @author reto + */ +public interface IntSet extends Set<Integer> { + /** + * + * @return an iterator over the primitive int + */ + public IntIterator intIterator(); + + public void add(int i); +} Copied: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/package-info.java (from r1651181, commons/sandbox/rdf/trunk/src/main/java/org/apache/commons/rdf/package-info.java) URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/package-info.java?p2=commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/package-info.java&p1=commons/sandbox/rdf/trunk/src/main/java/org/apache/commons/rdf/package-info.java&r1=1651181&r2=1659973&rev=1659973&view=diff ============================================================================== --- commons/sandbox/rdf/trunk/src/main/java/org/apache/commons/rdf/package-info.java (original) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/package-info.java Sun Feb 15 18:41:15 2015 @@ -16,6 +16,6 @@ */ /** - * Common RDF API + * Common RDF API Implementation utilities. */ -package org.apache.commons.rdf; \ No newline at end of file +package org.apache.commons.rdf.impl.utils; \ No newline at end of file Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraph.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraph.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraph.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraph.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,221 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import org.apache.commons.rdf.impl.utils.AbstractGraph; +import java.lang.ref.SoftReference; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.ConcurrentModificationException; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import org.apache.commons.rdf.BlankNodeOrIri; +import org.apache.commons.rdf.ImmutableGraph; +import org.apache.commons.rdf.RdfTerm; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.Iri; + +/** + * For now this is a minimalistic implementation, without any indexes or other + * optimizations. + * + * This class is not public, implementations should use {@link SimpleGraph} or + * {@link SimpleMGraph}. + * + * @author reto + */ +class SimpleGraph extends AbstractGraph { + + final Set<Triple> triples; + + private boolean checkConcurrency = false; + + class SimpleIterator implements Iterator<Triple> { + + private Iterator<Triple> listIter; + private boolean isValid = true; + + public SimpleIterator(Iterator<Triple> listIter) { + this.listIter = listIter; + } + private Triple currentNext; + + @Override + public boolean hasNext() { + checkValidity(); + return listIter.hasNext(); + } + + @Override + public Triple next() { + checkValidity(); + currentNext = listIter.next(); + return currentNext; + } + + @Override + public void remove() { + checkValidity(); + listIter.remove(); + triples.remove(currentNext); + invalidateIterators(this); + } + + private void checkValidity() throws ConcurrentModificationException { + if (checkConcurrency && !isValid) { + throw new ConcurrentModificationException(); + } + } + + private void invalidate() { + isValid = false; + } + } + + private final Set<SoftReference<SimpleIterator>> iterators = + Collections.synchronizedSet(new HashSet<SoftReference<SimpleIterator>>()); + + /** + * Creates an empty SimpleGraph + */ + public SimpleGraph() { + triples = Collections.synchronizedSet(new HashSet<Triple>()); + } + + /** + * Creates a SimpleGraph using the passed iterator, the iterator + * is consumed before the constructor returns + * + * @param iterator + */ + public SimpleGraph(Iterator<Triple> iterator) { + triples = new HashSet<Triple>(); + while (iterator.hasNext()) { + Triple triple = iterator.next(); + triples.add(triple); + } + } + + /** + * Creates a SimpleGraph for the specified set of triples, + * subsequent modification of baseSet do affect the created instance. + * + * @param baseSet + */ + public SimpleGraph(Set<Triple> baseSet) { + this.triples = baseSet; + } + + /** + * Creates a SimpleGraph for the specified collection of triples, + * subsequent modification of baseSet do not affect the created instance. + * + * @param baseSet + */ + public SimpleGraph(Collection<Triple> baseCollection) { + this.triples = new HashSet<Triple>(baseCollection); + } + + @Override + public int performSize() { + return triples.size(); + } + + @Override + public Iterator<Triple> performFilter(final BlankNodeOrIri subject, final Iri predicate, final RdfTerm object) { + final List<Triple> tripleList = new ArrayList<Triple>(); + synchronized (triples) { + Iterator<Triple> baseIter = triples.iterator(); + while (baseIter.hasNext()) { + Triple triple = baseIter.next(); + if ((subject != null) + && (!triple.getSubject().equals(subject))) { + continue; + } + if ((predicate != null) + && (!triple.getPredicate().equals(predicate))) { + continue; + } + if ((object != null) + && (!triple.getObject().equals(object))) { + continue; + } + tripleList.add(triple); + } + + final Iterator<Triple> listIter = tripleList.iterator(); + SimpleIterator resultIter = new SimpleIterator(listIter); + if (checkConcurrency) { + iterators.add(new SoftReference<SimpleIterator>(resultIter)); + } + return resultIter; + } + } + + + @Override + public boolean performAdd(Triple e) { + boolean modified = triples.add(e); + if (modified) { + invalidateIterators(null); + } + return modified; + } + + private void invalidateIterators(SimpleIterator caller) { + if (!checkConcurrency) { + return; + } + Set<SoftReference> oldReferences = new HashSet<SoftReference>(); + synchronized(iterators) { + for (SoftReference<SimpleGraph.SimpleIterator> softReference : iterators) { + SimpleIterator simpleIterator = softReference.get(); + if (simpleIterator == null) { + oldReferences.add(softReference); + continue; + } + if (simpleIterator != caller) { + simpleIterator.invalidate(); + } + } + } + iterators.removeAll(oldReferences); + } + + /** + * Specifies whether or not to throw <code>ConcurrentModificationException</code>s, + * if this simple triple collection is modified concurrently. Concurrency + * check is set to false by default. + * + * @param bool Specifies whether or not to check concurrent modifications. + */ + public void setCheckConcurrency(boolean bool) { + checkConcurrency = bool; + } + + + @Override + public ImmutableGraph getImmutableGraph() { + return new SimpleImmutableGraph(this); + } +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleImmutableGraph.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleImmutableGraph.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleImmutableGraph.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleImmutableGraph.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,79 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import org.apache.commons.rdf.impl.utils.AbstractImmutableGraph; +import java.util.Iterator; + +import org.apache.commons.rdf.BlankNodeOrIri; +import org.apache.commons.rdf.RdfTerm; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.Graph; +import org.apache.commons.rdf.Iri; + +/** + * + * @author reto + */ +public class SimpleImmutableGraph extends AbstractImmutableGraph { + + private Graph graph; + + /** + * Creates a ImmutableGraph with the triples in Graph + * + * @param Graph the collection of triples this ImmutableGraph shall consist of + */ + public SimpleImmutableGraph(Graph Graph) { + this.graph = new SimpleGraph(Graph.iterator()); + } + + /** + * Creates a ImmutableGraph with the triples in Graph. + * + * This construction allows to specify if the Graph might change + * in future. If GraphWillNeverChange is set to true it will + * assume that the collection never changes, in this case the collection + * isn't copied making things more efficient. + * + * @param Graph the collection of triples this ImmutableGraph shall consist of + * @param GraphWillNeverChange true if the caller promises Graph will never change + */ + public SimpleImmutableGraph(Graph Graph, boolean GraphWillNeverChange) { + if (!GraphWillNeverChange) { + this.graph = new SimpleGraph(Graph.iterator()); + } else { + this.graph = Graph; + } + } + + public SimpleImmutableGraph(Iterator<Triple> tripleIter) { + this.graph = new SimpleGraph(tripleIter); + } + + @Override + public int performSize() { + return graph.size(); + } + + @Override + public Iterator<Triple> performFilter(BlankNodeOrIri subject, Iri predicate, RdfTerm object) { + return graph.filter(subject, predicate, object); + } +} Added: commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleMGraph.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleMGraph.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleMGraph.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/main/java/org/apache/commons/rdf/impl/utils/simple/SimpleMGraph.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,55 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import java.util.Collection; +import java.util.Iterator; +import java.util.Set; + +import org.apache.commons.rdf.ImmutableGraph; +import org.apache.commons.rdf.Graph; +import org.apache.commons.rdf.Triple; + +/** + * + * @author reto + */ +public class SimpleMGraph extends SimpleGraph implements Graph { + + /** + * Creates an empty SimpleMGraph + */ + public SimpleMGraph() { + } + + public SimpleMGraph(Set<Triple> baseSet) { + super(baseSet); + } + + public SimpleMGraph(Collection<Triple> baseCollection) { + super(baseCollection); + } + + public SimpleMGraph(Iterator<Triple> iterator) { + super(iterator); + } + +} + + \ No newline at end of file Added: commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/PlainLiteralImplTest.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/PlainLiteralImplTest.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/PlainLiteralImplTest.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/PlainLiteralImplTest.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,71 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import org.apache.commons.rdf.impl.utils.PlainLiteralImpl; +import org.junit.Test; +import junit.framework.Assert; + +import org.apache.commons.rdf.Language; +import org.apache.commons.rdf.Literal; +/** + * + * @author reto + * + */ + +public class PlainLiteralImplTest { + + + @Test public void plainLiteralEquality() { + String stringValue = "some text"; + Literal literal1 = new PlainLiteralImpl(stringValue); + Literal literal2 = new PlainLiteralImpl(stringValue); + Assert.assertEquals(literal1, literal2); + Assert.assertEquals(literal1.hashCode(), literal2.hashCode()); + Literal literal3 = new PlainLiteralImpl("something else"); + Assert.assertFalse(literal1.equals(literal3)); + } + + @Test public void languageLiteralEquality() { + String stringValue = "some text"; + Language lang = new Language("en-ca"); + Literal literal1 = new PlainLiteralImpl(stringValue, lang); + Literal literal2 = new PlainLiteralImpl(stringValue, lang); + Assert.assertEquals(literal1, literal2); + Assert.assertEquals(literal1.hashCode(), literal2.hashCode()); + Language lang2 = new Language("de"); + Literal literal3 = new PlainLiteralImpl(stringValue, lang2); + Assert.assertFalse(literal1.equals(literal3)); + Literal literal4 = new PlainLiteralImpl(stringValue, null); + Assert.assertFalse(literal3.equals(literal4)); + Assert.assertFalse(literal4.equals(literal3)); + } + + /** + * hashCode of the lexical form plus the hashCode of the locale + */ + @Test public void checkHashCode() { + String stringValue = "some text"; + Language language = new Language("en"); + Literal literal = new PlainLiteralImpl(stringValue, language); + Assert.assertEquals(stringValue.hashCode() + language.hashCode(), literal.hashCode()); + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraphTest.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraphTest.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraphTest.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/SimpleGraphTest.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,109 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import org.apache.commons.rdf.impl.utils.TripleImpl; +import java.util.ConcurrentModificationException; +import java.util.Iterator; +import org.junit.Assert; +import org.junit.Test; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.Iri; +import org.apache.commons.rdf.impl.utils.simple.SimpleGraph; + +/** + * + * @author mir + */ +public class SimpleGraphTest { + + private Iri uriRef1 = new Iri("http://example.org/foo";); + private Iri uriRef2 = new Iri("http://example.org/bar";); + private Iri uriRef3 = new Iri("http://example.org/test";); + private Triple triple1 = new TripleImpl(uriRef1, uriRef2, uriRef3); + private Triple triple2 = new TripleImpl(uriRef2, uriRef2, uriRef1); + private Triple triple3 = new TripleImpl(uriRef3, uriRef1, uriRef3); + private Triple triple4 = new TripleImpl(uriRef1, uriRef3, uriRef2); + private Triple triple5 = new TripleImpl(uriRef2, uriRef3, uriRef2); + + @Test + public void iteratorRemove() { + SimpleGraph stc = new SimpleGraph(); + stc.add(triple1); + stc.add(triple2); + stc.add(triple3); + stc.add(triple4); + stc.add(triple5); + Iterator<Triple> iter = stc.iterator(); + while (iter.hasNext()) { + Triple triple = iter.next(); + iter.remove(); + } + Assert.assertEquals(0, stc.size()); + } + + @Test + public void removeAll() { + SimpleGraph stc = new SimpleGraph(); + stc.add(triple1); + stc.add(triple2); + stc.add(triple3); + stc.add(triple4); + stc.add(triple5); + SimpleGraph stc2 = new SimpleGraph(); + stc2.add(triple1); + stc2.add(triple3); + stc2.add(triple5); + stc.removeAll(stc2); + Assert.assertEquals(2, stc.size()); + } + + @Test + public void filterIteratorRemove() { + SimpleGraph stc = new SimpleGraph(); + stc.add(triple1); + stc.add(triple2); + stc.add(triple3); + stc.add(triple4); + stc.add(triple5); + Iterator<Triple> iter = stc.filter(uriRef1, null, null); + while (iter.hasNext()) { + Triple triple = iter.next(); + iter.remove(); + } + Assert.assertEquals(3, stc.size()); + } + + @Test(expected=ConcurrentModificationException.class) + public void remove() { + SimpleGraph stc = new SimpleGraph(); + stc.setCheckConcurrency(true); + stc.add(triple1); + stc.add(triple2); + stc.add(triple3); + stc.add(triple4); + stc.add(triple5); + Iterator<Triple> iter = stc.filter(uriRef1, null, null); + while (iter.hasNext()) { + Triple triple = iter.next(); + stc.remove(triple); + } + Assert.assertEquals(3, stc.size()); + } +} Added: commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TripleImplTest.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TripleImplTest.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TripleImplTest.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TripleImplTest.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,57 @@ +/* + * To change this template, choose Tools | Templates + * and open the template in the editor. + */ + +package org.apache.commons.rdf.impl.utils.simple; +/* + * + * 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. + * +*/ + + +import org.junit.Test; +import junit.framework.Assert; + +import org.apache.commons.rdf.BlankNodeOrIri; +import org.apache.commons.rdf.RdfTerm; +import org.apache.commons.rdf.Triple; +import org.apache.commons.rdf.Iri; +import org.apache.commons.rdf.impl.utils.PlainLiteralImpl; +import org.apache.commons.rdf.impl.utils.TripleImpl; +/** + * + * @author reto + * + */ + +public class TripleImplTest { + + + @Test public void tripleEquality() { + BlankNodeOrIri subject = new Iri("http://example.org/";); + Iri predicate = new Iri("http://example.org/property";); + RdfTerm object = new PlainLiteralImpl("property value"); + Triple triple1 = new TripleImpl(subject, predicate, object); + Triple triple2 = new TripleImpl(subject, predicate, object); + Assert.assertEquals(triple1.hashCode(), triple2.hashCode()); + Assert.assertEquals(triple1, triple2); + } + +} Added: commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TypedLiteralImplTest.java URL: http://svn.apache.org/viewvc/commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TypedLiteralImplTest.java?rev=1659973&view=auto ============================================================================== --- commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TypedLiteralImplTest.java (added) +++ commons/sandbox/rdf/trunk/impl.utils/src/test/java/org/apache/commons/rdf/impl/utils/simple/TypedLiteralImplTest.java Sun Feb 15 18:41:15 2015 @@ -0,0 +1,67 @@ +/* + * 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.commons.rdf.impl.utils.simple; + +import org.apache.commons.rdf.impl.utils.TypedLiteralImpl; +import org.junit.Test; +import junit.framework.Assert; + +import org.apache.commons.rdf.Iri; +import org.apache.commons.rdf.Literal; +/** + * + * @author reto/** + * + * @author reto/** + * + * @author reto/** + * + * @author reto + * + */ + +public class TypedLiteralImplTest { + + + @Test public void typedLiteralEquality() { + String stringValue = "some text"; + Iri uriRef = new Iri("http://example.org/datatypes/magic";); + Literal literal1 = new TypedLiteralImpl(stringValue, uriRef); + Literal literal2 = new TypedLiteralImpl(stringValue, uriRef); + Assert.assertEquals(literal1, literal2); + Assert.assertEquals(literal1.hashCode(), literal2.hashCode()); + Literal literal3 = new TypedLiteralImpl("something else", uriRef); + Assert.assertFalse(literal1.equals(literal3)); + Iri uriRef2 = new Iri("http://example.org/datatypes/other";); + Literal literal4 = new TypedLiteralImpl(stringValue, uriRef2); + Assert.assertFalse(literal1.equals(literal4)); + } + + + /** + * The hascode is equals to the hascode of the lexical form plus the hashcode of the dataTyp + */ + @Test public void checkHashCode() { + String stringValue = "some text"; + Iri uriRef = new Iri("http://example.org/datatypes/magic";); + Literal literal = new TypedLiteralImpl(stringValue, uriRef); + Assert.assertEquals(stringValue.hashCode() + uriRef.hashCode(), literal.hashCode()); + } + +}
