ADT Multimap implemented using Singly Linked Lists alocated dinamically
The problem
Create an application used to store and manage a bank account database, each client having an unique ID. For every client, the application will store the dates in which the client made a transaction. The application must be able to add, remove and print all transactions for all the clients. Also, it must be able to check if a user had any transaction on a given date.
Problem solved using a Multimap implemented using Singly Linked Lists alocated dinamically
See Specification
See Interface
See Representation
o Multimap = {m| m is a map with elements e = (k,v), where k ∈ TKey and v ∈ set on SLL}
o Set = S = {s|s is a set with elements of the type TElement}
o TKey -> each key has one single associated value and keys have to be unique.
The interface of TKey contains the following operations:
• assignment (k1 ← k2)
♣ pre: k1, k2 ∈ TKey
♣ post: k′1 = k2
• equality test (k1 = k2)
♣ pre: k1, k2 ∈ TKey
♣ post:
True, if k1 = k2
False, otherwise
TElement -> the general element in containers
The interface of TElem contains the following operations:
• assignment (e1 ← e2)
♣ pre: e1, e2 ∈ TElement
♣ post: e′1 = e2
• equality test (e1 = e2)
♣ pre: e1, e2 ∈ TElement
♣ post:
True, if e1 = e2
False, otherwise
o Iterator = { it | it – iterator over Multimap }
Multimap
• init(m):
♣ descr: creates a new empty map
♣ pre: True
♣ post: m∈M, m is an empty map
• destroy(m):
♣ descr: destroys a map
♣ pre: m∈M
♣ post: m was destroyed
• add(m,k,v):
♣ descr: add a new key-value pair to the map (the operation can be called put as well)
♣ pre: m ∈ M, k ∈ TKey, v ∈ set on SLL
♣ post: m′ ∈ M,m′ = m ∪ < k,v >
• remove(m,k,v):
♣ descr: removes a pair with a given key from the map
♣ pre: m ∈ M, k ∈ TKey
♣ post: v ∈ TValue
v = v’, if ∃
|0, otherwise
• search(m,k,v):
♣ descr: searches for the value associated with a given key in the map
♣ pre: m ∈ M, k ∈ TKey
♣ post: v ∈ Set on SLL
v = v’, if∃
0, otherwise
• iterator(m, it ):
♣ descr: returns an iterator for a map
♣ pre: m ∈ M
♣ post: it Iterator, it – iterator over m
• size(m):
♣ descr: returns the number of pairs from the map
♣ pre: m ∈ M
♣ post: size <- the number of pairs from m
• keys(m,s):
♣ descr: returns the set of keys from the map
♣ pre: m ∈ M
♣ post: s ∈ S, s is the set of all keys from m
• values(m,b):
♣ descr: returns a bag with all the values from the map
♣ pre: m ∈ M
♣ post: b ∈ B, b is the bag of all values from m
• add(m,s):
♣ descr: returns the set of pairs from the map
♣ pre: m ∈ M
♣ post: s ∈ S, s is the set of all pairs from m s
Iterator
• init(m):
♣ pre: m M
♣ post: it Iterator , it – iterator over m pointing to ”first element”
• next(it):
♣ pre: it Iterator, it is a valid iterator
♣ post: it′ - pointing to the next element
• valid( it ):
♣ pre: it Iterator
♣ post:
valid(it) = True, if it valid
False, otherwise
• getCurrent(it, v):
♣ pre: it Iterator
♣ post: e(k,v) Multimap, e – the current pair pointed by it
Multimap (Implemented on a singly linked list with dynamic allocation)
• cap : Integer
• k: TKey
• v: Set on SLL
• next: Integer[]
• head: Integer
Iterator
• m : ↑Multimap
• currentPos : ↑TKey