X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fext%2Fso%2FSequenceOntology.java;h=8a3805d1fb49c5c346274e4f215d6f14979edded;hb=9fcb12165750b20f8a73d0bb976b22be5fda94a2;hp=784229460e1320e576af3a657d800b5649336097;hpb=cd61435e058e0bf9b60292149c20299be7b4cf1f;p=jalview.git

diff --git a/src/jalview/ext/so/SequenceOntology.java b/src/jalview/ext/so/SequenceOntology.java
index 7842294..8a3805d 100644
--- a/src/jalview/ext/so/SequenceOntology.java
+++ b/src/jalview/ext/so/SequenceOntology.java
@@ -35,6 +35,7 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
+import java.util.Set;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipInputStream;
 
@@ -473,4 +474,82 @@ public class SequenceOntology extends OntologyBase
       return termsNotFound;
     }
   }
+
+  /**
+   * {@inheritDoc}
+   * 
+   * @throws IllegalStateException
+   *           if a loop is detected in the ontology
+   */
+  @Override
+  public List<String> getRootParents(final String term)
+  {
+    /*
+     * check in cache first
+     */
+    if (rootParents.containsKey(term))
+    {
+      return rootParents.get(term);
+    }
+    Term t = getTerm(term);
+    if (t == null)
+    {
+      return null;
+    }
+
+    /*
+     * todo: check for loops using 'seen', allowing for alternate paths e.g.
+     * stop_gained isA feature_truncation isA feature_variant
+     * " isA nonsynonymous_variant ... isA geneVariant isA feature_variant 
+     */
+    List<Term> seen = new ArrayList<>();
+    List<Term> top = new ArrayList<>();
+    List<Term> query = new ArrayList<>();
+    query.add(t);
+
+    while (!query.isEmpty())
+    {
+      List<Term> nextQuery = new ArrayList<>();
+      for (Term q : query)
+      {
+        Set<Triple> parents = ontology.getTriples(q, null, isA);
+        if (parents.isEmpty())
+        {
+          /*
+           * q has no parents so is a top level term
+           */
+          top.add(q);
+        }
+        else
+        {
+          /*
+           * search all parent terms
+           */
+          for (Triple triple : parents)
+          {
+            Term parent = triple.getObject();
+            nextQuery.add(parent);
+          }
+        }
+      }
+      query = nextQuery;
+    }
+
+    List<String> result = new ArrayList<>();
+    for (Term found : top)
+    {
+      String desc = found.getDescription();
+      if (!result.contains(desc))
+      {
+        result.add(desc);
+      }
+    }
+
+    /*
+     * save result in cache
+     */
+    rootParents.put(term, result);
+
+    return result;
+  }
 }