¿Hay una versión Scala de NavigableMap?

En Java 1.6, se introdujeron las interfaces NavigableMap (y NavigableSet) y se actualizó TreeMap para implementar la nueva interfaz. Entre otras cosas, NavigableMap es útil para hacer preguntas como "¿Qué elemento de la colección está más cerca de X?" (Ver this excellent blog post by François Sarradin para un ejemplo y discusión).¿Hay una versión Scala de NavigableMap?

Esperaba encontrar algo similar en la implementación TreeMap de Scala 2.8 , pero, por desgracia, no parece ser así (al menos, no es obvio). ¿Hay otra clase o rasgo de Scala que sea similar a NavigableMap de Java? De lo contrario, hay algunos modismos de Scala simples que se pueden usar para lograr algo similar?

Soy consciente de que puedo utilizar TreeMap de Java, pero me gustaría mantenerse dentro del marco de las colecciones Scala (aunque sólo sea por razones de simplicidad).

Fuente

2011-08-29 Jim Hurne

En las colecciones inmutables, tener las referencias posteriores hace que sea imposible hacer la colección persistente. Entonces, en cambio, las personas usan zippers para navegar a través de tales estructuras. tiene un buen ejemplo del uso de cremalleras cuando se trabaja con XML.

Fuente

2011-08-29 19:37:29

Está bastante claro cómo una cremallera podría ayudar a modificar (copiar) el árbol, pero no está tan claro cómo se usaría una cremallera para responder preguntas como "¿Qué elemento de la colección está más cerca de X?". Sé que estamos hablando principalmente de teoría aquí (ya que las cremalleras parecen ser principalmente experimentales), pero ¿puedes describir cómo una cremallera podría responder a la pregunta mencionada anteriormente? –

@Jim Cremalleras no son experimentales en absoluto. Las cremalleras tienen dos tipos de operación: inspeccionar/actualizar y navegar. Por lo tanto, si tiene una cremallera en X, sus operaciones de navegación naturalmente le darán los elementos más cercanos. –

¡Ah, ya veo! Gracias. La pregunta a la que se vinculó sobre las cremalleras es lo que me dio la impresión de que las cremalleras eran experimentales. Me alegra saber que están disponibles. –

Here's a thread on this topic

Parece SortedMap podría ser capaz de conseguir que parte del camino, pero lo que he probado hasta ahora no estoy seguro si es O (log (n)) de la manera una búsqueda debe BE:

def searchMap(m: SortedMap[Int,_], k: Int) = { 
    val left = m to(k) lastKey 
    val right = m from(k) take(2) lastKey 

    if (k - left < right - k) 
     left 
    else 
     right 
}

basado en las definiciones de from y to en términos de rangeImpl parece que este podría ser O (log (n)), pero basado en realidad de temporización que, parece crecer linealmente para todos plausibles valores de n.

Así que no estoy seguro.

Fuente

2011-08-29 01:37:26 Owen

Por qué no, pero las funciones hacia y desde están creando dos nuevos mapas, que pueden no ser deseables. –

¿Hay una versión Scala de NavigableMap?

Respuesta

Cuestiones relacionadas