//
//  RepetitionFinder.m
//  ArcParser
//
//  Created by David Palme on 15.04.07.
//  Copyright 2007 __MyCompanyName__. All rights reserved.
//

#import "RepetitionFinder.h"

NSString *superString = nil;
int minimalRepetitionLength;
NSMutableArray *dictionaries;
NSArray *checkedRepetitionRegions;		//repetitions regions: array with indexes, for every index an array sorted by length
NSArray *essentialMatchingPairs;

@implementation RepetitionFinder

- (id)initWithString:(NSString *)aString
{
	[super init];
	
	if (aString == nil)
		return nil;
	
	superString = aString;
	
	return self;
}

- (void)setString:(NSString *)aString
{
	[aString retain];
	superString = aString;
}

- (void)prepare
{
	if (superString == nil)
	{
		NSLog(@"String for RepetitionFinder not set.");
	}
	else
	{
		//start building data structures
		dictionaries = [NSMutableArray array];
		
		int dictionaryIndex = 0;	
		for(dictionaryIndex; dictionaryIndex < ([superString length] / 2); dictionaryIndex++)
		{
			[dictionaries addObject:[NSMutableDictionary dictionary]];
			
			int tokenIndex = 0;
			for (tokenIndex; tokenIndex < ([superString length] - dictionaryIndex); tokenIndex++)
			{
				NSRange tokenRange = NSMakeRange(tokenIndex, dictionaryIndex+1);
				NSString* tokenString = [superString substringWithRange:tokenRange];
				
				if ([[dictionaries objectAtIndex:dictionaryIndex] objectForKey:tokenString] == nil)
				{
					//create array
					[[dictionaries objectAtIndex:dictionaryIndex] setObject:[NSMutableArray array] forKey:tokenString];
					//add occurance
					[[[dictionaries objectAtIndex:dictionaryIndex] objectForKey:tokenString] addObject:[NSNumber numberWithInt:tokenIndex]];
				}
				else
				{
					//add occurance
					[[[dictionaries objectAtIndex:dictionaryIndex] objectForKey:tokenString] addObject:[NSNumber numberWithInt:tokenIndex]];
				}
			}
		}
	}
}

- (void)prepareWithString:(NSString *)aString
{
	[self setString:aString];
	[self prepare];
}

