Project: Managing a DB of Accounts
Your job is to implement a database (accounts stored in memory) management (access mechanisms) system as specified. Your program should loop forever to iteratively take an integer input from the user, and output accordingly with the information of the records in the database. A valid account #'s can be as large as up to 1 billion.
• Levels of completion:
1. DB of 8 records, reject new accounts when full
|
User input x within ±1 billion
|
If account # |x| existing in DB
|
If account # |x| not existing in DB
|
Note
|
|
x < 0
|
Delete account # |x|
|
Report error, account not found
|
|
|
x > 0
|
Report found account #
|
Add new account # |x|
|
Reject when DB is full (with 8 accounts)
|
|
x = 0
|
Display all accounts
|
Sorted, from min to max
|
2. DB with n (≤ 256) records, LRU replacement policy
a) allow the user to initialize the size of DB (instead of 8) to be up to 256
b) no longer reject new account when DB is full: store the new account and replace the "oldest" according to Least Recently Use policy (add new account, found account both are considered as a recent Use. Display all account is not considered a Use for any account)
3. DB w/ binary search tree structure implementation
• Similarly to Level 2, allow the user to initialize the DB size (n):
• Rejecting new accounts upon full DB, 10pt. Implementing LRU replacement policy, 20pts.
• You are required to use a binary search tree structure to maintain the DB. (see https://en.wikipedia.org/wiki/Binary_search_tree)
• When displaying all the records, you will need to display the binary tree structure. For example, the tree shown here could be displayed as a list of all its nodes with two pointers (<- and ->) to the child nodes.
All: #1 #3 #4 #6 #7 #8 #10 #13 #14
B-Tree:
<- #1 ->
#1 <- #3 -> #6
<- #4 ->
#4 <- #6 -> #7
<- #7 ->
#3 <- #8 -> #10
<- #10 -> #14
#13 <- #14 ->