/* Title: WeeBank * Author: John P. Spurgeon * Director's cut: 15 April 2018 * Available at: http://scribbledecobble.blogspot.com/2018/04/wee-bank.html * * EXCLAIMER * * The names, algorithms, and comments below are the products of the author's memory and * imagination or are the result of reading books or surfing the internet. Any resemblance * to actual persons, living or dead, or actual events might be an allusion. No drugs * (other than caffeine and maybe one or two BEAK BREAKER/BENDERS) were used during the * production of this program. */ // PART 0. IN A GALAXY FAR, FAR AWAY... // With a little help from our friends import java.util.Collections; import java.util.Comparator; import java.util.Stack; import java.util.List; import java.util.LinkedList; import java.util.ArrayList; // PART 1. INTRODUCING... /******************/ /* Insertion Sort */ /******************/ final class InsertionSort { // Exercise: Write insertIntoMultiset. public static <E> boolean insertIntoSet(E element, List<E> sortedSet, Comparator<E> cmp) { final int n = sortedSet.size(); int i = 0; while (i < n) { int result = cmp.compare(sortedSet.get(i), element); if (result == 0) return false; else if (result > 0) break; else i++; } sortedSet.add(i, element); return true; } } /*****************/ /* Binary Search */ /*****************/ interface Fun<X, Y> { Y apply(X element); } /* "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" * * Posted by Joshua Bloch on Friday, June 02, 2006 at * https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html */ final class BinarySearch { /* Ponder These: * * - When might a simple linear search be better? (What about the size of the list?) * - What values of the so-called sortedSet parameter could cause this method to fail? * - What type of List<E> object would you definitely not want to pass to this method? */ public static <E, V> int getIndex(V value, List<E> sortedSet, Fun<E, V> f, Comparator<V> cmp) { int i, lower = 0, upper = sortedSet.size() - 1; while (upper >= lower) { i = lower + ((upper - lower) / 2); // Ponder This: Why not (upper + lower) / 2 ? E element = sortedSet.get(i); int result = cmp.compare(value, f.apply(element)); if (result == 0) return i; else if (result < 0) upper = i - 1; else lower = i + 1; } return -1; } public static <E, V extends Comparable<V>> int getIndex(V value, List<E> sortedSet, Fun<E, V> f) { Comparator<V> cmp = (V v1, V v2) -> v1.compareTo(v2); return getIndex(value, sortedSet, f, cmp); } } // PART 2. TWIN SISTERS PICTURES (a virtual company) PRESENTS... /*******************************/ /* WeeBank: A New Feature Film */ /*******************************/ public class WeeBank // Our motto is too small to matter. { public static void main(String[] args) { final int n = args.length; final int numHolders = n == 2 ? Integer.parseInt(args[0]) : 16; final int numTransactions = n == 2 ? Integer.parseInt(args[1]) : 1024; final CommandProcessingUnit cpu = new CommandProcessingUnit(); final String[] lines = (n == 0 || n == 2) ? Writer.getScript(numHolders, numTransactions) : args; for (String line : lines) // Action! { BackupAcct backupAcct = null; switch(line) { case Keywords.CREATE_BANK: cpu.createBank(); break; case Keywords.OPEN_EXPOSED_CHECKING: backupAcct = cpu.openExposedCheckingAcct(); cpu.setBackupAcct(backupAcct); break; case Keywords.OPEN_PROTECTED_CHECKING: cpu.openProtectedCheckingAcct(); cpu.setBackupAcct(null); break; case Keywords.OPEN_SAVINGS: backupAcct = cpu.openSavingsAcct(); cpu.setBackupAcct(backupAcct); break; case Keywords.DEPOSIT: cpu.makeDeposit(); break; case Keywords.WITHDRAW: cpu.makeWithdrawal(); break; default: cpu.pushString(line); break; } } Banks.display(); // screening } } // PART 3. STARING... /*******************************************************************/ /* Banks (the personhood, not the famous metropolis) */ /* See also: https://en.wikipedia.org/wiki/Citizens_United_v._FEC */ /*******************************************************************/ /* We are uncovering better ways of profiting * by doing it and sabotaging others who do it. * Through this work we have come to value: * * Automated processes and tools over life * Share holders over account holders * Executives over managers over customers * Collecting fees over paying interest * * That is, while the items on the right are necessary, * the items on the left are to die for. * * (Not signed or said by dead board misdirectors.) */ final class Banks { public static final BankComparator bankComparator = new BankComparator(); private static final ArrayList<Bank> sortedBankSet = new ArrayList<Bank>(); public static Bank getBank(Integer routingNum) { Fun<Bank, Integer> f = (Bank b) -> (Integer)b.getRoutingNum(); final int i = BinarySearch.getIndex(routingNum, sortedBankSet, f); if (i < 0) Error.illegalArg("Bad routing number."); return sortedBankSet.get(i); } public static boolean createBank(int routingNum, String bankName) { Bank bank = new Bank(routingNum, bankName); return InsertionSort.insertIntoSet(bank, sortedBankSet, Banks.bankComparator); } public static void display() { for (Bank bank : sortedBankSet) System.out.println(bank); } } final class Bank { /* See: https://en.wikipedia.org/wiki/ABA_routing_transit_number * See also: https://en.wikipedia.org/wiki/Knuth_reward_check */ private final int routingNum; private final String bankName; private final List<Account> sortedAcctSet = new ArrayList<Account>(); private final List<Holder> sortedHolderSet = new ArrayList<Holder>(); private final CustomerService customerService; private final BankManager manager; public Bank(int routingNum, String bankName) { this.bankName = bankName; this.routingNum = routingNum; this.customerService = new CustomerService(sortedHolderSet); this.manager = new BankManager(this, customerService, sortedAcctSet); } public final BankManager getManager() { return manager; } public final int getRoutingNum() { return routingNum; } public final String getBankName() { return bankName; } public final boolean equals(Object that) { // System.out.println("Comparing " + this.toString() + " and " + that.toString()); if (that == null) return false; if (!Bank.class.isAssignableFrom(that.getClass())) return false; final Bank other = (Bank) that; return this.routingNum == other.routingNum; } public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Bank: " + bankName + "\n"); sb.append("Routing number: " + routingNum + "\n"); for (Account acct : sortedAcctSet) sb.append(acct.toString()); return sb.toString(); } } final class BankManager { private final Bank bank; private final CustomerService customerService; private final List<Account> sortedAcctSet; public BankManager(Bank bank, CustomerService customerService, List<Account> accounts) { this.bank = bank; this.customerService = customerService; sortedAcctSet = accounts; } public final ExposedCheckingAcct openExposedCheckingAcct(int acctNum, String holderId) { Holder holder = customerService.getOrCreateHolder(holderId); ExposedCheckingAcct acct = new ExposedCheckingAcct(bank, acctNum, holder); return addAccount(acct, holder) ? acct : null; } public final ProtectedCheckingAcct openProtectedCheckingAcct(int acctNum, String holderId, BackupAcct backup) { Holder holder = customerService.getOrCreateHolder(holderId); ProtectedCheckingAcct acct = new ProtectedCheckingAcct(bank, acctNum, holder, backup); return addAccount(acct, holder) ? acct : null; } public final SavingsAcct openSavingsAcct(int acctNum, String holderId) { Holder holder = customerService.getOrCreateHolder(holderId); SavingsAcct acct = new SavingsAcct(bank, acctNum, holder); return addAccount(acct, holder) ? acct : null; } public final Account getAccount(Integer acctNum) { Fun<Account, Integer> f = (Account a) -> (Integer)a.getAcctNum(); final int i = BinarySearch.getIndex(acctNum, sortedAcctSet, f); if (i < 0) Error.illegalArg("Bad account number."); return sortedAcctSet.get(i); } private final boolean addAccount(Account acct, Holder holder) { if (InsertionSort.insertIntoSet(acct, sortedAcctSet, Accounts.acctComparator)) { customerService.addHolder(holder); holder.addAccount(acct); return true; } return false; } } final class CustomerService { private final List<Holder> sortedHolderSet; public CustomerService(List<Holder> holders) { sortedHolderSet = holders; } public final int getHolderIndex(String holderId) { Fun<Holder, String> f = (Holder h) -> h.getId(); return BinarySearch.getIndex(holderId, sortedHolderSet, f); } public final boolean addHolder(Holder holder) { if (getHolderIndex(holder.getId()) >= 0) return false; return InsertionSort.insertIntoSet(holder, sortedHolderSet, Holders.holderIdComparator); } public final Holder getOrCreateHolder(String holderId) { final int i = getHolderIndex(holderId); return i < 0 ? new Holder(holderId) : sortedHolderSet.get(i); } } // PART 4. AND STARING... /************/ /* Accounts */ /************/ /* Entourage */ class Accounts { public static final Comparator<Account> acctComparator = new AcctComparator(), /* For future use... */ acctBalanceComparator = new AcctBalanceComparator(), reverseAcctBalanceComparator = Collections.reverseOrder(acctBalanceComparator); } /** Something (an account) that may be overdrawn and can thereby incur fees. */ interface Overdraftable // This is risky business. { int getOverdraftCount(); } /** An account that may be used for so-called overdraft protection. */ interface BackupAcct // Be sure to charge for this. { int getAcctNum(); int getRoutingNum(); boolean hasSufficientFunds(int requestedCents); boolean withdraw(int cents); } /* Leading Actor */ abstract class Account { private Holder holder; private int acctNum; private int balance; private Bank bank; protected Account(Bank bank, int acctNum, Holder holder) { if (bank == null) Error.illegalArg("bank cannot be null"); if (holder == null) Error.illegalArg("holder cannot be null"); if (acctNum < 0) Error.illegalArg("account number cannot be negative"); this.bank = bank; this.acctNum = acctNum; this.holder = holder; } public abstract double getInterestRate(); public Holder getHolder() { return holder; } public final int getAcctNum() { return acctNum; } public final int getRoutingNum() { return bank.getRoutingNum(); } public final int getBalance() { return balance; } public final boolean hasSufficientFunds(int requestedCents) { return balance >= requestedCents; } public final void deposit(int cents) { if (cents <= 0) Error.illegalArg("Cents must be greater than zero."); int newBalance = balance + cents; if (newBalance <= balance) Error.overflow(); balance = newBalance; } public boolean withdraw(int cents) { if (cents <= 0) Error.illegalArg("Cents must be greater than zero."); int newBalance = balance - cents; if (newBalance >= balance) Error.overflow(); balance = newBalance; return true; } public final boolean equals(Object that) { // System.out.println("Comparing " + this.toString() + " and " + that.toString()); if (that == null) return false; if (!Account.class.isAssignableFrom(that.getClass())) return false; final Account other = (Account) that; return this.bank.equals(other.bank) && this.acctNum == other.getAcctNum(); } public String toString() { StringBuilder sb = new StringBuilder(); sb.append("\n" + Strings.TAB + "Account #: " + acctNum); sb.append("\n" + Strings.TAB + "Account holder: " + holder.getId()); sb.append("\n" + Strings.TAB + "Balance: " + (balance/100.0) + "\n"); return sb.toString(); } } /* Account Understudies: Checking Accounts */ abstract class CheckingAcct extends Account implements Overdraftable { private int overdraftCount = 0; protected CheckingAcct(Bank bank, int acctNum, Holder holder) { super(bank, acctNum, holder); } public final double getInterestRate() { return 0.005; } public final int getOverdraftCount() { return overdraftCount; } public boolean withdraw(int cents) { boolean succeeded = super.withdraw(cents); if (succeeded && getBalance() < 0) { if (++overdraftCount < 0) Error.overflow(); } return succeeded; } public String toString() { return super.toString() + Strings.TAB + "Overdraft count: " + overdraftCount + "\n"; } } final class ExposedCheckingAcct extends CheckingAcct implements BackupAcct { public ExposedCheckingAcct(Bank bank, int acctNum, Holder holder) { super(bank, acctNum, holder); } public final boolean withdraw(int cents) { return super.withdraw(cents); // Ponder This: Why bother with this? } public String toString() { return "\n" + Strings.TAB + "Checking Account" + super.toString(); } } final class ProtectedCheckingAcct extends CheckingAcct { private final BackupAcct backup; // provides overdraft protection public ProtectedCheckingAcct(Bank bank, int acctNum, Holder holder, BackupAcct backup) { super(bank, acctNum, holder); if (backup == null) Error.illegalArg("backup cannot be null"); this.backup = backup; } public final boolean withdraw(int cents) { tryToEnsureSufficientFunds(cents); return super.withdraw(cents); } private final void tryToEnsureSufficientFunds(int requestedCents) { final int balance = getBalance(); if (requestedCents > balance) { final int deficit = requestedCents - balance; if (backup.hasSufficientFunds(deficit) && backup.withdraw(deficit)) deposit(deficit); } } public String toString() { return "\n" + Strings.TAB + "Checking Account" + super.toString() + Strings.TAB + "Protected by: " + backup.getAcctNum() + "\n"; } } /* Account Understudies: Savings Account */ final class SavingsAcct extends Account implements BackupAcct { public SavingsAcct(Bank bank, int acctNum, Holder holder) { super(bank, acctNum, holder); } public final double getInterestRate() { return 0.015; } public final boolean withdraw(int cents) { if (!hasSufficientFunds(cents)) return false; return super.withdraw(cents); } public String toString() { return "\n" + Strings.TAB + "Savings Account" + super.toString(); } } // PART 5. SUPPORTING CHARACTERS... /*******************/ /* Account Holders */ /*******************/ /* Holders are just extras. They don't do much. */ final class Holders { public static Comparator<Holder> holderIdComparator = new HolderIdComparator(); } class Holder { private String holderId; private List<Account> sortedAcctSet = new LinkedList<Account>(); public Holder(String holderId) { if (holderId == null) Error.illegalArg("holder id cannot be null"); if (holderId.length() == 0) Error.illegalArg("holder id length cannot be zero"); this.holderId = holderId; } public final boolean addAccount(Account acct) { if (acct == null) Error.illegalArg("account cannot be null"); return InsertionSort.insertIntoSet(acct, sortedAcctSet, Accounts.acctComparator); } public final String getId() { return holderId; } } // PART 6. ROLL CREDITS... /*******/ /* CPU */ /*******/ /* A gaffer in the motion picture industry and on a television crew is the head electrician, * responsible for the execution (and sometimes the design) of... * * https://en.wikipedia.org/wiki/Gaffer_(filmmaking) */ final class CommandProcessingUnit { private Stack<String> argStack = new Stack<String>(); private BackupAcct backupAcct; private int popInt() { return Integer.parseInt(argStack.pop()); } private String popString() { return argStack.pop(); } public void pushString(String s) { argStack.push(s); } public void setBackupAcct(BackupAcct acct) { backupAcct = acct; } public void createBank() { int routingNum = popInt(); String bankName = popString(); Banks.createBank(routingNum, bankName); } public BackupAcct openExposedCheckingAcct() { int acctNum = popInt(); int routingNum = popInt(); String holderId = popString(); Bank bank = Banks.getBank(routingNum); return bank.getManager().openExposedCheckingAcct(acctNum, holderId); } public void openProtectedCheckingAcct() { int acctNum = popInt(); int routingNum = popInt(); String holderId = popString(); Bank bank = Banks.getBank(routingNum); bank.getManager().openProtectedCheckingAcct(acctNum, holderId, backupAcct); } public BackupAcct openSavingsAcct() { int acctNum = popInt(); int routingNum = popInt(); String holderId = popString(); Bank bank = Banks.getBank(routingNum); return bank.getManager().openSavingsAcct(acctNum, holderId); } public void makeDeposit() { int cents = popInt(); int acctNum = popInt(); int routingNum = popInt(); Bank bank = Banks.getBank(routingNum); Account acct = bank.getManager().getAccount(acctNum); acct.deposit(cents); } public void makeWithdrawal() { int cents = popInt(); int acctNum = popInt(); int routingNum = popInt(); Bank bank = Banks.getBank(routingNum); Account acct = bank.getManager().getAccount(acctNum); acct.withdraw(cents); } } /***************/ /* Comparators */ /***************/ /* After the attachment phase is complete..., the physical auditions begin for all of the * remaining roles. During this time, depending on the budget of the film, they could have * what is called "pre-screens" where you audition only for a casting director (or associate) * to see if the actor is right for the material.... The resulting list of actors who were * selected to play a character for a production, is called a cast list ... A key intern will * work with many busy casting directors sorting mail, ..., help[ing] actors sign in, and * keep[ing] the flow of talent going in and out of the casting room as smooth[ly] as possible. * * https://en.wikipedia.org/wiki/Casting_(performing_arts) */ final class HolderIdComparator implements Comparator<Holder> { public int compare(Holder h1, Holder h2) { return h1.getId().compareTo(h2.getId()); } } final class BankComparator implements Comparator<Bank> { public int compare(Bank b1, Bank b2) { return Integer.compare(b1.getRoutingNum(), b2.getRoutingNum()); } } final class AcctComparator implements Comparator<Account> { public int compare(Account a1, Account a2) { int result = Integer.compare(a1.getRoutingNum(), a2.getRoutingNum()); if (result == 0) { result = Integer.compare(a1.getAcctNum(), a2.getAcctNum()); } return result; } } final class AcctBalanceComparator implements Comparator<Account> { public int compare(Account a1, Account a2) { return Integer.compare(a1.getBalance(), a2.getBalance()); } } /*******************/ /* Bits and Pieces */ /*******************/ /* Scenic Designers */ final class Keywords { public static final String CREATE_BANK = "create_bank", DEPOSIT = "deposit", OPEN_EXPOSED_CHECKING = "open_exposed_checking", OPEN_PROTECTED_CHECKING = "open_protected_checking", OPEN_SAVINGS = "open_savings", WITHDRAW = "withdraw"; } final class Strings { public static final String SEP = ","; // separator public static final String TAB = " "; public static final String[] POS_DIGITS = { "1", "2", "3", "4", "5", "6", "7", "8", "9" }; public static final String[] TEN_DIGITS = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }; public static final String[] FIRST_NAMES = { "Alan", "Barbara", "Bob", "David", "Don", "Fran", "John", "Judea", "Juris", "Ken", "Leslie", "Martin", "Marvin", "Niklaus", "Tony", "Whitfield" }; public static final String[] LAST_NAMES = { "Allen", "Diffie", "Floyd", "Hartmanis", "Hellman", "Hennessy", "Hoare", "Knuth", "Lamport", "Liskov", "Minsky", "Patterson", "Pearl", "Perlis", "Thompson", "Wirth" }; public static final String[] BANK_NAMES = { "DoA", "MoMoneyChaser", "WellGoFar", "UrbanCollection", "MenNGoldNBags" }; public static final String[] ROUTING_NUMBERS = { "503087512", "908170897", "275653426", "154509612", "677765703" // Ponder This: Which number is missing?? }; public static final String[] TRANSACTIONS = { Keywords.DEPOSIT, Keywords.WITHDRAW }; public static final String[] CREATE_EXPOSED_ACCT_COMMANDS = { /* Keywords.OPEN_EXPOSED_CHECKING, */ Keywords.OPEN_SAVINGS }; public static final String[] CREATE_CHECKING_ACCT_COMMANDS = { Keywords.OPEN_EXPOSED_CHECKING, Keywords.OPEN_PROTECTED_CHECKING }; } final class Tokens { public static String getRandom(String[] strings) { return strings[(int)(strings.length * Math.random())]; } public static String getRandom(List<String> strings) { return strings.get((int)(strings.size() * Math.random())); } private static String getRandomHolderId() { return getRandom(Strings.FIRST_NAMES) + getRandom(Strings.LAST_NAMES); } private static String getRandomNum(int n, String[] digits) { StringBuilder sb = new StringBuilder(); while (n-- > 0) sb.append(getRandom(digits)); return sb.toString(); } private static String getRandomCents() { int n = (int)(3 * Math.random()); return getRandomNum(3, Strings.POS_DIGITS) + getRandomNum(n, Strings.TEN_DIGITS); } private static String getRandomAcctNum() { return getRandomNum(1, Strings.POS_DIGITS) + getRandomNum(5, Strings.TEN_DIGITS); } private static String getRandomRoutingNum() { return getRandom(Strings.ROUTING_NUMBERS); } public static String getRandomHolderBankInfo() { return getRandomHolderId() + Strings.SEP + getRandomRoutingNum(); } public static String getRandomAccountInfo(String holderBankInfo) { /* Ponder These: * * - What could go wrong? Hint: getRandomAcctNum(). * - How would you know if it did? * - What are the odds? * - What are the consequences? * * Exercise: Eliminate the possibility. Hint: getUniqueAcctNum(). */ return holderBankInfo + Strings.SEP + getRandomAcctNum(); } public static String getRandomTransaction() { return getRandomCents() + Strings.SEP + getRandom(Strings.TRANSACTIONS); } } /***************/ /* Head Writer */ /***************/ /* Don't Bother Me. I'm creating. */ final class Writer { private static List<String> createAcctCommands; private static List<String> transactionInfo; private static String getCreateBankCommand(int i) { return Strings.BANK_NAMES[i] + Strings.SEP + Strings.ROUTING_NUMBERS[i] + Strings.SEP + "create_bank"; } private static String createExposedAcctCommand(String acctInfo) { return acctInfo + Strings.SEP + Tokens.getRandom(Strings.CREATE_EXPOSED_ACCT_COMMANDS); } private static String createCheckingAcctCommand(String acctInfo) { return acctInfo + Strings.SEP + Tokens.getRandom(Strings.CREATE_CHECKING_ACCT_COMMANDS); } private static void storyboard(int n) { createAcctCommands = new LinkedList<String>(); transactionInfo = new LinkedList<String>(); while (--n >= 0) { String holderBankInfo = Tokens.getRandomHolderBankInfo(); String a1 = Tokens.getRandomAccountInfo(holderBankInfo); String t1 = a1.substring(a1.indexOf(Strings.SEP) + 1); String a2 = Tokens.getRandomAccountInfo(holderBankInfo); String t2 = a2.substring(a2.indexOf(Strings.SEP) + 1); createAcctCommands.add(createExposedAcctCommand(a1)); createAcctCommands.add(createCheckingAcctCommand(a2)); transactionInfo.add(t1); transactionInfo.add(t2); } } private static String getCreateBankCommands() { final int len1 = Strings.BANK_NAMES.length; final int len2 = Strings.ROUTING_NUMBERS.length; int n = Math.min(len1, len2); StringBuilder sb = new StringBuilder(); while (--n > 0) sb.append(getCreateBankCommand(n) + Strings.SEP); if (n == 0) sb.append(getCreateBankCommand(n)); return sb.toString(); } private static String getCreateAcctCommands() { StringBuilder sb = new StringBuilder(); for (String cmd : createAcctCommands) sb.append(Strings.SEP + cmd); return sb.toString(); } private static String getTransactionCommands(int m) { StringBuilder sb = new StringBuilder(); while (m-- > 0) { String cmd = Strings.SEP + Tokens.getRandom(transactionInfo) + Strings.SEP + Tokens.getRandomTransaction(); sb.append(cmd); } return sb.toString(); } public static String[] getScript(int numHolders, int numTransactions) { StringBuilder sb = new StringBuilder(); storyboard(numHolders); sb.append(getCreateBankCommands()); sb.append(getCreateAcctCommands()); sb.append(getTransactionCommands(numTransactions)); return sb.toString().split("\\" + Strings.SEP); } } /******************/ /* Error Handling */ /******************/ /* Producer: I'm the only one allowed to say 'Cut!' */ final class Error { private static final String CUT = "Cut! "; public static void illegalArg(String message) { throw new IllegalArgumentException(CUT + message); } public static void illegalState(String message) { throw new IllegalStateException(CUT + message); } public static void overflow() { Error.overflow("Overflow detected."); } public static void overflow(String message) { throw new ArithmeticException(CUT + message); } }