- (void)findRepetitionRegions
{
	NSMutableArray *repetitionRegions = [NSMutableArray array];

	if (dictionaries)
	{
		int dictionaryIndex = 0;
		for (dictionaryIndex; dictionaryIndex < [dictionaries count]; dictionaryIndex++)
		{
			NSEnumerator *tokenOcurrenceEnumerator = [[dictionaries objectAtIndex:dictionaryIndex] objectEnumerator];
			NSEnumerator *tokenEnumerator = [[dictionaries objectAtIndex:dictionaryIndex] keyEnumerator];
			int tokenLength = dictionaryIndex + 1;
			id ocurrenceArray;
			id token;
			NSNumber *thisOcurrence = nil;
			NSNumber *nextOcurrence = nil;
			NSNumber *lastOcurrence = nil;
			int rangeStart;
			int rangeLength;
			
			while ((ocurrenceArray = [tokenOcurrenceEnumerator nextObject]))
			{				
				//NSString: substring
				token = [tokenEnumerator nextObject];
				
				if ([ocurrenceArray count] > 1)
				{
					int ocurrenceIndex = 0;
					
					for (ocurrenceIndex; ocurrenceIndex < [ocurrenceArray count] - 1; ocurrenceIndex++)
					{
						thisOcurrence = [ocurrenceArray objectAtIndex:ocurrenceIndex];
						nextOcurrence = [ocurrenceArray objectAtIndex:(ocurrenceIndex + 1)];
						
						//no active region
						if ((lastOcurrence == nil) || ([lastOcurrence intValue] != [thisOcurrence intValue] - tokenLength))
						{
							if ([thisOcurrence intValue] == [nextOcurrence intValue] - tokenLength)
							{
								rangeStart = [thisOcurrence intValue];
								rangeLength = 2 * tokenLength;
								
								lastOcurrence = [ocurrenceArray objectAtIndex:ocurrenceIndex];
							}
						}
						//active region in last step
						else if ([lastOcurrence intValue] == [thisOcurrence intValue] - tokenLength)
						{
							//region getting longer
							if ([thisOcurrence intValue] == [nextOcurrence intValue] - tokenLength)
							{
								rangeLength += tokenLength;
								lastOcurrence = [ocurrenceArray objectAtIndex:ocurrenceIndex];
							}
							//region ends
							else
							{
								NSRange completedRange = NSMakeRange(rangeStart, rangeLength);
								
								[repetitionRegions addObject:[[RepetitionRegion alloc] initWithFundamentalSubstring:token inRange:completedRange]];
								
								//dev...
								//NSLog(@"repetition region with substring '%@' from index %i for %i charachters -> %i repetitions", token, rangeStart, rangeLength, rangeLength / [token length]);
							}
						}
					}

					//do for last step
					thisOcurrence = [ocurrenceArray objectAtIndex:ocurrenceIndex];
					
					if (lastOcurrence != nil)
					{
						//end the very last region
						if ([lastOcurrence intValue] == [thisOcurrence intValue] - tokenLength)
						{
							NSRange completedRange = NSMakeRange(rangeStart, rangeLength);
							
							[repetitionRegions addObject:[[RepetitionRegion alloc] initWithFundamentalSubstring:token inRange:completedRange]];
							
							//dev...
							//NSLog(@"repetition region with substring '%@' from index %i for %i charachters -> %i repetitions", token, rangeStart, rangeLength, rangeLength / [token length]);
						}
					}
				}
			}
		}
		
		//dev...
		//NSLog(@"--- completed, number of unchecked regions found: %i", [repetitionRegions count]);
		
		//sort repetition regions by location
		//
		//an array for every index
		//
		NSMutableArray *sortedRepetitionRegions = [NSMutableArray arrayWithCapacity:[superString length]];
		
		int k = 0;
		for (k; k < [superString length]; k++)
		{
			[sortedRepetitionRegions insertObject:[NSMutableArray array] atIndex:k];
		}
		
		k = 0;
		for (k; k < [repetitionRegions count]; k++)
		{
			[[sortedRepetitionRegions objectAtIndex:[[repetitionRegions objectAtIndex:k] startLocation]] addObject:[repetitionRegions objectAtIndex:k]];
		}
		
		//sort repetition regions by length for their location
		NSMutableArray *sortedRepetitionRegionsByLength = [NSMutableArray arrayWithCapacity:[superString length]];
		NSMutableArray *temp;
		NSMutableArray *sortedRepetitionRegionsByLengthForALocation;
		RepetitionRegion *maximalRepetitionRegionForALocation;
		int innerIndex;
		int index = 0;
		for (index; index < [sortedRepetitionRegions count]; index++)
		{
			maximalRepetitionRegionForALocation = nil;
			
			temp = [NSMutableArray array];
			sortedRepetitionRegionsByLengthForALocation = [NSMutableArray array];
			innerIndex = 0;
			for (innerIndex; innerIndex < [[sortedRepetitionRegions objectAtIndex:index] count]; innerIndex++)
			{
				if (!maximalRepetitionRegionForALocation)
				{
					maximalRepetitionRegionForALocation = [[sortedRepetitionRegions objectAtIndex:index] objectAtIndex:innerIndex];
				}
				else if ([[[sortedRepetitionRegions objectAtIndex:index] objectAtIndex:innerIndex] length] > [maximalRepetitionRegionForALocation length])
				{
					[temp addObject:maximalRepetitionRegionForALocation];
					maximalRepetitionRegionForALocation = [[sortedRepetitionRegions objectAtIndex:index] objectAtIndex:innerIndex];
				}
				else
				{
					[temp addObject:[[sortedRepetitionRegions objectAtIndex:index] objectAtIndex:innerIndex]];
				}	
			}
			
			if (maximalRepetitionRegionForALocation)
			{
				[sortedRepetitionRegionsByLengthForALocation addObject:maximalRepetitionRegionForALocation];
				[sortedRepetitionRegionsByLengthForALocation addObjectsFromArray:temp];
			}
			
			[sortedRepetitionRegionsByLength insertObject:sortedRepetitionRegionsByLengthForALocation atIndex:index];
		}
		
		//on all locations check the biggest starting rrs for contained rrs
		int outerIndex = 0;
		int checkOuterIndex = 0;
		int checkInnerIndex = 0;
		int indexForLocation = 0;
		int followerCount = 0;
		int followerIndex = 0;
		int followerLocation = 0;
		RepetitionRegion *outerRegion = nil;
		RepetitionRegion *innerRegion = nil;
		RepetitionRegion *checkRegion = nil;
		NSMutableArray *splittedRepetitionRegions = nil;
		NSMutableArray *repetitionRegionsToDelete = [NSMutableArray array];
		BOOL splitted = NO;
		
		//run starting locations
		for (outerIndex; outerIndex < [sortedRepetitionRegionsByLength count]; outerIndex++)
		{
			outerRegion = nil;
			indexForLocation = 0;
			splitted = NO;
			
			//run all rrs beginning on the same index
			for (indexForLocation; indexForLocation < [[sortedRepetitionRegionsByLength objectAtIndex:outerIndex] count]; indexForLocation++)
			{
				if (splitted)
				{
					break;
				}
				
				//dev...
				//NSLog(@"outerindex: %i", outerIndex);
				
				outerRegion = [[sortedRepetitionRegionsByLength objectAtIndex:outerIndex] objectAtIndex:indexForLocation];

				//check other rrs contained in outerRegion
				checkOuterIndex = outerIndex + 1;
				
				//weird thing!
				int a = [outerRegion startLocation];
				int b = [[outerRegion fundamentalSubstring] length];
				int checker = a + b;
				
				//all inside first fundamemtal substring (plus check for a1aa,a1aa and aa1a,aa1a), if not: kickem ...
				for (checkOuterIndex; (checkOuterIndex < [superString length]) && (checkOuterIndex <= checker); checkOuterIndex++)
				{
					checkInnerIndex = 0;
					splittedRepetitionRegions = nil;
					checkRegion = nil;
					
					for (checkInnerIndex; checkInnerIndex < [[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] count]; checkInnerIndex++)
					{
						splittedRepetitionRegions = [NSMutableArray array];
						checkRegion = [[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex];
					
						//dev...
						//NSLog(@"checking:");
						//[outerRegion printToLog];
						//[checkRegion printToLog];
						//dev...
						
						//checks for contained intersecting rrs abb[aa]bba
						if ([outerRegion containsIntersectingRangeFrom:checkRegion])
						{
							//dev...
							//NSLog(@"out with: ");
							//[checkRegion printToLog];
							
							[splittedRepetitionRegions addObjectsFromArray:[outerRegion splitIntersectingRepetitionRegion:checkRegion]];
							
							//kick followers like: cababccabab[cc]abab[cc]ababc
							followerCount = 1;
							while (followerCount)
							{
								if (([outerRegion length] - (followerCount * [[outerRegion fundamentalSubstring] length])) > [[outerRegion fundamentalSubstring] length] && [checkRegion length] < ([[outerRegion fundamentalSubstring] length]))
								{
									followerIndex = 0;
									for (followerIndex; followerIndex < [[sortedRepetitionRegionsByLength objectAtIndex:([checkRegion startLocation] + followerCount * [[outerRegion fundamentalSubstring] length])] count]; followerIndex++)
									{
										followerLocation = ([checkRegion startLocation] + followerCount * [[outerRegion fundamentalSubstring] length]);
										
										[splittedRepetitionRegions addObjectsFromArray:[outerRegion splitIntersectingRepetitionRegion:[[sortedRepetitionRegionsByLength objectAtIndex:followerLocation] objectAtIndex:followerIndex]]];
										[repetitionRegionsToDelete addObject:[[sortedRepetitionRegionsByLength objectAtIndex:followerLocation] objectAtIndex:followerIndex]];
										[[sortedRepetitionRegionsByLength objectAtIndex:followerLocation] removeObjectsInArray:repetitionRegionsToDelete];
									}
								}
								else
								{
									break;
								}
								
								followerCount++;
							}
							
							//add splitted repetition regions to collection
							int x = 0;
							RepetitionRegion *split;
							for (x; x < [splittedRepetitionRegions count]; x++)
							{
								split = [splittedRepetitionRegions objectAtIndex:x];
								[[sortedRepetitionRegionsByLength objectAtIndex:[split startLocation]] addObject:split];
							}

							[repetitionRegionsToDelete addObject:checkRegion];
							
							//dev...
							//NSLog(@"---");
						}
					}
					
					[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] removeObjectsInArray:repetitionRegionsToDelete];
					[repetitionRegionsToDelete removeAllObjects];
				}
				
				
				
				//rrs in the last repetition: a11,a11,a1111
				//
				//and c[bb]bbabba
				//
				checkOuterIndex = [outerRegion startLocation];
				[splittedRepetitionRegions removeAllObjects];
				
				for (checkOuterIndex; (checkOuterIndex < [superString length]) && (checkOuterIndex <= (NSMaxRange([outerRegion range]) - 1)); checkOuterIndex++)
				{
					if (splitted)
					{
						break;
					}
					
					//dev...
					//NSLog(@"+++");
					//NSLog(@"cOI: %i", checkOuterIndex);
				
					checkInnerIndex = 0;
					for (checkInnerIndex; checkInnerIndex < [[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] count]; checkInnerIndex++)
					{
						if (splitted)
						{
							break;
						}
												
						//dev...
						//NSLog(@"overlapping ? :");
						//[outerRegion printToLog];
						//[[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] printToLog];
						//dev...
												
						if ([outerRegion overlappedByRangeFrom:[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]])
						{
							if ([outerRegion repetitionRegionStartingInLastRepetition:[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]])
							{
								//trunkating not possible: abbaabb[aa]
								if (![[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] trunkateWith:outerRegion])
								{
									[repetitionRegionsToDelete addObject:[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]];
								}
							}
							else
							{
								//wenn am ende andersrum
								int intersectionLength = NSIntersectionRange([outerRegion range], [[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] range]).length;
								
								//split innerRegion in the front
								if (intersectionLength < [[outerRegion fundamentalSubstring] length])
								{
									splittedRepetitionRegions = [[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] splitOnIndex:NSMaxRange([outerRegion range])];
									[repetitionRegionsToDelete addObject:[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]];
								}
								//split outerRegion in the back
								else if (intersectionLength < [[[[sortedRepetitionRegionsByLength objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] fundamentalSubstring] length])
								{
									splittedRepetitionRegions = [outerRegion splitOnIndex:checkOuterIndex];
									[repetitionRegionsToDelete addObject:outerRegion];
								}
								
								//dev...
								//NSLog(@"splitcount: %i", [splittedRepetitionRegions count]);
								
								//add splitted repetition regions to collection
								int x = 0;
								RepetitionRegion *split;
								for (x; x < [splittedRepetitionRegions count]; x++)
								{
									split = [splittedRepetitionRegions objectAtIndex:x];
									[[sortedRepetitionRegionsByLength objectAtIndex:[split startLocation]] addObject:split];
								}
								
								splitted = YES;
							}
							
						}
					}
					
					//dev...
					//NSLog(@"deleting %i:", [repetitionRegionsToDelete count], checkOuterIndex);
					
					int y = 0;
					for (y; y < [repetitionRegionsToDelete count]; y++)
					{
						[[sortedRepetitionRegionsByLength objectAtIndex:[[repetitionRegionsToDelete objectAtIndex:y] startLocation]] removeObjectsInArray:repetitionRegionsToDelete];
					}
					
					[repetitionRegionsToDelete removeAllObjects];
				}
			}
		}
		//checking for redundancy finished
		
		//dev...
		//
		//print to check
		NSLog(@"************");
		//NSLog(@"final check:");
		
		index = 0;
		innerIndex = 0;
		for (index; index < [sortedRepetitionRegionsByLength count]; index++)
		{
			innerIndex = 0;
			
			for (innerIndex; innerIndex < [[sortedRepetitionRegionsByLength objectAtIndex:index] count]; innerIndex++)
			{
				[[[sortedRepetitionRegionsByLength objectAtIndex:index] objectAtIndex:innerIndex] printToLog];
			}
		}
		//dev...
		
		[sortedRepetitionRegionsByLength retain];
		checkedRepetitionRegions = sortedRepetitionRegionsByLength;
	}
	else
	{
		NSLog(@"repitition finder not yet prepared.");
	}
}

- (void)findEssentialMatchingPairs
{
	NSLog(@"************");
	NSLog(@"finding matching pairs.");
	
	int outerIndex = 0;
	int innerIndex = 0;
	int checkOuterIndex = 0;
	int checkInnerIndex = 0;
	RepetitionRegion *outerRegion;
	NSMutableArray *matchingPairsToDelete = [NSMutableArray array];
	
	//find maximal matching pairs
	NSMutableArray *sortedMatchingPairsForLocation = [NSMutableArray arrayWithCapacity:[superString length]];
	int i = 0;
	for (i; i < [superString length]; i++)
	{
		[sortedMatchingPairsForLocation insertObject:[NSMutableArray array] atIndex:i];
	}
	
	NSEnumerator *tokenEnumerator;
	NSEnumerator *tokenOcurrenceEnumerator;
	MatchingPair *matchingPair;

	if (dictionaries)
	{
		int dictionaryIndex = 0;
		for (dictionaryIndex; dictionaryIndex < [dictionaries count]; dictionaryIndex++)
		{
			int tokenLength = dictionaryIndex + 1;
			tokenEnumerator = [[dictionaries objectAtIndex:dictionaryIndex] keyEnumerator];
			tokenOcurrenceEnumerator = [[dictionaries objectAtIndex:dictionaryIndex] objectEnumerator];
			NSArray *ocurrenceArray;
			NSString *token;
			NSNumber *thisOcurrence = nil;
			NSNumber *nextOcurrence = nil;
			
			while (ocurrenceArray = [tokenOcurrenceEnumerator nextObject])
			{
				token = [tokenEnumerator nextObject];
				
				if ([ocurrenceArray count] > 1)
				{
					int ocurrenceIndex = 0;
					
					for (ocurrenceIndex; ocurrenceIndex < [ocurrenceArray count] - 1; ocurrenceIndex++)
					{
						thisOcurrence = [ocurrenceArray objectAtIndex:ocurrenceIndex];
						nextOcurrence = [ocurrenceArray objectAtIndex:(ocurrenceIndex + 1)];
						matchingPair = [[MatchingPair alloc] initWithString:token firstLocation:[thisOcurrence intValue] secondLocation:[nextOcurrence intValue]];
						
						if (matchingPair)
						{
							[[sortedMatchingPairsForLocation objectAtIndex:[thisOcurrence intValue]] addObject:matchingPair];
						}
					}
				}
			}
		}
		
		//dev...
		NSLog(@"sorting by length...");
		
		//sort matching pairs by length for their location
		NSMutableArray *temp;
		NSMutableArray *sortedMatchingPairsByLengthForLocation = [NSMutableArray array];
		NSMutableArray *sortedMatchingPairsByLengthForALocation;
		MatchingPair *maximalMatchingPairForALocation;
		int innerIndex;
		int index = 0;
		
		for (index; index < [sortedMatchingPairsForLocation count]; index++)
		{
			maximalMatchingPairForALocation = nil;
			
			temp = [NSMutableArray array];
			sortedMatchingPairsByLengthForALocation = [NSMutableArray array];
			innerIndex = 0;
			for (innerIndex; innerIndex < [[sortedMatchingPairsForLocation objectAtIndex:index] count]; innerIndex++)
			{
				if (!maximalMatchingPairForALocation)
				{
					maximalMatchingPairForALocation = [[sortedMatchingPairsForLocation objectAtIndex:index] objectAtIndex:innerIndex];
				}
				else if ([[[sortedMatchingPairsForLocation objectAtIndex:index] objectAtIndex:innerIndex] stringLength] > [maximalMatchingPairForALocation stringLength])
				{
					[temp addObject:maximalMatchingPairForALocation];
					maximalMatchingPairForALocation = [[sortedMatchingPairsForLocation objectAtIndex:index] objectAtIndex:innerIndex];
				}
				else
				{
					[temp addObject:[[sortedMatchingPairsForLocation objectAtIndex:index] objectAtIndex:innerIndex]];
				}	
			}
			
			if (maximalMatchingPairForALocation)
			{
				[sortedMatchingPairsByLengthForALocation addObject:maximalMatchingPairForALocation];
				[sortedMatchingPairsByLengthForALocation addObjectsFromArray:temp];
			}
			
			//dev...
			//NSLog(@"on index %i adding %i pairs", index, [sortedMatchingPairsByLengthForALocation count]);
			
			[sortedMatchingPairsByLengthForLocation insertObject:sortedMatchingPairsByLengthForALocation atIndex:index];
		}
		
		NSLog(@"sort out via repetition regions...");
		
		//kick the ones in rrs
		outerIndex = 0;
		innerIndex = 0;
		checkOuterIndex = 0;
		checkInnerIndex = 0;
		RepetitionRegion *outerRegion;
		[matchingPairsToDelete removeAllObjects];
		
		for (outerIndex; outerIndex < [checkedRepetitionRegions count]; outerIndex++)
		{
			innerIndex = 0;
			for (innerIndex; innerIndex < [[checkedRepetitionRegions objectAtIndex:outerIndex] count]; innerIndex++)
			{
				outerRegion = [[checkedRepetitionRegions objectAtIndex:outerIndex] objectAtIndex:innerIndex];
				
				checkOuterIndex = [outerRegion startLocation];
				for (checkOuterIndex; checkOuterIndex < NSMaxRange([outerRegion range]); checkOuterIndex++)
				{
					checkInnerIndex = 0;
					
					for (checkInnerIndex; checkInnerIndex < [[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] count]; checkInnerIndex++)
					{
						NSLog(@"checkouterindex: %i", checkOuterIndex);
						NSLog(@"#####");
						[outerRegion printToLog];
						[[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] printToLog];
						NSLog(@"+++++");
						
						if ([[outerRegion fundamentalSubstring] length] >= [[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] stringLength])
						{
							//check these for consecutive fundamental substring or contained in fundamental substring ... else out
							if ((![outerRegion containsMatchingPairInFundamentalSubstring:[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]]) &&
								(![outerRegion matchingPairIsConsecutiveFundamentalSubstring:[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]]))
							{
								NSLog(@"out because not contained and no consecutive substrings");
								[matchingPairsToDelete addObject:[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]];
							}
							else
							{
								//[[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] setPartOfRepetitionRegion:outerRegion];
							}
						}
					}
					
					[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] removeObjectsInArray:matchingPairsToDelete];
					[matchingPairsToDelete removeAllObjects];
				}
			}
		}
		
		//dev...
		NSLog(@"checking for maximal...");
		
		//check that matching pairs are maximal
		outerIndex = 0;
		innerIndex = 0;
		checkOuterIndex = 0;
		checkInnerIndex = 0;
		MatchingPair *outerPair;
		matchingPairsToDelete = [NSMutableArray array];
		
		for (outerIndex; outerIndex < [sortedMatchingPairsByLengthForLocation count]; outerIndex++)
		{
			innerIndex = 0;
			for (innerIndex; innerIndex < [[sortedMatchingPairsByLengthForLocation objectAtIndex:outerIndex] count]; innerIndex++)
			{
				outerPair = [[sortedMatchingPairsByLengthForLocation objectAtIndex:outerIndex] objectAtIndex:innerIndex];
				checkOuterIndex = [outerPair firstLocation];
				
				for (checkOuterIndex; checkOuterIndex < NSMaxRange([outerPair secondRange]); checkOuterIndex++)
				{
					//dev...
					//NSLog(@">>> matching pairs on index %i: %i", checkOuterIndex, [[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] count]);
					
					checkInnerIndex = 0;
					for (checkInnerIndex; checkInnerIndex < [[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] count]; checkInnerIndex++)
					{
						//dev...
						//NSLog(@"contains?");
						//[outerPair printToLog];
						//[[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex] printToLog];
						
						
						if ([outerPair contains:[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]])
						{
							//dev...
							//NSLog(@"yes.");
							
							[matchingPairsToDelete addObject:[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] objectAtIndex:checkInnerIndex]];
						}
					}
					
					[[sortedMatchingPairsByLengthForLocation objectAtIndex:checkOuterIndex] removeObjectsInArray:matchingPairsToDelete];
					[matchingPairsToDelete removeAllObjects];
				}
			}	
		}
		
		//dev...
		NSLog(@"************");
		NSLog(@"essential matching pairs:");
		outerIndex = 0;
		for (outerIndex; outerIndex < [sortedMatchingPairsByLengthForLocation count]; outerIndex++)
		{
			innerIndex = 0;
			for (innerIndex; innerIndex < [[sortedMatchingPairsByLengthForLocation objectAtIndex:outerIndex] count]; innerIndex++)
			{
				[[[sortedMatchingPairsByLengthForLocation objectAtIndex:outerIndex] objectAtIndex:innerIndex] printToLog];
			}
		}
		//dev...
		
		[sortedMatchingPairsForLocation retain];
		essentialMatchingPairs = sortedMatchingPairsByLengthForLocation;
	}
	else
	{
		NSLog(@"repitition finder not yet prepared.");
	}
}

