Skip to content

Instantly share code, notes, and snippets.

@astynax

astynax/zipper.ipynb

Last active December 21, 2015 20:49
Show Gist options
  • Save astynax/6363755 to your computer and use it in GitHub Desktop.
Save astynax/6363755 to your computer and use it in GitHub Desktop.
Download ZIP
zipper на Python
Display the source blob
Display the rendered blob
Raw
zipper.ipynb
{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Zipper(object):\n",
" \"\"\"\n",
" \u041a\u043b\u0430\u0441\u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043e\u0431\u044a\u0435\u043a\u0442\u0430-\"\u0417\u0430\u0441\u0442\u0451\u0436\u043a\u0438\",\n",
" \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0435\u0433\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u043e\u0431\u0445\u043e\u0434 \u043d\u0435\u043a\u043e\u0435\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445.\n",
" \u0421\u0430\u043c \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u043d\u0435\u043a\u0443\u044e \u0438\u0435\u0440\u0430\u0440\u0445\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443,\n",
" \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0443\u044e \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u0432\u0432\u0435\u0440\u0445-\u0432\u043d\u0438\u0437 \u043f\u043e \u0443\u0440\u043e\u0432\u043d\u044f\u043c\n",
" \u0438 \u0432\u043b\u0435\u0432\u043e-\u0432\u043f\u0440\u0430\u0432\u043e \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0443\u0440\u043e\u0432\u043d\u044f.\n",
" \"\"\"\n",
"\n",
" def __init__(self, is_branch, children, make_node, root):\n",
" \"\"\"\n",
" \u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n",
" @is_branch - \u043f\u0440\u0435\u0434\u0438\u043a\u0430\u0442, \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0449\u0438\u0439 \u043d\u043e\u0434\u0443 \u0438\n",
" \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0438\u0439 True, \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0438\u043c\u0435\u0435\u0442 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0435 (\u043d\u043e\u0434\u0430-\u0432\u0435\u0442\u0432\u044c)\n",
" @children - \u0444\u0443\u043a\u043d\u0446\u0438\u044f, \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0449\u0430\u044f \u043d\u043e\u0434\u0443-\u0432\u0435\u0442\u0432\u044c \u0438\n",
" \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0430\u044f \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u043d\u043e\u0434\n",
" @make_mode - \u0444\u0443\u043a\u043d\u0446\u0438\u044f, \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0449\u0430\u044f \u043d\u043e\u0434\u0443-\u0432\u0435\u0442\u0432\u044c \u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u043d\u043e\u0434,\n",
" \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0430\u044f \u043d\u043e\u0432\u0443\u044e \u043d\u043e\u0434\u0443-\u0432\u0435\u0442\u0432\u044c, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u043c\u0435\u043d\u0438\u0442 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u0443\u044e\n",
" @root - \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043d\u043e\u0434\u043e\u0439\n",
" \"\"\"\n",
" self._is_branch = is_branch\n",
" self._children = children\n",
" self._make_node = make_node\n",
" self._node = root\n",
" self._lefts = []\n",
" self._rights = []\n",
" self._path = []\n",
" \n",
" def _fork(self):\n",
" result = self.__class__(\n",
" self._is_branch,\n",
" self._children,\n",
" self._make_node,\n",
" self._node,\n",
" )\n",
" result._path = self._path[:]\n",
" result._lefts = self._lefts[:]\n",
" result._rights = self._rights[:]\n",
" return result\n",
"\n",
" def __forking(fn):\n",
" def inner(self, *args, **kwargs):\n",
" return fn(self._fork(), *args, **kwargs)\n",
" return inner\n",
" \n",
" @property\n",
" def node(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b\n",
" \"\"\"\n",
" return self._node\n",
"\n",
" @property\n",
" def path(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043d\u043e\u0434 - \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b (\u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \"\u043a\u043e\u0440\u043d\u044f\")\n",
" \"\"\"\n",
" return [i[0] for i in self._path]\n",
"\n",
" @__forking\n",
" def down(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0439 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u043d\u0438\u0437\n",
" (\u0442.\u0435. \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0441\u0430\u043c\u0443\u044e \u043b\u0435\u0432\u0443\u044e \u043f\u043e\u0434-\u043d\u043e\u0434\u0443).\n",
" \u0415\u0441\u043b\u0438 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u043d\u0438\u0437 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if not self.is_branch:\n",
" raise TypeError(\"You can't go down from leaf node!\")\n",
" self._path.append((self._node, self._lefts, self._rights))\n",
" children = self._children(self._node)\n",
" if not children:\n",
" raise TypeError(\"Branch is empty!\")\n",
" self._lefts = []\n",
" self._rights = children[::-1]\n",
" self._node = self._rights.pop()\n",
" return self\n",
" \n",
" @__forking\n",
" def up(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0439 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u0432\u0435\u0440\u0445\n",
" (\u0442.\u0435. \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0443\u044e \u0434\u043b\u044f \u0442\u0435\u043a\u0449\u0435\u0439 \u043d\u043e\u0434\u0443).\n",
" \u0415\u0441\u043b\u0438 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u0432\u0435\u0440\u0445 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if self.is_root:\n",
" raise TypeError(\"You can't go up from root!\")\n",
" children = self._lefts + [self._node] + self._rights[::-1]\n",
" node, self._lefts, self._rights = self._path.pop()\n",
" self._node = self._make_node(node, children)\n",
" return self\n",
" \n",
" @__forking\n",
" def root(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u043a\u043e\u0440\u043d\u0435\u0432\u0443\u044e \u043d\u043e\u0434\u0443.\n",
" \"\"\"\n",
" while not self.is_root:\n",
" self = self.up()\n",
" return self\n",
" \n",
" @property\n",
" def is_leftmost(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 True, \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 - \u043a\u0440\u0430\u0439\u043d\u044f\u044f \u0441\u043b\u0435\u0432\u0430 \u0441\u0440\u0435\u0434\u0438 \u0441\u0432\u043e\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439\n",
" \"\"\"\n",
" return not self._lefts\n",
" \n",
" @property\n",
" def is_rightmost(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 True, \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 - \u043a\u0440\u0430\u0439\u043d\u044f\u044f \u0441\u043f\u0440\u0430\u0432\u0430 \u0441\u0440\u0435\u0434\u0438 \u0441\u0432\u043e\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439\n",
" \"\"\"\n",
" return not self._rights\n",
" \n",
" @property\n",
" def is_root(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 True, \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 - \u043a\u043e\u0440\u043d\u0435\u0432\u0430\u044f\n",
" \"\"\"\n",
" return not self._path\n",
" \n",
" @property\n",
" def is_branch(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 True, \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 - \u0432\u0435\u0442\u0432\u044c\n",
" \"\"\"\n",
" return self._is_branch(self._node)\n",
" \n",
" @__forking\n",
" def left(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0439 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0432\u043b\u0435\u0432\u043e\n",
" (\u0442.\u0435. \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e \u0441\u043b\u0435\u0432\u0430 \u043d\u043e\u0434\u0443).\n",
" \u0415\u0441\u043b\u0438 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u043b\u0435\u0432\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if self.is_leftmost:\n",
" raise TypeError(\"You can't go left from leftmost node!\")\n",
" self = self._fork()\n",
" self._rights.append(self._node)\n",
" self._node = self._lefts.pop()\n",
" return self\n",
" \n",
" @__forking\n",
" def right(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0439 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0432\u043f\u0440\u0430\u0432\u043e\n",
" (\u0442.\u0435. \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u043e\u0434\u0443).\n",
" \u0415\u0441\u043b\u0438 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u043f\u0440\u0430\u0432\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if self.is_rightmost:\n",
" raise TypeError(\"You can't go right from rightmost node!\")\n",
" self._lefts.append(self._node)\n",
" self._node = self._rights.pop()\n",
" return self\n",
"\n",
" @__forking\n",
" def leftmost(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u043a\u0440\u0430\u0439\u043d\u044e\u044e \u0441\u043b\u0435\u0432\u0430 \u043d\u043e\u0434\u0443\n",
" \"\"\"\n",
" # while not self.is_leftmost:\n",
" # self = self.left()\n",
" if not self.is_leftmost:\n",
" self._rights.append(self._node)\n",
" self._rights.extend(self._lefts[:0:-1])\n",
" self._node = self._lefts[0]\n",
" self._lefts = []\n",
" return self\n",
" \n",
" @__forking\n",
" def rightmost(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u043a\u0440\u0430\u0439\u043d\u044e\u044e \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u043e\u0434\u0443\n",
" \"\"\"\n",
" # while not self.is_rightmost:\n",
" # self = self.right()\n",
" if not self.is_rightmost:\n",
" self._lefts.append(self._node)\n",
" self._lefts.extend(self._rights[:0:-1])\n",
" self._node = self._rights[0]\n",
" self._rights = []\n",
" return self\n",
" \n",
" @__forking\n",
" def append_child(self, node):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u043a \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u043d\u043e\u0434\u0430\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0430 \u0421\u041f\u0420\u0410\u0412\u0410 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u0430\u044f \u043d\u043e\u0434\u0430 @node.\n",
" \u0415\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0435\u0442\u0432\u044c\u044e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if not self._is_branch(self._node):\n",
" raise TypeError(\"You can't append child to the leaf node!\")\n",
" self._node = self._make_node(\n",
" self._node,\n",
" self._children(self._node) + [node]\n",
" )\n",
" return self\n",
"\n",
" @__forking\n",
" def insert_child(self, node):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u043a \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u043d\u043e\u0434\u0430\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0430 \u0421\u041b\u0415\u0412\u0410 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u0430\u044f \u043d\u043e\u0434\u0430 @node.\n",
" \u0415\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0435\u0442\u0432\u044c\u044e, \u0432\u043e\u0437\u0431\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.\n",
" \"\"\"\n",
" if not self._is_branch(self._node):\n",
" raise TypeError(\"You can't append child to the leaf node!\")\n",
" self._node = self._make_node(\n",
" self._node,\n",
" [node] + self._children(self._node)\n",
" )\n",
" return self\n",
"\n",
" @__forking\n",
" def insert_left(self, node):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043d\u043e\u0434\u0430 @node.\n",
" \"\"\"\n",
" if self.is_root:\n",
" raise TypeError(\"Root node can't have the neighbours!\")\n",
" self._lefts.append(node)\n",
" return self\n",
"\n",
" @__forking\n",
" def insert_right(self, node):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u043f\u0440\u0430\u0432\u0430 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043d\u043e\u0434\u0430 @node.\n",
" \"\"\"\n",
" if self.is_root:\n",
" raise TypeError(\"Root node can't have the neighbours!\")\n",
" self._rights.append(node)\n",
" return self\n",
"\n",
" @__forking\n",
" def replace(self, node):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043c\u0435\u043d\u0435\u043d\u043e \u043d\u0430 @node.\n",
" \"\"\"\n",
" self._node = fn(self._node)\n",
" return self\n",
" \n",
" @property\n",
" def is_end(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 True, \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \"\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439\" (next_node)\n",
" \"\"\"\n",
" if self.is_root:\n",
" return not self.is_branch # \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0432\u044b\u0440\u043e\u0436\u0434\u0435\u043d\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f, \u043a\u043e\u0433\u0434\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u043d\u0435 \u0432\u0435\u0442\u0432\u0438\u0442\u0441\u044f\n",
" else:\n",
" if self.is_rightmost:\n",
" if self.is_branch:\n",
" return False\n",
" else:\n",
" while True:\n",
" self = self.up()\n",
" if self.is_root:\n",
" return True\n",
" if not self.is_rightmost:\n",
" return False\n",
" return False\n",
" \n",
" def next_node(self):\n",
" \"\"\"\n",
" \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a, \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043d\u043e\u0434\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e\n",
" \u0431\u0443\u0434\u0435\u0442 \"\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439\" \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043d\u043e\u0434\u0435 \u0434\u0430\u043d\u043e\u0433\u043e \u043e\u0431\u0445\u043e\u0434\u0447\u0438\u043a\u0430.\n",
" \"\"\"\n",
" if self.is_branch:\n",
" return self.down()\n",
" else:\n",
" if self.is_end:\n",
" return self\n",
" elif self.is_rightmost:\n",
" while self.is_rightmost:\n",
" self = self.up()\n",
" return self.right()\n",
"\n",
" def __repr__(self):\n",
" return \"Zipper[node: %r, path: %r]\" % (self.node, self.path)\n",
" \n",
" def __eq__(self, other):\n",
" return (\n",
" self._node == other._node\n",
" and\n",
" self._lefts == other._lefts\n",
" and\n",
" self._rights == other._rights\n",
" and\n",
" self._path == other._path\n",
" )\n"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from collections import Iterable"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"z = Zipper(\n",
" lambda x: isinstance(x, Iterable), # is_branch\n",
" list, # children\n",
" lambda x, ys: x.__class__(ys), # make_node\n",
" [[1, 2, (31, 32, 33)], (4, 5, [6, 7])])\n",
"\n",
"print \"\u041e\u0431\u0445\u043e\u0434:\"\n",
"zz = z\n",
"while True:\n",
" if not zz.is_branch:\n",
" print zz.node,\n",
" if zz.is_end:\n",
" print\n",
" break\n",
" else:\n",
" zz = zz.next_node()\n",
"\n",
"print \"\u041c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f:\"\n",
"print \"- \u0434\u043e\\t\", z.node\n",
"print \"- \u043f\u043e\u0441\u043b\u0435\\t\", z.down().rightmost().down().rightmost().append_child(8).root().node"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\u041e\u0431\u0445\u043e\u0434:\n",
"1 2 31 32 33 4 5 6 7\n",
"\u041c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f:\n",
"- \u0434\u043e\t[[1, 2, (31, 32, 33)], (4, 5, [6, 7])]\n",
"- \u043f\u043e\u0441\u043b\u0435\t[[1, 2, (31, 32, 33)], (4, 5, [6, 7, 8])]\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"z = Zipper(\n",
" lambda x: x[1], # is_branch\n",
" lambda x: x[1], # children\n",
" lambda x, ys: (x[0], ys), # make_node\n",
" ('root', [('a', [('aa', 1),\n",
" ('ab', 2),\n",
" ('ac', 3)]),\n",
" ('b', [('ba', 4),\n",
" ('bb', 5),\n",
" ('bc', [('bca', 6),\n",
" ('bcb', 7)])])]))\n",
"\n",
"node = z.down().rightmost().down().rightmost().down().right()\n",
"print node\n",
"print\n",
"print '/'.join(p[0] for p in node.path) + '/%s = %s' % node.node"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Zipper[node: ('bcb', 7), path: [('root', [('a', [('aa', 1), ('ab', 2), ('ac', 3)]), ('b', [('ba', 4), ('bb', 5), ('bc', [('bca', 6), ('bcb', 7)])])]), ('b', [('ba', 4), ('bb', 5), ('bc', [('bca', 6), ('bcb', 7)])]), ('bc', [('bca', 6), ('bcb', 7)])]]\n",
"\n",
"root/b/bc/bcb = 7\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import xml.dom.minidom as md"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def replace_element(e, chs):\n",
" # \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u043f\u043e\u043a\u0430 \u043d\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430\n",
" return e\n",
"\n",
"def get_nonempty_children(e):\n",
" return [\n",
" ch.cloneNode(True)\n",
" for ch in e.childNodes\n",
" if not (\n",
" ch.nodeType == md.Node.TEXT_NODE\n",
" and\n",
" ch.data.isspace()\n",
" )\n",
" ]\n",
"\n",
"z = Zipper(\n",
" lambda e: e.hasChildNodes,\n",
" get_nonempty_children,\n",
" replace_element,\n",
"\n",
" md.parseString('''\n",
" <root>\n",
" <branch>\n",
" <leaf>1</leaf>\n",
" <leaf>2</leaf>\n",
" </branch>\n",
" <folder>\n",
" <leaf>3</leaf>\n",
" <tag>Value</tag>\n",
" <innerFolder>\n",
" <deepTag>Hello!</deepTag>\n",
" </innerFolder>\n",
" </folder>\n",
" </root>\n",
" ''').firstChild\n",
")\n",
"\n",
"\n",
"n = z.down().rightmost().down().rightmost().down().down()\n",
"print n.node.data"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Hello!\n"
]
}
],
"prompt_number": 6
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment