Java: коллекция фильтров и извлечение данных по нескольким полям

Question

У меня есть класс:

public class Address { 
    private String country; 
    private String state; 
    private String city; 
} 

И есть список объектов Person. Класс Person выглядит следующим образом:

public class Person { 
    private String country; 
    private String state; 
    private String city; 
    //other fields 
} 

Мне нужно фильтровать Person объекты и получить наиболее подходящий. Address объект может иметь как минимум одно не пустое поле. Person Объект не может иметь ни одного, частично или все упомянутые поля инициализированы.

Вот один из возможных примеров ввода:

Three Person objects: 
a. PersonA: country = 'A' 
b. PersonB: country = 'A', state = 'B' 
c. PersonC: country = 'A', state = 'B', city = 'C' 

Address object: 
a. Address: country = 'A', state = 'B' 

Ожидаемый результат после фильтрации является PersonB. И в случае, когда есть только объекты PersonA и PersonC, тогда PersonA предпочтительнее.

Я хотел бы показать, как я пытался это сделать, но на самом деле это чистый алгоритм грубой силы, и мне это не нравится. С новым добавленным полем увеличивается сложность алгоритма. Я также думал об использовании фильтра guava по предикату, но понятия не имел, какой предикат должен быть.

Что является предпочтительным алгоритмом для такой фильтрации, если есть какая-либо кроме грубой силы?

Answer 1

Чтобы избежать грубой силы, вам нужно будет проиндексировать вас по адресу. Для хорошего поиска вам определенно нужна страна (предположите, что это или по умолчанию это как-то, иначе результаты в любом случае будут слишком неточными).

Индекс будет представлять собой число, первые 3 цифры для страны, следующие 3 цифры для состояния и последние 4 цифры для города. В таком случае в int вы сможете хранить 213 стран (only 206 as of 2016), до 999 штатов и 9999 городов.

Это дает нам возможность использовать hashCode и TreeSet для индексации ваших экземпляров Person и поиска их частично по адресу с помощью O (log (n)), не касаясь их полей. Поля будут затронуты конструкцией TreeSet, и вам нужно будет добавить дополнительную логику для модификации Person, чтобы сохранить индекс неизменным.

Индекс рассчитывается sequntially для каждой части, начиная от страны

import java.util.HashMap; 
    import java.util.Map; 

    public class PartialAddressSearch { 

     private final static Map<String, AddressPartHolder> COUNTRY_MAP = new HashMap<>(200); 

     private static class AddressPartHolder { 
      int id; 
      Map<String, AddressPartHolder> subPartMap; 

      public AddressPartHolder(int id, Map<String, AddressPartHolder> subPartMap) { 
       this.id = id; 
       this.subPartMap = subPartMap; 
      } 
     } 

     public static int getCountryStateCityHashCode(String country, String state, String city) { 
      if (country != null && country.length() != 0) { 
       int result = 0; 
       AddressPartHolder countryHolder = COUNTRY_MAP.get(country); 
       if (countryHolder == null) { 
        countryHolder = new AddressPartHolder(COUNTRY_MAP.size() + 1, new HashMap<>()); 
        COUNTRY_MAP.put(country, countryHolder); 
       } 
       result += countryHolder.id * 10000000; 

       if (state != null) { 
        AddressPartHolder stateHolder = countryHolder.subPartMap.get(state); 
        if (stateHolder == null) { 
         stateHolder = new AddressPartHolder(countryHolder.subPartMap.size() + 1, new HashMap<>()); 
         countryHolder.subPartMap.put(state, stateHolder); 
        } 
        result += stateHolder.id * 10000; 

        if (city != null && city.length() != 0) { 
         AddressPartHolder cityHolder = stateHolder.subPartMap.get(city); 
         if (cityHolder == null) { 
          cityHolder = new AddressPartHolder(stateHolder.subPartMap.size() + 1, null); 
          stateHolder.subPartMap.put(city, cityHolder); 
         } 
         result += cityHolder.id; 
        } 
       } 

       return result; 
      } else { 
       throw new IllegalArgumentException("Non-empty country is expected"); 
      } 
    } 

Для вашего лица и адреса, классы вы определяете хэш-код и CompareTo на основе естественного порядка междунар:

public class Person implements Comparable { 
     private String country; 
     private String state; 
     private String city; 

     @Override 
     public boolean equals(Object o) { 
      //it's important but I removed it for readability 
     } 

     @Override 
     public int hashCode() { 
      return getCountryStateCityHashCode(country, state, city); 
     } 

     @Override 
     public int compareTo(Object o) { 
      //could be further improved by storing hashcode in a field to avoid re-calculation on sorting 
      return hashCode() - o.hashCode(); 
     } 

    } 

    public class Address implements Comparable { 
     private String country; 
     private String state; 
     private String city; 


     @Override 
     public boolean equals(Object o) { 
      //removed for readability 
     } 

     @Override 
     public int hashCode() { 
      return getCountryStateCityHashCode(country, state, city); 
     } 

     @Override 
     public int compareTo(Object o) { 
      //could be further improved by storing hashcode in a field to avoid re-calculation on sorting 
      return hashCode() - o.hashCode(); 
     } 

    } 

    public class AddressPersonAdapter extends Person { 
     private final Address delegate; 

     public AddressPersonAdapter(Address delegate) { 
      this.delegate = delegate; 
     } 

     @Override 
     public boolean equals(Object o) { 
      return delegate.equals(o); 
     } 

     @Override 
     public int hashCode() { 
      return delegate.hashCode(); 
     } 
    } 

После что ваш код фильтрации будет уменьшаться до заполнения индекса и расчетного уровня для вашего частичного адреса:

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("A"); 
    personSetByAddress.add(personA); 
    Person personB = new Person(); 
    personB.setCountry("A"); 
    personB.setState("B"); 
    personSetByAddress.add(personB); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10010000, country='A', state='B', city='null'} 

