Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.
Решил сделать сам.
Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.
Пример валидных ярлыков:
Ярлыки | Объекты |
---|---|
green, wooden, alive | tree |
green, wooden, lifeless | bench |
green, alive, croak | frog |
Ярлыки, передаваемые в качестве аргумента | findValues() | findValuesOnlyIn() |
---|---|---|
green, wooden | tree, bench | |
green, wooden, alive, lifeless | tree, bench | |
tree, bench, frog |
public class LabelsMultiMap<L, V> {
private final Map<L, BitSet> labelsBitSets = new HashMap<>();
private final List<V> values = new ArrayList<>();
}
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();
}
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;
}
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;
}
}
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();
}
}
К сожалению, не доступен сервер mySQL