bp.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from unittest import TestCase, TestLoader, TextTestRunner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 348,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "fig1_B = np.array([1, 1, 1, 0, 1, 0, 1, 1 ,0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0], dtype=bool)\n",
    "assert fig1_B.sum() == (float(fig1_B.size) / 2)\n",
    "\n",
    "### NOTE: some doctext strings are copied and pasted from manuscript\n",
    "### http://www.dcc.uchile.cl/~gnavarro/ps/tcs16.2.pdf\n",
    "class BP(object):\n",
    "    def __init__(self, B):\n",
    "        assert B.sum() == (float(B.size) / 2)\n",
    "        self.B = B\n",
    "        \n",
    "        self._k_index = [np.unique((~self.B).cumsum(), return_index=True)[1], \n",
    "                         np.unique(self.B.cumsum(), return_index=True)[1] - 1]\n",
    "        self._r_index = [(~self.B).cumsum(), self.B.cumsum()]\n",
    "        \n",
    "    def rank(self, t, i):\n",
    "        \"\"\"The number of occurrences of the bit t in B\"\"\"\n",
    "        return self._r_index[t][i]\n",
    "    \n",
    "    def select(self, t, k):\n",
    "        \"\"\"The position in B of the kth occurrence of the bit t.\"\"\"\n",
    "        return self._k_index[t][k]\n",
    "    \n",
    "    def excess(self, i):\n",
    "        \"\"\"the number of opening minus closing parentheses in B[1, i]\"\"\"\n",
    "        # same as: self.rank(1, i) - self.rank(0, i)\n",
    "        if i < 0:\n",
    "            return 0  # wasn't stated as needed but appears so given testing\n",
    "        return (2 * self.rank(1, i) - i) - 1\n",
    "    \n",
    "    def fwdsearch(self, i, d):\n",
    "        for j in range(i + 1, len(self.B)):\n",
    "            if self.excess(j) == (self.excess(i) + d):\n",
    "                return j\n",
    "    \n",
    "    def bwdsearch(self, i, d):\n",
    "        for j in range(0, i)[::-1]:\n",
    "            if self.excess(j) == (self.excess(i) + d):\n",
    "                return j\n",
    "        return -1 # wasn't stated as needed but appears so given testing\n",
    "    \n",
    "    def close(self, i):\n",
    "        \"\"\"The position of the closing parenthesis that matches B[i]\"\"\"\n",
    "        return self.fwdsearch(i, -1)\n",
    "    \n",
    "    def open(self, i):\n",
    "        \"\"\"The position of the opening parenthesis that matches B[i]\"\"\"\n",
    "        return self.bwdsearch(i, 0) + 1\n",
    "    \n",
    "    def enclose(self, i):\n",
    "        \"\"\"The opening parenthesis of the smallest matching pair that contains position i\"\"\"\n",
    "        if self.B[i]:\n",
    "            return self.bwdsearch(i, -2) + 1\n",
    "        else:\n",
    "            return self.bwdsearch(i - 1, -2) + 1\n",
    "    \n",
    "    def rmq(self, i, j):\n",
    "        \"\"\"The leftmost minimum excess in i -> j\"\"\"\n",
    "        return np.array([self.excess(k) for k in range(i, j + 1)]).argmin() + i\n",
    "    \n",
    "    def rMq(self, i, j):\n",
    "        \"\"\"The leftmost maximmum excess in i -> j\"\"\"\n",
    "        return np.array([self.excess(k) for k in range(i, j + 1)]).argmax() + i\n",
    "        \n",
    "    def depth(self, i):\n",
    "        return self.excess(i)\n",
    "    \n",
    "    def root(self):\n",
    "        return 0\n",
    "    \n",
    "    def parent(self, i):\n",
    "        return self.enclose(i)\n",
    "    \n",
    "    def isleaf(self, i):\n",
    "        # publication describe this operation as \"iff B[i+1] == 0\" which is incorrect\n",
    "        return self.B[i] and (not self.B[i + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 351,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BPTests(TestCase):\n",
    "    def setUp(self):                       \n",
    "        #                       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21\n",
    "        self.fig1_B = np.array([1, 1, 1, 0, 1, 0, 1, 1 ,0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0], dtype=bool)\n",
    "        self.BP = BP(self.fig1_B)\n",
    "        \n",
    "    def test_rank(self):\n",
    "        counts_1 = self.fig1_B.cumsum()\n",
    "        counts_0 = (~self.fig1_B).cumsum()\n",
    "        for exp, t in zip((counts_1, counts_0), (1, 0)):\n",
    "            for idx, e in enumerate(exp):\n",
    "               \n",
    "                self.assertEqual(self.BP.rank(t, idx), e)\n",
    "                \n",
    "    def test_select(self):\n",
    "        pos_1 = np.unique(self.fig1_B.cumsum(), return_index=True)[1] - 1\n",
    "        pos_0 = np.unique((~self.fig1_B).cumsum(), return_index=True)[1]\n",
    "        \n",
    "        for exp, t in zip((pos_1, pos_0), (1, 0)):\n",
    "            for k in range(1, len(exp)):\n",
    "                self.assertEqual(self.BP.select(t, k), exp[k])\n",
    "    \n",
    "    def test_rank_property(self):\n",
    "        for i in range(len(self.fig1_B)):\n",
    "            self.assertEqual(self.BP.rank(1, i) + self.BP.rank(0, i), i+1)\n",
    "    \n",
    "    def test_rank_select_property(self):\n",
    "        pos_1 = np.unique(self.fig1_B.cumsum(), return_index=True)[1] - 1\n",
    "        pos_0 = np.unique((~self.fig1_B).cumsum(), return_index=True)[1]\n",
    "        \n",
    "        for t, pos in zip((0, 1), (pos_0, pos_1)):\n",
    "            for k in range(1, len(pos)):\n",
    "                self.assertEqual(self.BP.rank(t, self.BP.select(t, k)), k)    \n",
    "                \n",
    "    def test_excess(self):\n",
    "        # from fig 2\n",
    "        exp = [1, 2, 3, 2, 3, 2, 3, 4, 3, 2, 1, 2, 1, 2, 3, 4, 3, 4, 3, 2, 1, 0]\n",
    "        for idx, e in enumerate(exp):\n",
    "            self.assertEqual(self.BP.excess(idx), e)\n",
    "            \n",
    "    def test_close(self):\n",
    "        exp = [21, 10, 3, 5, 9, 8, 12, 20, 19, 16, 18]\n",
    "        for i, e in zip(np.argwhere(self.fig1_B == 1).squeeze(), exp):\n",
    "            self.assertEqual(self.BP.close(i), e)\n",
    "            self.assertEqual(self.BP.excess(self.BP.close(i)), self.BP.excess(i) - 1)\n",
    "    \n",
    "    def test_open(self):\n",
    "        exp = [2, 4, 7, 6, 1, 11, 15, 17, 14, 13, 0]\n",
    "        for i, e in zip(np.argwhere(self.fig1_B == 0).squeeze(), exp):\n",
    "            self.assertEqual(self.BP.open(i), e)\n",
    "            self.assertEqual(self.BP.excess(self.BP.open(i) - 1), self.BP.excess(i))\n",
    "    \n",
    "    def test_enclose(self):\n",
    "        # i > 0 and i < (len(B) - 1)\n",
    "        exp = [0, 1, 1, 1, 1, 1, 6, 6, 1, 0, 0, 0, 0, 13, 14, 14, 14, 14, 13, 0]\n",
    "        for i, e in zip(range(1, len(self.fig1_B) - 1), exp):\n",
    "            self.assertEqual(self.BP.enclose(i), e)\n",
    "            \n",
    "            # unable to get this condition to work. I _think_ this condition is inaccurate?\n",
    "            #self.assertEqual(self.BP.excess(self.BP.enclose(i) - 1), self.BP.excess(i) - 2)\n",
    "     \n",
    "    def test_rmq(self):\n",
    "        #       (  (  (  )  (  )  (  (  )  )   )   (   )   (   (   (   )   (   )   )   )   )\n",
    "        #excess 1  2  3  2  3  2  3  4  3  2   1   2   1   2   3   4   3   4   3   2   1   0\n",
    "        #i      0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21\n",
    "        \n",
    "        exp = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 21],\n",
    "                  [1, 1, 1, 1, 1, 1, 1, 1, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                     [2, 3, 3, 3, 3, 3, 3, 3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                        [3, 3, 3, 3, 3, 3, 3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                           [4, 5, 5, 5, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                              [5, 5, 5, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                 [6, 6, 6, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                    [7, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                       [8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                          [9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                             [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 21],\n",
    "                                                 [11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 21],\n",
    "                                                     [12, 12, 12, 12, 12, 12, 12, 12, 12, 21],\n",
    "                                                         [13, 13, 13, 13, 13, 13, 13, 20, 21],\n",
    "                                                             [14, 14, 14, 14, 14, 19, 20, 21],\n",
    "                                                                 [15, 16, 16, 16, 19, 20, 21],\n",
    "                                                                     [16, 16, 16, 19, 20, 21],\n",
    "                                                                         [17, 18, 19, 20, 21],\n",
    "                                                                             [18, 19, 20, 21],\n",
    "                                                                                 [19, 20, 21],\n",
    "                                                                                     [20, 21],\n",
    "                                                                                         [21]]\n",
    "        for i in range(len(self.fig1_B)):\n",
    "            for j in range(i+1, len(self.fig1_B)):\n",
    "                self.assertEqual(self.BP.rmq(i, j), exp[i][j - i])\n",
    "        \n",
    "    def test_rMq(self):\n",
    "        #       (  (  (  )  (  )  (  (  )  )   )   (   )   (   (   (   )   (   )   )   )   )\n",
    "        #excess 1  2  3  2  3  2  3  4  3  2   1   2   1   2   3   4   3   4   3   2   1   0\n",
    "        #i      0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21\n",
    "        \n",
    "        exp = [[0, 1, 2, 2, 2, 2, 2, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                  [1, 2, 2, 2, 2, 2, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                     [2, 2, 2, 2, 2, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                        [3, 4, 4, 4, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                           [4, 4, 4, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                              [5, 6, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                                 [6, 7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                                    [7, 7, 7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7, 7],\n",
    "                                       [8, 8,  8,  8,  8,  8,  8, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                          [9,  9,  9,  9,  9, 14, 15, 15, 15, 15, 15, 15, 15],  \n",
    "                                             [10, 11, 11, 11, 14, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                                 [11, 11, 11, 14, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                                     [12, 13, 14, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                                         [13, 14, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                                             [14, 15, 15, 15, 15, 15, 15, 15],\n",
    "                                                                 [15, 15, 15, 15, 15, 15, 15],\n",
    "                                                                     [16, 17, 17, 17, 17, 17],\n",
    "                                                                         [17, 17, 17, 17, 17],\n",
    "                                                                             [18, 18, 18, 18],\n",
    "                                                                                 [19, 19, 19],\n",
    "                                                                                     [20, 20],\n",
    "                                                                                         [21]]\n",
    "        for i in range(len(self.fig1_B)):\n",
    "            for j in range(i+1, len(self.fig1_B)):\n",
    "                self.assertEqual(self.BP.rMq(i, j), exp[i][j - i])\n",
    "         \n",
    "    def test_root(self):\n",
    "        self.assertEqual(self.BP.root(), 0)\n",
    "    \n",
    "    def test_depth(self):\n",
    "        pass # depth(i) == excess(i)\n",
    "    \n",
    "    def test_parent(self):\n",
    "        pass # parent(i) == enclose(i)\n",
    "    \n",
    "    def test_isleaf(self):\n",
    "        exp = [0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]\n",
    "        for i, e in enumerate(exp):\n",
    "            self.assertEqual(self.BP.isleaf(i), e)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 352,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "..............\n",
      "----------------------------------------------------------------------\n",
      "Ran 14 tests in 0.019s\n",
      "\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "test_loader = TestLoader()\n",
    "runner = TextTestRunner()\n",
    "\n",
    "tests = (BPTests, )\n",
    "\n",
    "for testcase in tests:\n",
    "    suite = test_loader.loadTestsFromModule(testcase())\n",
    "    runner.run(suite)"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}