Веб-Ярлыки С Двумя Нулями Для Java

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

Я решил сделать это сам.

Итак, нам нужно хранить объекты в коллекции этого типа (назовем ее, скажем, LabelsMultiMap).

И объекты, и метки могут быть любого типа.

Количество меток сверху не ограничено, как и количество объектов.

Одним и тем же набором меток может быть описано более одного объекта.

Для одного объекта одна метка может появиться только 1 раз.

Пример допустимых меток:

Ярлыки	Объекты
зеленый, деревянный, живой	дерево
зеленый, деревянный, безжизненный	лавка
зеленый, живой, каркать	лягушка

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

помещать() — размещать в нем объекты со списком прикрепленных меток
получить значения() — вернуть объекты, содержащиеся в коллекции
найти значения() — поиск объектов, метки которых содержат запрошенный набор меток
найтиValuesOnlyIn() — искать только те объекты, все метки которых входят в запрошенный набор меток

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

Метки, передаваемые в качестве аргумента	найти значения()	найтиValuesOnlyIn()
зеленый, деревянный	дерево, скамейка
зеленый, деревянный, живой, безжизненный		дерево, скамейка
	дерево, скамейка, лягушка

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

Те.

Сам объект хранится в массиве, а его порядковый номер в этом массиве является порядковым номером бита в битовой маске.

Давайте снова вернемся к нашему примеру: Нумерация объектов в массиве: 0 – дерево, 1 – скамейка, 2 – лягушка.

Тогда битовая маска для зеленой метки будет {1, 1, 1}, для деревянной - {1, 1, 0}, для живой - {1, 0, 1}, неживой - {0, 1, 0}, каркать - {0, 0, 1}.

Битовые маски позволяют упростить поиск объектов по метке, просто выполняя бинарные операции: И, ИЛИ, НЕ и т.д. В результате, если в определенной позиции остается один бит, то по его номеру мы легко извлекаем желаемый объект из массива.

Приступим к реализации: Здесь В — тип объектов, л - тип этикеток, меткиBitSets - хранение битовых масок ярлыков, ценности - хранилище объектов:

   

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

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

Далее для каждого ярлыка проверяем, есть ли у этого ярлыка битовая маска; если нет, то создаем пустую маску и добавляем ее в меткиBitSets , если она уже есть, то возвращаем старую маску и устанавливаем в ней бит единицы согласно положению объекта в массиве, который хранится в я :

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

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

Я использовал clone(), потому что в BitSet нет конструктора копирования:

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

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

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

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

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

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

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

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

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

Вспомогательный класс, позволяющий применять к массиву битовую маску, в размер кэшируйте количество единичных битов в маске ( BitSet.мощность() ):

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

Вспомогательный класс для перебора этой коллекции, в индекс сохраните позицию следующего установленного бита (или -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(); } }

Теги: #java #labels #collection #bitmap #tutorial #java #Алгоритмы