package version10_2_2_1.agnosticMemory;

import java.util.ArrayList;

import version10_2_2_1.Interface.InteractionList;

public class WorkMemory {

	public static int RELIABILITY=5;
	
	public Signature sig;
	private SignatureList sigList;
	
	public Point[] memory;
	
	public ArrayList<ArrayList<Byte[]>> pathList;
	public ArrayList<ArrayList<Short[]>> originList;

	public ArrayList<Byte[]> instanceList;
	public ArrayList<ArrayList<Short>> instanceParts;
	public ArrayList<ArrayList<Short>> instancePattern;
	
	public ArrayList<ArrayList<Byte[]>> movableInstances;
	public ArrayList<ArrayList<Short>> movableParts;
	public ArrayList<ArrayList<Short>> movablePattern;
	
	public ArrayList<Byte[]> movables;
	public ArrayList<Integer> movableIndex;
	public ArrayList<Byte[]> movableInstances1;
	public ArrayList<Byte[]> movableInstances2;
	
	public short[] objectMemory;
	
	public HypothesisMemory hypothesisMemory;
	
	public Point2[][] reference;		// used for reference changes
	
	public Constructible constructible;
	
	public ArrayList<Construction> construction;
	
	
	public WorkMemory(Signature s, SignatureList l){
		sig=s;
		sigList=l;
		memory=new Point[InteractionList.nbDF];
		for (short i=0;i<InteractionList.nbDF;i++) memory[i]=new Point(i);
		pathList=new ArrayList<ArrayList<Byte[]>>();
		originList=new ArrayList<ArrayList<Short[]>>();

		instanceList=new ArrayList<Byte[]>();
		instanceParts=new ArrayList<ArrayList<Short>>();
		instancePattern=new ArrayList<ArrayList<Short>>();
		
		movableInstances=new ArrayList<ArrayList<Byte[]>>();
		movableParts=new ArrayList<ArrayList<Short>>();
		movablePattern=new ArrayList<ArrayList<Short>>();
		
		movables=new ArrayList<Byte[]>();
		movableIndex=new ArrayList<Integer>();
		movableInstances1=new ArrayList<Byte[]>();
		movableInstances2=new ArrayList<Byte[]>();
		
		objectMemory=new short[InteractionList.length];
		
		reference=new Point2[2][InteractionList.length];
		for (short i=0;i<InteractionList.nbDF;i++){
			reference[0][i]=new Point2();
			reference[1][i]=new Point2();
		}
		
		hypothesisMemory=new HypothesisMemory();
		
		constructible=new Constructible();
		
		construction=new ArrayList<Construction>();
	}
	
	
	////////////////////////////////////////////////////////////////////////////
	public void projection(Signature s){
		
		// if false by default, project elements of the signature
		if (s.nb_s_f==100){
			
			for (byte c=0;c<s.context_f.size();c++){
				if (s.context_f.get(c).nb_s>=RELIABILITY && s.context_f.get(c).nb_s==s.context_f.get(c).nb_test){  // reliable
					for (int e=0;e<s.context_f.get(c).size();e++){
						
						Byte[] path=new Byte[0];
						Short[] origin= new Short[1];
						origin[0]=s.context_f.get(c).get(e);
						
						memory[s.context_f.get(c).get(e)].addPath(path, origin);

						projection(path,
								   origin, 					// origin element of initial signature
								   (short)0, 
								   s.context_f.get(c).get(e));
					}
				}
			}
		}
	}
	
