DOC PREVIEW
Stanford CS 106B - Stack and List Buffers

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Stack and List BuffersWhere Do We Go From Here?The EditorBuffer ClassThe Two-Stack ModelStack-Based Private Data for BufferStack-Based Buffer ImplementationSlide 7Slide 8Slide 9Insertion in Fixed TextList-Based BuffersRepresenting the CursorList-Based Private Data for BufferList-Based Buffer ImplementationSlide 15Slide 16Slide 17Slide 18The EndStack and List BuffersEric RobertsCS 106BMay 1, 2009Where Do We Go From Here?•Our strategy for the next two days is to implement the class EditorBuffer in three different ways and to compare the algorithmic efficiency of the various options. Those three representations are:A simple array model.1.A two-stack model that uses a pair of character stacks.2.A linked-list model that uses pointers to indicate the order.3.•For each model, we’ll calculate the complexity of each of the six fundamental methods in the EditorBuffer class. Some operations will be more efficient with one model, others will be more efficient with a different underlying representation.The EditorBuffer Class•The EditorBuffer class supports the following operations:buffer.moveCursorForward()Moves the cursor forward one character (does nothing if it’s at the end).buffer.moveCursorBackward()Moves the cursor backward one character (does nothing if it’s at the beginning).buffer.moveCursorToStart()Moves the cursor to the beginning of the buffer.buffer.moveCursorToEnd()Moves the cursor to the end of the buffer.buffer.insertCharacter(ch)Inserts the character ch at the cursor position and advances the cursor past it.buffer.deleteCharacter()Deletes the character after the cursor, if any.buffer.display()Displays the buffer on cout (primarily for debugging).The Two-Stack Model•In the two-stack implementation of the EditorBuffer class, the characters in the buffer are stored in one of two stacks. The characters before the cursor are stored in a stack called before and the characters that follow the cursor are stored in a stack called after. Characters in each stack are stored so that the ones close to the cursor are near the top of the stack.•For example, given the buffer contentsa b c d ethe characters would be stored like this:before afterabcedprivate:/* Data required to represent the two-stack form of the buffer */ CharStack before; /* Stack of characters before the cursor */ CharStack after; /* Stack of characters after the cursor */Stack-Based Private Data for Buffer/* * File: stackbuf.cpp * ------------------ * This file implements the EditorBuffer class using a pair of * stacks to represent the buffer. The characters before the * cursor are stored in the before stack, and the characters * after the cursor are stored in the after stack. */#include "genlib.h"#include "buffer.h"#include <iostream>/* * Implementation notes: EditorBuffer constructor/destructor * --------------------------------------------------------- * In this representation, the implementation of the CharStack class * automatically takes care of allocation and deallocation. */EditorBuffer::EditorBuffer() { /* Empty */}EditorBuffer::~EditorBuffer() { /* Empty */}Stack-Based Buffer Implementation/* * File: stackbuf.cpp * ------------------ * This file implements the EditorBuffer class using a pair of * stacks to represent the buffer. The characters before the * cursor are stored in the before stack, and the characters * after the cursor are stored in the after stack. */#include "genlib.h"#include "buffer.h"#include <iostream>/* * Implementation notes: EditorBuffer constructor/destructor * --------------------------------------------------------- * In this representation, the implementation of the CharStack class * automatically takes care of allocation and deallocation. */EditorBuffer::EditorBuffer() { /* Empty */}EditorBuffer::~EditorBuffer() { /* Empty */}/* * Implementation notes: moveCursor methods * ---------------------------------------- * These methods use push and pop to transfer values between the two stacks. */void EditorBuffer::moveCursorForward() { if (!after.isEmpty()) { before.push(after.pop()); }}void EditorBuffer::moveCursorBackward() { if (!before.isEmpty()) { after.push(before.pop()); }}void EditorBuffer::moveCursorToStart() { while (!before.isEmpty()) { after.push(before.pop()); }}void EditorBuffer::moveCursorToEnd() { while (!after.isEmpty()) { before.push(after.pop()); }}Stack-Based Buffer Implementation/* * Implementation notes: moveCursor methods * ---------------------------------------- * These methods use push and pop to transfer values between the two stacks. */void EditorBuffer::moveCursorForward() { if (!after.isEmpty()) { before.push(after.pop()); }}void EditorBuffer::moveCursorBackward() { if (!before.isEmpty()) { after.push(before.pop()); }}void EditorBuffer::moveCursorToStart() { while (!before.isEmpty()) { after.push(before.pop()); }}void EditorBuffer::moveCursorToEnd() { while (!after.isEmpty()) { before.push(after.pop()); }}/* * Implementation notes: insertCharacter and deleteCharacter * --------------------------------------------------------- * Each of the functions that inserts or deletes characters * can do so with a single push or pop operation. */void EditorBuffer::insertCharacter(char ch) { before.push(ch);}void EditorBuffer::deleteCharacter() { if (!after.isEmpty()) { after.pop(); }}Stack-Based Buffer Implementation/* * Implementation notes: insertCharacter and deleteCharacter * --------------------------------------------------------- * Each of the functions that inserts or deletes characters * can do so with a single push or pop operation. */void EditorBuffer::insertCharacter(char ch) { before.push(ch);}void EditorBuffer::deleteCharacter() { if (!after.isEmpty()) { after.pop(); }}/* * Implementation notes: display() * ------------------------------- * The display operator is complicated in the stack-based version, * but it is not part of the fundamental operator set. */void EditorBuffer::display() { int nBefore = before.size(); moveCursorToStart(); while (!after.isEmpty()) { cout << ' ' << after.peek(); moveCursorForward(); } cout << endl; moveCursorToStart(); for (int i = 0; i < nBefore; i++) { cout << " "; moveCursorForward(); } cout << '^' << endl;}Stack-Based Buffer


View Full Document

Stanford CS 106B - Stack and List Buffers

Download Stack and List Buffers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Stack and List Buffers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Stack and List Buffers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?