Link-Based Implementations of ADT Bag at National Taiwan University

SVVRL @ IM.NTU Link-Based Implementations The ADT Bag as an Example Yih-Kuen Tsay Dept. of Information Management National Taiwan University Based on [Carrano and Henry 2013] With Contributions by Ling-Chieh Kung 1 / 90

SVVRL @ IM.NTU Outline Nodes Implementations of Member Functions Constructors and Destructor Recursion and Some Remarks Operator Overloading Exception Handling Yih-Kuen Tsay DS 2017: Link-Based Implementations 2 / 90

SVVRL @ IM.NTU Link-Based Implementations Last time we implemented the ADT Bag with arrays. There are some drawbacks: Static arrays: The bag size is fixed. Dynamic arrays: Doubling the bag size requires a lot of copying and pasting. Here we will use pointers to do a link-based implementation. Bag items will be put on a list. On the list, each item is linked to the next item. Yih-Kuen Tsay DS 2017: Link-Based Implementations 3 / 90

SVVRL @ IM.NTU Nodes The type of an item is ItemType. template<typename ItemType> class BagInterface { public: virtual bool add(const ItemType& newEntry) = 0; // all other functions }; Source: Figure 4-1 [Carrano and Henry 2015] For each item, we will associate a pointer pointing to the next item-pointer pair. The combination of the item and pointer is often called a node. The pointer points to the next node, not the next item! Yih-Kuen Tsay DS 2017: Link-Based Implementations 4 / 90

SVVRL @ IM.NTU List of Nodes In effect, a list of nodes will be created to store items. Source: Figure 4-2 [Carrano and Henry 2015] Each node is linked to the next node. The pointer nextpoints to the next node. Yih-Kuen Tsay DS 2017: Link-Based Implementations 5 / 90

SVVRL @ IM.NTU The Class Node(1/4) template<class ItemType> class Node { private: ItemType item; Node<ItemType>* next; public: Node(); Node(const ItemType& anItem); Node(const ItemType& anItem, Node<ItemType>* nextNodePtr); void setItem(const ItemType& anItem); void setNext(Node<ItemType>* nextNodePtr); ItemType getItem() const ; Node<ItemType>* getNext() const ; }; Source: Figure 4-1 [Carrano and Henry 2015] Yih-Kuen Tsay DS 2017: Link-Based Implementations 6 / 90

SVVRL @ IM.NTU The Class Node(2/4) Constructors of Node: template<class ItemType> Node<ItemType>::Node() : next(nullptr) {} template<class ItemType> Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr) {} template<class ItemType> Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) : item(anItem), next(nextNodePtr) {} Yih-Kuen Tsay DS 2017: Link-Based Implementations 7 / 90