	private void projection(Byte[] path, Short[] origin, short level, short id){
		
		boolean found=true;
		
		// hypothesis to reduce number of paths
		/*if (level==5){
			found=false;
			int l=0;
			while (l<path.length-1 && !found){
				if (path[l]<2 && path[l+1]<2) found=true;
				l++;
			}
		}*/
		
		if (found && level<Projection.LENGTH){

			// if false by default, project elements of the signature that are not elements of the signature of the associated primary interaction
			if (sigList.get(id).nb_s_f==100){

				for (int c=0;c<sigList.get(id).context_f.size();c++){
					if (sigList.get(id).context_f.get(c).nb_s>=RELIABILITY && sigList.get(id).context_f.get(c).nb_s==sigList.get(id).context_f.get(c).nb_test){ // reliable
						for (int e=0;e<sigList.get(id).context_f.get(c).size();e++){

							Byte[] path_clone=new Byte[path.length+1];
							for (short i=0;i<path.length;i++) path_clone[i]=path[i];
							path_clone[path.length]=(byte)(sigList.get(id).interaction.getIndex());
							
							//////////////////////////////////////////////////////////////////////////////
							// simplification hypothesis
							//////////////////////////////////////////////////////////////////////////////
							boolean found1=true;
							// avoid sequences ^^^ or vvv
							if (path_clone.length>=3 &&
							   (path_clone[path_clone.length-1]==4 && path_clone[path_clone.length-2]==4 && path_clone[path_clone.length-3]==4 ||
								path_clone[path_clone.length-1]==5 && path_clone[path_clone.length-2]==5 && path_clone[path_clone.length-3]==5)) found1=false;
							
							// avoid sequences ^v and v^, and equivalent sequences ^[>X]v and v[>X]^
							if (found1 && path_clone.length>=2){
								int l=path_clone.length-1;
								boolean found2=false;
								while (!found2 && l>=1){
									if (path_clone[l]==4) found2=true;
									l--;
								}
								while (found2 && l>=0){
									if (path_clone[l]==5) l=-1; // end of the sub-sequence
									else{
										if (path_clone[l]!=2) found2=false; // sub-sequence does not match
									}
									l--;
								}
								
								if (found2) found1=false;
							}
							
							if (found1 && path_clone.length>=2){
								int l=path_clone.length-1;
								boolean found2=false;
								while (!found2 && l>=1){
									if (path_clone[l]==5) found2=true;
									l--;
								}
								while (found2 && l>=0){
									if (path_clone[l]==4) l=-1; // end of the sub-sequence
									else{
										if (path_clone[l]!=2) found2=false; // sub-sequence does not match
									}
									l--;
								}
								
								if (found2) found1=false;
							}
							
							//if (path_clone[path_clone.length-1]==2 || path_clone[path_clone.length-1]==3) found1=false;
							
							//////////////////////////////////////////////////////////////////////////////
							
							if (found1){
								short counter=0;
								short l=0;
								while (counter<2 && l<path_clone.length){
									if (path_clone[l]==(sig.index-InteractionList.nbDF)) counter++;
									l++;
								}
								
								if (counter<2){
									Short[] origin_clone=new Short[origin.length+1];
									for (short i=0;i<origin.length;i++) origin_clone[i]=origin[i];
									origin_clone[origin.length]=sigList.get(id).context_f.get(c).get(e);
									
									// detect loops
									l=1;
									/*while (found1 && l<origin_clone.length){
										if ((int)origin_clone[0]==(int)origin_clone[l]) found1=false;;
										l++;
									}*/
									
									if (found1){
										memory[sigList.get(id).context_f.get(c).get(e)].addPath(path_clone, origin_clone);
										projection(path_clone,
												   origin_clone, 
												   (short)(level+1), 
												   sigList.get(id).context_f.get(c).get(e));
									}
								}
							}
						}
					}
				}
			}
			
			// if true by default, we use the signature of the associated primary interaction
			if (sigList.get(id).nb_s_t==100){
				
				short index_sig=(short)sigList.get(id).interaction.getIndex();

				if (sigList.get(index_sig+InteractionList.nbDF).nb_s_f==100){
					for (int c=0;c<sigList.get(index_sig+InteractionList.nbDF).context_f.size();c++){
						if (sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s>=RELIABILITY
						 && sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s==sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_test){
							for (int e=0;e<sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).size();e++){

								Byte[] path_clone=new Byte[path.length+1];
								for (short i=0;i<path.length;i++) path_clone[i]=path[i];
								path_clone[path.length]=(byte)(sigList.get(index_sig+InteractionList.nbDF).interaction.getIndex());
								
								//////////////////////////////////////////////////////////////////////////////
								// simplification hypothesis
								//////////////////////////////////////////////////////////////////////////////
								boolean found1=true;
								// avoid sequences ^^^ or vvv
								if (path_clone.length>=3 &&
								   (path_clone[path_clone.length-1]==4 && path_clone[path_clone.length-2]==4 && path_clone[path_clone.length-3]==4 ||
									path_clone[path_clone.length-1]==5 && path_clone[path_clone.length-2]==5 && path_clone[path_clone.length-3]==5)) found1=false;
								
								// avoid sequences ^^ and vv, and equivalent sequences ^[>X]^ and v[>X]v
								if (found1 && path_clone.length>=2){
									int l=path_clone.length-1;
									boolean found2=false;
									while (!found2 && l>=1){
										if (path_clone[l]==4) found2=true;
										l--;
									}
									while (found2 && l>=0){
										if (path_clone[l]==5) l=-1; // end of the sub-sequence
										else{
											if (path_clone[l]!=2) found2=false; // sub-sequence does not match
										}
										l--;
									}
									
									if (found2) found1=false;
								}
								if (found1 && path_clone.length>=2){
									int l=path_clone.length-1;
									boolean found2=false;
									while (!found2 && l>=1){
										if (path_clone[l]==5) found2=true;
										l--;
									}
									while (found2 && l>=0){
										if (path_clone[l]==4) l=-1; // end of the sub-sequence
										else{
											if (path_clone[l]!=2) found2=false; // sub-sequence does not match
										}
										l--;
									}
									
									if (found2) found1=false;
								}
								
								//if (path_clone[path_clone.length-1]==2 || path_clone[path_clone.length-1]==3) found1=false;
								
								//////////////////////////////////////////////////////////////////////////////
								
								if (found1){

									int counter=0;
									short l=0;
									while (counter<2 && l<path_clone.length){
										if (path_clone[l]==(sig.index-InteractionList.nbDF)) counter++;
										l++;
									}
									
									if (counter<2){
										Short[] origin_clone=new Short[origin.length+1];
										for (short i=0;i<origin.length;i++) origin_clone[i]=origin[i];
										origin_clone[origin.length]=sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e);
										
										// detect loops
										l=1;
										/*while (found1 && l<origin_clone.length){
											if ((int)origin_clone[0]==(int)origin_clone[l]) found1=false;;
											l++;
										}*/
										
										if (found1){
											memory[sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e)].addPath(path_clone, origin_clone);
											projection(path_clone,
													   origin_clone, 
													   (short)(level+1), 
													   sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e));
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	
	////////////////////////////////////////////////////////////////////////////
	public void projectObject(Byte[] path, Short[] pointList){
		
		for (int i=0;i<InteractionList.length;i++) objectMemory[i]=0;

		// if false by default, project elements of the signature
		if (sig.nb_s_f==100){
			for (byte c=0;c<sig.context_f.size();c++){
				if (path.length>0 && path[0]==sig.context_f.get(c).index_primary-InteractionList.nbDF){ // context must be related to primary interaction given by the path

					if (sig.context_f.get(c).nb_s>=RELIABILITY && sig.context_f.get(c).nb_s==sig.context_f.get(c).nb_test){  // reliable
						
						// define if the current context contain the element of the path
						boolean found=false;
						for (int e=0;e<sig.context_f.get(c).size();e++){
							if (sig.context_f.get(c).get(e)==pointList[0]) found=true;
						}
						
						// if the current context contains the first point, then project it
						if (found){
							for (int e=0;e<sig.context_f.get(c).size();e++){
								projectObject(path, pointList, (short)1, sig.context_f.get(c).get(e),
											  sig.context_f.get(c).get(e)==pointList[0]);
							}
						}
					}
				}
				else{
					// case path of length 0 : copy signature
					if (path.length==0){
						if (sig.nb_s_f==100){
							for (c=0;c<sig.context_f.size();c++){
								
								// define if the current context contain the element of the path
								boolean found=false;
								for (int e=0;e<sig.context_f.get(c).size();e++){
									if (sig.context_f.get(c).get(e)==pointList[0]) found=true;
								}
								
								if (found){
									if (sig.context_f.get(c).nb_s>=RELIABILITY && sig.context_f.get(c).nb_s==sig.context_f.get(c).nb_test){ // reliable
										for (int e=0;e<sig.context_f.get(c).size();e++){
											objectMemory[sig.context_f.get(c).get(e)]=2;	
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	private void projectObject(Byte[] path, Short[] pointList, short level, short id, boolean mainPath){
		
		if (level<path.length){

			// if false by default, project elements of the signature
			if (sigList.signatureList.get(id).nb_s_f==100){
				for (int c=0;c<sigList.signatureList.get(id).context_f.size();c++){
					if (path[level]==sigList.signatureList.get(id).context_f.get(c).index_primary-InteractionList.nbDF){
						if (sigList.signatureList.get(id).context_f.get(c).nb_s>=RELIABILITY
						 && sigList.signatureList.get(id).context_f.get(c).nb_s==sigList.signatureList.get(id).context_f.get(c).nb_test){ // reliable
							
							if (mainPath){
								
								// define if the current context contain the element of the path
								boolean found=false;
								for (int e=0;e<sigList.signatureList.get(id).context_f.get(c).size();e++){
									if (sigList.signatureList.get(id).context_f.get(c).get(e)==pointList[level]) found=true;
								}

								if (found){
									for (int e=0;e<sigList.signatureList.get(id).context_f.get(c).size();e++){
										projectObject(path, pointList, (short)(level+1), sigList.signatureList.get(id).context_f.get(c).get(e),
												      sigList.signatureList.get(id).context_f.get(c).get(e)==pointList[level]);					
									}
								}
							}
							else{
								for (int e=0;e<sigList.signatureList.get(id).context_f.get(c).size();e++){
									projectObject(path, pointList, (short)(level+1), sigList.signatureList.get(id).context_f.get(c).get(e),
											      false);					
								}
							}
						}
					}
				}
			}
			
			// if true by default, we use the signature of the associated primary interaction
			if (sigList.signatureList.get(id).nb_s_t==100){
				short index_sig=(short)sigList.signatureList.get(id).interaction.getIndex();

				if (sigList.signatureList.get(index_sig+InteractionList.nbDF).nb_s_f==100){
					for (int c=0;c<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.size();c++){
						if (path[level]==(sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).index_primary)-InteractionList.nbDF){
							if (sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s>=RELIABILITY
							 && sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s==sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_test){
								
								if (mainPath){
									
									// define if the current context contain the element of the path
									boolean found=false;
									for (int e=0;e<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).size();e++){
										if (sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e)==pointList[level]) found=true;
									}
									
									if (found){
										for (int e=0;e<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).size();e++){
											projectObject(path, pointList, (short)(level+1), sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e),
													      sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e)==pointList[level]);					
										}
									}
								}
								else{
									for (int e=0;e<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).size();e++){
										projectObject(path, pointList, (short)(level+1), sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e),
												      false);					
									}
								}
							}
						}
					}
				}
			}
		}
		else{
			if (sigList.signatureList.get(id).nb_s_f==100){
				for (int c=0;c<sigList.signatureList.get(id).context_f.size();c++){
					if (sigList.signatureList.get(id).context_f.get(c).nb_s>=RELIABILITY && sigList.signatureList.get(id).context_f.get(c).nb_s==sigList.signatureList.get(id).context_f.get(c).nb_test){ // reliable
						for (int e=0;e<sigList.signatureList.get(id).context_f.get(c).size();e++){
							objectMemory[sigList.signatureList.get(id).context_f.get(c).get(e)]=2;	
						}
					}
				}
			}
		}
	}
	
	//////////////////////////////////////////////////////////////////////////////
	public void getObjectPaths(){
		/*System.out.println("------------------ path for the first memory ---------------------------");
		for (int i=0;i<InteractionList.length;i++){
			if (objectMemory[0][i]==2){
				System.out.println("+++ "+i);
				for (int j=0;j<memory[i].size();j++){
					for (int l=memory[i].pathList.get(j).length-1;l>=0;l--){
						System.out.print(memory[i].pathList.get(j)[l]+", ");
					}
					System.out.println();
				}
			}
		}
		System.out.println();
		System.out.println("------------------ path for the second memory ---------------------------");
		for (int i=0;i<InteractionList.length;i++){
			if (objectMemory[1][i]==2){
				System.out.println("+++ "+i);
				for (int j=0;j<memory[i].size();j++){
					for (int l=memory[i].pathList.get(j).length-1;l>=0;l--){
						System.out.print(memory[i].pathList.get(j)[l]+", ");
					}
					System.out.println();
				}
			}
		}
		System.out.println();
		System.out.println("------------------ path for the third memory ---------------------------");
		for (int i=0;i<InteractionList.length;i++){
			if (objectMemory[2][i]==2){
				System.out.println("+++ "+i);
				for (int j=0;j<memory[i].size();j++){
					for (int l=memory[i].pathList.get(j).length-1;l>=0;l--){
						System.out.print(memory[i].pathList.get(j)[l]+", ");
					}
					System.out.println();
				}
			}
		}*/
	}
	
	//////////////////////////////////////////////////////////////////////////////
	public void resetMemory(){
		for (short i=0;i<InteractionList.nbDF;i++) memory[i].reset();
	}
	
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// detect position of object instances and proto-objects
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public void detectPaths(float[] input){
		pathList.clear();
		originList.clear();

		instanceList.clear();
		instanceParts.clear();
		instancePattern.clear();
		
		movableInstances.clear();
		movableParts.clear();
		movablePattern.clear();
		
		movables.clear();
		movableIndex.clear();
		movableInstances1.clear();
		movableInstances2.clear();

		construction.clear();
		
		int id=sig.index-InteractionList.nbDF;
		
		// detect path where proto-objects are detected 						(instances and proto-objects)
		for (short i=0;i<InteractionList.nbDF;i++){
			if (input[i]>0){
				pathList.add(new ArrayList<Byte[]>());
				originList.add(new ArrayList<Short[]>());

				// for each path that characterizes the position of the current proto-object
				for (int p=0;p<memory[i].size();p++){
					
					//////////////////////////////////////////////////////////////////////////////
					// simplification hypothesis
					//////////////////////////////////////////////////////////////////////////////
					int l=0;
					boolean found2=true;
					
					l=0;
					// path does not contain an instance of the same object
					while (found2 && l<memory[i].pathList.get(p).length){
						if (memory[i].pathList.get(p)[l]==id) found2=false;
						l++;
					}
					//////////////////////////////////////////////////////////////////////////////
					
					// get the signature image through path p
					Projection proj=new Projection(sig, memory[i].pathList.get(p), sigList.signatureList, (byte)-1);
					
					// add object instance in memory if recognized
					if (proj.getResult(new short[InteractionList.length])){
						instanceList.add(memory[i].pathList.get(p));
						instanceParts.add(new ArrayList<Short>());
						instancePattern.add(new ArrayList<Short>());
					}
					
					if (found2){
						// add proto-object
						pathList.get(pathList.size()-1).add(memory[i].pathList.get(p));
						originList.get(originList.size()-1).add(memory[i].originList.get(p));
					}
				}
			}
		}
		
		// define instances parts and pattern
		for (int i=0;i<instanceList.size();i++){
			
			for (int p1=0;p1<pathList.size();p1++){
				for (int p2=0;p2<pathList.get(p1).size();p2++){
					
					if (instanceList.get(i).length==pathList.get(p1).get(p2).length){
						boolean identical=true;
						int l=0;
						while (identical && l<instanceList.get(i).length){
							if ((int)instanceList.get(i)[l]!=(int)pathList.get(p1).get(p2)[l]) identical=false;
							l++;
						}
						
						if (identical){
							l=0;
							identical=false;
							while (!identical && l<instanceParts.get(i).size()){
								if ((int)instanceParts.get(i).get(l)==(int)originList.get(p1).get(p2)[0]) identical=true;
								l++;
							}
							if (!identical) instanceParts.get(i).add(originList.get(p1).get(p2)[0]);
							
							l=0;
							identical=false;
							while (!identical && l<instancePattern.get(i).size()){
								if ((int)instancePattern.get(i).get(l)==(int)originList.get(p1).get(p2)[originList.get(p1).get(p2).length-1]) identical=true;
								l++;
							}
							if (!identical) instancePattern.get(i).add(originList.get(p1).get(p2)[originList.get(p1).get(p2).length-1]);
						}
					}
				}
			}
		}
		
		
		// remove proto-object path that contains an instance of the object
		for (int p=0;p<pathList.size();p++){
			for (int p2=0;p2<pathList.get(p).size();p2++){
				
				int l=pathList.get(p).get(p2).length-1;
				boolean found=false;
				while (!found && l>=0){
					if ((int)pathList.get(p).get(p2)[l]==sig.interaction.getIndex()) found=true;
					l--;
				}
				if (found){
					pathList.get(p).remove(p2);
					originList.get(p).remove(p2);
					p2--;
				}
			}
			if (pathList.size()==0){
				pathList.remove(p);
				originList.remove(p);
				p--;
			}
		}
		
		// remove redundant instances														(instances)
		// two paths are redundant if they correspond to the same instance
		for (int p=0;p<instanceList.size();p++){
			for (int p1=p+1;p1<instanceList.size();p1++){
				if (instanceList.get(p).length==instanceList.get(p1).length){
					boolean identical=true;
					int l=0;
					while (identical && l<instanceList.get(p).length){
						if (instanceList.get(p)[l]!=instanceList.get(p1)[l]) identical=false;
						l++;
					}
					
					// merge parts and patterns
					if (identical){
						
						for (int i=0;i<instanceParts.get(p1).size();i++){
							if (!instanceParts.get(p).contains(instanceParts.get(p1).get(i))) instanceParts.get(p).add(instanceParts.get(p1).get(i));
						}
						for (int i=0;i<instancePattern.get(p1).size();i++){
							if (!instancePattern.get(p).contains(instancePattern.get(p1).get(i))) instancePattern.get(p).add(instancePattern.get(p1).get(i));
						}
						
						instanceList.remove(p1);
						instanceParts.remove(p1);
						instancePattern.remove(p1);
						p1--;
					}
				}
			}
		}
		
		// remove redundant proto-objects
		for (int p=0;p<pathList.size();p++){
			
			for (int p1=0;p1<pathList.get(p).size();p1++){
				
				for (int p2=0;p2<pathList.get(p).size();p2++){
					
					if (pathList.get(p).get(p1).length<pathList.get(p).get(p2).length){

						int l1=pathList.get(p).get(p1).length-1;
						int l2=pathList.get(p).get(p2).length-1;
						
						if (l1==-1 || l2==-1 || pathList.get(p).get(p1)[l1]!=pathList.get(p).get(p2)[l2]){
							
							while (l1>=0 && l2>=0){
								if (pathList.get(p).get(p1)[l1]==pathList.get(p).get(p2)[l2]){
									l1--;
									l2--;
								}
								else{
									l2--;
								}
							}
							
							if (l1==0){
								pathList.get(p).remove(p2);
								originList.get(p).remove(p2);
								if (p1<p2) p2--;
								else{
									p1--;
									p2--;
								}
							}
						}
					}
					
				}
			}
		}
	}
	
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// remove instances and proto-objects with invalid paths and detect movable objects
	public void validePaths(float[] input){
		
		//////////////////////////////////////////////////////
		// remove instances with invalid path												(instances)
		for (int length=0;length<=Projection.LENGTH;length++)
		for (int p=0;p<instanceList.size();p++){
			if (instanceList.get(p).length==length){
				boolean valid=true;
				
				// for each element of the considered path
				int e=instanceList.get(p).length-1;
				int l=1;
				while (valid && e>=0){
					
					// if the element is not related to a default true interaction, check if the interaction is enactable
					if (sigList.signatureList.get(instanceList.get(p)[e]+InteractionList.nbDF).nb_s_t!=100){

						valid=false;
						
						// find an instance that validate this sub path
						int p2=0;
						while (!valid && p2<sigList.workMemory[instanceList.get(p)[e]].instanceList.size()){
							if (sigList.workMemory[instanceList.get(p)[e]].instanceList.get(p2).length==l-1 && p!=p2){
								boolean identical=true;
								int e2=0;
	
								while (identical && e2<l-1){
									if (sigList.workMemory[instanceList.get(p)[e]].instanceList.get(p2)[e2]!=instanceList.get(p)[e2+e+1]) identical=false;
									e2++;
								}
								if (identical)	valid=true;
							}
							p2++;
						}
					}
					e--;
					l++;
				}
				if (!valid){
					instanceList.remove(p);
					instanceParts.remove(p);
					instancePattern.remove(p);
					p--;
				}
			}
		}
		
		// detect instances that can be moved									(movable)
		for (short p1=0;p1<instanceList.size();p1++){
			for (short p2=0;p2<instanceList.size();p2++){
				if ( (instanceList.get(p1).length+1)==instanceList.get(p2).length){
						
					short l=0;
					boolean identical=true;
					while (identical && l<instanceList.get(p1).length){
						if (instanceList.get(p1)[l]!=instanceList.get(p2)[l+1]) identical=false;
						l++;
					}

					if (identical){
						movableInstances.add(new ArrayList<Byte[]>());
						movableInstances.get(movableInstances.size()-1).add(instanceList.get(p1));
						movableInstances.get(movableInstances.size()-1).add(instanceList.get(p2));
						movableParts.add(instanceParts.get(p1));
						movablePattern.add(instancePattern.get(p1));
					}
				}
			}
		}
		
		// eliminate redundant movements												(movements)
		for (short i=0;i<movableInstances.size();i++){
			for (short j=0;j<movableInstances.size();j++){
				if (movableInstances.get(i).get(1).length<=movableInstances.get(j).get(0).length){
					short l=0;
					int delta=movableInstances.get(j).get(0).length-movableInstances.get(i).get(1).length;
					boolean identical=true;
					while (identical && l<movableInstances.get(i).get(1).length){
						if (movableInstances.get(i).get(1)[l]!=movableInstances.get(j).get(0)[l+delta]) identical=false;
						l++;
					}
					if (identical){
						movableInstances.remove(j);
						movableParts.remove(j);
						movablePattern.remove(j);
						if (i>j){
							i--;
							j--;
						}
						else j--;
					}
				}
			}
		}
		
		
		///////////////////////////////////////////////////////////////
		// remove redundant proto-objects
		for (int p1=0;p1<pathList.size();p1++){
			
			for (int p2=0;p2<pathList.get(p1).size();p2++){
				for (int p4=0;p4<pathList.get(p1).size();p4++){
			
					boolean found=false;
					
					if (pathList.get(p1).get(p2).length<pathList.get(p1).get(p4).length){
						int l=0;
						found=true;
						int diff=pathList.get(p1).get(p4).length-pathList.get(p1).get(p2).length;
						while (found && l<pathList.get(p1).get(p2).length){
							if (pathList.get(p1).get(p2)[l]!=pathList.get(p1).get(p4)[l+diff]) found=false;
							l++;
						}
					}
					if (found){
						pathList.get(p1).remove(p4);
						originList.get(p1).remove(p4);
						
						if (p4>p2) p4--;
						else{
							p2--;
							p4--;
						}
					}
				}
			}
		}
		
		// remove proto-object that are already object instances					(proto-objects)
		for (short i=0;i<instanceList.size();i++){
			for (int p1=0;p1<pathList.size();p1++){
				for (int p2=0;p2<pathList.get(p1).size();p2++){
					
					boolean found=false;
					
					if (instanceList.get(i).length==pathList.get(p1).get(p2).length){
						int l=0;
						found=true;
						while (found && l<instanceList.get(i).length){
							if (instanceList.get(i)[l]!=pathList.get(p1).get(p2)[l]) found=false;
							l++;
						}
					}
					if (found){
						pathList.get(p1).remove(p2);
						originList.get(p1).remove(p2);
						p2--;
					}
				}
			}
		}
				
		//////////////////////
		// remove proto-objects with invalid path									(proto-objects)
		for (int p1=0;p1<pathList.size();p1++){
			for (int p2=0;p2<pathList.get(p1).size();p2++){

				boolean valid=true;
				
				// for each element of the considered path
				int e=pathList.get(p1).get(p2).length-1;
				int l=1;
				while (valid && e>0){
					
					// if the element is not related to a default true interaction, check if the interaction is enactable
					if (sigList.signatureList.get(pathList.get(p1).get(p2)[e]+InteractionList.nbDF).nb_s_t!=100){

						valid=false;
						
						// find an instance that validate this sub path
						int p0=0;
						while (!valid && p0<sigList.workMemory[pathList.get(p1).get(p2)[e]].instanceList.size()){
							if (sigList.workMemory[pathList.get(p1).get(p2)[e]].instanceList.get(p0).length==l-1){
								boolean identical=true;
								int e2=0;
	
								while (identical && e2<l-1){
									if (sigList.workMemory[pathList.get(p1).get(p2)[e]].instanceList.get(p0)[e2]!=pathList.get(p1).get(p2)[e2+e+1]) identical=false;
									e2++;
								}
								if (identical) valid=true;
							}
							p0++;
						}
					}
					e--;
					l++;
				}
				if (!valid){
					pathList.get(p1).remove(p2);
					originList.get(p1).remove(p2);
					p2--;
				}
			}
		}
		
		
		// define hypothesis from proto objects
		for (int p=0;p<pathList.size();p++){
			for (int p1=0;p1<pathList.get(p).size();p1++){
				
				projectObject(pathList.get(p).get(p1),
							  originList.get(p).get(p1));
				
				boolean valid=true;
				
				// group of secondary interactions related to a same primary interaction
				int id=originList.get(p).get(p1)[originList.get(p).get(p1).length-1]/(InteractionList.size*InteractionList.size*4);
				ArrayList<Short[]> list=new ArrayList<Short[]>();
				for (int j=id*InteractionList.size*InteractionList.size*4;j<(id+1)*InteractionList.size*InteractionList.size*4;j++){
						
					// for each element of the predecessor by pathList.get(p).get(p1), check for the existence of a path that lead to this element
					if (objectMemory[j]>0){
						boolean found=false;
						int k=0;
						while(!found && k<memory[j].size()){
							
							if (memory[j].pathList.get(k).length==pathList.get(p).get(p1).length){
								found=true;
								int l=0;
								while (found && l<memory[j].pathList.get(k).length){
									if (memory[j].pathList.get(k)[l]!=pathList.get(p).get(p1)[l]) found=false;
									l++;
								}
							}
							if (!found) k++;
						}
						if (found) list.add(memory[j].originList.get(k));
						else valid=false;			// element cannot be found by following the path
					}
				}
				
				if (list.size()>1 && list.size()<5){
					hypothesisMemory.addHypothesis(pathList.get(p).get(p1), list);
				}
			}
		}
		//System.out.println(" --- test : "+hypothesisMemory.memory.size());
		//hypothesisMemory.print();
		
		
		// last step : remove object instance with a path that contain an instance of the same object
		/*int id=sig.index-InteractionList.nbDF;
		for (int i=0;i<instanceList.size();i++){
			int l=0;
			boolean found=false;
			while (!found && l<instanceList.get(i).length){
				if (instanceList.get(i)[l]==id) found=true;
				l++;
			}
			if (found){
				instanceList.remove(i);
				instanceParts.remove(i);
				instancePattern.remove(i);
				i--;
			}
		}*/
	}
	
	public void detectConstructible(SignatureList sigList){
		
		// detect proto-objects that match hypothesis
		for (int i=0;i<hypothesisMemory.memory.size();i++){
			hypothesisMemory.memory.get(i).resetDetection();
			for (int p0=0;p0<pathList.size();p0++){
				for (int p1=0;p1<pathList.get(p0).size();p1++){
					hypothesisMemory.memory.get(i).detect(pathList.get(p0).get(p1), originList.get(p0).get(p1), sigList);		
				}
			}
		}
		
		// remove invalid hypothesis
		//hypothesisMemory.checkValidity();
		hypothesisMemory.removeRedundant();
	}
	
	
	public ArrayList<Hypothesis> getConstructibles(int id){
		return hypothesisMemory.detectActive(id, sigList);
	}
	

	
	public void changeReference(Byte[] path1, int mem){

		for (short i=0;i<InteractionList.nbDF;i++){
			reference[mem][i].reset();
		}
		
		//for (int l=0;l<path1.length+1;l++){
			for (short i=0;i<InteractionList.nbDF;i++){
				if (memory[i].isActive()) projectMap(i, i, path1, 0, mem);
			}
		//}
	}
	
	private void projectMap(short id, short origin, Byte[] path, int level, int mem){
		
		if (level<path.length){

			// if false by default, project elements of the signature
			if (sigList.signatureList.get(id).nb_s_f==100 && sigList.signatureList.get(id).interaction.getIndex()==path[level]){
				
				for (int c=0;c<sigList.signatureList.get(id).context_f.size();c++){
					if (sigList.signatureList.get(id).context_f.get(c).nb_s>=1 && 
						sigList.signatureList.get(id).context_f.get(c).nb_s==sigList.signatureList.get(id).context_f.get(c).nb_test //&&
					   //(sigList.signatureList.get(id).context_f.get(c).index_primary-InteractionList.nbDF)==path[level]
					    ){ // reliable and related to given path
						
						for (int e=0;e<sigList.signatureList.get(id).context_f.get(c).size();e++){

							projectMap(sigList.signatureList.get(id).context_f.get(c).get(e),
									   origin, path,
									   (short)(level+1),mem);					
						}
					}
				}
			}
			
			// if true by default, we use the signature of the associated primary interaction
			if (sigList.signatureList.get(id).nb_s_t==100){
				
				short index_sig=(short)sigList.signatureList.get(id).interaction.getIndex();

				if (sigList.signatureList.get(index_sig+InteractionList.nbDF).nb_s_f==100 && index_sig==path[level]){
					
					for (int c=0;c<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.size();c++){
						
						if (sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s>=1 &&
						    sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_s==sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).nb_test //&&
						   //(sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).index_primary-InteractionList.nbDF)==path[level]
						    ){
							
							for (int e=0;e<sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).size();e++){
	
								projectMap(sigList.signatureList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e),
										   origin, path, 
										   (short)(level+1),mem);					
							}
						}
					}
				}
			}
		}
		else{
			// end of the projection
			reference[mem][id].addPath(origin);
		}
	}
	
	
	public void addConstructiblePath(Byte[] path){
		constructible.addPath(path);
	}
	
	// detect equivalences between movable objects
	public void detectEquivalences(){
		
		for (int m1=0;m1<movableInstances.size();m1++){
			for (int m2=0;m2<movableInstances.size();m2++){
			
				if (m1!=m2){
					// must have the same pattern
					boolean found=true;
					if (movablePattern.get(m1).size()!=movablePattern.get(m2).size()
					 || movableInstances.get(m1).get(0).length>=movableInstances.get(m2).get(0).length){
						found=false;
					}
					if (found){
						int i=0;
						while (found && i<movablePattern.get(m1).size()){
							found=false;
							int j=0;
							while (!found && j<movablePattern.get(m2).size()){
								if ((int)movablePattern.get(m1).get(i)==(int)movablePattern.get(m2).get(j)) found=true;
								j++;
							}
							i++;
						}
					}
					
					if (found){
						// path must be included
						int l=0;
						int diff=movableInstances.get(m2).get(0).length-movableInstances.get(m1).get(0).length;
						while (found && l<movableInstances.get(m1).get(0).length){
							if ((int)movableInstances.get(m1).get(0)[l]!=(int)movableInstances.get(m2).get(0)[l+diff]) found=false;
							l++;
						}
						
						if (found){
							Byte[] temp_path=new Byte[diff];
							for (l=0;l<diff;l++){
								temp_path[l]=movableInstances.get(m2).get(0)[l];
							}

							constructible.addPath(temp_path);
						}
					}	
				}
			}
		}
	}
	
	
	public void detectFinalMovables(){
		
		// define extended movables
		for (int m=0;m<movableInstances.size();m++){
			for (int p=0;p<constructible.pathList.size();p++){
				int length=movableInstances.get(m).get(0).length+constructible.pathList.get(p).length;
				
				// generate pre-movement path
				Byte[] path_temp=new Byte[length];
				
				for (int l=0;l<constructible.pathList.get(p).length;l++){
					path_temp[l]=constructible.pathList.get(p)[l];
				}
				for (int l=0;l<movableInstances.get(m).get(0).length;l++){
					path_temp[l+constructible.pathList.get(p).length]=movableInstances.get(m).get(0)[l];
				}

				
				int i=0;
				boolean found=false;
				
				//if (path_temp.length>Projection.LENGTH) found=false;
				
				while (!found && i<movables.size()){
					if (path_temp.length==movables.get(i).length){
						found=true;
						int l=0;
						while (found && l<path_temp.length){
							if ((int)path_temp[l]!=(int)movables.get(i)[l]) found=false;
							l++;
						}
					}
					i++;
				}
				if (!found)	movables.add(path_temp);
			}
		}
		
		//-----------------------------------------------------
		//for (int i=0;i<movables.size();i++){
		//	System.out.print(" final "+sig.interaction.getIndex()+" -> [");
		//	for (int l=movables.get(i).length-1;l>=0;l--) System.out.print(movables.get(i)[l]+", ");
		//	System.out.println("]");
		//}
		//-----------------------------------------------------
		
		for (int m=0;m<movables.size();m++){
			for (int p=0;p<constructible.pathList.size();p++){
				int length=movables.get(m).length+constructible.pathList.get(p).length;
				
				// generate pre-movement path
				Byte[] path_temp=new Byte[length];
				
				for (int l=0;l<constructible.pathList.get(p).length;l++){
					path_temp[l]=constructible.pathList.get(p)[l];
				}
				for (int l=0;l<movables.get(m).length;l++){
					path_temp[l+constructible.pathList.get(p).length]=movables.get(m)[l];
				}
				
				// generate post-movement path
				Byte[] path_temp2=new Byte[length+1];
				
				for (int l=0;l<constructible.pathList.get(p).length;l++){
					path_temp2[l]=constructible.pathList.get(p)[l];
				}
				path_temp2[constructible.pathList.get(p).length]=(byte) sig.interaction.getIndex(); // add the movable
				for (int l=0;l<movables.get(m).length;l++){
					path_temp2[l+constructible.pathList.get(p).length+1]=movables.get(m)[l];
				}
				
				int i=0;
				boolean found=false;
				
				if (path_temp.length>Projection.LENGTH) found=false;
				
				while (!found && i<movableInstances2.size()){
					if (path_temp2.length==movableInstances2.get(i).length){
						found=true;
						int l=0;
						while (found && l<path_temp2.length){
							if ((int)path_temp2[l]!=(int)movableInstances2.get(i)[l]) found=false;
							l++;
						}
					}
					i++;
				}
				
				////////////////////////////////////////////////////////////////
				// simplification : avoid vv and ^^ subsequences (u_turns) in the lastss steps
				////////////////////////////////////////////////////////////////
				for (int l=0;l<path_temp.length-2;l++){
					if ( (path_temp2[l]==4 && path_temp2[l+1]==4) ||  (path_temp2[l]==5 && path_temp2[l+1]==5) ) found=true;
				}
				////////////////////////////////////////////////////////////////
				
				
				if (!found){
					//movables.add(movableInstances.get(m).get(0));
					movableIndex.add(m);
					movableInstances1.add(path_temp);
					movableInstances2.add(path_temp2);
				}
			}
		}
		//-----------------------------------------------------
		//for (int i=0;i<movableInstances1.size();i++){
		//	System.out.print(" movable "+sig.interaction.getIndex()+" -> [");
		//	for (int l=movableInstances1.get(i).length-1;l>=0;l--) System.out.print(movableInstances1.get(i)[l]+", ");
		//	System.out.print("] -> [");
		//	for (int l=movableInstances2.get(i).length-1;l>=0;l--) System.out.print(movableInstances2.get(i)[l]+", ");
		//	System.out.println("]");
		//}
		//-----------------------------------------------------
		
	}
	
	
	public void cleanMemory(int id){
		/*for (int i=0;i<memory.length;i++){
			if (i%250==0)System.out.print("#");
			// remove paths that are contained in an other one
			for (int p1=0;p1<memory[i].size();p1++){
				for (int p2=0;p2<memory[i].size();p2++){
					if (memory[i].originList.get(p1).length<memory[i].originList.get(p2).length &&
						(int)memory[i].originList.get(p1)[0]==(int)memory[i].originList.get(p2)[0]){
						
						int diff=memory[i].originList.get(p2).length-memory[i].originList.get(p1).length;
						
						if (memory[i].pathList.get(p2)[diff-1]!=id){
							int l1=memory[i].originList.get(p1).length-1;
							int l2=memory[i].originList.get(p2).length-1;
							
							while (l1>=0 && l2>=0){
								while (l2>=0 && (int)memory[i].originList.get(p1)[l1]!=(int)memory[i].originList.get(p2)[l2]){
									l2--;
								}
								l1--;
								l2--;
							}
							
							
							if (l1==-1){
								memory[i].pathList.remove(p2);
								memory[i].originList.remove(p2);
								
								if (p1>p2){
									p1--;
									p2--;
								}
								else p2--;
							}
						}
					}
				}
			}
		}*/
		
		// remove paths that are identical but have different origins
		int count=0;
		for (int i=0;i<memory.length;i++){
			if (i%250==0)System.out.print("#");
			// remove paths that are contained in an other one
			for (int p1=0;p1<memory[i].size();p1++){
				
				boolean found=false;
				
				for (int p2=p1+1;p2<memory[i].size();p2++){
					if (memory[i].originList.get(p1).length==memory[i].originList.get(p2).length &&
						(int)memory[i].originList.get(p1)[0]==(int)memory[i].originList.get(p2)[0]){

						boolean identical=true;
						int l=memory[i].pathList.get(p1).length-1;
						while (identical && l>=0){
							if ((int)memory[i].pathList.get(p1)[l]!=(int)memory[i].pathList.get(p2)[l]) identical=false;
							l--;
						}
						
						if (identical){
							memory[i].pathList.remove(p2);
							memory[i].originList.remove(p2);
							count++;
							p2--;
							found=true;
						}
					}
				}
				
				if (found){
					memory[i].pathList.remove(p1);
					memory[i].originList.remove(p1);
					p1--;
					count++;
				}
			}
		}
		
		
		System.out.println(count+" paths removed");
	}
	
	
	public void setDistance(int id_path, int element, int type, int dist, int dist1, int dist2){
		
		boolean found=false;
		int i=0;
		while (!found && i<construction.size()){
			if (construction.get(i).isEqual(movableIndex.get(id_path), element, type)) found=true;
			else i++;
		}
		
		if (!found) construction.add(new Construction((int)movableIndex.get(id_path), element, type));
		else{
			construction.get(i).setDistance(dist, dist1, dist2);
		}
	}
	                                                            
	
}
