Skip to content

Instantly share code, notes, and snippets.

@kom-bu

kom-bu/ArrayDeque.ipynb

Created May 22, 2020 05:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kom-bu/6e5eebea4f03f02a7898142851c0a2f1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kom-bu/6e5eebea4f03f02a7898142851c0a2f1 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
ArrayDeque.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 118,
"metadata": {},
"outputs": [],
"source": [
"class ArrayDeque:\n",
" def __init__(self):\n",
" self.array = []\n",
" self.head = 0\n",
" self.length = 0\n",
" def __len__(self):\n",
" return self.length;\n",
" def __getitem__(self, i):\n",
" if i < 0 or i >= len(self):\n",
" raise IndexError();\n",
" return self.array[(self.head + i) % len(self.array)]\n",
" def __setitem__(self, i, value):\n",
" if i < 0 or i >= len(self):\n",
" raise IndexError();\n",
" self.array[(self.head + i) % len(self.array)] = value\n",
" def __iter__(self):\n",
" for i in range(0, len(self)):\n",
" yield self[i]\n",
" def add(self, i, value):\n",
" if len(self) == len(self.array):\n",
" self.resize()\n",
" if i < len(self) // 2:\n",
" self.head = (self.head + len(self.array) - 1) % len(self.array)\n",
" for k in range(i):\n",
" self.array[(self.head + k) % len(self.array)] = self.array[(self.head + k + 1) % len(self.array)]\n",
" else:\n",
" for k in range(len(self), i, -1):\n",
" self.array[(self.head + k) % len(self.array)] = self.array[(self.head + k - 1) % len(self.array)]\n",
" \n",
" self.array[(self.head + i) % len(self.array)] = value\n",
" self.length += 1\n",
" def remove(self, i):\n",
" if i < 0 or i >= len(self):\n",
" raise IndexError();\n",
" if i < len(self) // 2:\n",
" self.head = (self.head + 1) % len(self.array)\n",
" for k in range(i - 1, -1, -1):\n",
" self.array[(self.head + k) % len(self.array)] = self.array[(self.head + k - 1) % len(self.array)]\n",
" else:\n",
" for k in range(i, len(self) - 1):\n",
" self.array[(self.head + k) % len(self.array)] = self.array[(self.head + k + 1) % len(self.array)]\n",
" self.length -= 1\n",
" def resize(self):#twice except 0\n",
" newarray = [None] * max(1, 2 * self.length)\n",
" for i in range(len(self)):\n",
" newarray[i] = self[i]\n",
" self.array = newarray\n",
" self.head = 0\n",
" def debug(self):\n",
" print(self.array)"
]
},
{
"cell_type": "code",
"execution_count": 127,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['0']\n",
"['0', '1']\n",
"['0', 'intervention', '1']\n",
"['new zero', '0', 'intervention', '1']\n",
"['new zero', '0', '1']\n",
"['new zero', '0', 'reintervention', '1']\n",
"['new zero', 'reintervention', '1']\n",
"['changed', 'reintervention', '1']\n"
]
}
],
"source": [
"ad = ArrayDeque()\n",
"ad.add(0, '0')\n",
"print([x for x in ad])\n",
"ad.add(1, '1')\n",
"print([x for x in ad])\n",
"ad.add(1, 'intervention')\n",
"print([x for x in ad])\n",
"ad.add(0, 'new zero')\n",
"print([x for x in ad])\n",
"ad.remove(2)\n",
"print([x for x in ad])\n",
"ad.add(2, 'reintervention')\n",
"print([x for x in ad])\n",
"ad.remove(1)\n",
"print([x for x in ad])\n",
"ad[0] = 'changed'\n",
"print([x for x in ad])"
]
},
{
"cell_type": "code",
"execution_count": 128,
"metadata": {},
"outputs": [],
"source": [
"ad = ArrayDeque()"
]
},
{
"cell_type": "code",
"execution_count": 132,
"metadata": {},
"outputs": [],
"source": [
"ad.add(0, 'a')"
]
},
{
"cell_type": "code",
"execution_count": 134,
"metadata": {},
"outputs": [],
"source": [
"ad.add(1, 'b')"
]
},
{
"cell_type": "code",
"execution_count": 136,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'b'"
]
},
"execution_count": 136,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ad[1]"
]
},
{
"cell_type": "code",
"execution_count": 137,
"metadata": {},
"outputs": [],
"source": [
"ad.add(0, 'z')"
]
},
{
"cell_type": "code",
"execution_count": 141,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'z'"
]
},
"execution_count": 141,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ad[0]"
]
},
{
"cell_type": "code",
"execution_count": 142,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a', 'b', None, 'z']\n"
]
}
],
"source": [
"ad.debug()"
]
},
{
"cell_type": "code",
"execution_count": 143,
"metadata": {},
"outputs": [],
"source": [
"ad.add(0, 'y')"
]
},
{
"cell_type": "code",
"execution_count": 145,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('y', 'z', 'a', 'b')"
]
},
"execution_count": 145,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ad[0], ad[1], ad[2], ad[3]"
]
},
{
"cell_type": "code",
"execution_count": 146,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a', 'b', 'y', 'z']\n"
]
}
],
"source": [
"ad.debug()"
]
},
{
"cell_type": "code",
"execution_count": 147,
"metadata": {},
"outputs": [],
"source": [
"ad.remove(1)"
]
},
{
"cell_type": "code",
"execution_count": 148,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('y', 'a', 'b')"
]
},
"execution_count": 148,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ad[0], ad[1], ad[2]"
]
},
{
"cell_type": "code",
"execution_count": 149,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a', 'b', 'y', 'y']\n"
]
}
],
"source": [
"ad.debug()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment