File PositionIndex.h

↰ Parent directory (ADS/dictionary)

The index of the positions of objects in a vector, beyond the book: a hash table from the address of an object to its position, of 32 bits, in a vector that holds it, e.g., the constraints or the variables of a model, whose positions change when some of them are erased.

Definition (ADS/dictionary/PositionIndex.h)

Detailed Description

Besides the operations of a dictionary, renumber() takes the sorted positions just erased from the vector and, in one pass over the table, drops the objects that were there and moves every other position p to :math:` p - |\{ e \in E : e < p \}| `, its place in the vector after the erasure of E.

The table is FlatHashTable [see File FlatHashTable.h], from the address to the position, with the hash of Namespace ADS, so that a search, an insertion and a removal cost what they cost there: in the common case one group of 16 control bytes and one line of the pairs, compared all at once.

renumber() walks all the pairs in the order of the places, which reads the memory of the table once and in order, and gives each key its new position: :math:` mathrm{rank}( p ) , the erased positions below p, is the count of the erased positions before the word of 64 bits of p in a bit vector of them plus the population count of the bits of that word below p, in O( 1 ) time and with no branch [Jacobson], and a position past the largest erased one, e, moves by m, the number of the erased ones; the word and its count sit side by side, so that a rank costs one access to the memory, which for :math: e le 2^{22} ` is a table of at most 1 MB. The keys of the erased positions are gathered on the way and removed afterwards. The whole of it takes :math:` O( N + m + e / 64 ) ` time for N places and :math:` e / 4 ` bytes of scratch, which stays with the index for the next call.

The contracts [see File Contract.h]: no key is nil, the positions are below :math:` 2^{32} - 1 `, and the positions given to renumber() are strictly increasing. The operations are defined in PositionIndex.tpp.

  1. Jacobson, Space-efficient static trees and graphs, 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), 549-554, 1989, doi:10.1109/SFCS.1989.63533 (rank by the counts of blocks)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes