Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.
Решил сделать сам.
Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.
Пример валидных ярлыков:
Ярлыки | Объекты |
---|---|
green, wooden, alive | tree |
green, wooden, lifeless | bench |
green, alive, croak | frog |
Коллекция должна позволять:
- put() — помещать в неё объекты со списком прикрепленных меток
- getValues() — возвращать объекты, содержащиеся в коллекции
- findValues() — осуществлять поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков
- 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(); } }
ссылка на оригинал статьи http://habrahabr.ru/post/270461/
Добавить комментарий