IntervalTree DeleteNode Implementazione Java

Question

Ho bisogno di un'implementazione IntervalTree o RangeTree in Java e sto avendo problemi a trovarne uno con il supporto per l'eliminazione.

C'è un built-in uno a sun.jvm.hotspot.utilities.IntervalTree, ma il metodo deleteNode negli stati superclasse RBTree:

/** 
* FIXME: this does not work properly yet for augmented red-black 
* trees since it doesn't update nodes. Need to figure out exactly 
* from which points we need to propagate updates upwards. 
*/ 

Cercando di eliminare i nodi da un albero finisce per gettare l'eccezione:

Nodo l'endpoint massimo non è stato aggiornato correttamente

Quanto sarebbe difficile pr implementare operativamente la funzionalità delete in una sottoclasse di sun.jvm.hotspot.utilities.IntervalTree? O c'è un'altra implementazione di Interval Tree che già implementa correttamente questo?

Attualmente sto cancellando l'albero e lo ricompongo ogni volta che c'è una cancellazione, che è tutt'altro che ideale (nota: l'impostazione DEBUGGING = false nel RBTree ha accelerato enormemente le cose).

Answer 1

Ho finito con la modifica dello sun.jvm.hotspot.utilities.IntervalTree per mantenere un Set di nodi cancellati. Quando faccio una ricerca, escludo qualsiasi articolo in questo set. Non ideale, ma questo è stato molto più facile che ottenere la cancellazione "reale" lavorando. Una volta che il set eliminato diventa troppo grande, ricostruisco l'albero.

Answer 2

This project ha un'implementazione RangeTree che potrebbe essere più utile per l'utente. I pacchetti solari potrebbero essere ok per l'uso rapido e sporco, ma non consiglierei di costruire qualcosa di importante contando su di essi. Il sole potrebbe non mantenerli stabili.

Answer 3

Non conosco i tuoi requisiti esatti ma un segmento di segmenti non statici potrebbe funzionare per te. Se sì, dai uno sguardo allo Layout Management SW, in particolare allo SegmentTree package. Ha la funzione di rimozione di cui hai bisogno.

Se si decide di eseguire il rollover, è possibile suggerire di aprirlo? Sono sorpreso che non sia già disponibile un Interval Tree semplice e aperto.

Answer 4

c'è un'implementazione C# basata su un albero AVL aumentato @http://code.google.com/p/intervaltree/. la traduzione in java non dovrebbe essere troppo difficile.

Answer 5

Ho trovato un'implementazione open source con eliminazione, ma ci vuole qualche sforzo per renderlo pienamente funzionante.

È un modulo di progetto open-source più grande Gephi, ma qui ci sono sources e javadoc. Se si desidera un barattolo è possibile installare il Gephi, ed è in:

/gephi/modules/org-gephi-data-attributes-api.jar 

Il metodo delete lì, rimuove tutti gli intervalli di sovrapposizione con l'intervallo di input (invece del solo un ingresso). Tuttavia ho trovato nei soruce che esistono metodi privati ​​che rimuovono un nodo specifico (che memorizza un intervallo). Anche i metodi di ricerca privati ​​restituiscono i nodi.

Quindi penso che con un piccolo sforzo è possibile rifattorizzare il codice e avere questa funzione 'Cancella intervallo specifico'. Il modo più veloce e più sporco sarebbe semplicemente rendere pubblici i metodi privati ​​/ la classe Node. Ma dal momento che si tratta di un progetto open source, forse potrebbe evolvere in futuro in una buona implementazione standard dell'albero degli intervalli.