И если вы не будете иметь PersonB:

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("A"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10000000, country='A', state='null', city='null'} 

EDIT:

Угловой случай, который потребует дополнительной проверки будет отсутствие элемента больше (или меньше, если нам нужно потолок) в пределах той же страны. Например:

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("D"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10000000, country='D', state='null', city='null'} 

I.e. мы выпадаем в ближайшую страну. Чтобы исправить это, нам нужно будет проверить, что номер страны остается прежним. Мы можем сделать это суб-причислять к TreeSet и добавить эту галку:

//we need this class to allow flooring just by id 
public class IntegerPersonAdapter extends Person { 
    private Integer id; 
    public IntegerPersonAdapter(Integer id) { 
     this.id = id; 
    } 

    @Override 
    public boolean equals(Object o) { 
     return id.equals(o); 
    } 

    @Override 
    public int hashCode() { 
     return id.hashCode(); 
    } 

    @Override 
    public int compareTo(Object o) { 
     return id.hashCode() - o.hashCode(); 
    } 

    @Override 
    public String toString() { 
     return id.toString(); 
    } 
} 

public class StrictCountryTreeSet extends TreeSet<Person> { 

    @Override 
    public Person floor(Person e) { 
     Person candidate = super.floor(e); 
     if (candidate != null) { 
      //we check if the country is the same 
      int candidateCode = candidate.hashCode(); 
      int eCode = e.hashCode(); 
      if (candidateCode == eCode) { 
       return candidate; 
      } else { 
       int countryCandidate = candidateCode/10000000; 
       if (countryCandidate == (eCode/10000000)) { 
        //we check if the state is the same 
        int stateCandidate = candidateCode/10000; 
        if (stateCandidate == (eCode/10000)) { 
         //we check if is a state 
         if (candidateCode % 10 == 0) { 
          return candidate; 
         } else { //since it's not exact match we haven't found a city - we need to get someone just from state 
          return this.floor(new IntegerPersonAdapter(stateCandidate * 10000)); 
         } 

        } else if (stateCandidate % 10 == 0) { //we check if it's a country already 
         return candidate; 
        } else { 
         return this.floor(new IntegerPersonAdapter(countryCandidate * 10000000)); 
        } 
       } 
      } 
     } 
     return null; 
    } 

Теперь наш тест даст null после инициализировать в StrictCountryTreeSet: тест

TreeSet<Person> personSetByAddress = new StrictCountryTreeSet(); 
    Person personA = new Person(); 
    personA.setCountry("D"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    null 

И для другого государства даст null, а также:

TreeSet<Person> personSetByAddress = new StrictCountryTreeSet(); 
    Person personD = new Person(); 
    personD.setCountry("D"); 
    personSetByAddress.add(personD); 

    Person personE = new Person(); 
    personE.setCountry("A"); 
    personE.setState("E"); 
    personSetByAddress.add(personE); 

    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressA = new Address(); 
    addressA.setCountry("A"); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    Address addressABC = new Address(); 
    addressABC.setCountry("A"); 
    addressABC.setState("B"); 
    addressABC.setCity("C"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    null 

Пожалуйста, обратите внимание, что в этом случае вам нужно будет хранить результаты Hashcode в A ddress и Person, чтобы избежать повторного расчета.

Answer 2

Как я понимаю, по грубой силе вы имеете в виду проверку всех полей всех сущностей. Ну, если вы не будете реорганизовывать свои классы, это невозможно, но есть простой трюк, который поможет. Он использует шаблон state.

Вы можете добавить флаг notNulls к обеим классам:

public class Address { 
    private int notNulls = 0; 
    private String country; 
    private String state; 
    private String city; 
} 

public class Person { 
    private int notNulls = 0; 
    private String country; 
    private String state; 
    private String city; 
    //other fields 
} 

Я покажу вам возможную реализацию одного инкубатора в остальном аналогично:

public void setCountry(String s) { 
    if (country == null { 
     if (s != null) { 
      country = s; 
      notNulls++; 
     } 
    } else { 
     if (s == null) { 
      country == null; 
      notNulls--; 
     } else { 
      country = s; 
     } 
    } 
} 

public boolean isValid() { 
    return notNulls != 0; 
} 

Теперь вы можете просто перебрать объекты.