SVVRL @ IM.NTU The Class Node(3/4) Getters and setters of Node: template<class ItemType> void Node<ItemType>::setItem(const ItemType& anItem) { item = anItem; } template<class ItemType> void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr) { next = nextNodePtr; } template<class ItemType> ItemType Node<ItemType>::getItem() const { return item; } template<class ItemType> Node<ItemType>* Node<ItemType>::getNext() const { return next; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 8 / 90

SVVRL @ IM.NTU The Class Node(4/4) The class Nodehas getters and setters for all instance variables. It does no data hiding at all. Sometimes people implement Nodeas a structure. Member variables of a structure are by default public. Though they can be set to be private. Sometimes a better way is to set LinkedBaga friend of Node. Yih-Kuen Tsay DS 2017: Link-Based Implementations 9 / 90

SVVRL @ IM.NTU Outline Nodes Implementations of Member Functions Constructors and Destructor Recursion and Some Remarks Operator Overloading Exception Handling Yih-Kuen Tsay DS 2017: Link-Based Implementations 10 / 90

SVVRL @ IM.NTU The Class LinkedBag What should be contained in the class LinkedBag? Let s look at ArrayBagagain: itemCountis still needed. class ArrayBag : public BagInterface { private: static const int DEFAULT_CAPACITY = 6; string items[DEFAULT_CAPACITY]; int itemCount; int maxItems; // ... public: // ... }; Capacity-related members are not needed. Where to store our nodes? The 1stnode links to the 2nd. The ithnode linkes to the (i + 1)th. All we need is to store the 1st node, i.e., the head. Yih-Kuen Tsay DS 2017: Link-Based Implementations 11 / 90

SVVRL @ IM.NTU The Head Pointer headPtr An object of LinkedBagwill have an item counter itemCount. Its type is int. An object of LinkedBagwill have a head pointer headPtr. Source: Figure 4-5 [Carrano and Henry 2015] Its type is Node<itemType>*. It is a pointer, not a node. headPtris a static member; all other nodes are dynamic members. Yih-Kuen Tsay DS 2017: Link-Based Implementations 12 / 90

SVVRL @ IM.NTU The Class LinkedBag The basic elements of LinkedBag: template<class ItemType> class LinkedBag : public BagInterface<ItemType> { private: Node<ItemType>* headPtr; int itemCount; // something else public: // some constructors and destructor // functions defined in BagInterface, such as getCurrentSize(), // isEmpty(), add(), remove(), etc. }; Let s implement those functions first. Yih-Kuen Tsay DS 2017: Link-Based Implementations 13 / 90

SVVRL @ IM.NTU isEmpty()and getCurrentSize() Some member functions are straightforward. template<class ItemType> bool LinkedBag<ItemType>::isEmpty() const { return itemCount == 0; } template<class ItemType> int LinkedBag<ItemType>::getCurrentSize() const { return itemCount; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 14 / 90

SVVRL @ IM.NTU add() We define add()to add an item at the beginning of the list. template<class ItemType> bool LinkedBag<ItemType>::add(const ItemType& newEntry) { Node<ItemType>* newNodePtr = new Node<ItemType>(); newNodePtr->setItem(newEntry); newNodePtr->setNext(headPtr); headPtr = newNodePtr; itemCount++; return true; } Why? What if we add it at the end of the list? Source: Figure 4-6 [Carrano and Henry 2015] Yih-Kuen Tsay DS 2017: Link-Based Implementations 15 / 90

SVVRL @ IM.NTU toVector()and List Traversal (1/2) We still want to put all items into a vector. We need to traverse the list. With headPtr, we have the address of the first node. With headPtr->getNext(), we have the address of the second node. How to proceed? We need a location pointer curPtrto store a node address in each iteration. Let curPtr point to the first node in the list while curPtr is not a null pointer { Assign the data portion of the current node to the next element in a vector Set curPtr to the next pointer portion of the current node } Yih-Kuen Tsay DS 2017: Link-Based Implementations 16 / 90

SVVRL @ IM.NTU toVector()and List Traversal (2/2) template<class ItemType> vector<ItemType> LinkedBag<ItemType>::toVector() const { vector<ItemType> bagContents; Node<ItemType>* curPtr = headPtr; while(curPtr != nullptr) { bagContents.push_back(curPtr->getItem()); curPtr = curPtr->getNext(); // the above line is equivalent to: // Node<ItemType>* temp = curPtr->getNext(); // curPtr = temp } return bagContents; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 17 / 90

SVVRL @ IM.NTU curPtr = curPtr->getNext() Source: Figure 4-7 [Carrano and Henry 2015] Yih-Kuen Tsay DS 2017: Link-Based Implementations 18 / 90

SVVRL @ IM.NTU remove()(1/2) To remove an item, we will remove the first copy (the one closest to the head). First we locate that copy (if there is one). Then we rewrite the data portion of that node as that of the first node. Finally, we redirect headPtrto the second node and release the first node. Node<ItemType>* nodeToDeletePtr = headPtr; headPtr = headPtr->getNext(); // redirect delete nodeToDeletePtr; // release We will create a private function getPointerTo()to do the locating task. Recall that for ArrayBag, we have getIndexOf(). Yih-Kuen Tsay DS 2017: Link-Based Implementations 19 / 90

SVVRL @ IM.NTU remove()(2/2) template<class ItemType> bool LinkedBag<ItemType>::remove(const ItemType& anEntry) { Node<ItemType>* entryNodePtr = getPointerTo(anEntry); // step 1 bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr); if(canRemoveItem) { entryNodePtr->setItem(headPtr->getItem()); // step 2 Node<ItemType>* nodeToDeletePtr = headPtr; // step 3 headPtr = headPtr->getNext(); delete nodeToDeletePtr; nodeToDeletePtr = nullptr; itemCount--; } return canRemoveItem; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 20 / 90

SVVRL @ IM.NTU getPointerTo()(1/2) Given an item, we want to find the location of the first copy of this item. In ArrayBag, the location is represented by an array index. In LinkedBag, the location is represented by an address. We want to define the following private function (why private?): template<class ItemType> Node<ItemType>* LinkedBag<ItemType> ::getPointerTo(const ItemType& anEntry) const If the item does not exist, return nullptr. Note that returning a pointer is nothing but returning an address. The idea: Traverse the list, stop when a node contains the given item, and then return the address. Yih-Kuen Tsay DS 2017: Link-Based Implementations 21 / 90

SVVRL @ IM.NTU getPointerTo()(2/2) The implementation: template<class ItemType> Node<ItemType>* LinkedBag<ItemType> ::getPointerTo(const ItemType& anEntry) const { bool found = false; Node<ItemType>* curPtr = headPtr; while(!found && (curPtr != nullptr)) { if(anEntry == curPtr->getItem()) found = true; else curPtr = curPtr->getNext(); } return curPtr; } If the bag is empty, curPtrwill be set to nullptrat initialization. If the item does not exist, curPtrwill be set to nullptr when we assign curPtr- >getNext()to curPtr for the last time. In either case, nullptr will be returned. Yih-Kuen Tsay DS 2017: Link-Based Implementations 22 / 90

SVVRL @ IM.NTU contains() With getPointerTo(), contains()is easy. template<class ItemType> bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const { return (getPointerTo(anEntry) != nullptr); } Yih-Kuen Tsay DS 2017: Link-Based Implementations 23 / 90

SVVRL @ IM.NTU getFrequencyOf() A single traversal determines the frequency of a given item: template<class ItemType> int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const { int frequency = 0; Node<ItemType>* curPtr = headPtr; while(curPtr != nullptr) { if(anEntry == curPtr->getItem()) frequency++; curPtr = curPtr->getNext(); } return frequency; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 24 / 90

SVVRL @ IM.NTU clear() The function clear()releases all the dynamically allocated spaces: template<class ItemType> void LinkedBag<ItemType>::clear() { Node<ItemType>* nodeToDeletePtr = headPtr; while(headPtr != nullptr) { headPtr = headPtr->getNext(); delete nodeToDeletePtr; nodeToDeletePtr = headPtr; } itemCount = 0; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 25 / 90

SVVRL @ IM.NTU Outline Nodes Implementations of Member Functions Constructors and Destructor Recursion and Some Remarks Operator Overloading Exception Handling Yih-Kuen Tsay DS 2017: Link-Based Implementations 26 / 90

SVVRL @ IM.NTU Constructors and the Destructor As always, the class LinkedBagshould have some constructors. It should have a default constructor (and probably some other constructors with various parameters). It should have a copy constructor to do deep copy. It should have a destructor to deallocate dynamically allocated nodes. Yih-Kuen Tsay DS 2017: Link-Based Implementations 27 / 90

SVVRL @ IM.NTU The Class LinkedBag The basic elements of LinkedBag: template<class ItemType> class LinkedBag : public BagInterface<ItemType> { private: Node<ItemType>* headPtr; int itemCount; // ... public: LinkedBag(); // default constructor LinkedBag(const LinkedBag<ItemType>& aBag); // copy constructor virtual ~LinkedBag(); // destructor // ... }; Yih-Kuen Tsay DS 2017: Link-Based Implementations 28 / 90

SVVRL @ IM.NTU Default Constructor and Destructor The default constructors and destructor of LinkedBag: template<class ItemType> LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0) { } template<class ItemType> LinkedBag<ItemType>::~LinkedBag() { clear(); } The destructor is set virtual. Why? Yih-Kuen Tsay DS 2017: Link-Based Implementations 29 / 90

SVVRL @ IM.NTU Virtual Destructor Suppose the destructor is not virtual: class LinkedBag { // ... ~LinkedBag() { // some cleaning } }; class DerivedLB : public LinkedBag { // ... ~DerivedLB() { // more cleaning } } If DerivedLBhas its own dynamic contents, it needs to have its own destructor to clean them up. If we use polymorphism on the LinkedBag-DerivedLBrelationship: When we delete bto release the space, the behavior is undefined. LinkedBag* b = new DerivedLB(); // use b to do something delete b; // What will happen? LinkedBag s destructor may be called. To ensure the invocation of DerivedLB s destructor, set LinkedBag s destructor to be virtual. Yih-Kuen Tsay DS 2017: Link-Based Implementations 30 / 90

SVVRL @ IM.NTU Copy Constructor: Shallow Copy If we do not define a copy constructor by ourselves, the default copy constructor of LinkedBagwill be like: template<class ItemType> LinkedBag<ItemType>::LinkedBag (const LinkedBag<ItemType>& aBag) { itemCount = aBag->itemCount; headPtr = aBag->headPtr; } Source: Figure 4-8 (a) [Carrano and Henry 2015] Yih-Kuen Tsay DS 2017: Link-Based Implementations 31 / 90

SVVRL @ IM.NTU Copy Constructor: Deep Copy (1/3) What we want is deep copy: A new list of items should be dynamically created. Source: Figure 4-8 (b) [Carrano and Henry 2015] To do so, we need to define our own copy constructor for LinkedBag. Yih-Kuen Tsay DS 2017: Link-Based Implementations 32 / 90

SVVRL @ IM.NTU Copy Constructor: Deep Copy (2/3) The copy constructor of LinkedBag: template<class ItemType> LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag) { itemCount = aBag->itemCount; Node<ItemType>* origChainPtr = aBag->headPtr; if(origChainPtr == nullptr) headPtr = nullptr; else { headPtr = new Node<ItemType>(); headPtr->setItem(origChainPtr->getItem()); // continued on the next page Yih-Kuen Tsay DS 2017: Link-Based Implementations 33 / 90

SVVRL @ IM.NTU Copy Constructor: Deep Copy (3/3) The copy constructor of LinkedBag: // continued from the previous page Node<ItemType>* newChainPtr = headPtr; while(origChainPtr != nullptr) { origChainPtr = origChainPtr->getNext(); ItemType nextItem = origChainPtr->getItem(); Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem); newChainPtr->setNext(newNodePtr); newChainPtr = newChainPtr->getNext(); } newChainPtr->setNext(nullptr); } } Yih-Kuen Tsay DS 2017: Link-Based Implementations 34 / 90

SVVRL @ IM.NTU Outline Nodes Implementations of Member Functions Constructors and Destructor Recursion and Some Remarks Operator Overloading Exception Handling Yih-Kuen Tsay DS 2017: Link-Based Implementations 35 / 90

SVVRL @ IM.NTU Recursion Recursion can again be applied to implement member functions. E.g., when the function does a list traversal. Let s use getPointerTo()and toVector()to illustrate the idea. Other functions may also be implemented with recursion. Yih-Kuen Tsay DS 2017: Link-Based Implementations 36 / 90

SVVRL @ IM.NTU Recursive getPointerTo() getPointerTo() may be redefined as a recursive function. template<class ItemType> Node<ItemType>* LinkedBag<ItemType> ::getPointerTo(const ItemType& target, Node<ItemType>* curPtr) const { // pass headPtr as the 2nd argument // to traverse the whole bag Node<ItemType>* result = nullptr; if(curPtr != nullptr) { if(target == curPtr->getItem()) result = curPtr; else result = getPointerTo(target, curPtr->getNext()); } return result; } A new argument is added. Yih-Kuen Tsay DS 2017: Link-Based Implementations 37 / 90

SVVRL @ IM.NTU Recursive toVector()(1/2) Similarly, toVector() can be re-implemented: We add a recursive member function fillVector(). template<class ItemType> vector<ItemType> LinkedBag<ItemType> ::toVector() const { vector<ItemType> bagContents; fillVector(bagContents, headPtr); return bagContents; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 38 / 90

SVVRL @ IM.NTU Recursive toVector()(2/2) template<class ItemType> void LinkedBag<ItemType> ::fillVector(vector<ItemType>& bagContents, Node<ItemType>* curPtr) const { if (curPtr != nullptr) { bagContents.push_back(curPtr->getItem()); fillVector(bagContents, curPtr->getNext()); } } Why do we define fillVector()? How about getPointerTo()? Should fillVector()be private, public, or protected? Does recursion improve the efficiency of the program? Yih-Kuen Tsay DS 2017: Link-Based Implementations 39 / 90

SVVRL @ IM.NTU Polymorphism Regarding Bag (1/2) We have defined a pure virtual base class BagInterface. We have implemented two concrete derived classes ArrayBagand LinkedBag. BagInterface ArrayBag LinkedBag Thanks to polymorphism, we may now dynamically determine which implementation to use at run time. Yih-Kuen Tsay DS 2017: Link-Based Implementations 40 / 90

SVVRL @ IM.NTU Polymorphism Regarding Bag (2/2) int main() { BagInterface<string>* bagPtr = nullptr; char userChoice = 0; cin >> userChoice; if(userChoice == 'A') bagPtr = new ArrayBag<string>(); else bagPtr = new LinkedBag<string>(); bagTester(bagPtr); delete bagPtr; bagPtr = nullptr; return 0; } void bagTester (BagInterface<string>* bagPtr) { string items[] = {"aa", "bb", "cc"}; for(int i = 0; i < 3; i++) bagPtr->add(items[i]); cout << bagPtr->isEmpty(); cout << bagPtr->getCurrentSize(); bagPtr->remove("two"); cout << bagPtr->isEmpty(); cout << bagPtr->getCurrentSize(); } Yih-Kuen Tsay DS 2017: Link-Based Implementations 41 / 90

SVVRL @ IM.NTU Benefits of Link-Based Implementations Array-based Implementations Link-based Implementations A static array has a size limit Does not have a size limit A dynamic array requires a lot of time to increase the size May need to predict the maximum number of items Does not have a size limit No need to predict this May waste space Use space when you need it Yih-Kuen Tsay DS 2017: Link-Based Implementations 42 / 90

SVVRL @ IM.NTU Benefits of Array-Based Implementations Array-based Implementations Link-based Implementations Require less space to store an item Require more space to store an item A traversal is needed to access an item Accessing the ith items takes more time for larger i One may directly access any item Accessing each item requires a constant time Easier to write the program Harder to write the program Yih-Kuen Tsay DS 2017: Link-Based Implementations 43 / 90

SVVRL @ IM.NTU Comparisons Use arrays if: The maximum number of items is fixed and known. The maximum number of items may vary but will be small. Accessing efficiency is critical for you. Use links if: The number of items varies a lot. The data portion occupies huge space. Yih-Kuen Tsay DS 2017: Link-Based Implementations 44 / 90

SVVRL @ IM.NTU Outline Nodes Implementations of Member Functions Constructors and Destructor Recursion and Some Remarks Operator Overloading Exception Handling Yih-Kuen Tsay DS 2017: Link-Based Implementations 45 / 90

SVVRL @ IM.NTU Recall Our MyVector Class class MyVector { private: int n; double* m; public: MyVector() : n(0), m(NULL) { }; MyVector(int n, double m[]); MyVector(const MyVector& v); ~MyVector() { delete [] m; } void print() const; }; MyVector::MyVector(int n, double m[]) { this->n = n; this->m = new double[n]; for(int i = 0; i < n; i++) this->m[i] = m[i]; } MyVector::MyVector(const MyVector& v) { this->n = v.n; this->m = new double[n]; for(int i = 0; i < n; i++) this->m[i] = v.m[i]; } void MyVector::print() const { cout << "("; for(int i = 0; i < n - 1; i++) cout << m[i] << ", "; cout << m[n-1] << ")\n"; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 46 / 90

SVVRL @ IM.NTU Comparing MyVector Objects When we have many vectors, we may need to compare them. For vectors u and v: u = v if their dimensions are equal and ui= vifor all i. u < v if their dimensions are equal and ui< vifor all i. u v if their dimensions are equal and ui vifor all i. How to add member functions that do comparisons? Naturally, they should be instance rather than static functions. Yih-Kuen Tsay DS 2017: Link-Based Implementations 47 / 90

SVVRL @ IM.NTU Member Function isEqual() class MyVector { private: int n; double* m; public: MyVector() : n(0), m(NULL) { }; MyVector(int n, double m[]); MyVector(const MyVector& v); ~MyVector() { delete [] m; } void print() const; bool isEqual(const MyVector& v) const; }; bool MyVector::isEqual(const MyVector& v) const { if(this->n != v.n) return false; else { for(int i = 0; i < n; i++) { if(this->m[i] != v.m[i]) return false; } } return true; } Yih-Kuen Tsay DS 2017: Link-Based Implementations 48 / 90

SVVRL @ IM.NTU isEqual() Is Fine, But Adding the instance function isEqual()is fine. But it is not intuitive. If we could write if(a1 == a2), it would be great! Of course we cannot (without further definitions). The compiler does not know what to do to this statement. We need to define ==for MyVectorjust as we define member functions. In fact, ==has been overloaded for different data types. We may compare two ints, two doubles, one intand one double, etc. We will now define how ==should compare two MyVectors. This is called operator overloading. Yih-Kuen Tsay DS 2017: Link-Based Implementations 49 / 90

SVVRL @ IM.NTU Operator Overloading (1/2) Most operators (if not all) have been overloaded in the C++ standard. E.g., the division operator /has been overloaded. Divisions between integers is just different from divisions fractional values! Overloading operators for self-defined classes are not required. Each overloaded operator can be replaced by an instance function. However, it often makes programs clearer and the class easier to use. Yih-Kuen Tsay DS 2017: Link-Based Implementations 50 / 90