Prev Up
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.
See also
Grid Element Function   Grid Function   Mutable Grid Function   Container Grid Function   Total Grid Function  
Guntram Berti

Prev Up