- (NSArray *)essentialMatchingPairsWithMinimalRepetitionLength:(int)minimalLength
{
	if (minimalLength == 0)
	{
		minimalRepetitionLength = 1;
	}
	else
	{
		minimalRepetitionLength = minimalLength;
	}
	
	[self findRepetitionRegions];
	[self findEssentialMatchingPairs];
	
	//remove pairs smaller than minimal repetition length
	NSMutableArray *pairsToDelete = [NSMutableArray array];
	int outerIndex = 0;
	int innerIndex = 0;
	for (outerIndex; outerIndex < [essentialMatchingPairs count]; outerIndex++)
	{
		innerIndex = 0;
		for (innerIndex; innerIndex < [[essentialMatchingPairs objectAtIndex:outerIndex] count]; innerIndex++)
		{
			if ([[[essentialMatchingPairs objectAtIndex:outerIndex] objectAtIndex:innerIndex] stringLength] < minimalRepetitionLength)
			{			
				[pairsToDelete addObject:[[essentialMatchingPairs objectAtIndex:outerIndex] objectAtIndex:innerIndex]];
			}
			else
			{
				//dev...
				[[[essentialMatchingPairs objectAtIndex:outerIndex] objectAtIndex:innerIndex] printToLog];
			}
		}
		
		[[essentialMatchingPairs objectAtIndex:outerIndex] removeObjectsInArray:pairsToDelete];
		[pairsToDelete removeAllObjects];
	}
	
	return essentialMatchingPairs;
}

- (void)printToLog
{
	if (dictionaries != nil)
	{
		int i = 0;
		for (i; i < [dictionaries count]; i++)
		{
			NSEnumerator *tokenEnumerator = [[dictionaries objectAtIndex:i] objectEnumerator];
			NSEnumerator *keyEnumerator = [[dictionaries objectAtIndex:i] keyEnumerator];
			id ocurrenceArray;
			id key;
			
			while ((ocurrenceArray = [tokenEnumerator nextObject]))
			{
				key = [keyEnumerator nextObject];
				
				if ([ocurrenceArray count] > 1)
				{
					NSLog(@"token %@: %ix found:", key, [ocurrenceArray count]);
					
					int j = 0;
					for (j; j < [ocurrenceArray count]; j++)
					{
						NSLog(@"%@", [ocurrenceArray objectAtIndex:j]);
					}
				}
			}
		}
	}
	else
	{
		NSLog(@"RepititionFinder not properly initialised.");
	}
}

- (void)dealloc
{
	[superString release];
	[dictionaries release];
	[checkedRepetitionRegions release];
	[essentialMatchingPairs release];

	[super dealloc];
}

@end
