Jak binarne wyszukiwania w jednej dziedzinie elementów listę za

Question

Niech C być zdefiniowana klasa (częściowo) przez

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; 
    } 
} 

i niech cs być List<C> realizacji RandomAccess i klasyfikowane na C.getX().

Jakie jest standardowe podejście do wykonywania wyszukiwania binarnego w cs dla x1 na C.getX()? (Innymi słowy, udając, że każdy element c zastępuje c.getX() a następnie szukamy x1 wśród tych liczb.)

---

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

ma tę wadę, że wymaga budowy nowej C (co może wymagać wiele fałszywych argumentów i wiedzy o C).

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

ma tę wadę, że tworzy całą nową listę i jest prawdopodobnie O (n).

---

Czy istnieje możliwość bezpośredniego wyszukiwania w strumieniu, bez jego pobierania? A może w jakiś inny sposób przeszukać oryginalną listę bez konieczności konstruowania fikcyjnego przedmiotu?

---

Z braku lepszego podejścia, chciałbym to zrobić:

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(); 
    }  
} 

a następnie

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

Answer 1

Innym rozwiązaniem mogłoby być tak:

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 , jeśli nie masz nic przeciwko zależności, możesz to zrobić z Guava:

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

Answer 2

Ponieważ jesteś w kontroli realizacji Comparator, można zaimplementować symetryczną funkcję porównawczą, która pozwala porównać wystąpień C z wartości żądanej własności, czyli wartości int (zawinięte jako Integer) w przypadku twojej własności x. Pomaga poznać metody fabrycznych comparing… w Comparator interface które Cię uchronić od powtarzania kodu dla obu stron stosunku:

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

ten sposób można wyszukać wartości x1int bez owijania go w instancji C.