Kind¶
Leaving out a tag you need does not compile: the operation does not exist.
A request names its kind first, with its element types (include/urd/kinds.hpp): set<K> (keys, each once),
map<K, V> (a value per key), multiset<V> (values by value, in order), sequence<V> (values by position; sequence<V, P> addressed by an index type P),
queue<V> (values by their front or top: fifo, lifo or by_priority), pool<V> (each distinct value
once, by handle), slots<V> (values in slots, by handle) and partition<K> (keys in disjoint classes). Every
argument after it is a tag.
A kind decides what the Store is: which operations it has (its facets, see the kinds), what its
elements are (its element types), and which questions its requests answer (its request format: its own, then those
every kind answers: how it stores, what it costs and how it is used). A tag outside that format does not compile, and
nor does a request its kind’s rules call contradictory (a queue reached neither by fifo, lifo nor
by_priority). Answer the questions below first: every other answer is read against them. A kind added outside urd
is a kind like these (Extending urd).
A plain sequence<V> may be held where V is still incomplete, as std::vector<V> may, so a recursive type
holds a sequence of itself (struct Node { urd::Store<urd::sequence<Node>> children; };). Such a type writes its
== and <=> out: defaulted in the class, they would ask the Store’s, which ask the element’s. Every other kind,
and a sequence with stable_refs or concurrent, needs its element types complete, because choosing or building
their containers asks what the elements are.
Question |
Tags |
Kinds |
|---|---|---|
|
queue |
|
|
queue, pool, slots |
|
|
partition |
|
|
slots |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
Abstract data types: a type is the operations it offers (Liskov and Zilles, 1974).
How are elements taken out?¶
Category any_access, which promises nothing: a request that leaves the question open gets it. Asked of: queue.
A queue: reached by front or top; iterated in the order pushed, or a priority queue in none.
fifo¶
A queue: elements leave in the order they came.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: queue, fifo, breadth first, worklist.
Instead of:
lifo,by_priority(one answer per question).Shortest served request:
Store<queue<Id>, fifo>.
lifo¶
A stack: the last element pushed leaves first.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: stack, lifo, depth first.
Instead of:
fifo,by_priority(one answer per question).Shortest served request:
Store<queue<Id>, lifo>.
by_priority¶
A priority queue: the least element leaves first.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: priority queue, heap, best first, open list.
Instead of:
fifo,lifo(one answer per question).Shortest served request:
Store<queue<Id>, by_priority>.
Reached by handle?¶
Category any_handle, which promises nothing: a request that leaves the question open gets it. Asked of: queue, pool, slots.
A pool: insert gives an urd::index; with unique equal rows get equal handles. On a priority
queue, push gives a handle to update or erase by.
handles¶
A pool: insert gives a handle; with unique, equal elements get equal handles.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: interning, handles, deduplicated rows, hash consing.
Shortest served request:
Store<queue<Id>, by_priority, handles>.
Groups of keys?¶
Category any_grouping, which promises nothing: a request that leaves the question open gets it. Asked of: partition.
Union-find classes: merge, find, same.
partition¶
A partition: elements fall into disjoint classes that merge joins.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: union find, disjoint sets, equivalence classes.
Shortest served request:
Store<partition<Id>>.
Freed slots kept by a key?¶
Category any_keying, which promises nothing: a request that leaves the question open gets it. Asked of: slots.
Slots acquired by key (keyed<K>): make_shared(key, args...) reuses only a slot given back under an equal
key, else makes T(key, args...).
keyed¶
Slots acquired by a key: a freed slot is reused only under an equal key.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: pooled by shape, reuse by key, free lists per key.
Shortest served request: none in What a request resolves to.
Is room made ahead?¶
Category any_room, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
reserve(n): room for n elements before they come. Tables, contiguous storage and the containers built on
them have it; trees and segmented storage do not.
reservable¶
Offers reserve: its storage can be sized ahead.
Role: a kind: it says how a kind’s Store is reached (fifo, handles).
In plain words: reserve, preallocate, size known ahead.
Shortest served request: none in What a request resolves to.