Specification (d_array)
Definition
- statement of the definition of d_array… (see next slide)
Creation
- d_array<I,E> A;
- d_array<I,E> A(E x); creates an injective function a from I to the set of unused variable of type E, sets xdef to x and dom(A) to the empty set, and initializes A with a
Operation
- E& A[I i] returns the variable A(i)
- bool A.defined(I i) returns true if i in dom(A)…
- void A.undefined(I i) removes i from dom(A); {make i undefined}
Iteration
- forall_defined(i, A) {“the elements from dom(A) are successfully assigned to i”}
- forall(x, A) {“for all i in dom(A) the entries A[i] are sucessfully assigned to x”}
Implementation
- impl. by randomized search tree;
- Access in O(log dom(A)); O(dom(A)) space;