Una forma eficiente de hacerlo, que toma tiempo lineal sería la siguiente:
Nombremos m
como la longitud de los elementos en mCalendar
y n
como la longitud de los elementos en dates
(adentro de fillFeriaeAdventus
).
Hacer una copia de mCalendar
, pero guardar los valores en un HashMap para permitir búsqueda O(1)
, antes de empezar a agregar elementos a mCalendar
. Esto toma tiempo O(m)
De la lista dates
agregar a mCalendar
los elementos que no se encuentren en el HashMap. Gracias a que es un HashMap, esto toma tiempo O(n)
.
De esta forma aseguramos que a mCalendar
ingresen objetos que no sean duplicados, o que no existieran ya previamente en el arreglo.
La implementación sería la siguiente:
class Main {
public static ArrayList<LocalDate> mCalendar = new ArrayList<>();
private static void fillFeriaeAdventus() {
LocalDate start = LocalDate.of(2021, 11, 28);
LocalDate end = LocalDate.of(2021, 12, 24);
List<LocalDate> dates = Stream.iterate(start, date -> date.plusDays(1))
.limit(ChronoUnit.DAYS.between(start, end))
.collect(Collectors.toList());
// copiamos las fechas ya existentes en mCalendar en un hashmap para permitir busqueda O(1)
HashMap<LocalDate, Boolean> datesMap = new HashMap<>();
mCalendar.forEach(date -> {datesMap.put(date, true);}); // O(m)
// del hashmap realmente solo nos importa la llave, el valor no lo usamos
// agregamos más fechas
// vamos a agregar las que están en dates
// pero que no estén ya previamente en mCalendar
mCalendar.addAll(
dates.stream()
.filter(Predicate.not(datesMap::containsKey)) // la busqueda se hace en O(1)
.collect(Collectors.toList())
); // O(n)
// La otra opción es hacerlo con un for
/*for (LocalDate date : dates)
if (!datesMap.containsKey(date))
mCalendar.add(date);*/
System.out.println("mCalendar.size(): " + mCalendar.size());
mCalendar.forEach(System.out::println);
}
public static void main(String... args) {
System.out.println("Primera invocación: Debería agregar elementos al arreglo");
fillFeriaeAdventus();
System.out.println("Segunda invocación: NO debería agregar elementos al arreglo pues serían duplicados");
fillFeriaeAdventus();
}
}
Si lo ejecutas verás que en efecto, la segunda invocación no agregó elementos duplicados.
Ahora, la desventaja de esto es que se debe ocupar más memoria, prácticamente el doble de memoria que se ocupa realmente para mCalendar
.
Se podría modificar el algoritmo para que no ocupara tanta memoria pero entonces tomaría tiempo O(m log(m))
pues se requeriría el arreglo ordenado para realizar búsqueda binaria.
Nota final sobre el hashcode de la clase LocalDate
:
El código de openjdk es el siguiente:
@Override
public int hashCode() {
int yearValue = year;
int monthValue = month;
int dayValue = day;
return (yearValue & 0xFFFFF800) ^ ((yearValue << 11) + (monthValue << 6) + (dayValue));
}
En ese caso sería seguro utilizar el algoritmo pues se tomarían dos objetos LocalDate
iguales si sus fechas son iguales.
No sé cómo sea el hashcode en otras implementaciones pero supongo que se mantiene esa condición de que dos objetos LocalDate
son iguales si sus fechas son iguales.
Espero que esto te sirva, saludos.
Edit 1
Aquí está el cambio en la solución inicial tomando en cuenta que se deben guardar en mCalendar
objetos de tipo Celebration
.
class Main {
public static ArrayList<Celebration> mCalendar = new ArrayList<>();
private static void fillFeriaeAdventus() {
LocalDate start = LocalDate.of(2021, 11, 28);
LocalDate end = LocalDate.of(2021, 12, 24);
List<LocalDate> dates = Stream.iterate(start, date -> date.plusDays(1))
.limit(ChronoUnit.DAYS.between(start, end))
.collect(Collectors.toList());
// copiamos las fechas ya existentes en mCalendar en un hashmap para permitir busqueda O(1)
HashMap<LocalDate, Boolean> datesMap = new HashMap<>();
mCalendar.forEach(date -> {datesMap.put(date.getDate(), true);}); // O(n)
// agregamos más fechas
// vamos a agregar las que están en dates
// pero que no estén ya previamente en mCalendar
/*AtomicInteger n = new AtomicInteger(0);
mCalendar.addAll(
dates.stream()
.filter(Predicate.not(datesMap::containsKey)) // la busqueda se hace en O(1)
.map(date -> new Celebration(n.getAndIncrement(), date)) // convertimos o mapeamos los objetos LocalDate a Celebration
.collect(Collectors.toList())
); // O(n)*/
// La otra opción es hacerlo con un for
for (int i = 0; i < dates.size(); ++i)
if (!datesMap.containsKey(dates.get(i)))
mCalendar.add(new Celebration(i, dates.get(i)));
System.out.println("mCalendar.size(): " + mCalendar.size());
mCalendar.forEach(System.out::println);
}
public static void main(String... args) {
System.out.println("Primera invocación: Debería agregar elementos al arreglo");
fillFeriaeAdventus();
System.out.println("Segunda invocación: NO debería agregar elementos al arreglo pues serían duplicados");
fillFeriaeAdventus();
}
private static class Celebration {
private int idx;
private LocalDate localDate;
public Celebration(int idx, LocalDate localDate) {
this.idx = idx;
this.localDate = localDate;
}
public LocalDate getDate() {
return this.localDate;
}
@Override
public String toString() {
return this.localDate.toString();
}
}
}
En este caso no hay mucho cambio salvo por el .map()
para crear los objetos Celebration
. Sin embargo, dado que uno de los fundamentos de la programación funcional es que no debe haber modificaciones de estado (como con el iterador n
), decidí comentar esa solución para preferir la normal con un for
. Además, quizá tenga mejor performance (pero no estoy seguro).