Managing Document History with Stacks in Kotlin

Lesson 5

Introduction

Welcome! Today, we will delve into managing a document's editing history using stacks. Imagine building a text editor; you would need to handle actions like adding text, undoing it, and redoing those changes. We will see how these features can be efficiently implemented using stacks. By the end of this lesson, you will possess an in-depth understanding of applying stacks in practical scenarios.

Defining Methods

Before starting the coding portion, let's dissect the methods we will implement. These methods will manage a document's edit history, allowing us to apply changes, undo them, and redo them effectively.

applyChange(change: String): This method applies a change to the document. The change, represented as a string, is stored in a way that allows us to remember the order of applied changes. Any previously undone changes are discarded.
undo(): String?: This method undoes the most recent change and allows us to store it for a possible redo. It returns the change that was undone. If there are no changes available to undo, it returns null.
redo(): String?: This method redoes the most recent undone change, making it active again. It returns the change that was redone. If there are no changes available to redo, it returns null.
getChanges(): List<String>: This method returns a list of all applied changes in the order they were applied.

Methods Implementation with Stacks

To implement these methods efficiently, we'll use two stacks. We use stacks to keep track of applied changes and undone changes because of their LIFO (Last In, First Out) property. The most recent change is always at the top, making it easy to undo and redo.

Let's break down each method's implementation and study how they interact with the stacks.

Step 1: Define the class and initialize the stacks

Let's implement the solution step-by-step. Firstly, we define our class and set up the initial state.

Kotlin
1class DocumentHistory {
2    // Stacks to track current changes and undone changes that can be redone
3    private val changesStack = mutableListOf<String>()
4    private val redoStack = mutableListOf<String>()
5}

Here, DocumentHistory is the class, and we initialize changesStack as a MutableList to act as our stack of applied changes, and redoStack as another MutableList for undone changes.

Step 2: Implement the 'applyChange' method

Next, we put into effect the method to apply changes.

Kotlin
1class DocumentHistory {
2    /* Other methods and properties omitted for brevity */
3
4    // Adds a new change and clears the redo history
5    fun applyChange(change: String) {
6        changesStack.add(change)
7        redoStack.clear()
8    }
9}

With applyChange, we take a string change and append it to the changesStack list. Additionally, we clear the redoStack to ensure that once a new change is applied, any previously undone changes cannot be redone.

Step 3: Implement the 'undo' method

Now, we will implement the method to undo the most recent change.

Kotlin
1class DocumentHistory {
2    /* Other methods and properties omitted for brevity */
3    
4    // Removes and returns the most recent change, moving it to the redo stack
5    // Returns null if there are no changes to undo    
6    fun undo(): String? {
7        return if (changesStack.isNotEmpty()) {
8            val change = changesStack.removeAt(changesStack.lastIndex)
9            redoStack.add(change)
10            change
11        } else {
12            null
13        }
14    }
15}

Here, undo checks if changesStack is not empty. If it's not, it removes the last item from the list, simulating a stack pop operation, adds it to redoStack, and returns the undone change. Otherwise, it returns null.

Step 4: Implement the 'redo' method

Now we'll create the method to redo the most recent undone change.

Kotlin
1class DocumentHistory {
2    /* Other methods and properties omitted for brevity */
3
4    // Restores the most recently undone change back to the document history
5    // Returns null if there are no changes to redo    
6    fun redo(): String? {
7        return if (redoStack.isNotEmpty()) {
8            val change = redoStack.removeAt(redoStack.lastIndex)
9            changesStack.add(change)
10            change
11        } else {
12            null
13        }
14    }
15}

The redo method checks if redoStack is not empty. If it's not, it removes the last item, simulating a LIFO operation, adds it back to changesStack, and returns the redone change. Otherwise, it returns null.

Step 5: Implement the 'getChanges' method

Lastly, we implement the method to retrieve all applied changes.

Kotlin
1class DocumentHistory {
2    /* Other methods and properties omitted for brevity */
3
4    // Returns a copy of the current document history in chronological order
5    // Changes are returned in the order they were applied
6    fun getChanges(): List<String> {
7        return changesStack.toList()
8    }
9}

The getChanges method simply returns a copy of the changesStack list, which includes all changes applied to the document in the order they were applied.

The Final Implementation

Here is the final implementation of our DocumentHistory class, combining all the methods we've discussed:

Kotlin
1class DocumentHistory {
2    // Stacks to track current changes and undone changes that can be redone
3    private val changesStack = mutableListOf<String>()
4    private val redoStack = mutableListOf<String>()
5
6    // Adds a new change to the history and clears any undone changes that could be redone
7    fun applyChange(change: String) {
8        changesStack.add(change)
9        redoStack.clear()
10    }
11    
12    // Removes and returns the most recent change, moving it to the redo stack
13    // Returns null if there are no changes to undo
14    fun undo(): String? {
15        return if (changesStack.isNotEmpty()) {
16            val change = changesStack.removeAt(changesStack.lastIndex)
17            redoStack.add(change)
18            change
19        } else {
20            null
21        }
22    }
23
24    // Restores the most recently undone change back to the document history
25    // Returns null if there are no changes to redo
26    fun redo(): String? {
27        return if (redoStack.isNotEmpty()) {
28            val change = redoStack.removeAt(redoStack.lastIndex)
29            changesStack.add(change)
30            change
31        } else {
32            null
33        }
34    }
35
36    // Returns a copy of the current document history in chronological order
37    fun getChanges(): List<String> {
38        return changesStack.toList()
39    }
40}

Let's test this with an example:

Kotlin
1fun main() {
2    val docHist = DocumentHistory()
3
4    // Apply changes
5    docHist.applyChange("Added header")
6    docHist.applyChange("Added footer")
7    println(docHist.getChanges())  // Output: [Added header, Added footer]
8
9    // Undo last change
10    println(docHist.undo())  // Output: Added footer
11    println(docHist.getChanges())  // Output: [Added header]
12
13    // Redo last undone change
14    println(docHist.redo())  // Output: Added footer
15    println(docHist.getChanges())  // Output: [Added header, Added footer]
16
17    // Undo all changes
18    println(docHist.undo())  // Output: Added footer
19    println(docHist.undo())  // Output: Added header
20    println(docHist.getChanges())  // Output: []
21
22    // Try undoing when no changes are left
23    println(docHist.undo())  // Output: null
24
25    // Redo changes
26    println(docHist.redo())  // Output: Added header
27    println(docHist.redo())  // Output: Added footer
28    println(docHist.getChanges())  // Output: [Added header, Added footer]
29
30    // Try redoing when no changes are left to redo
31    println(docHist.redo())  // Output: null
32}

Summary

In today's lesson, we learned how to manage a document's editing history using stacks. We implemented methods to apply changes, undo the last change, redo the most recent undone change, and retrieve all applied changes. This exercise provided us with practical experience in using stacks to efficiently track and revert operations in a real-life scenario. Keep practicing similar challenges to deepen your understanding of data structures in various applications. Fantastic job today, and keep up the good work!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.