Go backward to Total Grid Function Concept
Go up to Grid Functions

### 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) impliesf(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
1. 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.