From a83adb45bdf9554e270921b4baad94defd314b36 Mon Sep 17 00:00:00 2001 From: Ben Soares Date: Fri, 30 Aug 2019 17:19:52 +0100 Subject: [PATCH] JAL-3210 Improvements to eclipse detection. New src tree and SwingJS updated from the applet branch. AND IT WORKS (sometimes) --- README | 2 +- build.gradle | 31 +- gradle.properties | 3 +- src/com/stevesoft/pat/RegOpt.java | 8 +- src/com/stevesoft/pat/Regex.java | 7 +- src/com/stevesoft/pat/RegexReader.java | 4 - src/com/stevesoft/pat/RegexTokenizer.java | 4 +- src/ext/edu/ucsf/rbvi/strucviz2/ChimUtils.java | 4 +- src/ext/edu/ucsf/rbvi/strucviz2/ChimeraChain.java | 2 +- .../edu/ucsf/rbvi/strucviz2/StructureManager.java | 19 +- src/ext/vamsas/JpredSoapBindingStub.java | 6 +- src/ext/vamsas/MuscleWSSoapBindingStub.java | 6 +- src/ext/vamsas/RegistryServiceSoapBindingStub.java | 3 +- .../vamsas/SeqSearchServiceSoapBindingStub.java | 7 +- src/ext/vamsas/ServiceHandle.java | 4 +- src/intervalstore/api/IntervalI.java | 192 + src/intervalstore/api/IntervalStoreI.java | 96 + src/intervalstore/impl/BinarySearcher.java | 91 + src/intervalstore/impl/IntervalStore.java | 543 ++ src/intervalstore/impl/NCList.java | 752 +++ src/intervalstore/impl/NCListBuilder.java | 143 + src/intervalstore/impl/NCNode.java | 381 ++ src/intervalstore/nonc/IntervalStore.java | 1053 +++ src/jalview/analysis/AlignmentSorter.java | 147 +- src/jalview/analysis/Conservation.java | 4 +- src/jalview/analysis/CrossRef.java | 26 +- src/jalview/analysis/Finder.java | 3 +- src/jalview/analysis/GeneticCodes.java | 91 +- src/jalview/analysis/ParseProperties.java | 5 +- src/jalview/analysis/SeqsetUtils.java | 4 +- src/jalview/analysis/StructureFrequency.java | 12 +- .../analysis/scoremodels/FeatureDistanceModel.java | 15 +- src/jalview/analysis/scoremodels/ScoreMatrix.java | 3 +- src/jalview/analysis/scoremodels/ScoreModels.java | 30 +- .../analysis/scoremodels/SimilarityParams.java | 14 + src/jalview/api/AlignFrameI.java | 13 + src/jalview/api/AlignViewportI.java | 6 + src/jalview/api/AlignmentColsCollectionI.java | 18 + src/jalview/api/AlignmentViewPanel.java | 7 + src/jalview/api/FeatureColourI.java | 5 +- src/jalview/api/FeatureRenderer.java | 4 +- src/jalview/api/JalviewApp.java | 82 + src/jalview/appletgui/AlignFrame.java | 16 +- src/jalview/appletgui/AlignViewport.java | 4 +- src/jalview/appletgui/AlignmentPanel.java | 8 + src/jalview/appletgui/AnnotationColourChooser.java | 7 +- src/jalview/appletgui/AnnotationLabels.java | 4 +- src/jalview/appletgui/AnnotationPanel.java | 4 +- src/jalview/appletgui/EmbmenuFrame.java | 16 +- src/jalview/appletgui/FeatureColourChooser.java | 2 +- src/jalview/appletgui/FeatureSettings.java | 2 +- src/jalview/appletgui/FontChooser.java | 6 +- src/jalview/appletgui/IdPanel.java | 4 +- src/jalview/appletgui/OverviewCanvas.java | 75 +- src/jalview/appletgui/OverviewPanel.java | 45 +- src/jalview/appletgui/ScalePanel.java | 4 +- src/jalview/appletgui/SeqPanel.java | 5 +- src/jalview/appletgui/TreePanel.java | 6 +- src/jalview/bin/AppletParams.java | 447 ++ src/jalview/bin/ApplicationSingletonProvider.java | 164 + src/jalview/bin/ArgsParser.java | 101 +- src/jalview/bin/Cache.java | 241 +- src/jalview/bin/Jalview.java | 1666 +++-- src/jalview/bin/JalviewAppLoader.java | 1483 ++++ src/jalview/bin/JalviewJS2.java | 29 +- src/jalview/bin/JalviewJSApi.java | 52 + src/jalview/bin/JalviewLite.java | 1209 ++-- src/jalview/bin/JalviewTaskbar.java | 39 - src/jalview/bin/Launcher.java | 178 - src/jalview/bin/MemorySetting.java | 51 - src/jalview/commands/ChangeCaseCommand.java | 16 +- src/jalview/controller/AlignViewController.java | 14 +- src/jalview/datamodel/Alignment.java | 39 +- src/jalview/datamodel/AlignmentAnnotation.java | 4 +- src/jalview/datamodel/AlignmentI.java | 6 + src/jalview/datamodel/AllColsCollection.java | 23 + src/jalview/datamodel/BinarySequence.java | 2 +- src/jalview/datamodel/ColumnSelection.java | 6 +- src/jalview/datamodel/DBRefEntry.java | 3 +- src/jalview/datamodel/DBRefSource.java | 15 +- src/jalview/datamodel/HiddenColumns.java | 33 +- src/jalview/datamodel/PDBEntry.java | 23 +- src/jalview/datamodel/ResidueCount.java | 5 +- .../datamodel/SecondaryStructureAnnotation.java | 6 +- src/jalview/datamodel/Sequence.java | 73 +- src/jalview/datamodel/SequenceFeature.java | 24 +- src/jalview/datamodel/SequenceI.java | 42 + src/jalview/datamodel/VisibleColsCollection.java | 26 + .../datamodel/features/FeatureAttributes.java | 31 +- src/jalview/datamodel/features/FeatureSources.java | 25 +- src/jalview/datamodel/features/FeatureStore.java | 914 ++- src/jalview/datamodel/features/FeatureStoreI.java | 58 + .../datamodel/features/FeatureStoreImpl.java | 304 + src/jalview/datamodel/features/FeatureStoreJS.java | 414 ++ .../datamodel/features/SequenceFeatures.java | 172 +- .../datamodel/features/SequenceFeaturesI.java | 19 + src/jalview/ext/ensembl/EnsemblCdna.java | 15 +- src/jalview/ext/ensembl/EnsemblCds.java | 2 +- src/jalview/ext/ensembl/EnsemblGene.java | 10 +- src/jalview/ext/ensembl/EnsemblInfo.java | 94 +- src/jalview/ext/ensembl/EnsemblMap.java | 24 +- src/jalview/ext/ensembl/EnsemblProtein.java | 9 +- src/jalview/ext/ensembl/EnsemblRestClient.java | 2 +- src/jalview/ext/ensembl/EnsemblSeqProxy.java | 12 +- .../ext/ensembl/EnsemblSequenceFetcher.java | 21 +- src/jalview/ext/htsjdk/VCFReader.java | 12 +- src/jalview/ext/jmol/JalviewJmolBinding.java | 71 +- src/jalview/ext/paradise/Annotate3D.java | 140 +- src/jalview/ext/so/SequenceOntology.java | 10 +- src/jalview/fts/core/FTSRestRequest.java | 3 +- src/jalview/fts/service/pdb/PDBFTSRestClient.java | 25 +- .../fts/service/uniprot/UniProtFTSRestClient.java | 36 +- src/jalview/gui/APQHandlers.java | 151 - src/jalview/gui/AlignExportOptions.java | 2 +- src/jalview/gui/AlignFrame.java | 345 +- src/jalview/gui/AlignViewport.java | 160 +- src/jalview/gui/AlignmentPanel.java | 181 +- src/jalview/gui/AnnotationColourChooser.java | 6 +- src/jalview/gui/AnnotationColumnChooser.java | 6 +- src/jalview/gui/AnnotationLabels.java | 8 +- src/jalview/gui/AnnotationPanel.java | 20 +- src/jalview/gui/AppJmol.java | 21 +- src/jalview/gui/AppVarna.java | 6 +- src/jalview/gui/AppVarnaBinding.java | 7 +- src/jalview/gui/AssociatePdbFileWithSeq.java | 77 +- src/jalview/gui/BlogReader.java | 2 +- src/jalview/gui/CalculationChooser.java | 166 +- src/jalview/gui/ChimeraViewFrame.java | 6 +- src/jalview/gui/ColourMenuHelper.java | 8 +- src/jalview/gui/ComboBoxTooltipRenderer.java | 3 +- src/jalview/gui/Console.java | 5 +- src/jalview/gui/CrossRefAction.java | 14 +- src/jalview/gui/CutAndPasteTransfer.java | 9 +- src/jalview/gui/Desktop.java | 411 +- src/jalview/gui/FeatureEditor.java | 12 +- src/jalview/gui/FeatureRenderer.java | 8 +- src/jalview/gui/FeatureSettings.java | 4 +- src/jalview/gui/FeatureTypeSettings.java | 56 +- src/jalview/gui/Finder.java | 4 +- src/jalview/gui/FontChooser.java | 14 +- src/jalview/gui/IdCanvas.java | 44 +- src/jalview/gui/IdPanel.java | 5 +- src/jalview/gui/IdwidthAdjuster.java | 196 +- src/jalview/gui/JalviewAppender.java | 10 +- src/jalview/gui/JalviewDialog.java | 8 +- src/jalview/gui/JvSwingUtils.java | 48 +- src/jalview/gui/LineartOptions.java | 4 +- src/jalview/gui/MenuChooser.java | 99 - src/jalview/gui/OOMWarning.java | 2 +- src/jalview/gui/OverviewCanvas.java | 238 +- src/jalview/gui/OverviewPanel.java | 266 +- src/jalview/gui/PCAPanel.java | 10 +- src/jalview/gui/PopupMenu.java | 35 +- src/jalview/gui/Preferences.java | 472 +- src/jalview/gui/PromptUserConfig.java | 2 +- src/jalview/gui/RotatableCanvas.java | 2 +- src/jalview/gui/ScalePanel.java | 60 +- src/jalview/gui/SeqCanvas.java | 292 +- src/jalview/gui/SeqPanel.java | 82 +- src/jalview/gui/SequenceFetcher.java | 33 +- src/jalview/gui/SequenceRenderer.java | 18 +- src/jalview/gui/SliderPanel.java | 48 +- src/jalview/gui/SplashScreen.java | 15 +- src/jalview/gui/SplitFrame.java | 22 +- src/jalview/gui/StructureChooser.java | 166 +- src/jalview/gui/StructureViewer.java | 143 + src/jalview/gui/StructureViewerBase.java | 2 +- src/jalview/gui/UserDefinedColours.java | 21 +- src/jalview/gui/UserQuestionnaireCheck.java | 12 +- src/jalview/gui/VamsasApplication.java | 20 +- src/jalview/gui/WebserviceInfo.java | 2 +- src/jalview/gui/WsJobParameters.java | 12 +- src/jalview/gui/WsParamSetManager.java | 6 +- src/jalview/gui/WsPreferences.java | 30 +- src/jalview/httpserver/HttpServer.java | 21 +- src/jalview/io/AlignFile.java | 13 +- src/jalview/io/AnnotationFile.java | 6 +- src/jalview/io/BackupFilenameParts.java | 9 +- src/jalview/io/BackupFiles.java | 51 +- src/jalview/io/BackupFilesPresetEntry.java | 173 - src/jalview/io/FeaturesFile.java | 12 +- src/jalview/io/FileFormats.java | 37 +- src/jalview/io/FileLoader.java | 110 +- src/jalview/io/FormatAdapter.java | 12 +- src/jalview/io/HTMLOutput.java | 20 +- src/jalview/io/HtmlSvgOutput.java | 4 +- src/jalview/io/IdentifyFile.java | 7 +- src/jalview/io/IntKeyStringValueEntry.java | 21 - src/jalview/io/JPredFile.java | 4 +- src/jalview/io/JalviewFileFilter.java | 5 - src/jalview/io/JnetAnnotationMaker.java | 4 +- src/jalview/io/ModellerDescription.java | 17 +- src/jalview/io/NewickFile.java | 142 +- src/jalview/io/PIRFile.java | 9 +- src/jalview/io/RnamlFile.java | 12 +- src/jalview/io/StockholmFile.java | 136 +- src/jalview/io/TCoffeeScoreFile.java | 10 +- src/jalview/io/VamsasAppDatastore.java | 27 +- src/jalview/io/WSWUBlastClient.java | 2 +- src/jalview/io/cache/AppCache.java | 39 +- src/jalview/io/cache/JvCacheableInputBox.java | 115 +- src/jalview/io/gff/Gff3Helper.java | 4 +- src/jalview/io/gff/InterProScanHelper.java | 2 +- src/jalview/io/gff/SequenceOntologyFactory.java | 57 +- src/jalview/io/vamsas/DatastoreRegistry.java | 6 +- src/jalview/io/vamsas/Rangetype.java | 12 +- src/jalview/io/vamsas/Sequencefeature.java | 23 +- src/jalview/io/vamsas/Sequencemapping.java | 10 +- src/jalview/io/vamsas/Tree.java | 6 +- src/jalview/io/vcf/VCFLoader.java | 193 +- src/jalview/javascript/JSFunctionExec.java | 114 +- src/jalview/javascript/JalviewLiteJsApi.java | 164 +- src/jalview/javascript/JsSelectionSender.java | 72 +- src/jalview/javascript/MouseOverListener.java | 25 +- .../javascript/MouseOverStructureListener.java | 85 +- src/jalview/javascript/json/JSON.java | 2 +- src/jalview/jbgui/GAlignFrame.java | 80 +- src/jalview/jbgui/GAlignmentPanel.java | 1 + src/jalview/jbgui/GCutAndPasteHtmlTransfer.java | 10 +- src/jalview/jbgui/GCutAndPasteTransfer.java | 8 +- src/jalview/jbgui/GDesktop.java | 30 +- src/jalview/jbgui/GPCAPanel.java | 5 +- src/jalview/jbgui/GPreferences.java | 489 +- src/jalview/jbgui/GRnaStructureViewer.java | 6 +- src/jalview/jbgui/GSequenceLink.java | 4 +- src/jalview/jbgui/GSliderPanel.java | 5 +- src/jalview/jbgui/GSplitFrame.java | 3 +- src/jalview/jbgui/GStructureChooser.java | 26 +- src/jalview/jbgui/GStructureViewer.java | 3 +- src/jalview/jbgui/GTreePanel.java | 3 +- src/jalview/project/Jalview2XML.java | 412 +- src/jalview/renderer/OverviewRenderer.java | 570 +- src/jalview/renderer/OverviewResColourFinder.java | 107 +- src/jalview/renderer/ResidueColourFinder.java | 5 +- src/jalview/renderer/ResidueShader.java | 83 + src/jalview/renderer/ResidueShaderI.java | 2 + .../renderer/seqfeatures/FeatureColourFinder.java | 42 +- .../renderer/seqfeatures/FeatureRenderer.java | 137 +- src/jalview/rest/RestHandler.java | 16 +- src/jalview/schemes/AnnotationColourGradient.java | 8 +- src/jalview/schemes/ColourSchemeProperty.java | 43 +- src/jalview/schemes/ColourSchemes.java | 69 +- src/jalview/schemes/Consensus.java | 4 +- src/jalview/schemes/FeatureColour.java | 6 +- src/jalview/schemes/RNAHelicesColour.java | 8 +- src/jalview/schemes/ResidueProperties.java | 34 +- src/jalview/structure/StructureImportSettings.java | 63 +- .../structure/StructureSelectionManager.java | 216 +- .../structures/models/AAStructureBindingModel.java | 16 +- src/jalview/urls/IdOrgSettings.java | 31 +- src/jalview/urls/IdentifiersUrlProvider.java | 4 +- src/jalview/util/BrowserLauncher.java | 86 +- src/jalview/util/ColorUtils.java | 92 +- src/jalview/util/DBRefUtils.java | 33 +- src/jalview/util/GroupUrlLink.java | 566 +- src/jalview/util/MessageManager.java | 10 +- src/jalview/util/Platform.java | 349 +- src/jalview/util/ShortcutKeyMaskExWrapper.java | 57 - src/jalview/util/UrlLink.java | 37 +- src/jalview/viewmodel/AlignmentViewport.java | 30 +- src/jalview/viewmodel/OverviewDimensions.java | 37 +- .../viewmodel/OverviewDimensionsHideHidden.java | 10 +- .../viewmodel/OverviewDimensionsShowHidden.java | 12 +- src/jalview/viewmodel/ViewportRanges.java | 59 +- .../seqfeatures/FeatureRendererModel.java | 16 +- src/jalview/workers/AlignCalcManager.java | 17 +- src/jalview/ws/DBRefFetcher.java | 9 +- src/jalview/ws/SequenceFetcher.java | 103 +- src/jalview/ws/SequenceFetcherFactory.java | 28 +- src/jalview/ws/dbsources/EmblCdsSource.java | 9 +- src/jalview/ws/dbsources/EmblSource.java | 9 +- src/jalview/ws/dbsources/Pdb.java | 12 +- src/jalview/ws/dbsources/PfamFull.java | 4 +- src/jalview/ws/dbsources/PfamSeed.java | 4 +- src/jalview/ws/dbsources/Uniprot.java | 14 +- src/jalview/ws/jws1/Discoverer.java | 74 +- src/jalview/ws/jws1/JPredClient.java | 2 +- src/jalview/ws/jws1/MsaWSClient.java | 4 +- src/jalview/ws/jws1/SeqSearchWSClient.java | 4 +- src/jalview/ws/jws2/AAConClient.java | 2 +- src/jalview/ws/jws2/AADisorderClient.java | 75 +- src/jalview/ws/jws2/Jws2Client.java | 4 +- src/jalview/ws/jws2/Jws2Discoverer.java | 63 +- src/jalview/ws/jws2/MsaWSClient.java | 4 +- src/jalview/ws/jws2/RNAalifoldClient.java | 2 +- .../ws/jws2/SequenceAnnotationWSClient.java | 4 +- src/jalview/ws/jws2/jabaws2/Jws2Instance.java | 8 +- .../ws/jws2/jabaws2/Jws2InstanceFactory.java | 34 +- src/jalview/ws/rest/HttpResultSet.java | 11 +- src/jalview/ws/rest/RestClient.java | 241 +- src/jalview/ws/seqfetcher/ASequenceFetcher.java | 129 +- src/jalview/ws/seqfetcher/DbSourceProxy.java | 8 +- src/jalview/ws/seqfetcher/DbSourceProxyRoot.java | 11 + src/jalview/ws/sifts/SiftsClient.java | 51 +- src/jalview/ws/sifts/SiftsSettings.java | 46 +- .../xml/binding/jalview/JalviewModelType.java | 5090 -------------- src/mc_view/PDBfile.java | 8 +- src/org/jibble/epsgraphics/EpsGraphics2D.java | 91 +- src/uk/ac/ebi/www/InputParams.java | 6 +- .../AccessionMapperBindingStub.java | 4 +- utils/jalviewjs/SwingJS-site.zip | Bin 5343095 -> 5316828 bytes .../jalviewjs/eclipse/dropins/net.sf.j2s.core.jar | Bin 93131 -> 93159 bytes utils/jalviewjs/site-resources/applets-nocore.html | 230 + utils/jalviewjs/site-resources/applets.html | 230 + utils/jalviewjs/site-resources/css/ie6.css | 91 + utils/jalviewjs/site-resources/css/ie7.css | 85 + utils/jalviewjs/site-resources/css/reset.css | 113 + utils/jalviewjs/site-resources/css/style.css | 457 ++ utils/jalviewjs/site-resources/examples/1gaq.txt | 691 ++ utils/jalviewjs/site-resources/examples/2GIS.pdb | 2693 ++++++++ utils/jalviewjs/site-resources/examples/3W5V.pdb | 7088 ++++++++++++++++++++ .../site-resources/examples/backupfilestest.fa | 2 + .../site-resources/examples/biojsonschema.json | 1 + .../site-resources/examples/dna_interleaved.phy | 132 + .../site-resources/examples/dna_sequential.phy | 11 + .../examples/estrogenReceptorCdna.fa | 221 + .../examples/estrogenReceptorCdna_aln.fa | 320 + .../examples/estrogenReceptorCdna_frag.fa | 32 + .../examples/estrogenReceptorProtein.aln | 162 + .../examples/estrogenReceptorProtein.fa | 81 + .../examples/estrogenReceptorProtein_aln.fa | 112 + .../examples/estrogenReceptorProtein_frag.fa | 16 + .../jalviewjs/site-resources/examples/example.json | 1 + .../site-resources/examples/ferredoxin.nw | 1 + .../site-resources/examples/jpred_msa.fasta | 45 + .../site-resources/examples/jpred_msa.seq.concise | 30 + .../site-resources/examples/plantfdx.annotations | 7 + .../jalviewjs/site-resources/examples/plantfdx.fa | 60 + .../site-resources/examples/plantfdx.features | 118 + .../site-resources/examples/unfolded_RF00031.aln | 126 + .../site-resources/examples/uniref50.score_ascii | 99 + .../site-resources/examples/uniref50_mz.fa | 30 + .../images/coolJalviewBackgroundFading.png | Bin 0 -> 527022 bytes .../site-resources/images/coolVeryLightBG.png | Bin 0 -> 560379 bytes .../site-resources/jalview_embedded_example1.html | 134 + .../site-resources/javascript/deployJava.js | 1 + .../site-resources/javascript/facebox-1.3.js | 309 + .../jalviewjs/site-resources/javascript/jalview.js | 380 ++ .../site-resources/javascript/jquery-1.4.4.min.js | 167 + .../site-resources/javascript/jquery.blockUI.js | 490 ++ .../site-resources/javascript/jquery.timer.js | 75 + .../site-resources/javascript/jshashtable-2.1.js | 16 + .../site-resources/javascript/jvcontroller.js | 220 + .../site-resources/swingjs/JalviewApplet.js | 191 + 344 files changed, 31409 insertions(+), 12418 deletions(-) mode change 100755 => 100644 src/ext/vamsas/JpredSoapBindingStub.java create mode 100644 src/intervalstore/api/IntervalI.java create mode 100644 src/intervalstore/api/IntervalStoreI.java create mode 100644 src/intervalstore/impl/BinarySearcher.java create mode 100644 src/intervalstore/impl/IntervalStore.java create mode 100644 src/intervalstore/impl/NCList.java create mode 100644 src/intervalstore/impl/NCListBuilder.java create mode 100644 src/intervalstore/impl/NCNode.java create mode 100644 src/intervalstore/nonc/IntervalStore.java create mode 100644 src/jalview/api/AlignFrameI.java create mode 100644 src/jalview/api/JalviewApp.java create mode 100644 src/jalview/bin/AppletParams.java create mode 100644 src/jalview/bin/ApplicationSingletonProvider.java create mode 100644 src/jalview/bin/JalviewAppLoader.java create mode 100644 src/jalview/bin/JalviewJSApi.java delete mode 100644 src/jalview/bin/JalviewTaskbar.java delete mode 100644 src/jalview/bin/Launcher.java delete mode 100644 src/jalview/bin/MemorySetting.java create mode 100644 src/jalview/datamodel/features/FeatureStoreI.java create mode 100644 src/jalview/datamodel/features/FeatureStoreImpl.java create mode 100644 src/jalview/datamodel/features/FeatureStoreJS.java delete mode 100644 src/jalview/gui/APQHandlers.java delete mode 100644 src/jalview/gui/MenuChooser.java delete mode 100644 src/jalview/io/BackupFilesPresetEntry.java delete mode 100644 src/jalview/io/IntKeyStringValueEntry.java delete mode 100644 src/jalview/util/ShortcutKeyMaskExWrapper.java create mode 100644 src/jalview/ws/seqfetcher/DbSourceProxyRoot.java delete mode 100644 src/jalview/xml/binding/jalview/JalviewModelType.java create mode 100644 utils/jalviewjs/site-resources/applets-nocore.html create mode 100644 utils/jalviewjs/site-resources/applets.html create mode 100644 utils/jalviewjs/site-resources/css/ie6.css create mode 100644 utils/jalviewjs/site-resources/css/ie7.css create mode 100644 utils/jalviewjs/site-resources/css/reset.css create mode 100644 utils/jalviewjs/site-resources/css/style.css create mode 100644 utils/jalviewjs/site-resources/examples/1gaq.txt create mode 100644 utils/jalviewjs/site-resources/examples/2GIS.pdb create mode 100644 utils/jalviewjs/site-resources/examples/3W5V.pdb create mode 100644 utils/jalviewjs/site-resources/examples/backupfilestest.fa create mode 100644 utils/jalviewjs/site-resources/examples/biojsonschema.json create mode 100644 utils/jalviewjs/site-resources/examples/dna_interleaved.phy create mode 100644 utils/jalviewjs/site-resources/examples/dna_sequential.phy create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorCdna.fa create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorCdna_aln.fa create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorCdna_frag.fa create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorProtein.aln create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorProtein.fa create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorProtein_aln.fa create mode 100644 utils/jalviewjs/site-resources/examples/estrogenReceptorProtein_frag.fa create mode 100644 utils/jalviewjs/site-resources/examples/example.json create mode 100644 utils/jalviewjs/site-resources/examples/ferredoxin.nw create mode 100644 utils/jalviewjs/site-resources/examples/jpred_msa.fasta create mode 100644 utils/jalviewjs/site-resources/examples/jpred_msa.seq.concise create mode 100644 utils/jalviewjs/site-resources/examples/plantfdx.annotations create mode 100644 utils/jalviewjs/site-resources/examples/plantfdx.fa create mode 100644 utils/jalviewjs/site-resources/examples/plantfdx.features create mode 100644 utils/jalviewjs/site-resources/examples/unfolded_RF00031.aln create mode 100644 utils/jalviewjs/site-resources/examples/uniref50.score_ascii create mode 100644 utils/jalviewjs/site-resources/examples/uniref50_mz.fa create mode 100644 utils/jalviewjs/site-resources/images/coolJalviewBackgroundFading.png create mode 100644 utils/jalviewjs/site-resources/images/coolVeryLightBG.png create mode 100644 utils/jalviewjs/site-resources/jalview_embedded_example1.html create mode 100644 utils/jalviewjs/site-resources/javascript/deployJava.js create mode 100644 utils/jalviewjs/site-resources/javascript/facebox-1.3.js create mode 100644 utils/jalviewjs/site-resources/javascript/jalview.js create mode 100644 utils/jalviewjs/site-resources/javascript/jquery-1.4.4.min.js create mode 100644 utils/jalviewjs/site-resources/javascript/jquery.blockUI.js create mode 100644 utils/jalviewjs/site-resources/javascript/jquery.timer.js create mode 100644 utils/jalviewjs/site-resources/javascript/jshashtable-2.1.js create mode 100644 utils/jalviewjs/site-resources/javascript/jvcontroller.js create mode 100644 utils/jalviewjs/site-resources/swingjs/JalviewApplet.js diff --git a/README b/README index 33f0319..43ffa63 100644 --- a/README +++ b/README @@ -1,6 +1,6 @@ Download and install a clean eclipse-jee-2019-06 -In gradle.properties edit `jalviewjs_eclipse_root` to point to the root dir. Include up to the Eclipse.app folder if it's the macOS version. +In gradle.properties edit `jalviewjs_eclipse_root` to point to the root dir. DO NOT include the Eclipse.app folder in the path (up to this point, but not the .app folder) if it's the macOS version. gradle tasks of interest: diff --git a/build.gradle b/build.gradle index 351d9ac..7890fd0 100644 --- a/build.gradle +++ b/build.gradle @@ -233,19 +233,25 @@ def eclipseBinary def eclipseDropinsDir def eclipsePluginsDir task jalviewjsEclipsePaths { + def eclipseRoot = jalviewjs_eclipse_root + if (eclipseRoot.startsWith("~")) { + eclipseRoot = System.getProperty("user.home") + eclipseRoot.substring(1) + } if (OperatingSystem.current().isMacOsX()) { - eclipseDropinsDir = jalviewjs_eclipse_root+"/Contents/Eclipse/dropins" - eclipsePluginsDir = jalviewjs_eclipse_root+"/Contents/Eclipse/plugins" - eclipseBinary = jalviewjs_eclipse_root+"/Contents/MacOS/eclipse" - } else if (OperatingSystem.current().isWindows()) { // check this! - eclipseDropinsDir = jalviewjs_eclipse_root+"/dropins" - eclipsePluginsDir = jalviewjs_eclipse_root+"/plugins" - eclipseBinary = jalviewjs_eclipse_root+"/eclipse" + eclipseRoot += "/Eclipse.app" + eclipseDropinsDir = eclipseRoot+"/Contents/Eclipse/dropins" + eclipsePluginsDir = eclipseRoot+"/Contents/Eclipse/plugins" + eclipseBinary = eclipseRoot+"/Contents/MacOS/eclipse" + } else if (OperatingSystem.current().isWindows()) { // check these paths!! + eclipseDropinsDir = eclipseRoot+"/dropins" + eclipsePluginsDir = eclipseRoot+"/plugins" + eclipseBinary = eclipseRoot+"/eclipse" } else { // linux or unix - eclipseDropinsDir = jalviewjs_eclipse_root+"/dropins" - eclipsePluginsDir = jalviewjs_eclipse_root+"/plugins" - eclipseBinary = jalviewjs_eclipse_root+"/eclipse" + eclipseDropinsDir = eclipseRoot+"/dropins" + eclipsePluginsDir = eclipseRoot+"/plugins" + eclipseBinary = eclipseRoot+"/eclipse" } + println("ECLIPSE ROOT: "+eclipseRoot) } task jalviewjsEclipseCopyDropins (type: Copy) { @@ -353,8 +359,9 @@ task jalviewjsProjectImport(type: Exec) { executable(eclipseBinary) args(["-nosplash", "--launcher.suppressErrors", "-application", "com.seeq.eclipse.importprojects.headlessimport", "-data", tempEclipseWorkspace.getPath(), "-import", jalviewDirAbsolutePath]) - def tempdir = tempEclipseWorkspace.getPath()+"/.metadata/.plugins/org.eclipse.core.resources/.projects/jalview" - outputs.dir(tempdir) + def projdir = tempEclipseWorkspace.getPath()+"/.metadata/.plugins/org.eclipse.core.resources/.projects/jalview/org.eclipse.jdt.core/" + inputs.file(jalviewDir+"/.project") + outputs.dir(projdir) } task jalviewjsTranspile(type: Exec) { diff --git a/gradle.properties b/gradle.properties index 1fa2f14..e30dcb5 100644 --- a/gradle.properties +++ b/gradle.properties @@ -34,8 +34,7 @@ j11libDir = j11lib dev = false -#jalviewjs_eclipse_root = /Users/bsoares/buildtools/eclipse/eclipse-jee-2019-06/Eclipse.app -jalviewjs_eclipse_root = /home/bsoares/buildtools/eclipse/eclipse-jee-2019-06 +jalviewjs_eclipse_root = ~/buildtools/eclipse/eclipse-jee-2019-06 jalviewjs_utils_dir = utils/jalviewjs jalviewjs_eclipse_plugins_dir = eclipse/plugins diff --git a/src/com/stevesoft/pat/RegOpt.java b/src/com/stevesoft/pat/RegOpt.java index d5f62de..50d799f 100755 --- a/src/com/stevesoft/pat/RegOpt.java +++ b/src/com/stevesoft/pat/RegOpt.java @@ -138,16 +138,16 @@ class Branch extends Pattern n = RegOpt.opt(n, ignoreCase, dontMinQ); } n.setParent(this); - set(Character.valueOf(o.c), n, ignoreCase, dontMinQ); + set(new Character(o.c), n, ignoreCase, dontMinQ); if (ignoreCase) { if (o.c != o.altc) { - set(Character.valueOf(o.altc), n, ignoreCase, dontMinQ); + set(new Character(o.altc), n, ignoreCase, dontMinQ); } if (o.c != o.altc2 && o.altc != o.altc2) { - set(Character.valueOf(o.altc2), n, ignoreCase, dontMinQ); + set(new Character(o.altc2), n, ignoreCase, dontMinQ); } } } @@ -250,7 +250,7 @@ class Branch extends Pattern { return -1; } - Pattern n = (Pattern) h.get(Character.valueOf(pt.src.charAt(pos))); + Pattern n = (Pattern) h.get(new Character(pt.src.charAt(pos))); if (n == null) { return -1; diff --git a/src/com/stevesoft/pat/Regex.java b/src/com/stevesoft/pat/Regex.java index 6d07427..455f040 100755 --- a/src/com/stevesoft/pat/Regex.java +++ b/src/com/stevesoft/pat/Regex.java @@ -16,6 +16,7 @@ import java.util.Hashtable; import com.stevesoft.pat.wrap.StringWrap; + /** Matches a Unicode punctuation character. */ class UnicodePunct extends UniValidator { @@ -306,6 +307,7 @@ class UnicodeLower extends UniValidator */ public class Regex extends RegRes implements FilenameFilter { + /** * BackRefOffset gives the identity number of the first pattern. Version 1.0 * used zero, version 1.1 uses 1 to be more compatible with perl. @@ -1095,16 +1097,13 @@ public class Regex extends RegRes implements FilenameFilter { try { - return getClass().getDeclaredConstructor().newInstance(); + return getClass().newInstance(); } catch (InstantiationException ie) { return null; } catch (IllegalAccessException iae) { return null; - } catch (ReflectiveOperationException roe) - { - return null; } } diff --git a/src/com/stevesoft/pat/RegexReader.java b/src/com/stevesoft/pat/RegexReader.java index a0b42ce..837821e 100755 --- a/src/com/stevesoft/pat/RegexReader.java +++ b/src/com/stevesoft/pat/RegexReader.java @@ -233,7 +233,6 @@ public class RegexReader extends Reader * * @deprecated */ - @Deprecated public int getMaxLines() { return max_lines; @@ -244,7 +243,6 @@ public class RegexReader extends Reader * * @deprecated */ - @Deprecated public void setMaxLines(int ml) { max_lines = ml; @@ -257,7 +255,6 @@ public class RegexReader extends Reader * * @deprecated */ - @Deprecated public char getEOLchar() { return EOLchar; @@ -268,7 +265,6 @@ public class RegexReader extends Reader * * @deprecated */ - @Deprecated public void setEOLchar(char c) { EOLchar = c; diff --git a/src/com/stevesoft/pat/RegexTokenizer.java b/src/com/stevesoft/pat/RegexTokenizer.java index c99bfea..31fa2ba 100755 --- a/src/com/stevesoft/pat/RegexTokenizer.java +++ b/src/com/stevesoft/pat/RegexTokenizer.java @@ -43,13 +43,13 @@ public class RegexTokenizer implements Enumeration if (r.searchFrom(toParse, pos)) { v.addElement(r.left().substring(pos)); - vi.addElement(Integer.valueOf(r.matchFrom() + r.charsMatched())); + vi.addElement(new Integer(r.matchFrom() + r.charsMatched())); for (int i = 0; i < r.numSubs(); i++) { if (r.substring() != null) { v.addElement(r.substring(i + offset)); - vi.addElement(Integer.valueOf(r.matchFrom(i + offset) + vi.addElement(new Integer(r.matchFrom(i + offset) + r.charsMatched(i + offset))); } } diff --git a/src/ext/edu/ucsf/rbvi/strucviz2/ChimUtils.java b/src/ext/edu/ucsf/rbvi/strucviz2/ChimUtils.java index 6b5e36c..1d57a31 100644 --- a/src/ext/edu/ucsf/rbvi/strucviz2/ChimUtils.java +++ b/src/ext/edu/ucsf/rbvi/strucviz2/ChimUtils.java @@ -173,7 +173,7 @@ public abstract class ChimUtils float[] rgbValues = new float[4]; for (int i = 0; i < rgbStrings.length; i++) { - Float f = Float.valueOf(rgbStrings[i]); + Float f = new Float(rgbStrings[i]); rgbValues[i] = f.floatValue(); } if (rgbStrings.length == 4) @@ -203,7 +203,7 @@ public abstract class ChimUtils */ public static Integer makeModelKey(int model, int subModel) { - return Integer.valueOf(model * MAX_SUB_MODELS + subModel); + return new Integer(model * MAX_SUB_MODELS + subModel); } // invoked by the getResdiue (parseConnectivityReplies in diff --git a/src/ext/edu/ucsf/rbvi/strucviz2/ChimeraChain.java b/src/ext/edu/ucsf/rbvi/strucviz2/ChimeraChain.java index 4f871d3..9a29a99 100644 --- a/src/ext/edu/ucsf/rbvi/strucviz2/ChimeraChain.java +++ b/src/ext/edu/ucsf/rbvi/strucviz2/ChimeraChain.java @@ -200,7 +200,7 @@ public class ChimeraChain implements ChimeraStructuralObject */ public ChimeraResidue getResidue(String index) { - // Integer index = Integer.valueOf(residueIndex); + // Integer index = new Integer(residueIndex); if (residueMap.containsKey(index)) return residueMap.get(index); return null; diff --git a/src/ext/edu/ucsf/rbvi/strucviz2/StructureManager.java b/src/ext/edu/ucsf/rbvi/strucviz2/StructureManager.java index 22c9098..09a9713 100644 --- a/src/ext/edu/ucsf/rbvi/strucviz2/StructureManager.java +++ b/src/ext/edu/ucsf/rbvi/strucviz2/StructureManager.java @@ -121,8 +121,8 @@ public class StructureManager for (String chimObjName : names) { // get or open the corresponding models if they already exist - List currentModels = chimeraManager - .getChimeraModels(chimObjName, type); + List currentModels = chimeraManager.getChimeraModels( + chimObjName, type); if (currentModels.size() == 0) { // open and return models @@ -562,11 +562,11 @@ public class StructureManager // Get the corresponding "real" model if (chimeraManager.hasChimeraModel(modelNumber, subModelNumber)) { - ChimeraModel dataModel = chimeraManager - .getChimeraModel(modelNumber, subModelNumber); - if (dataModel.getResidueCount() == selectedModel.getResidueCount() - || dataModel - .getModelType() == StructureManager.ModelType.SMILES) + ChimeraModel dataModel = chimeraManager.getChimeraModel( + modelNumber, subModelNumber); + if (dataModel.getResidueCount() == selectedModel + .getResidueCount() + || dataModel.getModelType() == StructureManager.ModelType.SMILES) { // Select the entire model addChimSelection(dataModel); @@ -576,8 +576,8 @@ public class StructureManager { for (ChimeraChain selectedChain : selectedModel.getChains()) { - ChimeraChain dataChain = dataModel - .getChain(selectedChain.getChainId()); + ChimeraChain dataChain = dataModel.getChain(selectedChain + .getChainId()); if (selectedChain.getResidueCount() == dataChain .getResidueCount()) { @@ -931,7 +931,6 @@ public class StructureManager pathList.add("/usr/local/chimera/bin/chimera"); pathList.add("/usr/local/bin/chimera"); pathList.add("/usr/bin/chimera"); - pathList.add(System.getProperty("user.home") + "/opt/bin/chimera"); } else if (os.startsWith("Windows")) { diff --git a/src/ext/vamsas/JpredSoapBindingStub.java b/src/ext/vamsas/JpredSoapBindingStub.java old mode 100755 new mode 100644 index cff8081..8345551 --- a/src/ext/vamsas/JpredSoapBindingStub.java +++ b/src/ext/vamsas/JpredSoapBindingStub.java @@ -31,7 +31,7 @@ public class JpredSoapBindingStub extends org.apache.axis.client.Stub private java.util.Vector cachedDeserFactories = new java.util.Vector(); - static org.apache.axis.description.OperationDesc[] _operations; + private static org.apache.axis.description.OperationDesc[] _operations; static { @@ -260,6 +260,7 @@ public class JpredSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public java.lang.String predict(vamsas.objects.simple.Sequence seq) throws java.rmi.RemoteException { @@ -297,6 +298,7 @@ public class JpredSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public java.lang.String predictOnMsa( vamsas.objects.simple.Msfalignment msf) throws java.rmi.RemoteException @@ -335,6 +337,7 @@ public class JpredSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.Secstructpred getpredict( java.lang.String job_id) throws java.rmi.RemoteException { @@ -373,6 +376,7 @@ public class JpredSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.JpredResult getresult(java.lang.String job_id) throws java.rmi.RemoteException { diff --git a/src/ext/vamsas/MuscleWSSoapBindingStub.java b/src/ext/vamsas/MuscleWSSoapBindingStub.java index 1f8d231..026066c 100755 --- a/src/ext/vamsas/MuscleWSSoapBindingStub.java +++ b/src/ext/vamsas/MuscleWSSoapBindingStub.java @@ -23,7 +23,7 @@ package ext.vamsas; public class MuscleWSSoapBindingStub extends org.apache.axis.client.Stub implements ext.vamsas.MuscleWS { - static org.apache.axis.description.OperationDesc[] _operations; + private static final org.apache.axis.description.OperationDesc[] _operations; static { @@ -296,6 +296,7 @@ public class MuscleWSSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.WsJobId align( vamsas.objects.simple.SequenceSet seqSet) throws java.rmi.RemoteException @@ -337,6 +338,7 @@ public class MuscleWSSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.Alignment getalign(java.lang.String job_id) throws java.rmi.RemoteException { @@ -378,6 +380,7 @@ public class MuscleWSSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.MsaResult getResult(java.lang.String job_id) throws java.rmi.RemoteException { @@ -419,6 +422,7 @@ public class MuscleWSSoapBindingStub extends org.apache.axis.client.Stub } } + @Override public vamsas.objects.simple.WsJobId cancel(java.lang.String jobId) throws java.rmi.RemoteException { diff --git a/src/ext/vamsas/RegistryServiceSoapBindingStub.java b/src/ext/vamsas/RegistryServiceSoapBindingStub.java index 08b2a6b..f010ee8 100755 --- a/src/ext/vamsas/RegistryServiceSoapBindingStub.java +++ b/src/ext/vamsas/RegistryServiceSoapBindingStub.java @@ -31,7 +31,7 @@ public class RegistryServiceSoapBindingStub extends private java.util.Vector cachedDeserFactories = new java.util.Vector(); - static org.apache.axis.description.OperationDesc[] _operations; + private static org.apache.axis.description.OperationDesc[] _operations; static { @@ -192,6 +192,7 @@ public class RegistryServiceSoapBindingStub extends } } + @Override public ext.vamsas.ServiceHandles getServices() throws java.rmi.RemoteException { diff --git a/src/ext/vamsas/SeqSearchServiceSoapBindingStub.java b/src/ext/vamsas/SeqSearchServiceSoapBindingStub.java index 390ceb6..df0a504 100644 --- a/src/ext/vamsas/SeqSearchServiceSoapBindingStub.java +++ b/src/ext/vamsas/SeqSearchServiceSoapBindingStub.java @@ -31,7 +31,7 @@ public class SeqSearchServiceSoapBindingStub extends private java.util.Vector cachedDeserFactories = new java.util.Vector(); - static org.apache.axis.description.OperationDesc[] _operations; + private static final org.apache.axis.description.OperationDesc[] _operations; static { @@ -299,6 +299,7 @@ public class SeqSearchServiceSoapBindingStub extends } } + @Override public java.lang.String getDatabase() throws java.rmi.RemoteException { if (super.cachedEndpoint == null) @@ -335,6 +336,7 @@ public class SeqSearchServiceSoapBindingStub extends } } + @Override public vamsas.objects.simple.SeqSearchResult getResult( java.lang.String job_id) throws java.rmi.RemoteException { @@ -373,6 +375,7 @@ public class SeqSearchServiceSoapBindingStub extends } } + @Override public vamsas.objects.simple.WsJobId psearch( vamsas.objects.simple.Alignment al, java.lang.String database) throws java.rmi.RemoteException @@ -412,6 +415,7 @@ public class SeqSearchServiceSoapBindingStub extends } } + @Override public vamsas.objects.simple.WsJobId search( vamsas.objects.simple.Sequence s, java.lang.String database) throws java.rmi.RemoteException @@ -450,6 +454,7 @@ public class SeqSearchServiceSoapBindingStub extends } } + @Override public vamsas.objects.simple.WsJobId cancel(java.lang.String jobId) throws java.rmi.RemoteException { diff --git a/src/ext/vamsas/ServiceHandle.java b/src/ext/vamsas/ServiceHandle.java index 83412ea..428b5ea 100755 --- a/src/ext/vamsas/ServiceHandle.java +++ b/src/ext/vamsas/ServiceHandle.java @@ -126,6 +126,7 @@ public class ServiceHandle implements java.io.Serializable private java.lang.Object __equalsCalc = null; + @Override public synchronized boolean equals(java.lang.Object obj) { if (obj == null) @@ -162,6 +163,7 @@ public class ServiceHandle implements java.io.Serializable private boolean __hashCodeCalc = false; + @Override public synchronized int hashCode() { if (__hashCodeCalc) @@ -191,7 +193,7 @@ public class ServiceHandle implements java.io.Serializable } // Type metadata - private static org.apache.axis.description.TypeDesc typeDesc = new org.apache.axis.description.TypeDesc( + private static final org.apache.axis.description.TypeDesc typeDesc = new org.apache.axis.description.TypeDesc( ServiceHandle.class, true); static diff --git a/src/intervalstore/api/IntervalI.java b/src/intervalstore/api/IntervalI.java new file mode 100644 index 0000000..c170a43 --- /dev/null +++ b/src/intervalstore/api/IntervalI.java @@ -0,0 +1,192 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.api; + +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +public interface IntervalI +{ + + /** + * Compare intervals by start position ascending and end position descending. + */ + static Comparator COMPARATOR_BIGENDIAN = new Comparator() + { + @Override + public int compare(IntervalI o1, IntervalI o2) + { + int ret = Integer.signum(o1.getBegin() - o2.getBegin()); + return (ret == 0 ? Integer.signum(o2.getEnd() - o1.getEnd()) : ret); + } + }; + + /** + * Compare intervals by start position ascending and end position ascending. + */ + static Comparator COMPARATOR_LITTLEENDIAN = new Comparator() + { + @Override + public int compare(IntervalI o1, IntervalI o2) + { + int ret = Integer.signum(o1.getBegin() - o2.getBegin()); + return (ret == 0 ? Integer.signum(o1.getEnd() - o2.getEnd()) : ret); + } + }; + + /** + * a comparator for sorting intervals by start position ascending + */ + static Comparator FORWARD_STRAND = new Comparator() + { + @Override + public int compare(IntervalI o1, IntervalI o2) + { + return Integer.signum(o1.getBegin() - o2.getBegin()); + } + }; + + /** + * a comparator for sorting intervals by end position descending + */ + static Comparator REVERSE_STRAND = new Comparator() + { + @Override + public int compare(IntervalI o1, IntervalI o2) + { + return Integer.signum(o2.getEnd() - o1.getEnd()); + } + }; + + static int NOT_CONTAINED = Integer.MIN_VALUE; + static int CONTAINMENT_UNKNOWN = 0; + + int getBegin(); + int getEnd(); + + /** + * Answers true if this interval contains (or matches) the given interval + * based solely on start and end. + * + * @param i + * @return + */ + default boolean containsInterval(IntervalI i) + { + return i != null && i.getBegin() >= getBegin() + && i.getEnd() <= getEnd(); + } + + + /** + * Answers true if this interval properly contains the given interval, that + * is, it contains it and is larger than it + * + * @param i + * @return + */ + default boolean properlyContainsInterval(IntervalI i) + { + return containsInterval(i) + && (i.getBegin() > getBegin() || i.getEnd() < getEnd()); + } + + /** + * Slower than equalsInterval; also includes type. + * + * Ensure that subclasses override equals(Object). For example: + * + * public boolean equals(Object o) { return o != null && o instanceof XXX && + * equalsInterval((XXX) i); } + * + * + * equalsInterval also must be overridden. + * + * public boolean equalsInterval(IntervalI i) {return ((SimpleFeature)i).start + * == start && ((SimpleFeature)i).end == end && ((SimpleFeature)i).description + * == this.description; } + * + * + * @param o + * @return true if equal, including a type check + */ + @Override + abstract boolean equals(Object o); + + + + /** + * Check that two intervals are equal, in terms of end points, descriptions, + * or any other distinguishing features. + * + * Used in IntervalStore in searches, since it is faster than equals(), as at + * that point we know that we have the correct type. + * + * @param i + * @return true if equal + */ + abstract boolean equalsInterval(IntervalI i); + + default boolean overlapsInterval(IntervalI i) + { + if (i == null) + { + return false; + } + if (i.getBegin() < getBegin()) + { + return i.getEnd() >= getBegin(); + } + if (i.getEnd() > getEnd()) + { + return i.getBegin() <= getEnd(); + } + return true; // i internal to this + } + + /** + * Sorts the list by start position ascending (if forwardString==true), or by + * end position descending + * + * @param intervals + * @param forwardStrand + */ + static void sortIntervals(List intervals, + final boolean forwardStrand) + { + Collections.sort(intervals, + forwardStrand ? FORWARD_STRAND : REVERSE_STRAND); + } + + +} diff --git a/src/intervalstore/api/IntervalStoreI.java b/src/intervalstore/api/IntervalStoreI.java new file mode 100644 index 0000000..3b0f575 --- /dev/null +++ b/src/intervalstore/api/IntervalStoreI.java @@ -0,0 +1,96 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.api; + +import java.util.Collection; +import java.util.List; + +import intervalstore.impl.NCList; + +public interface IntervalStoreI extends Collection +{ + + /** + * Returns a (possibly empty) list of items whose extent overlaps the given + * range + * + * @param from + * start of overlap range (inclusive) + * @param to + * end of overlap range (inclusive) + * @return + */ + List findOverlaps(long from, long to); + + /** + * Ensures that the IntervalStore is ready for findOverlap. + * + * @return true iff the data held satisfy the rules of construction of an + * IntervalStore. + * + */ + boolean isValid(); + + /** + * Answers the level of nesting of intervals in the store, as + *
    + *
  • 0 if the store is empty
    • + *
  • 1 if all intervals are 'top level' (non nested)
    • + *
  • else 1 plus the depth of the enclosed NCList
    • + *
+ * + * @return + * @see NCList#getDepth() + */ + int getDepth(); + + /** + * Return the number of top-level (not-contained) intervals. + * + * @return + */ + int getWidth(); + + List findOverlaps(long start, long end, List result); + + String prettyPrint(); + + /** + * Resort and rebuild links. + * + * @return + */ + boolean revalidate(); + + IntervalI get(int i); + +} \ No newline at end of file diff --git a/src/intervalstore/impl/BinarySearcher.java b/src/intervalstore/impl/BinarySearcher.java new file mode 100644 index 0000000..1086e91 --- /dev/null +++ b/src/intervalstore/impl/BinarySearcher.java @@ -0,0 +1,91 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.impl; + +import java.util.List; +import java.util.function.Function; + +/** + * Provides a method to perform binary search of an ordered list for the first + * entry that satisfies a supplied condition + * + * @author gmcarstairs + */ +public final class BinarySearcher +{ + private BinarySearcher() + { + } + + /** + * Performs a binary search of the list to find the index of the first entry + * for which the test returns true. Answers the length of the list if there is + * no such entry. + *

+ * For correct behaviour, the provided list must be ordered consistent with + * the test, that is, any entries returning false must precede any entries + * returning true. Note that this means that this method is not + * usable to search for equality (to find a specific entry), as all unequal + * entries will answer false to the test. To do that, use + * Collections.binarySearch instead. + * + * @param list + * @param test + * @return + * @see java.util.Collections#binarySearch(List, Object) + */ + public static int findFirst(List list, + Function test) + { + int start = 0; + int end = list.size() - 1; + int matched = list.size(); + + while (start <= end) + { + int mid = (start + end) / 2; + T entry = list.get(mid); + boolean itsTrue = test.apply(entry); + if (itsTrue) + { + matched = mid; + end = mid - 1; + } + else + { + start = mid + 1; + } + } + + return matched; + } +} diff --git a/src/intervalstore/impl/IntervalStore.java b/src/intervalstore/impl/IntervalStore.java new file mode 100644 index 0000000..8634ad4 --- /dev/null +++ b/src/intervalstore/impl/IntervalStore.java @@ -0,0 +1,543 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.impl; + +import java.util.AbstractCollection; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import intervalstore.api.IntervalI; +import intervalstore.api.IntervalStoreI; + +/** + * A collection class to store interval-associated data, with O(log N) + * performance for overlap queries, insertion and deletion (where N is the size + * of the store). Accepts duplicate entries but not null values. + * + * @author gmcarstairs + * + * @param + * any type providing getBegin() and getEnd() + */ +public class IntervalStore + extends AbstractCollection implements IntervalStoreI +{ + /** + * An iterator over the intervals held in this store, with no particular + * ordering guaranteed. The iterator does not support the optional + * remove operation (throws + * UnsupportedOperationException if attempted). + * + * @author gmcarstairs + * + * @param + */ + private class IntervalIterator implements Iterator + { + /* + * iterator over top level non-nested intervals + */ + Iterator topLevelIterator; + + /* + * iterator over NCList (if any) + */ + Iterator nestedIterator; + + /** + * Constructor initialises iterators over the top level list and any nested + * NCList + * + * @param intervalStore + */ + public IntervalIterator( + IntervalStore intervalStore) + { + topLevelIterator = nonNested.iterator(); + if (nested != null) + { + nestedIterator = nested.iterator(); + } + } + + @Override + public boolean hasNext() + { + return topLevelIterator.hasNext() ? true + : (nestedIterator != null && nestedIterator.hasNext()); + } + + @SuppressWarnings("unchecked") + @Override + public V next() + { + if (topLevelIterator.hasNext()) + { + return (V) topLevelIterator.next(); + } + if (nestedIterator != null) + { + return (V) nestedIterator.next(); + } + throw new NoSuchElementException(); + } + + } + + private List nonNested; + + private NCList nested; + + /** + * Constructor + */ + public IntervalStore() + { + nonNested = new ArrayList<>(); + } + + /** + * Constructor given a list of intervals. Note that the list may get sorted as + * a side-effect of calling this constructor. + */ + public IntervalStore(List intervals) + { + this(); + + /* + * partition into subranges whose root intervals + * have no mutual containment (if no intervals are nested, + * each subrange is of length 1 i.e. a single interval) + */ + List sublists = new NCListBuilder() + .partitionNestedSublists(intervals); + + /* + * add all 'subrange root intervals' (and any co-located intervals) + * to our top level list of 'non-nested' intervals; + * put aside any left over for our NCList + */ + List nested = new ArrayList<>(); + + for (IntervalI subrange : sublists) + { + int listIndex = subrange.getBegin(); + IntervalI root = intervals.get(listIndex); + while (listIndex <= subrange.getEnd()) + { + T t = intervals.get(listIndex); + if (root.equalsInterval(t)) + { + nonNested.add(t); + } + else + { + nested.add(t); + } + listIndex++; + } + } + + if (!nested.isEmpty()) + { + this.nested = new NCList<>(nested); + } + } + + /** + * Adds one interval to the store. + * + * @param interval + */ + @Override + public boolean add(T interval) + { + if (interval == null) + { + return false; + } + if (!addNonNestedInterval(interval)) + { + /* + * detected a nested interval - put it in the NCList structure + */ + addNestedInterval(interval); + } + return true; + } + + @Override + public boolean contains(Object entry) + { + if (listContains(nonNested, entry)) + { + return true; + } + + return nested == null ? false : nested.contains(entry); + } + + protected boolean addNonNestedInterval(T entry) + { + synchronized (nonNested) + { + /* + * find the first stored interval which doesn't precede the new one + */ + int insertPosition = BinarySearcher.findFirst(nonNested, + val -> val.getBegin() >= entry.getBegin()); + /* + * fail if we detect interval enclosure + * - of the new interval by the one before or after it + * - of the next interval by the new one + */ + if (insertPosition > 0) + { + if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry)) + { + return false; + } + } + if (insertPosition < nonNested.size()) + { + T following = nonNested.get(insertPosition); + if (entry.properlyContainsInterval(following) + || following.properlyContainsInterval(entry)) + { + return false; + } + } + + /* + * checks passed - add the interval + */ + nonNested.add(insertPosition, entry); + + return true; + } + } + + @Override + public List findOverlaps(long from, long to) + { + List result = new ArrayList<>(); + + findNonNestedOverlaps(from, to, result); + + if (nested != null) + { + result.addAll(nested.findOverlaps(from, to)); + } + + return result; + } + + @Override + public String prettyPrint() + { + String pp = nonNested.toString(); + if (nested != null) + { + pp += System.lineSeparator() + nested.prettyPrint(); + } + return pp; + } + + @Override + public boolean isValid() + { + for (int i = 0; i < nonNested.size() - 1; i++) + { + IntervalI i1 = nonNested.get(i); + IntervalI i2 = nonNested.get(i + 1); + + if (i2.getBegin() < i1.getBegin()) + { + System.err.println("nonNested wrong start order : " + i1.toString() + + ", " + i2.toString()); + return false; + } + if (i1.properlyContainsInterval(i2) + || i2.properlyContainsInterval(i1)) + { + System.err.println("nonNested invalid containment!: " + + i1.toString() + + ", " + i2.toString()); + return false; + } + } + return nested == null ? true : nested.isValid(); + } + + @Override + public int size() + { + int i = nonNested.size(); + if (nested != null) + { + i += nested.size(); + } + return i; + } + + @Override + public synchronized boolean remove(Object o) + { + if (o == null) + { + return false; + } + try + { + @SuppressWarnings("unchecked") + T entry = (T) o; + + /* + * try the non-nested positional intervals first + */ + boolean removed = removeNonNested(entry); + + /* + * if not found, try nested intervals + */ + if (!removed && nested != null) + { + removed = nested.remove(entry); + } + + return removed; + } catch (ClassCastException e) + { + return false; + } + } + + /** + * Removes the given entry from the list of non-nested entries, returning true + * if found and removed, or false if not found. Specifically, removes the + * first item in the list for which item.equals(entry). + * + * @param entry + * @return + */ + protected boolean removeNonNested(T entry) + { + /* + * find the first interval that might match, i.e. whose + * start position is not less than the target range start + * (NB inequality test ensures the first match if any is found) + */ + int startIndex = BinarySearcher.findFirst(nonNested, + val -> val.getBegin() >= entry.getBegin()); + + /* + * traverse intervals to look for a match + */ + int from = entry.getBegin(); + int i = startIndex; + int size = nonNested.size(); + while (i < size) + { + T sf = nonNested.get(i); + if (sf.getBegin() > from) + { + break; + } + if (sf.equals(entry)) + { + nonNested.remove(i); + return true; + } + i++; + } + return false; + } + + @Override + public int getDepth() + { + if (size() == 0) + { + return 0; + } + return (nonNested.isEmpty() ? 0 : 1) + + (nested == null ? 0 : nested.getDepth()); + } + + /** + * Adds one interval to the NCList that can manage nested intervals (creating + * the NCList if necessary) + */ + protected synchronized void addNestedInterval(T interval) + { + if (nested == null) + { + nested = new NCList<>(); + } + nested.add(interval); + } + + /** + * Answers true if the list contains the interval, else false. This method is + * optimised for the condition that the list is sorted on interval start + * position ascending, and will give unreliable results if this does not hold. + * + * @param intervals + * @param entry + * @return + */ + protected boolean listContains(List intervals, Object entry) + { + if (intervals == null || entry == null || !(entry instanceof IntervalI)) + { + return false; + } + + IntervalI interval = (IntervalI) entry; + + /* + * locate the first entry in the list which does not precede the interval + */ + int pos = BinarySearcher.findFirst(intervals, + val -> val.getBegin() >= interval.getBegin()); + int len = intervals.size(); + while (pos < len) + { + T sf = intervals.get(pos); + if (sf.getBegin() > interval.getBegin()) + { + return false; // no match found + } + if (sf.equals(interval)) + { + return true; + } + pos++; + } + return false; + } + + /** + * Answers an iterator over the intervals in the store, with no particular + * ordering guaranteed. The iterator does not support the optional + * remove operation (throws + * UnsupportedOperationException if attempted). + */ + @Override + public Iterator iterator() + { + return new IntervalIterator<>(this); + } + + @Override + public void clear() + { + this.nonNested.clear(); + this.nested = new NCList<>(); + } + + /** + * Adds non-nested intervals to the result list that lie within the target + * range + * + * @param from + * @param to + * @param result + */ + protected void findNonNestedOverlaps(long from, long to, + List result) + { + /* + * find the first interval whose end position is + * after the target range start + */ + int startIndex = BinarySearcher.findFirst(nonNested, + val -> val.getEnd() >= from); + + final int startIndex1 = startIndex; + int i = startIndex1; + while (i < nonNested.size()) + { + T sf = nonNested.get(i); + if (sf.getBegin() > to) + { + break; + } + if (sf.getBegin() <= to && sf.getEnd() >= from) + { + result.add(sf); + } + i++; + } + } + + @Override + public String toString() + { + String s = nonNested.toString(); + if (nested != null) + { + s = s + System.lineSeparator() + nested.toString(); + } + return s; + } + + @Override + public int getWidth() + { + // TODO Auto-generated method stub + return 0; + } + + @Override + public List findOverlaps(long start, long end, List result) + { + // TODO Auto-generated method stub + return null; + } + + @Override + public boolean revalidate() + { + // TODO Auto-generated method stub + return false; + } + + @Override + public IntervalI get(int i) + { + // TODO Auto-generated method stub + return null; + } +} diff --git a/src/intervalstore/impl/NCList.java b/src/intervalstore/impl/NCList.java new file mode 100644 index 0000000..0bf6e1b --- /dev/null +++ b/src/intervalstore/impl/NCList.java @@ -0,0 +1,752 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.impl; + +import java.util.AbstractCollection; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import intervalstore.api.IntervalI; +import intervalstore.impl.Range; + +/** + * An adapted implementation of NCList as described in the paper + * + * 

+ * Nested Containment List (NCList): a new algorithm for accelerating
+ * interval query of genome alignment and interval databases
+ * - Alexander V. Alekseyenko, Christopher J. Lee
+ * https://doi.org/10.1093/bioinformatics/btl647
+ *
+ */ +public class NCList extends AbstractCollection +{ + /** + * A depth-first iterator over the elements stored in the NCList + */ + private class NCListIterator implements Iterator + { + int subrangeIndex; + + Iterator nodeIterator; + + /** + * Constructor bootstraps a pointer to an iterator over the first subrange + * (if any) + */ + NCListIterator() + { + subrangeIndex = nextSubrange(-1); + } + + /** + * Moves the subrange iterator to the next subrange, and answers its index + * in the list of subranges. If there are no more, sets the iterator to null + * and answers -1. + * + * @return + */ + private int nextSubrange(int after) + { + int nextIndex = after + 1; + if (nextIndex < subranges.size()) + { + nodeIterator = subranges.get(nextIndex).iterator(); + return nextIndex; + } + nodeIterator = null; + return -1; + } + + @Override + public boolean hasNext() + { + return nodeIterator != null && nodeIterator.hasNext(); + } + + /** + * Answers the next element returned by the current NCNode's iterator, and + * advances the iterator (to the next NCNode if necessary) + */ + @Override + public T next() + { + if (nodeIterator == null || !nodeIterator.hasNext()) + { + throw new NoSuchElementException(); + } + T result = nodeIterator.next(); + + if (!nodeIterator.hasNext()) + { + subrangeIndex = nextSubrange(subrangeIndex); + } + return result; + } + + } + + /* + * the number of interval instances represented + */ + private int size; + + /* + * a list, in start position order, of sublists of ranges ordered so + * that each contains (or is the same as) the one that follows it + */ + private List> subranges; + + /** + * Constructor given a list of things that are each located on a contiguous + * interval. Note that the constructor may reorder the list. + *

+ * We assume here that for each range, start <= end. Behaviour for reverse + * ordered ranges is undefined. + * + * @param ranges + */ + public NCList(List ranges) + { + this(); + build(ranges); + } + + /** + * Sorts and groups ranges into sublists where each sublist represents an + * interval and its contained subintervals + * + * @param ranges + */ + protected void build(List ranges) + { + /* + * sort and partition into subranges + * which have no mutual containment + */ + List sublists = partitionNestedSublists(ranges); + + /* + * convert each subrange to an NCNode consisting of a range and + * (possibly) its contained NCList + */ + for (IntervalI sublist : sublists) + { + subranges.add(new NCNode<>( + ranges.subList(sublist.getBegin(), sublist.getEnd() + 1))); + } + + size = ranges.size(); + } + + /** + * Default constructor + */ + public NCList() + { + subranges = new ArrayList<>(); + } + + /** + * Sorts and traverses the ranges to identify sublists, whose start intervals + * are overlapping or disjoint but not mutually contained. Answers a list of + * start-end indices of the sorted list of ranges. + * + * @param ranges + * @return + */ + protected List partitionNestedSublists(List ranges) + { + List sublists = new ArrayList<>(); + + if (ranges.isEmpty()) + { + return sublists; + } + + /* + * sort by start ascending, length descending, so that + * contained intervals follow their containing interval + */ + Collections.sort(ranges, new NCListBuilder<>().getComparator()); + + int listStartIndex = 0; + + IntervalI lastParent = ranges.get(0); + boolean first = true; + + for (int i = 0; i < ranges.size(); i++) + { + IntervalI nextInterval = ranges.get(i); + if (!first && !lastParent.properlyContainsInterval(nextInterval)) + { + /* + * this interval is not properly contained in the parent; + * close off the last sublist + */ + sublists.add(new Range(listStartIndex, i - 1)); + listStartIndex = i; + lastParent = nextInterval; + } + first = false; + } + + sublists.add(new Range(listStartIndex, ranges.size() - 1)); + return sublists; + } + + /** + * Adds one entry to the stored set + * + * @param entry + */ + @Override + public synchronized boolean add(final T entry) + { + final NCNode newNode = new NCNode<>(entry); + addNode(newNode); + return true; + } + + /** + * Adds one NCNode to this NCList + *

+ * This method does not update the size (interval count) of this + * NCList, as it may be used to rearrange nodes without changing their count. + * Callers should increment the count if needed. + * + * @param newNode + */ + protected void addNode(final NCNode newNode) + { + final long start = newNode.getBegin(); + final long end = newNode.getEnd(); + size += newNode.size(); + + /* + * cases: + * 1) precedes all subranges - add as NCNode on front of list + * 2) follows all subranges - add as NCNode on end of list + * 3) matches a subrange - add as a sibling in the list + * 4) properly enclosed by a subrange - add recursively to subrange + * 5) properly encloses one or more subranges - push them inside it + * 6) spans two subranges - insert between them + */ + + /* + * find the first subrange whose end does not precede entry's start + */ + int candidateIndex = findFirstOverlap(start); + + /* + * search for maximal span of subranges i-k that the new entry + * encloses; or a subrange that encloses the new entry + */ + boolean enclosing = false; + int firstEnclosed = 0; + int lastEnclosed = 0; + + for (int j = candidateIndex; j < subranges.size(); j++) + { + NCNode subrange = subranges.get(j); + + if (subrange.equalsInterval(newNode)) + { + /* + * matching interval - insert adjacent + */ + subranges.add(j, newNode); + return; + } + + if (end < subrange.getBegin() && !enclosing) + { + /* + * new entry lies between subranges j-1 j + */ + subranges.add(j, newNode); + return; + } + + if (subrange.properlyContainsInterval(newNode)) + { + /* + * push new entry inside this subrange as it encloses it + */ + subrange.addNode(newNode); + return; + } + + if (start <= subrange.getBegin()) + { + if (end >= subrange.getEnd()) + { + /* + * new entry encloses this subrange (and possibly preceding ones); + * continue to find the maximal list it encloses + */ + if (!enclosing) + { + firstEnclosed = j; + } + lastEnclosed = j; + enclosing = true; + continue; + } + else + { + /* + * entry spans from before this subrange to inside it + */ + if (enclosing) + { + /* + * entry encloses one or more preceding subranges + */ + push(newNode, firstEnclosed, lastEnclosed); + } + else + { + /* + * entry overlaps two subranges but doesn't enclose either + * so just add it + */ + subranges.add(j, newNode); + } + return; + } + } + } + + /* + * drops through to here if new range encloses all others + * or overlaps the last one + */ + if (enclosing) + { + push(newNode, firstEnclosed, lastEnclosed); + } + else + { + subranges.add(newNode); + } + } + + @Override + public boolean contains(Object entry) + { + if (!(entry instanceof IntervalI)) + { + return false; + } + IntervalI interval = (IntervalI) entry; + + /* + * find the first sublist that might overlap, i.e. + * the first whose end position is >= from + */ + int candidateIndex = findFirstOverlap(interval.getBegin()); + + int to = interval.getEnd(); + + for (int i = candidateIndex; i < subranges.size(); i++) + { + NCNode candidate = subranges.get(i); + if (candidate.getBegin() > to) + { + /* + * we are past the end of our target range + */ + break; + } + if (candidate.contains(interval)) + { + return true; + } + } + return false; + } + + /** + * Update the tree so that the new node encloses current subranges i to j + * (inclusive). That is, replace subranges i-j (inclusive) with a new subrange + * that contains them. + * + * @param node + * @param i + * @param j + * @throws IllegalArgumentException + * if any of the subranges is not contained by the node's start-end + * range + */ + protected synchronized void push(NCNode node, final int i, + final int j) + { + for (int k = i; k <= j; k++) + { + NCNode n = subranges.get(k); + if (!node.containsInterval(n)) { + throw new IllegalArgumentException("Can't push " + n.toString() + + " inside " + node.toString()); + } + node.addNode(n); + } + + for (int k = j; k >= i; k--) + { + subranges.remove(k); + } + subranges.add(i, node); + } + + /** + * Answers a list of contained intervals that overlap the given range + * + * @param from + * @param to + * @return + */ + public List findOverlaps(long from, long to) + { + List result = new ArrayList<>(); + + findOverlaps(from, to, result); + + return result; + } + + /** + * Recursively searches the NCList adding any items that overlap the from-to + * range to the result list + * + * @param from + * @param to + * @param result + */ + protected void findOverlaps(long from, long to, List result) + { + /* + * find the first sublist that might overlap, i.e. + * the first whose end position is >= from + */ + int candidateIndex = findFirstOverlap(from); + + for (int i = candidateIndex; i < subranges.size(); i++) + { + NCNode candidate = subranges.get(i); + if (candidate.getBegin() > to) + { + /* + * we are past the end of our target range + */ + break; + } + candidate.findOverlaps(from, to, result); + } + + } + + /** + * Search subranges for the first one whose end position is not before the + * target range's start position, i.e. the first one that may overlap the + * target range. Returns the index in the list of the first such range found, + * or the length of the list if none found. + * + * @param from + * @return + */ + protected int findFirstOverlap(final long from) + { + return BinarySearcher.findFirst(subranges, + val -> val.getEnd() >= from); + } + + /** + * Formats the tree as a bracketed list e.g. + * + * 

+   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
+   *
+ */ + @Override + public String toString() + { + return subranges.toString(); + } + + /** + * Answers the NCList as an indented list + * + * @return + */ + public String prettyPrint() + { + StringBuilder sb = new StringBuilder(512); + int offset = 0; + int indent = 2; + prettyPrint(sb, offset, indent); + sb.append(System.lineSeparator()); + return sb.toString(); + } + + /** + * @param sb + * @param offset + * @param indent + */ + void prettyPrint(StringBuilder sb, int offset, int indent) + { + boolean first = true; + for (NCNode subrange : subranges) + { + if (!first) + { + sb.append(System.lineSeparator()); + } + first = false; + subrange.prettyPrint(sb, offset, indent); + } + } + + /** + * Answers true if the store's structure is valid (nesting containment rules + * are obeyed), else false. For use in testing and debugging. + * + * @return + */ + public boolean isValid() + { + int count = 0; + for (NCNode subrange : subranges) + { + count += subrange.size(); + } + if (count != size) + { + return false; + } + return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE); + } + + /** + * Answers true if the data held satisfy the rules of construction of an + * NCList bounded within the given start-end range, else false. + *

+ * Each subrange must lie within start-end (inclusive). Subranges must be + * ordered by start position ascending, and within that by end position + * descending. + *

+ * + * @param start + * @param end + * @return + */ + boolean isValid(final int start, final int end) + { + NCNode lastRange = null; + + for (NCNode subrange : subranges) + { + if (subrange.getBegin() < start) + { + System.err.println("error in NCList: range " + subrange.toString() + + " starts before " + end); + return false; + } + if (subrange.getEnd() > end) + { + System.err.println("error in NCList: range " + subrange.toString() + + " ends after " + end); + return false; + } + + if (lastRange != null) + { + if (subrange.getBegin() < lastRange.getBegin()) + { + System.err.println("error in NCList: range " + subrange.toString() + + " starts before " + lastRange.toString()); + return false; + } + if (subrange.properlyContainsInterval(lastRange)) + { + System.err.println("error in NCList: range " + subrange.toString() + + " encloses preceding: " + lastRange.toString()); + return false; + } + if (lastRange.properlyContainsInterval(subrange)) + { + System.err.println("error in NCList: range " + subrange.toString() + + " enclosed by preceding: " + lastRange.toString()); + return false; + } + } + lastRange = subrange; + + if (!subrange.isValid()) + { + return false; + } + } + return true; + } + + /** + * Answers the number of intervals stored + * + * @return + */ + @Override + public int size() + { + return size; + } + + /** + * Answers a list of all entries stored, in no guaranteed order. This method + * is not synchronized, so is not thread-safe. + */ + public List getEntries() + { + List result = new ArrayList<>(); + getEntries(result); + return result; + } + + /** + * Adds all contained entries to the given list + * + * @param result + */ + void getEntries(List result) + { + for (NCNode subrange : subranges) + { + subrange.getEntries(result); + } + } + + /** + * Removes the first interval Ifound that is equal to T + * (I.equals(T)). Answers true if an interval is removed, false + * if no match is found. This method is synchronized so thread-safe. + * + * @param entry + * @return + */ + public synchronized boolean remove(T entry) + { + if (entry == null) + { + return false; + } + int i = findFirstOverlap(entry.getBegin()); + + for (; i < subranges.size(); i++) + { + NCNode subrange = subranges.get(i); + if (subrange.getBegin() > entry.getBegin()) + { + /* + * not found + */ + return false; + } + NCList subRegions = subrange.getSubRegions(); + + if (subrange.getRegion().equals(entry)) + { + /* + * if the subrange is rooted on this entry, remove it, + * and remove and promote its subregions (if any) + */ + subranges.remove(i); + size -= subrange.size(); + if (subRegions != null) + { + for (NCNode r : subRegions.subranges) + { + addNode(r); + } + } + return true; + } + else + { + if (subrange.remove(entry)) + { + size--; + return true; + } + } + } + return false; + } + + /** + * Answers the depth of interval nesting of this object, where 1 means there + * are no nested sub-intervals + * + * @return + */ + public int getDepth() + { + int subDepth = 0; + for (NCNode subrange : subranges) + { + subDepth = Math.max(subDepth, subrange.getDepth()); + } + + return subDepth; + } + + /** + * Answers an iterator over the contained intervals, with no particular order + * guaranteed. The iterator does not support the optional remove + * operation (throws UnsupportedOperationException if attempted). + */ + @Override + public Iterator iterator() + { + return new NCListIterator(); + } + + @Override + public synchronized void clear() + { + subranges.clear(); + size = 0; + } +} diff --git a/src/intervalstore/impl/NCListBuilder.java b/src/intervalstore/impl/NCListBuilder.java new file mode 100644 index 0000000..4c87306 --- /dev/null +++ b/src/intervalstore/impl/NCListBuilder.java @@ -0,0 +1,143 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.impl; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +import intervalstore.api.IntervalI; +import intervalstore.impl.Range; + +/** + * A comparator that orders ranges by either start position ascending. If + * position matches, ordering is by length descending. This provides the + * canonical ordering of intervals into subranges in order to build a nested + * containment list. + * + * @author gmcarstairs + */ +public class NCListBuilder +{ + class NCListComparator implements Comparator + { + /** + * Compares two intervals in a way that will sort a list by start position + * ascending, then by length descending. Answers + *