CS2400 M3 Flashcards
What is an ADT Bag
Finite collection of objects in no order, and can contain duplicates.
- get # of items
- check for empty
- add/remove
How long do the user and producer need to wait to get to work?
As soon as they can agree on an interface, both sides can start development. Tunnel analogy.
Bag: Public methods
+getCurrentSize(): integer
+isEmpty(): boolean
+add(newEntry: T): boolean
+remove(): T
+remove(anEntry: T): boolean
+clear(): void
+getFrequencyOf(anEntry: T): integer
+contains(anEntry: T): boolean
+toArray(): T[]
Bag: private methods
-bag: T[]
-numberOfEntries: integer
-DEFAULT_CAPACITY: integer
Why would you make a private data field final?
To avoid any possibility of the user having control over data using the reference.
How to write constructor for array bag?
@SuppressWarnings(“unchecked”)
T[] tempBag = (T[])new Object[capacity];
bag = tempBag;
Bag .add method
If full: return false and don’t add
Else add new entry after the last entry and return true.
Safe code/assertion
Can be in comment form if not important, but for delicate, important code there are failsafes to ensure that certain variables MUST have certain values before proceeding.
What is a Linked Bag?
Another way to implement bag interface, but using nodes. Each node contains a data value and a “next” value.
Pros/cons of Linked Bags
- Can’t move backwards
- Takes up more space
+ Easier to transport
+ Generally faster to transport
Linked Add Method
2 cases: empty or not
newNode.next= firstNode;
firstNode = newNode;
numberOfEntries++;
Linked Remove Method
2 cases: specified or not
If unspecified return firstNode and remove its link.
If specified first swap with firstNode then remove.
Set
Similar to bag, but doesn’t allow duplicates & lacks a getFrequencyOf() method.
