/*
 *  Copyright (C) 2009  E.Albert, P.Arenas, S.Genaim, G.Puebla, and D.Zanardini
 *                      https://costa.ls.fi.upm.es
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package pubs;
/**
 * A class with a method del used as running example in the SAS'08 paper.
 * 
 * @author E.Albert, P.Arenas, S.Genaim, and G.Puebla
 *
 */
class Delete{

	/**
	 * 
	 * @param l list from which we will remove elements
	 * @param p pivot
	 * @param a array with elements to remove from l which are smaller than p
	 * @param la length of a
	 * @param b array with elements to remove from l which are greater or equal to p
	 * @param lb length of b
	 * 
	 * All elements in a and in b are also in l.
	 */
	static void del(List l, int p, int a[], int la, int b[], int lb){
		while (l!=null){
			if (l.data < p) {
				la=rm_vec(l.data,a,la);
				//la=la-1;

			}
			else  {
				lb=rm_vec(l.data,b,lb);
				//lb=lb-1;

			}
			l=l.next;
		}
	}


	static int rm_vec(int e, int a[], int la){
		int i=0;
		while (i < la && a[i]<e) {i++;};
		// if (i<=la){
		for (int j=i; j<la-1; j++) a[j]=a[j+1];
		return la-1;
		//}
		//else return la;
	}
}

/*
split[l,p,a,la,b,lb] ==   1 +  loop1[l,la,lb],

   size: l>=0,la>=0,lb>=0


loop1[l,la,lb] ==   2,

   size: l=0

loop1[l,la,lb] ==   23 +  loop2[lb,0] + loop1[l',la,lb'],

   size: lb>= -1 , lb-1 <= lb' <= lb , l-l'>=1 , l'>=0

loop1[l,la,lb] ==   27 +  loop3[lb,j] + loop2[lb,0] + loop1[l',la,lb'],

   size: lb >= j ,  j>=0   , lb-1 <= lb' <= lb , l-l'>=1 , l'>=0

loop1[l,la,lb] ==   24 +  loop2[la,0] + loop1[l',la',lb],

   size: la>= -1 , la-1 <= la' <= la  , l-l'>=1 , l'>=0

loop1[l,la,lb] ==   28 +  loop3[la,j] + loop2[la,0] + loop1[l',la',lb],

   size: la-1 <= la' <= la , la >=j , j>=0  , l-l'>=1 , l'>=0


-------------------------------------------------
loop2[la,i] ==   3,
    size: i>=la , i>=0 ,

loop2[la,i] ==   8,
    size: i<la , i>=0 ,

loop2[la,i] ==   10 + loop2[la,i'],

    size: i < la , i>=0 , i'= i+1

--------------------------------------------------
loop3[la,j] ==   5,

    size: j>= la-1 , j>=0

loop3[la,j] ==   15 + m2[la,j'],

    size: j < la-1, j>=0 , j'=j+1

 */