pdavidow / heditor2 Goto Github PK

Rewrite of SimpleEditor in Haskell (without using exceptions)

stack test

==================================================

THE PROBLEM

Problem Statement

In this challenge, you must implement a simple text editor. Initially, your editor contains an empty string, S. You must perform Q operations of the following 4 types:

1. append(W) - Append string W to the end of S.
2. delete(k) - Delete the last k characters of S.
3. print(k) - Print the kth character of S.
4. undo() - Undo the last (not previously undone) operation of type 1 or 2, reverting S to the state it was in prior to that operation.

Input Format

The first line contains an integer, Q, denoting the number of operations. Each line i of the Q subsequent lines (where 1 <= i <= Q) defines an operation to be performed. Each operation starts with a single integer, t (where t is a member of set {1,2,3,4}), denoting a type of operation as defined in the Problem Statement above. If the operation requires an argument, t is followed by its space-separated argument. For example, if t = 1 and W = "abcd", line i will be 1 abcd.

Constraints

• 1 <= Q <= 1000000
• 1 <= k <= S length
• The sum of the lengths of all W in the input <= 1000000
• The sum of k over all delete operations <= 2000000
• All input characters are lowercase English letters.
• It is guaranteed that the sequence of operations given as input is possible to perform.

Output Format

Each operation of type 3 must print the kth character on a new line.

Sample Input

8
1 abc
3 3
2 3
1 xy
3 2
4 
4 
3 1

Sample Output

c
y
a