Código Natural/Representação interna: mudanças entre as edições
| Linha 18: | Linha 18: | ||
|} | |} | ||
O tipo de dado relativo a essa representação foi apelidado como '''"hInt"''' (do inglês '''"hierarchical Integer"'''), com as variantes acima apelidadas hInt16, hInt32 e hInt64 respectivamente. O valor inteiro hInt além de preservar a integridade da cadeia de bits original no seu interior, | O tipo de dado relativo a essa representação foi apelidado como '''"hInt"''' (do inglês '''"hierarchical Integer"'''), com as variantes acima apelidadas hInt16, hInt32 e hInt64 respectivamente. O valor inteiro hInt além de preservar a integridade da cadeia de bits original no seu interior, '''preserva a ordem lexicográfica'''. | ||
Abaixo um exemplo com o conjunto completo de todas as cadeias de até 3 bits (coluna ''bitString''), e a representação de cada uma delas como hInt16 — seu valor em representação decimal na coluna "hInt16_dec" e sua representação interna dentro do inteiro de 16 bits na coluna "internal_16bits". | Abaixo um exemplo com o conjunto completo de todas as cadeias de até 3 bits (coluna ''bitString''), e a representação de cada uma delas como hInt16 — seu valor em representação decimal na coluna "hInt16_dec" e sua representação interna dentro do inteiro de 16 bits na coluna "internal_16bits". | ||
<pre> | <pre> | ||
bitstring | hInt16_dec| internal_16bits | value_dec | len_dec | bitstring | hInt16_dec| internal_16bits | value_dec | len_dec | ||
| Linha 41: | Linha 42: | ||
A coluna "len_dec" fornece o valor decimal dos 4 bits de ''cache-length'' (facilmente extraído pela operação ''bitwise'' <code>hInt16 & 15</code>), e a coluna "value_dec" o valor decimal dos 11 bits centrais (extraído por <code>hInt16>>4</code>). | A coluna "len_dec" fornece o valor decimal dos 4 bits de ''cache-length'' (facilmente extraído pela operação ''bitwise'' <code>hInt16 & 15</code>), e a coluna "value_dec" o valor decimal dos 11 bits centrais (extraído por <code>hInt16>>4</code>). | ||
A preservação da ordem lexicográfica é conseguida devido à "cópia à esquerda", como podemos notar pela coluna "value_dec". Em seguida a coluna "len_dec" mostra que o ''cache-length'' faz também o papel de ajuste fino, nas linhas onde os valores "value_dec" se repetem (ver 0, 512 e 1024). | |||
A ordem '''garante que cada ramo da hierarquia esteja contido dentro de um único intervalo hInt'''. Por exemplo <code>00</code> e seus "filhos" (<code>000</code> e <code>001</code>), estão entre os valores hInt 2 e 4099. Analogamente todos os "filhos de <code>1</code>" estão entre os valores hInt 16385 e 28675. | |||
===Exemplo mais completo=== | ===Exemplo mais completo=== | ||
| Linha 128: | Linha 133: | ||
11111111111 | 32763 | 0 11111111111 1011 | 2047 | 11 | 11111111111 | 32763 | 0 11111111111 1011 | 2047 | 11 | ||
</pre> | </pre> | ||
=== Operações essenciais === | |||
O tipo de dado ''hInt'' vem munido de um conjunto de operações com aplicações relevantes: | |||
:{| class="wikitable" | |||
!Função ou operação sobre ''x''!!Descrição !! Aplicação | |||
|- | |||
| ''x'' & max_len || Máscara do ''cache-length''. Retorna o comprimento da bitstring || ordenação por nível, recorte da bitstring, etc. | |||
|- | |||
|''succ''(''x'') || Sucessor, como gerador serial de identificadores. || Contadores e geradores de identificador serial. | |||
|- | |||
|''p''=''prefix''(''x'',''k'') || Prefixo ''p'' de ''k'' bits. || ... | |||
|- | |||
|''p''=''prefix''(''x'',''y'') || Prefixo comum de ''x'' e ''y''. || ... | |||
|- | |||
|''prefix_to_max''(''p'') || Valor hInt que corresponde ao máximo valor de um "filho" de ''p''. || Resgatar elementos com prefixo ''p'', ou seja, um ramo inteiro da árvore. | |||
|- | |||
|...||...||... | |||
|} | |||
== Hidden-bit strategy == | == Hidden-bit strategy == | ||