Skip to content

Instantly share code, notes, and snippets.

@krsnvijay

krsnvijay/undo_stack_help.ipynb

Last active April 22, 2021 15:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save krsnvijay/eaa3bf294ab79e8305e5b261d96658f8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save krsnvijay/eaa3bf294ab79e8305e5b261d96658f8 to your computer and use it in GitHub Desktop.
Download ZIP
Simplify your undo stack data structure
Display the source blob
Display the rendered blob
Raw
undo_stack_help.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Are you having problems implementing the undo datastructure?\n",
"## Let's simplify it\n",
"* Go through the cells written in python to understand how you could implement the undo_stack and undo_group in your project\n",
"* Use the same logic in the language that you're implementing your project in i.e Java|Javascript\n",
"* if you want to run this notebook, make sure to run all cells on jupyter notebook, dont run the same cell twice"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'This is line 1\\nThis is line 2\\nThis is line 3\\n'"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from pprint import pprint\n",
"# this is the text that is displayed in your editor\n",
"text = '''\\\n",
"This is line 1\n",
"This is line 2\n",
"This is line 3\n",
"'''\n",
"text"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Use a 2D list as your datastructure for undo stack\n",
"* You could store the state of each line as a list\n",
"* Use line number as index to your 2d array to get all the states of a particular line number\n",
"* The last item in the line state would be your current state"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges'],\n",
" ['I play tennis', 'I play tennis on weekends'],\n",
" ['I dont speak french']]"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you've made changes to the second line in your editor\n",
"text = '''\\\n",
"I like oranges\n",
"I play tennis\n",
"I dont speak french\n",
"'''\n",
"undo_stack = [\n",
" ['I like oranges'], #original state of line 1\n",
" ['I play tennis'], #original state of line 2\n",
" ['I dont speak french'] #original state of line 3\n",
"]\n",
"# add new state of line 2 to your current state of line 2\n",
"# use indices to get the state of a particular line\n",
"undo_stack[1].append('I play tennis on weekends') \n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Adding a line"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges'],\n",
" ['I play tennis', 'I play tennis on weekends'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver']]"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you've added a fourth line in your editor\n",
"text = '''\\\n",
"I like oranges\n",
"I play tennis on weekends\n",
"I dont speak french\n",
"I live in vancouver\n",
"'''\n",
"# create a new list which would hold all the states of line 4 and add it to the stack\n",
"undo_stack.append(['I live in vancouver']) \n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Updating a line"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges', 'I eat oranges a lot'],\n",
" ['I play tennis', 'I play tennis on weekends'],\n",
" ['I study at concordia'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver']]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you've changed the first line and added a line between 2 & 3\n",
"text = '''\\\n",
"I eat oranges a lot\n",
"I play tennis on weekends\n",
"I study at concordia\n",
"I dont speak french\n",
"I live in vancouver\n",
"'''\n",
"undo_stack[0].append('I eat oranges a lot')\n",
"undo_stack.insert(2,['I study at concordia']) \n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Deleting a line"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges', 'I eat oranges a lot'],\n",
" ['I play tennis', 'I play tennis on weekends'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver', 'I live in vancouver, its always raining']]"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you deleted the third line\n",
"# also changed the fourth line\n",
"text = '''\\\n",
"I eat oranges a lot\n",
"I play tennis on weekends\n",
"I dont speak french\n",
"I live in vancouver, its always raining\n",
"'''\n",
"undo_stack.pop(2)\n",
"undo_stack[3].append('I live in vancouver, its always raining')\n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Splitting a Line into two"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges', 'I eat oranges a lot'],\n",
" ['I play tennis', 'I play tennis on weekends'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver',\n",
" 'I live in vancouver, its always raining',\n",
" 'I live in vancouver,'],\n",
" ['its always raining']]"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you've split fourth line into two lines (pressed enter in the middle of the line)\n",
"text = '''\\\n",
"I eat oranges a lot\n",
"I play tennis on weekends\n",
"I dont speak french\n",
"I live in vancouver,\n",
"its always raining\n",
"'''\n",
"undo_stack[3].append('I live in vancouver,')\n",
"undo_stack.append(['its always raining'])\n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Get current text from all the latest states"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"I eat oranges a lot\n",
"I play tennis on weekends\n",
"I dont speak french\n",
"I live in vancouver,\n",
"its always raining\n"
]
}
],
"source": [
"# get all the latest edits to get the current text to be shown in the editor\n",
"# get the last state for each line and join only non blank lines with '\\n'\n",
"lines = (line[-1] for line in undo_stack)\n",
"display_text = '\\n'.join(lines)\n",
"print(display_text)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Apply selective undo"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[['I like oranges', 'I eat oranges a lot'],\n",
" ['I play tennis on weekends', 'I play tennis'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver',\n",
" 'I live in vancouver, its always raining',\n",
" 'I live in vancouver,'],\n",
" ['its always raining']]"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you want to revert second line to its original state\n",
"# move the position of the state to the end\n",
"undo_stack[1].append(undo_stack[1].pop(0))\n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Delete an old state"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['I eat oranges a lot'],\n",
" ['I play tennis on weekends', 'I play tennis'],\n",
" ['I dont speak french'],\n",
" ['I live in vancouver',\n",
" 'I live in vancouver, its always raining',\n",
" 'I live in vancouver,'],\n",
" ['its always raining']]"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# you want to remove the original state of the first line and only keep the latest change\n",
"# remove the first element in the first line's state\n",
"undo_stack[0].pop(0)\n",
"undo_stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Create a new undo group"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"I play tennis on weekends\n",
"I live in vancouver\n"
]
}
],
"source": [
"# create groups of edits\n",
"undo_groups = {}\n",
"# create a group called likes that will store list of 2d indexes for line_no and line_state\n",
"undo_groups['likes'] = [(1,0),(3,0)]\n",
"\n",
"# display all edits of a group 'likes' from undo_stack\n",
"for line_number, line_state in undo_groups['likes']:\n",
" print(undo_stack[line_number][line_state])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Delete an undo group and its states"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"undo_groups before:\n",
"{'likes': [(1, 0), (3, 0)], 'other_info': [(2, 1)]}\n",
"undo_stack before:\n",
"[['I eat oranges a lot'],\n",
" ['I play tennis on weekends', 'I play tennis'],\n",
" ['I dont speak french', 'I dont speak french, yet'],\n",
" ['I live in vancouver',\n",
" 'I live in vancouver, its always raining',\n",
" 'I live in vancouver,'],\n",
" ['its always raining']]\n",
"undo_groups after:\n",
"{'other_info': [(2, 1)]}\n",
"undo_stack after:\n",
"[['I eat oranges a lot'],\n",
" ['I play tennis'],\n",
" ['I dont speak french', 'I dont speak french, yet'],\n",
" ['I live in vancouver, its always raining', 'I live in vancouver,'],\n",
" ['its always raining']]\n"
]
}
],
"source": [
"# you've changed the third line\n",
"undo_stack[2].append('I dont speak french, yet')\n",
"# add a new group and delete the group 'likes'\n",
"# groups should only store old edits indices, should not store the latest edit for this datastructure\n",
"undo_groups['other_info'] = [(2,1)]\n",
"\n",
"print('undo_groups before:')\n",
"print(undo_groups)\n",
"print('undo_stack before:')\n",
"pprint(undo_stack)\n",
"\n",
"for line_number, line_state in undo_groups['likes']:\n",
" undo_stack[line_number].pop(line_state)\n",
"del undo_groups['likes']\n",
"\n",
"print('undo_groups after:')\n",
"print(undo_groups)\n",
"print('undo_stack after:')\n",
"pprint(undo_stack)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Super delete"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['I eat oranges a lot', 'I play tennis', 'I dont speak french, yet', 'I live in vancouver,', 'its always raining']\n",
"{}\n"
]
}
],
"source": [
"# super delete!\n",
"# only keep the latest state and remove other states\n",
"undo_stack = [line[-1] for line in undo_stack]\n",
"undo_groups.clear()\n",
"print(undo_stack)\n",
"print(undo_groups)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment