A set of pairs consists of \(\texttt{key}-\texttt{value}\) pairs where the keys belong to a given type \(\texttt{key_type}\) and values to another type \(\texttt{val_type}\).
The set \(\{\texttt{<size-170>, <age-18>, <weight-71>, <number-12>}\}\) is an example of a set of pairs in which \(\texttt{key_type} \in \{\texttt{size, age, weight, number}\}\) and \(\texttt{val_type} \in \{\texttt{integer}\}\).
Note that a key appears only once in a set and pairs are not sorted.
We define \(\texttt{set of pairs}\) ADT by including the operators that:
- Creates an empty set of pairs;
- Tests if a set is empty;
- Adds a key-value pair;
- Removes a pair;
- Replaces the value associated with a key by another value;
- Returns the value associated to a key;
- Tests the membership of a key to a set;
- Counts a set pairs.
Type: \(\texttt{set_pairs(pair)}\) where \(\texttt{ pair = <key_type, val_type>}\)
Use: \(\texttt{key_type, val_type, Boolean, integer}\)
Functions:
\(\begin{array}{p{1cm} l l l} & \textbf{Create} & & \rightarrow \texttt{set_pairs}\\ & \textbf{Is_empty} & \texttt{set_pairs} & \rightarrow \texttt{Boolean}\\ & \textbf{Delete} & \texttt{set_pairs} \times \texttt{key_type} & \rightarrow \texttt{set_pairs}\\ & \textbf{Add} & \texttt{set_pairs} \times \texttt{pair} & \rightarrow \texttt{set_pairs}\\ & \textbf{Replace} & \texttt{set_pairs} \times \texttt{key_type} \times \texttt{val_type} & \rightarrow \texttt{set_pairs}\\ & \textbf{Get_val} & \texttt{set_pairs} \times \texttt{key_type} & \rightarrow \texttt{val_type}\\ & \textbf{Belong} & \texttt{set_pairs} \times \texttt{key_type} & \rightarrow \texttt{Boolean}\\ & \textbf{Number_pairs} & \texttt{set_pairs} & \rightarrow \texttt{integer} \end{array}\)
Preconditions:
Let \(\texttt{E}\) a \(\texttt{set$\_$pairs}\) and \(\texttt{<c,v>}\) a \(\texttt{pair}\),
\(\begin{array}{p{1cm} l l} & \texttt{Add(E,<c,v>)} & \text{defined iff } \texttt{Belong(E,c) = false}\\ & \texttt{Replace(E,c,v)} & \text{defined iff } \texttt{Belong(E,c) = true}\\ & \texttt{Delete(E,c)} & \text{defined iff } \texttt{Belong(E,c) = true}\\ & \texttt{Get$\_$val(E,c)}& \text{defined iff } \texttt{Belong(E,c) = true} \end{array}\)
Note that \(\texttt{Replace}\), \(\texttt{Delete}\) and \(\texttt{get$\_$val}\) functions aren't applied to an empty set of pairs.
You are asked to complete the constructors and axioms paragraphs.
Difficulty level
This exercise is mostly suitable for students
Let E be set_pairs, <c,v1> a pair and v2 a value
Constructors: Create and Add
Is_empty(Create ()) = true
Is_empty (Add(E,<c,v1>)) = false
Replace(Add(E,<c,v1>), c, v2) = Add(E,<c,v2>)
Get_val(Add(E,<c,v1>), c) = v1
Belong(Create(), c) = false
Belong(Add(E,<c,v1>), c) = true
Number_pairs(Create()) = 0
Number_pairs(Add(E,<c,v1>)) = Number_pairs(E) + 1
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Search for saddle point