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
}