BitSet
BitSet implementa um conjunto de bits compacto sobre uma capacidade fixa, apoiado em um array de palavras de 64 bits, com operações de conjunto.
Construção
| Sintaxe | Descrição |
|---|---|
BitSet(n) | Cria um conjunto de bits com capacidade para n bits, todos inicialmente zerados |
BitSet.fromArray(arr) | Cria um conjunto de bits com os bits das posições em arr ligados |
fromArray exige um argumento usize[]. As posições de bits são indexadas a partir de 0 até n - 1.
Métodos
| Método | Assinatura | Retorno | Descrição |
|---|---|---|---|
set | (index: usize, value?: boolean) => void | void | Liga, desliga ou define condicionalmente o bit em index (padrão: true) |
flip | (index: usize) => void | void | Alterna o bit em index |
get | (index: usize) => boolean | boolean | Se o bit em index está ligado |
count | () => usize | usize | Número de bits ligados |
isEmpty | () => boolean | boolean | Se nenhum bit está ligado |
isSubset | (other: BitSet) => boolean | boolean | Se todo bit ligado também está ligado em other |
isSuperset | (other: BitSet) => boolean | boolean | Se todo bit ligado em other também está ligado |
union | (other: BitSet) => BitSet | BitSet | Conjunto de bits com todos os bits de ambos os conjuntos |
intersection | (other: BitSet) => BitSet | BitSet | Conjunto de bits com os bits ligados em ambos |
difference | (other: BitSet) => BitSet | BitSet | Conjunto de bits com os bits ligados aqui mas não em other |
complement | () => BitSet | BitSet | Conjunto de bits com cada bit alternado sobre a capacidade |
clear | () => void | void | Zera todos os bits |
union, intersection, difference e complement retornam um BitSet novo de posse do chamador; ele é liberado automaticamente quando a variável sai de escopo.
Complexidade
| Operação | Complexidade de Tempo |
|---|---|
set | O(1) |
flip | O(1) |
get | O(1) |
count | O(n), número de palavras de máquina |
isEmpty | O(n), número de palavras de máquina |
isSubset | O(n), número de palavras de máquina |
isSuperset | O(n), número de palavras de máquina |
union | O(n), número de palavras de máquina |
intersection | O(n), número de palavras de máquina |
difference | O(n), número de palavras de máquina |
complement | O(n), número de palavras de máquina |
clear | O(n), número de palavras de máquina |
Exemplos
Construção
tyrus
import { BitSet } from "tyrus:algorithm";
const bs = BitSet(100);set e get
tyrus
const bs = BitSet(100);
bs.set(5);
bs.set(10, true);
bs.set(3, false);
print(bs.get(5)); // true
print(bs.get(3)); // false
print(bs.get(10)); // trueflip
tyrus
const bs = BitSet(100);
bs.set(3);
print(bs.get(3)); // true
bs.flip(3);
print(bs.get(3)); // falsecount e isEmpty
tyrus
const bs = BitSet(100);
print(bs.count()); // 0
print(bs.isEmpty()); // true
bs.set(1);
bs.set(2);
print(bs.count()); // 2
print(bs.isEmpty()); // falseisSubset e isSuperset
tyrus
const a = BitSet(100);
a.set(1);
a.set(3);
const b = BitSet(100);
b.set(1);
b.set(3);
b.set(5);
print(a.isSubset(b)); // true
print(b.isSuperset(a)); // true
print(b.isSubset(a)); // falseunion, intersection e difference
tyrus
const a = BitSet(100);
a.set(1);
a.set(3);
a.set(5);
const b = BitSet(100);
b.set(3);
b.set(5);
b.set(7);
print(a.union(b).count()); // 4
print(a.intersection(b).count()); // 2
print(a.difference(b).count()); // 1complement
tyrus
const bs = BitSet(100);
bs.set(3);
bs.set(5);
bs.set(7);
print(bs.complement().count()); // 97
print(bs.complement().get(1)); // truefromArray
tyrus
const indexes: usize[] = [3, 5, 10];
const bs = BitSet.fromArray(indexes);
print(bs.count()); // 3
print(bs.get(10)); // true
print(bs.get(4)); // falseclear
tyrus
const bs = BitSet(100);
bs.set(1);
bs.set(2);
print(bs.isEmpty()); // false
bs.clear();
print(bs.isEmpty()); // true