[Tm4j-commits] tm4j/src/org/tm4j/topicmap/tmdm/merged MergedTopicMapView.java, 1.12, 1.13

[Xuan B. <med...@us...>]

Update of /cvsroot/tm4j/tm4j/src/org/tm4j/topicmap/tmdm/merged
In directory sc8-pr-cvs10.sourceforge.net:/tmp/cvs-serv14516/src/org/tm4j/topicmap/tmdm/merged

Modified Files:
	MergedTopicMapView.java 
Log Message:
Support for considerably faster merging (speedups factors of more than 20 have been observed).

Index: MergedTopicMapView.java
===================================================================
RCS file: /cvsroot/tm4j/tm4j/src/org/tm4j/topicmap/tmdm/merged/MergedTopicMapView.java,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -d -r1.12 -r1.13
*** MergedTopicMapView.java	18 Jun 2008 03:28:02 -0000	1.12
--- MergedTopicMapView.java	19 Jun 2008 11:06:45 -0000	1.13
***************
*** 524,527 ****
--- 524,531 ----
  	}
  	
+ 	/**
+ 		Slow implementation. Leads to O(n²) behaviour when merging a MergedTopic with lots of components:
+ 		we iterate over all components to unindex and then we iterate over all components to reindex.
+ 	*/
  	protected MergedTopic merge(MergedTopic mergedTopic0,MergedTopic mergedTopic1,boolean emitMergeTopicEventsToListeners) {
  		assert mergedTopic0!=mergedTopic1;
***************
*** 575,578 ****
--- 579,641 ----
  	}
  	
+ 	/**
+ 		Faster implementation. We do not unindex (locators) which we would reindex anyways.
+ 	*/
+ 	protected MergedTopic mergeNew(MergedTopic mergedTopic0,MergedTopic mergedTopic1,boolean emitMergeTopicEventsToListeners) {
+ 		assert mergedTopic0!=mergedTopic1;
+ 		assert mergedTopic0.getParent()==mergedTopic1.getParent();
+ 		assert mergedTopic0.getParent()==getMergedTopicMap();
+ 		
+ 		/*
+ 		unindex(mergedTopic0);
+ 		unindex(mergedTopic1);
+ 		*/
+ 		
+ 		Collection<ReadableTopic> components0 = mergedTopic0.getComponents();
+ 		Collection<ReadableTopic> components1 = mergedTopic1.getComponents();
+ 		
+ 		
+ 		if (components1.size()>components0.size()) { // Ensure that components0 has the bigger size if size differs.
+ 			Collection<ReadableTopic> tmp = components0;
+ 			components0 = components1;
+ 			components1 = tmp;
+ 			
+ 			MergedTopic	tmpT	= mergedTopic0;
+ 			mergedTopic0			=	mergedTopic1;
+ 			mergedTopic1			=	tmpT;
+ 		}
+ 		
+ 		
+ 		
+ 		unindex(mergedTopic1);
+ 		
+ 		components0.addAll(components1);
+ 		
+ 		MergedTopic result;
+ 		
+ 		result = mergedTopic0;
+ 
+ 		reindexPartially(result,mergedTopic1);
+ 		
+ 		Collection<ReadableTopic> components1again = mergedTopic1.invalidate();
+ 		
+ 		assert components1again==components1;
+ 		
+ 		if (emitMergeTopicEventsToListeners) {
+ 			internalNotifyMergedTopicsMerged(result.getParent(),mergedTopic0,mergedTopic1,result);
+ 		}
+ 		
+ 		/* // always false
+ 		if (mergedTopic0!=result) {
+ 			mergedTopic0.forget();
+ 		}
+ 		*/
+ 		
+ 		assert mergedTopic1!=result;
+ 		mergedTopic1.forget();
+ 		
+ 		return result;		
+ 	}
+ 	
  	protected void unindex(MergedTopic mergedTopic) {
  		MergedTopicMapConstruct removeResult;
***************
*** 614,642 ****
  		assert isNowUnkownAndUnindexed(mergedTopic);
  		
  		MergedTopicMapConstruct putResult;
  		
! 		for (Locator itemIdentifierOrSubjectIdentifier : mergedTopic.getItemIdentifiersTogetherWithSubjectIdentifiersCollection()) {
! 			putResult = itemIdentifierOrSubjectIdentifierToMergedTopicMapConstruct.put(itemIdentifierOrSubjectIdentifier,mergedTopic);
  			
! 			assert (putResult==null)||(putResult==mergedTopic);  
  		}
  		
! 		for (Locator subjectLocator : mergedTopic.getSubjectLocatorsCollection()) {
! 			putResult = subjectLocatorToMergedTopic.put(subjectLocator,mergedTopic);
  			
! 			assert (putResult==null)||(putResult==mergedTopic);  
  		}
  		
! 		for (ReadableTopic topic : mergedTopic.getComponents()) {
! 			putResult = topicToMergedTopic.put(topic,mergedTopic);
  			
! 			assert (putResult==null)||(putResult==mergedTopic); 
  		}
  		
- 		boolean success = mergedTopics.add(mergedTopic);
- 		
- 		assert success;
- 		
- 		// FIXME: maybe deal with reification
  	}
  	
--- 677,712 ----
  		assert isNowUnkownAndUnindexed(mergedTopic);
  		
+ 		reindexPartially(mergedTopic,mergedTopic);
+ 		
+ 		boolean success = mergedTopics.add(mergedTopic);
+ 		
+ 		assert success;
+ 		
+ 		// FIXME: maybe deal with reification
+ 	}
+ 	
+ 	protected void reindexPartially(MergedTopic destinationMergedTopic,MergedTopic sourceMergedTopic) {
+ 		assert isNowUnkownAndUnindexed(sourceMergedTopic);
+ 		
  		MergedTopicMapConstruct putResult;
  		
! 		for (Locator itemIdentifierOrSubjectIdentifier : sourceMergedTopic.getItemIdentifiersTogetherWithSubjectIdentifiersCollection()) {
! 			putResult = itemIdentifierOrSubjectIdentifierToMergedTopicMapConstruct.put(itemIdentifierOrSubjectIdentifier,destinationMergedTopic);
  			
! 			assert (putResult==null)||(putResult==destinationMergedTopic);  
  		}
  		
! 		for (Locator subjectLocator : sourceMergedTopic.getSubjectLocatorsCollection()) {
! 			putResult = subjectLocatorToMergedTopic.put(subjectLocator,destinationMergedTopic);
  			
! 			assert (putResult==null)||(putResult==destinationMergedTopic);
  		}
  		
! 		for (ReadableTopic topic : sourceMergedTopic.getComponents()) {
! 			putResult = topicToMergedTopic.put(topic,destinationMergedTopic);
  			
! 			assert (putResult==null)||(putResult==destinationMergedTopic); 
  		}
  		
  	}