Documentation of the Grid Category Components -- Partial Grid Function Concept

Partial Grid Function Concept

Partial Grid Function Concept

Description

The Partial Grid Function concept refines the Container Grid Function concept. A partial grid function reserves storage only for those values which are write-accessed explicitly. This is in contrast to Total Grid Function which allocates storage for each value.

Partial grid functions are of particular importance for locally operating algorithms with sublinear runtime and memory requirements.

Refinement of

Container Grid Function

Notation

F is a type which is a model of Partial Grid Function
f is an object of type F
G is shorthand for F::grid_type
g is an object of type G.

Associated types

None, exept those defined in Container Grid Function

Valid Expressions

Name	Expression	Type requirements	return type
Definition test	`f.defined(e);`		`bool`
Definition undo	`f.undefine(e);`
Default setting	`f.set_default(t);`
Default access	`f.default();`		F::value_type

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
construction from grid	`F f(g);`		construct and bind `f` to `g`	`f` is bound to `g` write access is allowed read access is undefined `f.size()` is equal to the cardinality of the range of `f`
construction and initialization	`F f(g,t);`		construct and bind `f` to `g`, initialize the default value to `t`	`f` is bound to `g` write access is allowed `f(e)` is equal to `t` for all elements `e` in the range of `f`. `f.size()` is equal to the cardinality of the range of `f`
Binding to grid	`f.set_grid(g);`	f is unbound	bind `f` to `g`	`f` is bound to `g` write access is allowed, read access is undefined `f.size()` is equal to the cardinality of the range of `f`
Definition test	`if(f.defined(e))`		true if `f[e]` has been explicitely set.
Definition undo	`f.undefine(e)`	`f.defined(e)`	remove `e` from the set of explicitely defined values	`f(e)` is equal to `f.default()` `f.defined(e) == false`
Default setting	`f.set_default(t)`		set default value to `t`	`! f.defined(e)` implies`f(e)` is equal to `t` `f.default()` is equal to `t`
Default access	`t = f.default()`	default has been set by constructor `f(g,t)` or by `f.set_default(t)`	set `t` to default value of `f`	`t` is equal to `f.default()`
write access	`t = f[e];`	`f` is bound to a grid `e.TheGrid() == f.TheGrid()`	create storage for a valueX if `! f.defined(e)`; assign `f(e)` to `t`.	`f(e)` is equal to `t`

Invariants

Default value

If not f.defined(e) then f(e) is equal to f.default()

Complexity Guarantees

Default construction takes constant time.
Construction from grid and construction with initalization both take constant time.
The set_default(t) operation takes constant time.
The access operations f(e), f[e] and the test f.defined(e) take at most logarithmic time, or amortized constant time, or expected constant time.
The memory requirements are at most proportional to the total number of different elements e for which f[e] has ever been called.

Models

partial_grid_function<E,T> -- a generic implementation of partial grid functions by hash tables, defined in partial-grid-function-hash.h.

Notes

This means that storage is also added if the access is meant read-only! Therefore, one should use the syntax t = f(e) in this case.