einen Komparator für eine Verbindung Objekt für binäre Such Schreiben

Question

ich eine Klasse haben, und die Liste der Instanzen, die (die Unschuldigen/proprietäre zu schützen geändert Feldnamen) etwa wie folgt aussieht:

public class Bloat 
{ 
    public long timeInMilliseconds; 
    public long spaceInBytes; 
    public long costInPennies; 
} 

public class BloatProducer 
{ 
    final private List<Bloat> bloatList = new ArrayList<Bloat>(); 
    final private Random random = new Random(); 
    public void produceMoreBloat() 
    { 
     int n = bloatList.size(); 
     Bloat previousBloat = (n == 0) ? new Bloat() : bloatList.get(n-1); 
     Bloat newBloat = new Bloat(); 
     newBloat.timeInMilliseconds = 
      previousBloat.timeInMilliseconds + random.nextInt(10) + 1; 
     newBloat.spaceInBytes = 
      previousBloat.spaceInBytes + random.nextInt(10) + 1; 
     newBloat.costInPennies = 
      previousBloat.costInPennies + random.nextInt(10) + 1; 
     bloatList.add(newBloat); 
    } 
    /* other fields/methods */ 

    public boolean testMonotonicity() 
    { 
    Bloat previousBloat = null; 
    for (Bloat thisBloat : bloatList) 
      { 
       if (previousBloat != null) 
       { 
        if ((previousBloat.timeInMilliseconds 
        >= thisBloat.timeInMilliseconds) 
        || (previousBloat.spaceInBytes 
        >= thisBloat.spaceInBytes) 
        || (previousBloat.costInPennies 
        >= thisBloat.costInPennies)) 
         return false; 
       } 
       previousBloat = thisBloat; 
      } 
      return true; 
    } 

BloatProducer bloatProducer; 

Die Liste bloatList wird intern von BloatProducer gehalten und wird so verwaltet, dass es nur neue Bloat Datensätze anfügt, keine der alten ändert und jedes der Felder monoton ansteigt, z bloatProducer.testMonotonicity() würde immer true zurückgeben.

Ich möchte Collections.binarySearch(list,key,comparator) verwenden, um nach dem Bloat Datensatz entweder in den Feldern timeInMilliseconds, spaceInBytes oder costInPennies zu suchen. (und wenn die Zahl zwischen zwei Datensätzen liegt, möchte ich den vorherigen Datensatz finden)

Was ist der einfachste Weg, eine Reihe von 3 Comparator-Klassen zu schreiben, um dies zu erreichen? Muss ich einen Schlüssel verwenden, der ein Bloat-Objekt mit Dummy-Feldern für diejenigen ist, nach denen ich nicht suche?

Answer 1

Sie werden über einen separaten Komparator für jedes Feld schreiben müssen Sie vergleichen wollen:

public class BloatTimeComparator implements Comparator<Bloat> { 
    public int compare(Bloat bloat1, Bloat bloat2) { 
     if (bloat1.timeInMilliseconds > bloat2.timeInMilliseconds) { 
      return 1; 
     } else if (bloat1.timeInMilliseconds < bloat2.timeInMilliseconds) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

Und so weiter für Jede Eigenschaft in Bloat, die Sie vergleichen möchten (Sie müssen für jede eine Vergleichsklasse erstellen). Dann nutzen Sie die Kollektionen Hilfsmethode:

Collections.binarySearch(bloatList, bloatObjectToFind, 
    new BloatTimeComparator()); 

Vom Java documentation für die binarysearch Methode, wird der Rückgabewert:

der Index des Suchschlüssels, wenn es in der Liste enthalten ist; andernfalls (- (Einfügepunkt) - 1). Der Einfügepunkt ist definiert als der Punkt, an dem der Schlüssel in die Liste eingefügt wird: der Index des ersten Elements, der größer als der Schlüssel ist, oder list.size(), wenn alle Elemente in der Liste kleiner als der angegebene Schlüssel sind. Beachten Sie, dass dies garantiert, dass der Rückgabewert genau dann> = 0 ist, wenn der Schlüssel gefunden wird.

Welchen Index haben Sie angegeben?

Answer 2

Wenn Sie die binäre Suche für alle drei Eigenschaften nutzen möchten, müssen Sie Vergleicher für sie erstellen und zusätzliche Listen oder TreeSets nach den Vergleichern sortiert haben.

Answer 3

Sie müssen 3 separate Comparator s haben, wenn Sie nach jeder der 3 Eigenschaften suchen möchten.

Eine sauberere Option wäre ein generischer Comparator, der einen Parameter erhält, der angibt, welches Feld er vergleichen soll.

Eine grundlegende sollte generic Komparator etwa wie folgt aussehen:

public class BloatComparator implements Comparator<Bloat> 
{ 
    CompareByEnum field; 

    public BloatComparator(CompareByEnum field) { 
     this.field = field; 
    } 

    @Override 
    public int compare(Bloat arg0, Bloat arg1) { 
     if (this.field == CompareByEnum.TIME){ 
      // compare by field time 
     } 
     else if (this.field == CompareByEnum.SPACE) { 
      // compare by field space 
     } 
     else { 
      // compare by field cost 
     } 
    } 
} 

Answer 4

Hier ist ein Test-Driven Ansatz den ersten Komparator zum Schreiben:

public class BloatTest extends TestCase{ 
    public class Bloat { 
     public long timeInMilliseconds; 
     public long spaceInBytes; 
     public long costInPennies; 

     public Bloat(long timeInMilliseconds, long spaceInBytes, long costInPennies) { 
      this.timeInMilliseconds = timeInMilliseconds; 
      this.spaceInBytes = spaceInBytes; 
      this.costInPennies = costInPennies; 
     } 
    } 

    public void testMillisecondComparator() throws Exception { 
     Bloat a = new Bloat(5, 10, 10); 
     Bloat b = new Bloat(3, 12, 12); 
     Bloat c = new Bloat(5, 12, 12); 

     Comparator<Bloat> comparator = new MillisecondComparator(); 
     assertTrue(comparator.compare(a, b) > 0); 
     assertTrue(comparator.compare(b, a) < 0); 
     assertEquals(0, comparator.compare(a, c)); 
    } 

    private static class MillisecondComparator implements Comparator<Bloat> { 
     public int compare(Bloat a, Bloat b) { 
      Long aTime = a.timeInMilliseconds; 
      return aTime.compareTo(b.timeInMilliseconds); 
     } 
    } 


} 

Answer 5

Testprogramm (MultiBinarySearch.java), wenn diese Ideen zu sehen, richtig (sie erscheinen):

package com.example.test; 

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 
import java.util.List; 
import java.util.Random; 

class Bloat 
{ 
    final public long timeInMilliseconds; 
    final public long spaceInBytes; 
    final public long costInPennies; 
    static final private int N = 100; 
    public Bloat(long l1, long l2, long l3) { 
     timeInMilliseconds = l1; 
     spaceInBytes = l2; 
     costInPennies = l3; 
    } 
    public Bloat() { this(0,0,0); } 
    public Bloat moreBloat(Random r) 
    { 
     return new Bloat(
       timeInMilliseconds + r.nextInt(N) + 1, 
       spaceInBytes + r.nextInt(N) + 1, 
       costInPennies + r.nextInt(N) + 1 
     ); 
    } 
    public String toString() { 
     return "[bloat: time="+timeInMilliseconds 
      +", space="+spaceInBytes 
      +", cost="+costInPennies 
      +"]"; 
    } 

    static int compareLong(long l1, long l2) 
    { 
     if (l2 > l1) 
      return -1; 
     else if (l1 > l2) 
      return 1; 
     else 
      return 0; 
    } 

    public static class TimeComparator implements Comparator<Bloat> { 
     public int compare(Bloat bloat1, Bloat bloat2) { 
      return compareLong(bloat1.timeInMilliseconds, bloat2.timeInMilliseconds); 
     } 
    } 
    public static class SpaceComparator implements Comparator<Bloat> { 
     public int compare(Bloat bloat1, Bloat bloat2) { 
      return compareLong(bloat1.spaceInBytes, bloat2.spaceInBytes); 
     } 
    } 
    public static class CostComparator implements Comparator<Bloat> { 
     public int compare(Bloat bloat1, Bloat bloat2) { 
      return compareLong(bloat1.costInPennies, bloat2.costInPennies); 
     } 
    } 
    enum Type { 
     TIME(new TimeComparator()), 
     SPACE(new SpaceComparator()), 
     COST(new CostComparator()); 

     public Comparator<Bloat> comparator; 
     Type(Comparator<Bloat> c) { this.comparator = c; } 
    } 
} 

class BloatProducer 
{ 
    final private List<Bloat> bloatList = new ArrayList<Bloat>(); 
    final private Random random = new Random(); 
    public void produceMoreBloat() 
    { 
     int n = bloatList.size(); 
     Bloat newBloat = 
      (n == 0) ? new Bloat() : bloatList.get(n-1).moreBloat(random); 
      bloatList.add(newBloat); 
    } 
    /* other fields/methods */ 

    public boolean testMonotonicity() 
    { 
     Bloat previousBloat = null; 
     for (Bloat thisBloat : bloatList) 
     { 
      if (previousBloat != null) 
      { 
       if ((previousBloat.timeInMilliseconds 
         >= thisBloat.timeInMilliseconds) 
        || (previousBloat.spaceInBytes 
         >= thisBloat.spaceInBytes) 
        || (previousBloat.costInPennies 
         >= thisBloat.costInPennies)) 
        return false; 
      } 
      previousBloat = thisBloat; 
     } 
     return true; 
    } 
    public int searchBy(Bloat.Type t, Bloat key) 
    { 
     return Collections.binarySearch(bloatList, key, t.comparator); 
    } 
    public void showSearch(Bloat.Type t, Bloat key) 
    { 
     System.out.println("Search by "+t+": "); 
     System.out.println(key); 
     int i = searchBy(t,key); 
     if (i >= 0) 
     { 
      System.out.println("matches"); 
      System.out.println(bloatList.get(i)); 
     } 
     else 
     { 
      System.out.println("is between"); 
      i = -i-1; 
      Bloat b1 = (i == 0) ? null : bloatList.get(i-1); 
      System.out.println(b1); 
      Bloat b2 = (i >= bloatList.size()) ? null : bloatList.get(i); 
      System.out.println("and"); 
      System.out.println(b2); 
     } 
    } 
} 

public class MultiBinarySearch { 
    private static int N = 1000; 
    public static void main(String[] args) 
    { 
     BloatProducer bloatProducer = new BloatProducer(); 
     for (int i = 0; i < N; ++i) 
     { 
      bloatProducer.produceMoreBloat(); 
     } 

     System.out.println("testMonotonicity() returns "+ 
       bloatProducer.testMonotonicity()); 
     Bloat key; 
     key = new Bloat(10*N, 20*N, 30*N); 
     bloatProducer.showSearch(Bloat.Type.COST, key); 
     bloatProducer.showSearch(Bloat.Type.SPACE, key); 
     bloatProducer.showSearch(Bloat.Type.TIME, key); 
     key = new Bloat(-10000, 0, 1000*N); 
     bloatProducer.showSearch(Bloat.Type.COST, key); 
     bloatProducer.showSearch(Bloat.Type.SPACE, key); 
     bloatProducer.showSearch(Bloat.Type.TIME, key); 
    } 
}