Code Fragment (Host by Theang Yinh)
Code Fragment (Host by Theang Yinh)
Code Fragment (Host by Theang Yinh)
Passenger::Passenger() { name = "--NO NAME--"; mealPref = NO_PREF; isFreqFlyer = false; freqFlyerNo = "NONE"; } // default constructor
// constructor given member values Passenger::Passenger(const string& nm, MealType mp, string ffn) { name = nm; mealPref = mp; isFreqFlyer = (ffn != "NONE"); // true only if ffn given freqFlyerNo = ffn; } // copy constructor Passenger::Passenger(const Passenger& pass) { name = pass.name; mealPref = pass.mealPref; isFreqFlyer = pass.isFreqFlyer; freqFlyerNo = pass.freqFlyerNo; }
// avoid self// delete old // set new size // allocate new array { // copy the
friend class Matrix; Matrix access to coord }; class Matrix { private: double a[3][3]; public: // ... Vector multiplyBy(const Vector& v) { * v) Vector w(0, 0, 0); for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) w.coord[i] += a[i][j] * v.coord[j]; return w; } };
#ifndef CREDIT_CARD_H expansion #define CREDIT_CARD_H #include <string> #include <iostream> using std::string; accessible class CreditCard { private: string number; string name; int limit; double balance; public:
// allow
// a 3x3 array
// multiply (a
// avoid repeated
// // // // //
private member data credit card number card owner's name credit limit credit card balance
// standard constructor CreditCard(string no, string nm, int lim, double bal=0); // accessors functions string getNumber() const { return number; } string getName() const { return name; } double getBalance() const { return balance; } int getLimit() const { return limit; } // update functions bool chargeIt(double price); // make a charge void makePayment(double payment) { balance -= payment; } }; // print card information std::ostream& operator<<(std::ostream& out, const CreditCard& c); #endif // make a payment
// allocate 3 new cards wallet[0] = new CreditCard("5391 0375 9387 5309", "John Bowman", 2500); wallet[1] = new CreditCard("3485 0399 3395 1954", "John Bowman", 3500); wallet[2] = new CreditCard("6011 4902 3294 2994", "John Bowman", 5000); for (int j=1; j <= 16; j++) { // make some charges
cout << "Card payments:\n"; for (int i=0; i < 3; i++) { // make more charges cout << *wallet[i]; while (wallet[i]->getBalance() > 100.0) { wallet[i]->makePayment(100.0); cout << "New balance = " << wallet[i]->getBalance() << "\n"; } cout << "\n"; delete wallet[i]; // deallocate storage } } int main() { testCard(); return EXIT_SUCCESS; } // main function // successful execution
// member data // first value of the // current value of the // reset and return first value
// advance and return next value // constructor given first value // print the first n values // virtual destructor
void Progression::printProgression(int n) { std::cout << firstValue(); // print the first value for (int i = 2; i <= n; i++) { std::cout << ' ' << nextValue(); // print values 2 through n } std::cout << '\n'; // print end of line }
prev = cur; cur += temp; return cur; } public: // constructor from first and second FibonacciProgression(long f = 0, long s = 1) : Progression(f) { // initialize base with first second = s; prev = second - first; // create fictitious previous } };
string getMessage() const { return errorMsg; } }; inline std::ostream& operator<<(std::ostream& out, const RuntimeException& e) { return out << e.getMessage(); }
class Object { public: virtual void printMe() class Place : public Object { public: virtual void printMe() class Region : public Place { public: virtual void printMe() class State : public Region { public: virtual void printMe() class Maryland : public State { public: virtual void printMe()
= 0; }; { cout << "Buy it.\n"; } }; { cout << "Box it.\n"; } }; { cout << "Ship it.\n"; } }; { cout << "Read it.\n"; } };
int main() { Region* mid = new State; State* md = new Maryland; Object* obj = new Place; Place* usa = new Region; md->printMe(); mid->printMe(); (dynamic_cast<Place*>(obj))->printMe(); obj = md; (dynamic_cast<Maryland*>(obj))->printMe(); obj = usa; (dynamic_cast<Place*>(obj))->printMe(); usa = md; (dynamic_cast<Place*>(usa))->printMe(); return EXIT_SUCCESS; }
< n; i++) a = i;
< n; i+=2) a = i;
void push(const Object& obj); /** * Removes and returns the top object from the stack. * Throws StackEmptyException if the stack is empty. */ Object pop() throw(StackEmptyException); };
// // // // //
member data default capacity of stack actual length of stack array the stack array index of the top of the stack
// return the top of the stack Object& top() throw(StackEmptyException) { if (isEmpty()) throw StackEmptyException("Access to empty stack"); return S[t]; } // push object onto the stack void push(const Object& elem) throw(StackFullException) { if (size() == capacity) throw StackFullException("Stack overflow"); S[++t] = elem; } // pop the stack Object pop() throw(StackEmptyException) { if (isEmpty()) throw StackEmptyException("Access to empty stack"); return S[t--]; } // ...
constructor ArrayStack& operator=(const ArrayStack& st); ~ArrayStack() // destructor { delete [] S; } }; template <typename Object> // copy constructor ArrayStack<Object>:: ArrayStack(const ArrayStack& st) { capacity = st.capacity; t = st.t; S = new Object[capacity]; for (int i = 0; i <= t; i++) { // copy contents S[i] = st.S[i]; } } template <typename Object> // assignment operator ArrayStack<Object>& ArrayStack<Object>:: operator=(const ArrayStack& st) { if (this != &st) { // avoid self copy (x = x) delete [] S; // delete old contents capacity = st.capacity; t = st.t; S = new Object[capacity]; for (int i = 0; i <= t; i++) { // copy contents
/** * Interface for a queue: A collection of objects that are inserted * and removed according to the first-in first-out principle. */ template <typename Object> class Queue { public: /** * Returns the number of objects in the queue. */ int size() const; /** * Returns true if the queue is empty, false otherwise. */ bool isEmpty() const; /** * Returns the front object of the queue. * Throws QueueEmptyException if the queue is empty. */ Object& front() throw(QueueEmptyException); /** * Inserts an object at the rear of the queue. */ void enqueue (const Object& obj); /** * Remove and returns the object at the front of the queue. * Throws QueueEmptyException if the queue is empty. */ Object dequeue() throw(QueueEmptyException); };
* and removed according to the first-in first-out principle. */ template <typename Object> class Queue { public: /** * Returns the number of objects in the queue. */ int size() const; /** * Returns true if the queue is empty, false otherwise. */ bool isEmpty() const; /** * Returns the front object of the queue. * Throws QueueEmptyException if the queue is empty. */ Object& front() throw(QueueEmptyException); /** * Inserts an object at the rear of the queue. */ void enqueue (const Object& obj); /** * Remove and returns the object at the front of the queue. * Throws QueueEmptyException if the queue is empty. */ Object dequeue() throw(QueueEmptyException); };
// local node structure // member data // pointer to stack top // number of items in stack // default constructor
tp = NULL; sz = 0; } int size() const { return sz; } stack bool isEmpty() const { return sz == 0; } // number of elements in // is the stack empty? // return stack top
Object& top() throw(StackEmptyException) { if (isEmpty()) throw StackEmptyException("Top of empty stack"); return tp->element; } void push(const Object& e) { // push element onto stack NodePtr v = new Node(e, tp); tp = v; // v is now the top sz++; } Object pop() throw(StackEmptyException) { // pop top element if (isEmpty()) throw StackEmptyException("Pop of empty stack"); NodePtr old = tp; // node to remove tp = tp->next; sz--; Object result = old->element; // element to return delete old; return result; } // ... (insert housekeeping functions here) };
// protected utilities // remove entire stack // copy from ls copy constructor copy new contents assignment operator avoid self copy (x =
// // // LinkedStack& operator=(const LinkedStack& ls) { if (this != &ls) { // removeAll(); copyFrom(ls); } return *this; } ~LinkedStack()
// destructor
{ removeAll(); }
struct Node { // a node in the deque Object element; // element Node* prev; // previous node Node* next; // next node Node(const Object& e = Object(), Node* p = NULL, Node* n = NULL) : element(e), prev(p), next(n) { } // constructor }; typedef Node* NodePtr; // pointer to node
/** * A stock-quote class, which contains a day's stock price and span. */ class Quote {
public: int day; // which day int price; // this day's price int span; // this day's span Quote(int d = 0, int p = 0) // constructor { day = d; price = p; } }; /** * Compute the span of the stock price on each day by means of a * stack, and store the information in the Quote array Q. */ void computeDailyHighSpan(vector<Quote>& Q) { int prevHigh; // previous higher day LinkedStack<Quote> D; for (int i = 0 ; i < Q.size(); i++) { // process the current day i while ( !D.isEmpty() && // if stack not empty and Q[i].price >= D.top().price ) { // ... today's price is higher D.pop(); } if (D.isEmpty()) prevHigh = -1; // day i is a new high else prevHigh = D.top().day; // else stack top is high Q[i].span = i - prevHigh; span D.push(Q[i]); stack } } // add current to the // compute and store the
{ return size() == 0; } Object& elemAtRank(int r) rank r { return a[r]; } void replaceAtRank(int r, const Object& e) given rank { a[r] = e; } void removeAtRank(int r); given rank void insertAtRank(int r, const Object& e); given rank // ... (housekeeping functions omitted) };
// handle overflow by // double capacity // copy contents to new array // discard old array // make b the new array
Object element; // element Node* prev; // previous node Node* next; // next node Node(const Object& e = Object(), Node* p = NULL, Node* n = NULL) : element(e), prev(p), next(n) { } // constructor }; typedef Node* NodePtr; // pointer to a Node
// ... (insert Position class definition here) protected: // utility to convert Position to node pointer NodePtr nodePtr(const Position& p) const throw(InvalidPositionException) { if (p.node == NULL) throw InvalidPositionException("Attempt to use null position"); else return p.node; } protected: // data members int sz; // number of items NodePtr header; // head of list sentinel NodePtr trailer; // tail of list sentinel public: NodeList() { // default constructor sz = 0; header = new Node; // create sentinels trailer = new Node; header->next = trailer; // head points to trailer trailer->prev = header; // trailer points to head } int size() const // list size { return sz; } bool isEmpty() const // is the list empty? { return (sz == 0); } bool isFirst(const Position& p) const // is this the first? throw(InvalidPositionException) { NodePtr v = nodePtr(p); return v->prev == header; } bool isLast(const Position& p) const // is this the last? throw(InvalidPositionException) { NodePtr v = nodePtr(p); return v->next == trailer; } // ...
Position atRank(int rank) const throw(BoundaryViolationException); int rankOf(Position position) const throw(InvalidPositionException); };
insert at no checkRank
remove from
position to
replace at
// search for p.node // found it here // else advance // did not find found");
for (int j = 1; j < n-i; j++) if ( S.elemAtRank(j-1) > S.elemAtRank(j) ) S.swapElements(S.atRank(j-1), S.atRank(j)); } template <typename Sequence> void bubbleSort2(Sequence& S) { // bubble-sort using positions typedef typename Sequence::Position Position; int n = S.size(); for (int i = 0; i < n; i++) { // i-th pass Position prec = S.first(); for (int j = 1; j < n-i; j++) { Position succ = S.after(prec); if ( prec.element() > succ.element() ) S.swapElements(prec, succ); prec = succ; } } }
root of tree // get parent of // iterator for // internal // external // the root?
// leaf has
// 1 + (max
int diskSpace(const Tree& T, const Position& v) { int s = size(v); size of v PositionIterator children = T.children(v); while (children.hasNext()) s += diskSpace(T, children.next()); of subtrees if (T.isInternal(v)) cout << name(v) << ": " << s << endl; and weight return s; }
// start with
// close
// ... (insert Position definition here) private: // member data NodePtr theRoot; // pointer to the root int sz; // number of nodes protected: // protected utilities // ... (insert LinkedBinaryTree utilities here) public: LinkedBinaryTree() // constructor { theRoot = new Node; sz = 1; } int size() const // size of tree { return sz; } bool isEmpty() const // is tree empty? { return (sz == 0); } Position root() const // returns root { return Position(theRoot); } Position leftChild(const Position& v) const // returns left child { return Position(nodePtr(v)->left); } // ... (rightChild(), parent(), and sibling() are omitted but similar) bool isRoot(const Position& v) const // is v the root? { return isRoot(nodePtr(v)); } bool isInternal(const Position& v) const // is v internal? { return isInternal(nodePtr(v)); } bool isExternal(const Position& v) const // is v external? { return isExternal(nodePtr(v)); } void replaceElement(const Position& v, const Object& o) { replaceElement(nodePtr(v), o); } // replace element void swapElements(const Position& v, const Position& w) { swapElements(nodePtr(v), nodePtr(w)); } // swap elements void expandExternal(const Position& v) { expandExternal(nodePtr(v)); } // expand external node Position removeAboveExternal(const Position& v) // remove v and parent { return Position(removeAboveExternal(nodePtr(v))); } // ... (housekeeping and iterator functions omitted) };
// convert to
bool isExternal(NodePtr n) const external? { return (n->left == NULL && n->right == NULL); } bool isInternal(NodePtr n) const internal? { return ! isExternal(n); } bool isRoot(NodePtr n) const root? { return (n == theRoot); } void setRoot(NodePtr r) root { theRoot = r; r->parent = NULL; } void replaceElement(NodePtr n, const Object& o) element { n->element = o; } void swapElements(NodePtr n, NodePtr w) { Object temp = w->element; w->element = n->element; n->element = temp; } void expandExternal(NodePtr n) { external node n->left = new Node; n->left->parent = n; n->right = new Node; n->right->parent = n; sz += 2; } NodePtr removeAboveExternal(NodePtr n) { parent NodePtr p = n->parent; NodePtr s = n->sibling(); if (isRoot(p)) setRoot(s); now s is else { NodePtr g = p->parent; grandparent if (p == g->left) g->left = s; parent by sibling else g->right = s; s->parent = g; } delete n; delete p; removed nodes sz -= 2; nodes return s; }
// expand
// remove n and
Element _elem; // element public: Item(const Key& k = Key(), const Element& e = Element()) : _key(k), _elem(e) { } // constructor const Key& key() const // gets the key (read only) { return _key; } Element& element() // gets the element { return _elem; } const Element& element() const // gets the element (read only) { return _elem; } void setKey(const Key& k) // sets the key value { _key = k; } void setElement(const Element& e) // sets the element { _elem = e; } };
while (comp(k, key(curr)) > 0) // skip over small keys curr = S.after(curr); S.insertBefore(curr, Item(k,e)); // insert here } } Element& minElement() // element with min key throw(EmptyContainerException) { if (S.isEmpty()) throw EmptyContainerException("Minimum element of empty queue"); else return element(S.first()); } const Key& minKey() const // returns minimum key throw(EmptyContainerException) { if (S.isEmpty()) throw EmptyContainerException("Minimum key of empty queue"); else return key(S.first()); } void removeMin() // remove minimum throw(EmptyContainerException) { if (S.isEmpty()) throw EmptyContainerException("Removal from empty queue"); S.remove(S.first()); } };
typedef VectorHeapTree<Item> HeapTree; items typedef HeapTree::Position Position; heap protected: utilities const Key& key(const Position& p) const key { return p.element().key(); } Element& element(const Position& p) element { return p.element().element(); } private: HeapTree T; Comp comp; public: HeapPriorityQueue(int capac = 100) : T(capac), comp() { } int size() const elements { return (T.size()-1)/2; } bool isEmpty() const { return size() == 0; }
// a heap of // a position in // local // position's // position's // member data // heap tree // comparator // constructor // number of // is the queue empty? // insert (key,
Element& minElement() // return min element throw(EmptyContainerException) { if (isEmpty()) throw EmptyContainerException("Minimum element of empty queue"); return element(T.root()); } const Key& minKey() const // return minimum key throw(EmptyContainerException) { if (isEmpty()) throw EmptyContainerException("Minimum key of empty queue"); return key(T.root()); } void removeMin() throw(EmptyContainerException); // remove minimum };
Position u = T.parent(z); if (comp(key(u), key(z)) <= 0) break; T.swapElements(u, z); z = u; } } template <typename Key, typename Element, typename Comp> void HeapPriorityQueue<Key, Element, Comp>:: removeMin() // remove minimum throw(EmptyContainerException) { if (isEmpty()) throw EmptyContainerException("Removal from empty queue"); if (size() == 1) T.remove(); else { T.replaceElement(T.root(), T.remove()); Position r = T.root(); while (T.isInternal(T.leftChild(r))) { // down-heap bubbling Position s = T.rightChild(r); if (T.isExternal(T.rightChild(r)) || comp(key(T.leftChild(r)), key(T.rightChild(r))) <= 0) s = T.leftChild(r); if (comp(key(s), key(r)) < 0) { T.swapElements(r, s); r = s; } else break; } } }
class Locator { // a locator private: LocItemPtr locItem; // pointer to the item public: Locator(LocItemPtr ip = NULL) // constructor { locItem = ip; } bool isNull() const // is locator null? { return locItem == NULL; } const Key& key() const // get key (read-only) { return locItem->key(); } Element& element() // get element { return locItem->element(); } const Element& element() const // get element (read-only) { return locItem->element(); } friend class SortedSeqPriorityQueueLoc<Key, Element, Comp>; };
Locator min() const // minimum item throw(EmptyContainerException) { if (S.isEmpty()) throw EmptyContainerException("Min of empty queue"); else return Locator(S.first().element()); } Locator insertItem(const Key& k, const Element& e) { // insert (key,element) LocItemPtr locItem = new LocItem(k, e); // allocate new item locInsert(locItem); // insert it return Locator(locItem); // return its locator } void remove(Locator& loc) // remove item throw(InvalidPositionException) { if (loc.isNull()) throw InvalidPositionException("Removal of null locator"); S.remove(loc.locItem->pos); // remove from sequence delete loc.locItem; // delete the item loc.locItem = NULL; // invalidate pointer } // ...
loc.locItem->item.setKey(newKey); key
locInsert(loc.locItem); // sequence } // ... (housekeeping and other functions omitted) }; template <typename Key, typename Element, typename Comp> void SortedSeqPriorityQueueLoc<Key, Element, Comp>:: locInsert(LocItemPtr locItem) { // utility Position& pos = locItem->pos; // position Key k = locItem->key(); // if (S.isEmpty()) pos = S.insertFirst(locItem); // insert first else if (comp(k, key(S.last())) > 0) // last? pos = S.insertAfter(S.last(), locItem); // else { Position curr = S.first(); // while (comp(k, key(curr)) > 0) // small keys curr = S.after(curr); pos = S.insertBefore(curr, locItem); // } }
insert insertion key to insert if empty greater than insert at end start search skip over insert here
Dictionaries
Code Fragment: HashEntry
enum Status { EMPTY, USED, FREE }; status // table entry
struct HashEntry : public Item<Key, Element> { // a hash table entry Status status; // entry status HashEntry(const Key& k = Key(), // constructor const Element& e = Element(), Status st = EMPTY) : Item<Key,Element>(k, e), status(st) { } }; typedef HashEntry* EntryPtr; // pointer to an entry
void insertItem(const Key& key, const Element& element) throw(HashTableFullException) { // insert (key,element) EntryPtr e = inserter(key, element); // attempt to insert if (e == NULL) // failure throw HashTableFullException("Insertion into full hash table"); } void removeElement(const Key& key) // remove using key throw(NonexistentElementException) { EntryPtr e = finder(key); // look up key if (e == NULL) // not found? throw NonexistentElementException("Key not found"); e->status = FREE; // mark entry as free n--; // decrease size } // ... (some functions omitted) };
int start = i; do { if (A[i].status != USED) { available? A[i] = HashEntry(key, element, USED); n++; return &A[i]; success } i = (i + 1) % N; } while (i != start); start return NULL; failure }
// starting point // slot is // store it here // increase size // return with // try next slot // until back to // return with