Come binario di ricerca su un campo di un elenco elementi

Question

Sia C essere una classe definita (in parte) in

private static class C { 
    private final int x; 
    // lots more fields be here 

    public C(int x, /* lots more arguments here */) { 
     this.x = x; 
     // lots more fields initialized here 
    } 

    public int getX(){ 
     return x; 
    } 
} 

e lasciare cs essere un List<C> attuazione RandomAccess, e ordinati su C.getX().

Quale sarebbe l'approccio standard per eseguire una ricerca binaria in cs per x1 su C.getX()? (In altre parole, facendo finta che ciascun elemento c è sostituito da c.getX() e poi cercare x1 tra i numeri interi.)

---

Collections.binarySearch(
    cs, 
    new C(x1,/* dummy arguments */), 
    (a,b) -> Integer.compare(a.getX(),b.getX()) 
); 

ha l'inconveniente di richiedere la costruzione di un nuovo C (che può richiedere molti argomenti fittizi e conoscenze su C).

Collections.binarySearch(
    cs.stream().map(C::getX).collect(Collectors.toList()), 
    x1 
); 

ha lo svantaggio di creare un'intera nuova lista ed è presumibilmente O (n).

---

C'è un modo per cercare nello stream direttamente, senza raccoglierlo? O forse un altro modo per cercare l'elenco originale senza dover costruire un oggetto fittizio?

---

In assenza di un approccio migliore, vorrei fare questo:

public class MappedView<T,E> extends AbstractList<E> { 

    public static <T,E> MappedView<T,E> of(List<T> backingList, Function<T,E> f){ 
     return new MappedView<>(backingList, f); 
    } 

    private final List<T> backingList; 
    private final Function<T,E> f; 

    private MappedView(List<T> backingList, Function<T,E> f){ 
     this.f = f; 
     this.backingList = backingList; 
    } 

    @Override 
    public E get(int i) { 
     return f.apply(backingList.get(i)); 
    } 

    @Override 
    public int size() { 
     return backingList.size(); 
    }  
} 

e poi

Collections.binarySearch(
    MappedView.of(cs, c -> c.getX()), 
    x1 
); 

Answer 1

Un altro approccio potrebbe essere questo:

private static class C { 
    private final int x; 
    // lots more fields be here 

    private C() { 
    } 

    public C(int x, /* lots more arguments here */) { 
     this.x = x; 
     // lots more fields initialized here 
    } 

    public int getX(){ 
     return x; 
    } 

    public static C viewForX(int x) { 
     C viewInstance = new C(); 
     viewInstance.x = x; 
     return viewInstance; 
    } 
} 

Collections.binarySearch(cs, 
    C.viewForX(x1), 
    (a,b) -> Integer.compare(a.getX(),b.getX())); 

Or , se non ti dispiace una dipendenza, puoi farlo con Guava:

List<Integer> xs = Lists.transform(cs, C::getX()); 
Collections.binarySearch(xs, x1); 

Answer 2

Poiché siete nel controllo della Comparator attuazione, è possibile implementare una funzione simmetrica confronto che permette di confrontare istanze di C con valori della struttura desiderata, cioè int valori (avvolto come Integer) in caso di proprietà x. Aiuta a conoscere i metodi di fabbrica comparing… nel Comparator interface cui si salva di ripetere il codice per entrambi i lati del confronto:

int index = Collections.binarySearch(cs, x1, 
    Comparator.comparingInt(o -> o instanceof C? ((C)o).getX(): (Integer)o)); 

In questo modo è possibile cercare il valore x1int senza avvolgendolo in un'istanza C.