Skip to content

ADT Multimap implemented using Singly Linked Lists alocated dinamically

Notifications You must be signed in to change notification settings

vanpana/MultiMapSLL

Folders and files

NameName
Last commit message
Last commit date

Latest commit

d1677c7 Β· Jun 12, 2017

History

40 Commits
Jun 12, 2017
Jun 9, 2017
Jun 12, 2017
Jun 12, 2017
Jun 12, 2017
Jun 9, 2017
Jun 12, 2017
Jun 12, 2017
Jun 12, 2017
Jun 12, 2017
Jun 11, 2017
Jun 11, 2017
Jun 11, 2017
Jun 12, 2017
Jun 12, 2017
Jun 11, 2017
Jun 12, 2017
Jun 5, 2017
Jun 11, 2017
Jun 12, 2017
Jun 12, 2017
Jun 11, 2017
Jun 11, 2017
Jun 11, 2017
Jun 11, 2017
Jun 11, 2017
Jun 11, 2017

Repository files navigation

Bank Account and Transaction Management πŸ”₯πŸ”₯πŸ”₯

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 πŸ”₯

ADT Specification

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 }

ADT Interface

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 βˆƒ<k,vβ€² >∈m and mβ€² ∈M, m’ = m<k,v’>
|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βˆƒ<k,vβ€² >∈m
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

ADT Representation

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