Eu tenho 2 “conjuntos” de elementos, neo e old, que tem elementos do tipo T, todos não nulos. Além disso, eu sei que esses elementos são identificados por uma chave K e eu posso extrair usando essa chave usando uma Function<T, K> getKey. Garanto a unicidade da chave dentro de neo e dentro de old (isto é, não existem 2 elementos de neo com a mesma chave, nem 2 elementos distintos de old com a mesma chave).
Além disso, eu garanto que os elementos em neo e old estão ordenados de modo estritamente decrescente nessa chave considerando um Comparator<K> keyComparator. Informalmente, como se neo(i).key < neo(j).key para todo i < j, e semelhantemente old(i).key < old(j).key.
Eu defino que um elemento oldEl foi removido se old.contains(oldEl) e se não existir nenhum neoEl pertencente a neo tal que getkey.apply(oldEl).equals(getkey.apply(neoEl)).
Eu defino uma modificação neoEl se neo.contains(neoEl) e se existir algum oldEl pertencente a old tal que getkey.apply(oldEl).equals(getkey.apply(neoEl)), porém !oldEl.equals(neoEl) (se por acaso oldEl.equals(neoEl), devo considerar que o elemento aparece repetidamente).
Eu defino uma criação do elemento neoEl se neo.contains(neoEl) e se não existir nenhum oldEl pertencente a old tal que getkey.apply(oldEl).equals(getkey.apply(neoEl)).
Até o momento, consegui fazer o seguinte:
final Consumer<T> NOOP = __ -> {};
public void doDelta(Iterator<T> old, Iterator<T> neo,
Function<T, K> getkey, Comparator<K> keyComparator,
Consumer<T> insertInterceptor,
Consumer<T> updateInterceptor,
Consumer<T> deleteInterceptor,
Consumer<T> ignoreInterceptor) {
final int TAKE_OLD = 1;
final int TAKE_NEO = 2;
final int TAKE_BOTH = TAKE_OLD | TAKE_NEO;
int nextAction = TAKE_BOTH;
T oldT = null, neoT = null;
K oldK = null, neoK = null;
if (!old.hasNext()) {
// não há old, portanto só tem inserção
if (insertInterceptor != NOOP) {
neo.forEachRemaining(insertInterceptor);
}
return;
}
if (!neo.hasNext()) {
// não há neo, portanto só tem remoção
if (deleteInterceptor != NOOP) {
old.forEachRemaining(deleteInterceptor);
}
return;
}
while (true) {
if (nextAction == TAKE_BOTH) {
if (!old.hasNext()) {
if (!neo.hasNext()) {
return;
}
neoT = neo.next();
nextAction = TAKE_NEO;
break;
}
oldT = old.next();
oldK = getkey.apply(oldT);
if (!neo.hasNext()) {
nextAction = TAKE_OLD;
break;
}
neoT = neo.next();
neoK = getkey.apply(neoT);
} else if (nextAction == TAKE_OLD) {
if (!old.hasNext()) {
nextAction = TAKE_NEO;
break;
}
oldT = old.next();
oldK = getkey.apply(oldT);
} else { //if (nextAction == TAKE_NEO) {
if (!neo.hasNext()) {
nextAction = TAKE_OLD;
break;
}
neoT = neo.next();
neoK = getkey.apply(neoT);
}
int cmp = keyComparator.compare(oldK, neoK);
if (cmp == 0) {
nextAction = TAKE_BOTH;
if (oldT.equals(neoT)) {
ignoreInterceptor.accept(neoT);
} else {
updateInterceptor.accept(neoT);
}
} else if (cmp < 0) {
deleteInterceptor.accept(oldT);
nextAction = TAKE_OLD;
} else {
insertInterceptor.accept(neoT);
nextAction = TAKE_NEO;
}
}
// entrou aqui porque acabou o old
if (nextAction == TAKE_NEO) {
if (insertInterceptor != NOOP) {
insertInterceptor.accept(neoT);
neo.forEachRemaining(insertInterceptor);
}
return;
}
if (nextAction == TAKE_OLD) {
if (deleteInterceptor != NOOP) {
deleteInterceptor.accept(oldT);
old.forEachRemaining(deleteInterceptor);
}
}
}
A ideia é basicamente, a cada ciclo, saber se preciso puxar elemento do conjunto neo, do old ou de ambos; no começo precisa pegar elementos de ambos os conjuntos. Depois, o que pode acontecer enquanto houver elementos dos dois lados:
- se a chave for a mesma, pegar de ambos e testar para ver se foi atualização ou o elemento se manteve idêntico
- se a chave menor for do
old, então esse elemento foi removido do novo conjunto de elementos e preciso pegar apenas do old
- se a chave menor for do
neo, então esse elemento foi criado no novo conjunto de elemento e preciso pegar apenas do neo
neo e old são definidos como Iterator<T> para não precisar carregar a priori toda a informação desses conjuntos na memória, mas outra alternativa lazy loading é válida também.
Os Consumer<T> fazem o trabalho de interceptar caso seja descoberto se o elemento é adicionado/removido/atualizado da lista (o ignoreInterceptor é usado mais como curiosidade caso um elemento se repita igual nos dois conjuntos).
O NOOP é o interceptador trivial, descarta silenciosamente caso receba algo.
Note que não há uso de memória extra nesse algoritmo, considerando que os Consumers, getkey, keyComparator e os equals das classes envolvidas sejam funções oráculo.
Também levando em consideração que Consumers, getkey, keyComparator e os equals das classes envolvidas sejam funções oráculo, farei no máximo O(|old| + |neo|) operações ao todo, portanto sigo que a complexidade temporal é linear no tamanho dos conjuntos.
O que me incomoda aqui são os casos quando se esgota uma das coleções, ou quando recebo uma coleção vazia. Parece que está muito convoluto e bagunçado o código. Como deixar mais limpo o código?
Teria como usar Stream para o fim que estou usando o Iterator? Isso poderia deixar mais limpo o código?
E Spliterator, teria alguma vantagem nele além de me garantir as características (comparador fornecido pelo próprio Spliterator, ordenado, distinto, não nulo)?
