[Из песочницы] Веб-два-нольные ярлыки для Java09.11.2015 13:18

Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.

Решил сделать сам.

Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.

Пример валидных ярлыков:

Ярлыки Объекты
green, wooden, alive tree
green, wooden, lifeless bench
green, alive, croak frog


Коллекция должна позволять:

  1. put() — помещать в неё объекты со списком прикрепленных меток
  2. getValues() — возвращать объекты, содержащиеся в коллекции
  3. findValues() — осуществлять поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков
  4. findValuesOnlyIn() — осуществлять поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков


Поясню последние 2 пункта на следующей таблице по тем объектам, которые были рассмотрены в предыдущем примере:

Ярлыки, передаваемые в качестве аргумента findValues() findValuesOnlyIn()
green, wooden tree, bench
green, wooden, alive, lifeless tree, bench
tree, bench, frog


Поиск должен быть быстрым, поэтому для индексации будем использовать битовые маски. Т.е. сам объект храним в массиве, а его порядковый номер в этом массиве — это порядковый номер бита в битовой маске.

Опять же вернемся к нашему примеру:

Нумерация объектов в массиве: 0 — tree, 1 — bench, 2 — frog.
Тогда битовая маска для ярлыка green будет {1, 1, 1}, для wooden — {1, 1, 0}, для alive — {1, 0, 1}, lifeless — {0, 1, 0}, croak — {0, 0, 1}.

Битовые маски позволяют упростить поиск объектов по ярлыку, просто выполняя двоичные операции: AND, OR, NOT и т.п… В результате, если на определенной позиции останется единичный бит, то по её номеру легко извлечём из массива искомый объект.

Начинаем реализацию:

Здесь V — тип объектов, L — тип ярлыков, labelsBitSets — хранилище битовых масок ярлыков, values — хранилище объектов:

public class LabelsMultiMap<L, V> {
  private final Map<L, BitSet> labelsBitSets = new HashMap<>();
  private final List<V> values = new ArrayList<>();
}


Метод, помещающий новый объект с его описывающими ярлыками в нашу коллекцию:

Здесь мы помещаем наш объект в values в методе addValue(), который вернет индекс новой ячейки массива. Далее по каждому ярлыку проверяем, есть ли битовая маска для данного ярлыка, если нет, то создаем пустую маску, добавляем в labelsBitSets, если уже есть, то возвращаем старую маску, и выставляем единичный бит в ней по позиции объекта в массиве, которая хранится в i:

public void put(Set<L> labels, V value) {
  int i = addValue(value);
  for(L label : labels) {
    BitSet bitSet = getOrCreateLabel(label);
    bitSet.set(i);
  }
}


Метод, возвращающий все объекты из коллекции:

public List<V> getValues() {
  return Collections.unmodifiableList(values);
}


Метод, осуществляющий поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков:

public Collection<V> findValues(Set<L> labels) {
  Iterator<L> it = labels.iterator();


Если список ярлыков в аргументе пуст, то возвращаем весь список:

  if (!it.hasNext()) {
    return getValues();
  }


Если по первому попавшемуся ярлыку не нашли ни одной битовой маски, то возвращаем пустой результат:

  BitSet firstBitSet = labelsBitSets.get(it.next());
  if (firstBitSet == null) {
    return Collections.emptySet();
  }


Инициализируем аккумулятор, куда будем накапливать найденный битовые маски с помощью операции AND. Использовал clone(), т.к. у BitSet отсутствует конструктор копирования:

  BitSet accumulator = (BitSet) firstBitSet.clone();


Накапливаем в accumulator все маски, если не нашли хоть одну битовую маску по одному из последующих ярлыков, то возвращаем пустую коллекцию:

  while (it.hasNext()) {
    BitSet nextBitSet = labelsBitSets.get(it.next());
    if (nextBitSet == null) {
      return Collections.emptySet();
    }
    accumulator.and(nextBitSet);
  }


Возвращаем результат в виде новой коллекции по накопленной маске в accumulator:

  return new ValuesByBitSetCollection<>(accumulator, values);
}


Ну и последний метод, осуществляющий поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков:

В inAccumulator накапливаем те битовые маски, которые есть в нашем запросе, а в outAccumulator — которых нет в нашем запросе, если исходный запрос пуст, возвращаем пустое множество:

public Collection<V> findValuesOnlyIn(Set<L> labels) {
  if (labels.isEmpty()) {
    return Collections.emptySet();
  }
  BitSet inAccumulator = new BitSet(values.size());
  BitSet outAccumulator = new BitSet(values.size());


Пробегаем по всем сохраненным ярлыкам в нашей коллекции, откладывая их битовые маски в in-/outAccumulator в зависимости от наличия их в labels, в конце просто вычтем одно множество из другого и вернем результат в виде коллекции по результирующей маске.

  for(Map.Entry<L, BitSet> bitSetEntry : labelsBitSets.entrySet()) {
    BitSet accumulator = labels.contains(bitSetEntry.getKey()) ? inAccumulator : outAccumulator;
    accumulator.or(bitSetEntry.getValue());
  }
  
  inAccumulator.andNot(outAccumulator);

  return new ValuesByBitSetCollection<>(inAccumulator, values);
}


Вспомогательные классы и методы
Вспомогательная функция по добавлению элемента в массив (добавляем элемент в конец массива, возвращаем его позицию):
private int addValue(V value) {
  values.add(value);
  return values.size() - 1;
}

Вспомогательная функция по возврату битовой маски для данного ярлыка:
private BitSet createOrGetLabel(L label) {
  BitSet ret = labelsBitSets.get(label);
  if (ret == null) {
    ret = new BitSet(values.size());
    labelsBitSets.put(label, ret);
  }
  return ret;
}

Вспомогательный класс, позволяющий накладывать на массив битовую маску, в size кэшируем количество единичных бит в маске (BitSet.cardinality()):
private static class ValuesByBitSetCollection<V> extends AbstractCollection<V> {
  private final BitSet bitSet;
  private final List<V> values;
  private int size = -1;
  
  private ValuesByBitSetCollection(BitSet bitSet, List<V> values) {
    this.bitSet = bitSet;
    this.values = values;
  }

  @Override
  public boolean isEmpty() {
    return bitSet.isEmpty();
  }

  @Override
  public Iterator<V> iterator() {
    return new ValuesByBitSetIterator<>(bitSet, values);
  }

  @Override
  public int size() {
    if (size < 0) {
      size = bitSet.cardinality();
    }
    return size;
  }
}

Вспомогательный класс для итерирования по этой коллекции, в index храним позицию следующего установленного бита (или -1, если такого бита больше нет):
private static class ValuesByBitSetIterator<V> implements Iterator<V> {
  private final BitSet bitSet;
  private final List<V> values;
  private int index;

  private ValuesByBitSetIterator(BitSet bitSet, List<V> values) {
    this.bitSet = bitSet;
    this.values = values;
    index = bitSet.nextSetBit(0);
  }

  @Override
  public boolean hasNext() {
    return index >= 0;
  }

  @Override
  public V next() {
    if (index < 0) {
      throw new NoSuchElementException();
    }
    V ret = values.get(index);
    index = bitSet.nextSetBit(index + 1);
    return ret;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

© Habrahabr.ru