package version10_2_2_1.agnosticMemory;

import java.util.ArrayList;

import version10_2_2_1.Interface.InteractionList;

public class WorkMemory {

	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<Byte[]>> movableInstances;
	
	public ArrayList<ArrayList<Byte[]>> instancesPosition;
	
	public int[][] objectMemory;
	
	public HypothesisMemory hypothesisMemory;
	
	public Point2[][] reference;
	
	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[]>();
		movableInstances=new ArrayList<ArrayList<Byte[]>>();
		instancesPosition=new ArrayList<ArrayList<Byte[]>>();
		
		objectMemory=new int[3][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();
	}
	
	
	////////////////////////////////////////////////////////////////////////////
	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>=2 && 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);

						//if (sigList.signatureList.get(s.context_f.get(c).get(e)).interaction.getIndex()!=2){		// hypothesis to reduce the number of path
						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){
				
				short index_sig=(short)sigList.get(id).interaction.getIndex();
				
				for (int c=0;c<sigList.get(id).context_f.size();c++){
					if (sigList.get(id).context_f.get(c).nb_s>=2 && 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++){
							
							short index_next=(short)sigList.get(sigList.get(id).context_f.get(c).get(e)).interaction.getIndex();
							
							if (!(index_next==4 && index_sig==5) 
							 && !(index_next==5 && index_sig==4) /*&& index_sig!=2 && index_sig!=3*/){		// hypothesis to reduce the number of path

								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;
								//////////////////////////////////////////////////////////////////////////////
								
								
								
								// remove weights that belong to signature of associated primary interaction
								/*if (found1){
									int c1=0;
									int e1=0;
									System.out.println("+++++++++++++ "+(sig.index-InteractionList.nbDF)+" ; "+id);
									while (found1 && c1<sigList.get(sig.index).context_f.size()){
										while (found1 && e1<sigList.get(sig.index).context_f.get(c1).size()){
											if ((int)sigList.get(id).context_f.get(c).get(e)==(int)sigList.get(sig.index).context_f.get(c1).get(e1)){
												found1=false;
												System.out.println("##################### "+(sig.index-InteractionList.nbDF)+" ; "+id+" ; "+sigList.get(id).context_f.get(c).get(e));
												//sigList.get(id).context_f.get(c).context.remove(e);
											}
											e1++;
										}
										c1++;
									}
								}*/
								
								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>=2
						 && 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++){
	
								short index_next=(short)sigList.get(sigList.get(index_sig+InteractionList.nbDF).context_f.get(c).get(e)).interaction.getIndex();
								
								if (// index_sig!=2 &&
								   !(index_next==4 && index_sig==5) 
								&& !(index_next==5 && index_sig==4) /*&& index_sig!=2 && index_sig!=3*/){		// hypothesis to reduce the number of path
									
									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;
									//////////////////////////////////////////////////////////////////////////////
									
									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, int mem){
		
		for (int i=0;i<InteractionList.length;i++) objectMemory[mem][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>=2 && 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), mem,
											  sig.context_f.get(c).get(e)==pointList[0]);
							}
						}
					}
				}
			}
		}
	}
	
	private void projectObject(Byte[] path, Short[] pointList, short level, short id, int mem, 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>=2
						 && 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), mem,
												      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), mem,
											      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>=2
							 && 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), mem,
													      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), mem,
												      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>=1 && 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[mem][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, ArrayList<Signature> signatureList){
		pathList.clear();
		originList.clear();

		movableInstances.clear();
		instanceList.clear();
		instancesPosition.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[]>());
				
				instancesPosition.add(new ArrayList<Byte[]>());
				
				
				// 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), signatureList, (byte)-1);
					
					// add object instance in memory if recognized
					if (proj.getResult(new short[InteractionList.length])){
						instanceList.add(memory[i].pathList.get(p));
						instancesPosition.get(instancesPosition.size()-1).add(memory[i].pathList.get(p));
					}
					
					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));
					}
				}
			}
		}

		// remove redundant instances														(instances)
		// two instances 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++;
					}
					if (identical){
						instanceList.remove(p1);
						p1--;
					}
				}
			}
		}
	}
	
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// remove instances and proto-objects with invalid paths and detect movable objects
	public void validePaths(float[] input, ArrayList<Signature> signatureList){
		
		//////////////////////////////////////////////////////
		// 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 (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);
					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));
					}
				}
			}
		}
		
		// 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);
						if (i>j){
							i--;
							j--;
						}
						else j--;
					}
				}
			}
		}
		
		///////////////////////////////////////////////
		// get minimal path for each instance												(instances)
		for (short i=0;i<instancesPosition.size();i++){
			int lmin=Projection.LENGTH+1;
			// first, eliminate paths that are invalid and find minimum length
			for (int j=0;j<instancesPosition.get(i).size();j++){
				boolean found=false;
				int k=0;
				while (!found && k<instanceList.size()){
					
					if (instancesPosition.get(i).get(j).length==instanceList.get(k).length){
						found=true;
						int l=0;
						while (found && l<instanceList.get(k).length){
							if (instancesPosition.get(i).get(j)[l]!=instanceList.get(k)[l]) found=false;
							l++;
						}
					}
					k++;
				}
				if (!found){
					// invalid sequence
					instancesPosition.get(i).remove(j);
					j--;
				}
				else{
					if (instancesPosition.get(i).get(j).length<lmin) lmin=instancesPosition.get(i).get(j).length;
				}
			}
			
			// remove path that are not minimal
			for (int j=0;j<instancesPosition.get(i).size();j++){
				if (instancesPosition.get(i).get(j).length>lmin){
					instancesPosition.get(i).remove(j);
					j--;
				}
			}
			if (instancesPosition.size()==0){
				instancesPosition.remove(i);
				i--;
			}
		}
		
		// 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 (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),
							  1);
				
				// 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++){
						
					if (objectMemory[1][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));
						}
					}
				}
				
				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);
				i--;
			}
			// hypothesis to reduce number of instances
			else{
				l=0;
				while (!found && l<instanceList.get(i).length-2){
					if (instanceList.get(i)[l]==4 && instanceList.get(i)[l+1]==4 && instanceList.get(i)[l+2]==4 ||
					    instanceList.get(i)[l]==5 && instanceList.get(i)[l+1]==5 && instanceList.get(i)[l+2]==5) found=true;
					l++;
				}
				if (found){
					instanceList.remove(i);
					i--;
				}
			}
		}
	}
	
	public void detectConstructible(ArrayList<Signature> signatureList){
		
		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));		
				}
			}
		}
		
		hypothesisMemory.checkValidity();
		hypothesisMemory.removeRedundant();
	}
	
	
	public void detectConstructible2(ArrayList<Signature> signatureList){
		
		ArrayList<Byte> interList=new ArrayList<Byte>();
		ArrayList<ArrayList<Byte[]>> constructibleList=new ArrayList<ArrayList<Byte[]>>();
		ArrayList<ArrayList<Short>> constructibleOrigin=new ArrayList<ArrayList<Short>>();
		
		for (int p=0;p<pathList.size();p++){
			for (int p1=0;p1<pathList.get(p).size();p1++){
				Hypothesis hypothesis=hypothesisMemory.getContructible(pathList.get(p).get(p1)[0],originList.get(p).get(p1));
				
				if (hypothesis==null){
					pathList.get(p).remove(p1);
					originList.get(p).remove(p1);
					p1--;
				}
				else{
					System.out.println("--------------------------------------");
					System.out.print("proto-object : ");
					for (int i=pathList.get(p).get(p1).length-1;i>=0;i--){
						System.out.print(pathList.get(p).get(p1)[i]+", ");
					}
					System.out.println(" requires :");
					hypothesis.print();
					
					boolean complete=true;
					for (int m=0;m<hypothesis.inter.size();m++){
						if (sigList.workMemory[hypothesis.inter.get(m)].instanceList.size()>0){
							//System.out.println("element "+hypothesis.inter.get(m)+" found at "+sigList.workMemory[hypothesis.inter.get(m)].instanceList.size()+" positions");
						}
						else{
							//System.out.print("element "+m+" cannot be found");
							complete=false;
						}
					}
					if (!complete){
						//System.out.println("cannot be constructed");
						pathList.get(p).remove(p1);
						originList.get(p).remove(p1);
						p1--;
					}
					else{
						//System.out.println("can be constructed");
						
						for (int m=0;m<hypothesis.inter.size();m++){
							boolean found=false;
							int n=0;
							while (!found && n<interList.size()){
								if (interList.get(n)==hypothesis.inter.get(m)) found=true;
								else n++;
							}
							
							///////////////////////////////////////////////////
							// simplification
							boolean found2=pathList.get(p).get(p1).length<Projection.LENGTH;
							int a=1;
							while (found2 && a<pathList.get(p).get(p1).length){
								if (pathList.get(p).get(p1)[a]==1 || pathList.get(p).get(p1)[a]==2 || pathList.get(p).get(p1)[a]==3) found2=false;
								a++;
							}
							
							if (found2){
							if (!found){
								interList.add(hypothesis.inter.get(m));
								constructibleOrigin.add(new ArrayList<Short>());
								constructibleOrigin.get(constructibleOrigin.size()-1).add(originList.get(p).get(p1)[originList.get(p).get(p1).length-1]);
								constructibleList.add(new ArrayList<Byte[]>());
								constructibleList.get(constructibleList.size()-1).add(pathList.get(p).get(p1));
							}
							else{
								constructibleOrigin.get(n).add(originList.get(p).get(p1)[originList.get(p).get(p1).length-1]);
								constructibleList.get(n).add(pathList.get(p).get(p1));
							}
							}
						}
					}
				}
			}
		}
		
		/*System.out.println("final list of constructibles :");
		for (int i=0;i<constructibleOrigin.size();i++){
			System.out.println("--- "+interList.get(i)+" -> ");
			for (int c=0;c<constructibleOrigin.get(i).size();c++){
				System.out.print("    "+constructibleOrigin.get(i).get(c)+" ; ");
				for (int l=0;l<constructibleList.get(i).get(c).length;l++){
					System.out.print(constructibleList.get(i).get(c)[l]+", ");
				}
				System.out.println();
			}
		}
		System.out.println();*/
		
		// compute movements effects
		for (int i=0;i<interList.size();i++){
			for (int inst=0;inst<sigList.workMemory[interList.get(i)].instanceList.size();inst++){
				
				// change reference
				changeReference(sigList.workMemory[interList.get(i)].instanceList.get(inst), (short)0);
				
				for (int c=0;c<constructibleOrigin.get(i).size();c++){
					//System.out.print("#### "+reference[0][constructibleOrigin.get(i).get(c)].originList.size()+" ; ");
					//for (int k=0;k<reference[0][constructibleOrigin.get(i).get(c)].originList.size();k++){
					//	System.out.print(memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].min_length+", ");
					//}
					//System.out.println();
					
					// get the minimum distance
					short dist=Projection.LENGTH;
					for (int k=0;k<reference[0][constructibleOrigin.get(i).get(c)].originList.size();k++){
						if (memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].min_length<dist)
							dist=memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].min_length;
					}
					
					// find a path that begin with the interaction interList.get(i)
					boolean found=false;
					int k=0;
					while (!found && k<reference[0][constructibleOrigin.get(i).get(c)].originList.size()){
						
						if (memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].min_length==dist){
							
							int k2=0;
							while (!found && k2<memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].size()){
								
								if (memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].pathList.get(k2).length==dist &&
									memory[reference[0][constructibleOrigin.get(i).get(c)].originList.get(k)].pathList.get(k2)[0]==interList.get(i)){
									found=true;
								}
								k2++;
							}	
						}
						k++;
					}
					
					
					// get result
					/*if (found){
						System.out.print(" d- : instance {");
						for (int l=sigList.workMemory[interList.get(i)].instanceList.get(inst).length-1;l>=0;l--){
							System.out.print(sigList.workMemory[interList.get(i)].instanceList.get(inst)[l]+",");
						}
						System.out.print("}["+interList.get(i)+">  ->  dist -1 of ");
						
						for (int l=constructibleList.get(i).get(c).length-1;l>=0;l--){
							System.out.print(constructibleList.get(i).get(c)[l]+",");
						}
						System.out.println();
					}
					else{
						System.out.print(" d+ : instance {");
						for (int l=sigList.workMemory[interList.get(i)].instanceList.get(inst).length-1;l>=0;l--){
							System.out.print(sigList.workMemory[interList.get(i)].instanceList.get(inst)[l]+",");
						}
						System.out.print("}["+interList.get(i)+">  ->  dist +1 of ");
						
						for (int l=constructibleList.get(i).get(c).length-1;l>=0;l--){
							System.out.print(constructibleList.get(i).get(c)[l]+",");
						}
						System.out.println();
					}*/
					
				}
			}
		}
	}
	
	
	
	
	
	public void changeReference(Byte[] path1, short mem){
		for (short i=0;i<InteractionList.nbDF;i++){
			reference[mem][i].reset();
		}
		
		for (int l=0;l<path1.length;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, short 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 cleanMemory(int id){
		for (int i=0;i<memory.length;i++){
			System.out.println(" +++ "+id+" : "+i);
			// 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==0){
								memory[i].pathList.remove(p2);
								memory[i].originList.remove(p2);
								
								System.out.print(" +++ ");
								for (int n=memory[i].originList.get(p1).length-1;n>=0;n--) System.out.print(memory[i].originList.get(p1)[n]+", ");
								System.out.print(" eliminates : ");
								for (int n=memory[i].originList.get(p2).length-1;n>=0;n--) System.out.print(memory[i].originList.get(p2)[n]+", ");
								System.out.println();
								
								if (p1>p2){
									p1--;
									p2--;
								}
								else p2--;
							}
						}
					}
				}
			}
			
		
		}
	}
	
	/*public void removeInvalid(int id, SignatureList sigList){
		
		for (int i=0;i<memory.length;i++){
			
			for (int p=0;p<memory[i].pathList.size();p++){
				
				int length1=memory[i].pathList.get(p).length;
				
				if (length1<Projection.LENGTH){
					
					for (int m=0;m<4;m++){
						if (m!=id){
							
							for (int p2=0;p2<sigList.workMemory[m].memory[i].pathList.size();p2++){
								
								int diff=sigList.workMemory[m].memory[i].pathList.get(p2).length-length1;
								
								if (memory[i].pathList.get(p).length<sigList.workMemory[m].memory[i].pathList.get(p2).length
								 && sigList.workMemory[m].memory[i].pathList.get(p2)[diff-1]==id){
									
									boolean found=true;
									int l=memory[i].originList.get(p).length-1;
									while (found && l>=0){
										if (!memory[i].originList.get(p)[l].equals(sigList.workMemory[m].memory[i].originList.get(p2)[l+diff])) found=false;
										l--;
									}
									
									if (found){
										System.out.print("##################### "+id+" -> ");
										for (int i1=memory[i].pathList.get(p).length-1;i1>=0;i1--) System.out.print(memory[i].pathList.get(p)[i1]+", ");
										System.out.print(" eliminates : "+m+" -> ");
										for (int i1=sigList.workMemory[m].memory[i].pathList.get(p2).length-1;i1>=0;i1--) System.out.print(sigList.workMemory[m].memory[i].pathList.get(p2)[i1]+", ");
										System.out.println();
										sigList.workMemory[m].memory[i].pathList.remove(p2);
										sigList.workMemory[m].memory[i].originList.remove(p2);
										p2--;
									}
								}
							}
							
						}
					}
					
				}
			}
			
		}
	}*/
	
	
	//////////////////////////////////////////////////////////////////////////////
	// return true if the two paths are equivalent
	/*private boolean equivalence(Short[] i1, Short[] i2, ArrayList<Signature> signatureList){
		
		if (i1[0]==i2[0]) return true;		// case where the two elements are the same
		
		boolean found=true;
		int e=0;
		for (short c=0;c<signatureList.get(i2[0]).context_f.size();c++){
			e=0;
			while (found && e<signatureList.get(i2[0]).context_f.get(c).size()){
				if (signatureList.get(i2[0]).context_f.get(c).get(e)==i1[0]) found=false;
				e++;
			}
		}/**/
		
		/*if (found){
			int i=0;
			int j=0;
			
			while (i<i1.length && j<i2.length){
				if (i1[i].equals(i2[j])){
					i++;
					j++;
				}
				else{
					j++;
				}
			}
			
			if (i!=i1.length) found=false;
		}/**/

		/*return found;
		
	}*/

}
