/*
* 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
*/