LCOV - code coverage report
Current view: top level - testsuite - IteratorTest.cc (source / functions) Hit Total Coverage
Test: STX B+ Tree Testsuite Lines: 370 370 100.0 %
Date: 2011-05-18 Functions: 13 14 92.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 109 128 85.2 %

           Branch data     Line data    Source code
       1                 :            : // $Id: IteratorTest.cc 128 2011-05-18 07:23:35Z tb $
       2                 :            : 
       3                 :            : /*
       4                 :            :  * STX B+ Tree Template Classes v0.8.6
       5                 :            :  * Copyright (C) 2008-2011 Timo Bingmann
       6                 :            :  *
       7                 :            :  * This library is free software; you can redistribute it and/or modify it
       8                 :            :  * under the terms of the GNU Lesser General Public License as published by the
       9                 :            :  * Free Software Foundation; either version 2.1 of the License, or (at your
      10                 :            :  * option) any later version.
      11                 :            :  *
      12                 :            :  * This library is distributed in the hope that it will be useful, but WITHOUT
      13                 :            :  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            :  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
      15                 :            :  * for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU Lesser General Public License
      18                 :            :  * along with this library; if not, write to the Free Software Foundation,
      19                 :            :  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <cppunit/extensions/HelperMacros.h>
      23                 :            : 
      24                 :            : #include <stdlib.h>
      25                 :            : 
      26                 :            : #include <vector>
      27                 :            : 
      28                 :            : #include <stx/btree_multiset.h>
      29                 :            : #include <stx/btree_multimap.h>
      30                 :            : #include <stx/btree_map.h>
      31                 :            : #include <stx/btree_set.h>
      32                 :            : 
      33                 :            : class IteratorTest : public CPPUNIT_NS::TestFixture
      34 [ +  - ][ #  # ]:         12 : {
      35 [ +  - ][ +  - ]:          2 :     CPPUNIT_TEST_SUITE( IteratorTest );
                 [ #  # ]
      36                 :          1 :     CPPUNIT_TEST(test_iterator1);
      37                 :          1 :     CPPUNIT_TEST(test_iterator2);
      38                 :          1 :     CPPUNIT_TEST(test_iterator3);
      39                 :          1 :     CPPUNIT_TEST(test_iterator4);
      40                 :          1 :     CPPUNIT_TEST(test_iterator5);
      41                 :          1 :     CPPUNIT_TEST(test_erase_iterator1);
      42                 :          2 :     CPPUNIT_TEST_SUITE_END();
      43                 :            : 
      44                 :            : protected:
      45                 :            : 
      46                 :            :     struct traits_nodebug
      47                 :            :     {
      48                 :            :         static const bool       selfverify = true;
      49                 :            :         static const bool       debug = false;
      50                 :            : 
      51                 :            :         static const int        leafslots = 8;
      52                 :            :         static const int        innerslots = 8;
      53                 :            :     };
      54                 :            : 
      55                 :          1 :     void test_iterator1()
      56                 :            :     {
      57                 :            :         typedef stx::btree_multiset<unsigned int,
      58                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
      59                 :            : 
      60                 :          1 :         std::vector<unsigned int> vector;
      61                 :            : 
      62                 :          1 :         srand(34234235);
      63         [ +  + ]:       3201 :         for(unsigned int i = 0; i < 3200; i++)
      64                 :            :         {
      65                 :       3200 :             vector.push_back( rand() % 1000 );
      66                 :            :         }
      67                 :            : 
      68                 :          1 :         CPPUNIT_ASSERT( vector.size() == 3200 );
      69                 :            : 
      70                 :            :         // test construction and insert(iter, iter) function
      71                 :          1 :         btree_type bt(vector.begin(), vector.end());
      72                 :            : 
      73                 :          1 :         CPPUNIT_ASSERT( bt.size() == 3200 );
      74                 :            : 
      75                 :            :         // copy for later use
      76                 :          1 :         btree_type bt2 = bt;
      77                 :            : 
      78                 :            :         // empty out the first bt
      79                 :          1 :         srand(34234235);
      80         [ +  + ]:       3201 :         for(unsigned int i = 0; i < 3200; i++)
      81                 :            :         {
      82                 :       3200 :             CPPUNIT_ASSERT(bt.size() == 3200 - i);
      83                 :       3200 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
      84                 :       3200 :             CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
      85                 :            :         }
      86                 :            : 
      87                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
      88                 :            : 
      89                 :            :         // copy btree values back to a vector
      90                 :            : 
      91                 :          1 :         std::vector<unsigned int> vector2;
      92                 :          1 :         vector2.assign( bt2.begin(), bt2.end() );
      93                 :            : 
      94                 :            :         // afer sorting the vector, the two must be the same
      95                 :          1 :         std::sort(vector.begin(), vector.end());
      96                 :            : 
      97                 :          1 :         CPPUNIT_ASSERT( vector == vector2 );
      98                 :            : 
      99                 :            :         // test reverse iterator
     100                 :          1 :         vector2.clear();
     101                 :          1 :         vector2.assign( bt2.rbegin(), bt2.rend() );
     102                 :            : 
     103                 :          1 :         std::reverse(vector.begin(), vector.end());
     104                 :            : 
     105                 :          1 :         btree_type::reverse_iterator ri = bt2.rbegin();
     106         [ +  + ]:       3201 :         for(unsigned int i = 0; i < vector2.size(); ++i)
     107                 :            :         {
     108                 :       3200 :             CPPUNIT_ASSERT( vector[i] == vector2[i] );
     109                 :       3200 :             CPPUNIT_ASSERT( vector[i] == *ri );
     110                 :            : 
     111                 :       3200 :             ri++;
     112                 :            :         }
     113                 :            : 
     114                 :          1 :         CPPUNIT_ASSERT( ri == bt2.rend() );
     115                 :          1 :     }
     116                 :            : 
     117                 :          1 :     void test_iterator2()
     118                 :            :     {
     119                 :            :         typedef stx::btree_multimap<unsigned int, unsigned int,
     120                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
     121                 :            : 
     122                 :          1 :         std::vector< btree_type::value_type > vector;
     123                 :            : 
     124                 :          1 :         srand(34234235);
     125         [ +  + ]:       3201 :         for(unsigned int i = 0; i < 3200; i++)
     126                 :            :         {
     127                 :       3200 :             vector.push_back( btree_type::value_type(rand() % 1000, 0) );
     128                 :            :         }
     129                 :            : 
     130                 :          1 :         CPPUNIT_ASSERT( vector.size() == 3200 );
     131                 :            : 
     132                 :            :         // test construction and insert(iter, iter) function
     133                 :          1 :         btree_type bt(vector.begin(), vector.end());
     134                 :            : 
     135                 :          1 :         CPPUNIT_ASSERT( bt.size() == 3200 );
     136                 :            : 
     137                 :            :         // copy for later use
     138                 :          1 :         btree_type bt2 = bt;
     139                 :            : 
     140                 :            :         // empty out the first bt
     141                 :          1 :         srand(34234235);
     142         [ +  + ]:       3201 :         for(unsigned int i = 0; i < 3200; i++)
     143                 :            :         {
     144                 :       3200 :             CPPUNIT_ASSERT(bt.size() == 3200 - i);
     145                 :       3200 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 1000) );
     146                 :       3200 :             CPPUNIT_ASSERT(bt.size() == 3200 - i - 1);
     147                 :            :         }
     148                 :            : 
     149                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
     150                 :            : 
     151                 :            :         // copy btree values back to a vector
     152                 :            : 
     153                 :          1 :         std::vector< btree_type::value_type > vector2;
     154                 :          1 :         vector2.assign( bt2.begin(), bt2.end() );
     155                 :            : 
     156                 :            :         // afer sorting the vector, the two must be the same
     157                 :          1 :         std::sort(vector.begin(), vector.end());
     158                 :            : 
     159                 :          1 :         CPPUNIT_ASSERT( vector == vector2 );
     160                 :            : 
     161                 :            :         // test reverse iterator
     162                 :          1 :         vector2.clear();
     163                 :          1 :         vector2.assign( bt2.rbegin(), bt2.rend() );
     164                 :            : 
     165                 :          1 :         std::reverse(vector.begin(), vector.end());
     166                 :            : 
     167                 :          1 :         btree_type::reverse_iterator ri = bt2.rbegin();
     168         [ +  + ]:       3201 :         for(unsigned int i = 0; i < vector2.size(); ++i, ++ri)
     169                 :            :         {
     170                 :       3200 :             CPPUNIT_ASSERT( vector[i].first == vector2[i].first );
     171                 :       3200 :             CPPUNIT_ASSERT( vector[i].first == ri->first );
     172                 :       3200 :             CPPUNIT_ASSERT( vector[i].second == ri->second );
     173                 :            :         }
     174                 :            : 
     175                 :          1 :         CPPUNIT_ASSERT( ri == bt2.rend() );
     176                 :          1 :     }
     177                 :            : 
     178                 :          1 :     void test_iterator3()
     179                 :            :     {
     180                 :            :         typedef stx::btree_map<unsigned int, unsigned int,
     181                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
     182                 :            : 
     183                 :          1 :         btree_type map;
     184                 :            : 
     185                 :          1 :         unsigned int maxnum = 1000;
     186                 :            : 
     187         [ +  + ]:       1001 :         for(unsigned int i = 0; i < maxnum; ++i)
     188                 :            :         {
     189                 :       1000 :             map.insert( std::make_pair(i, i*3) );
     190                 :            :         }
     191                 :            : 
     192                 :            :         { // test iterator prefix++
     193                 :          1 :             unsigned int nownum = 0;
     194                 :            : 
     195         [ +  + ]:       1001 :             for(btree_type::iterator i = map.begin();
     196                 :            :                 i != map.end(); ++i)
     197                 :            :             {
     198                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     199                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     200                 :            : 
     201                 :       1000 :                 nownum++;
     202                 :            :             }
     203                 :            : 
     204                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     205                 :            :         }
     206                 :            : 
     207                 :            :         { // test iterator prefix--
     208                 :          1 :             unsigned int nownum = maxnum;
     209                 :            : 
     210                 :          1 :             btree_type::iterator i;
     211 [ -  + ][ +  + ]:       1000 :             for(i = --map.end(); i != map.begin(); --i)
     212                 :            :             {
     213                 :        999 :                 nownum--;
     214                 :            : 
     215                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     216                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     217                 :            :             }
     218                 :            : 
     219                 :          1 :             nownum--;
     220                 :            : 
     221                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     222                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     223                 :            : 
     224                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     225                 :            :         }
     226                 :            : 
     227                 :            :         { // test const_iterator prefix++
     228                 :          1 :             unsigned int nownum = 0;
     229                 :            : 
     230         [ +  + ]:       1001 :             for(btree_type::const_iterator i = map.begin();
     231                 :            :                 i != map.end(); ++i)
     232                 :            :             {
     233                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     234                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     235                 :            : 
     236                 :       1000 :                 nownum++;
     237                 :            :             }
     238                 :            : 
     239                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     240                 :            :         }
     241                 :            : 
     242                 :            :         { // test const_iterator prefix--
     243                 :          1 :             unsigned int nownum = maxnum;
     244                 :            : 
     245                 :          1 :             btree_type::const_iterator i;
     246 [ -  + ][ +  + ]:       1000 :             for(i = --map.end(); i != map.begin(); --i)
     247                 :            :             {
     248                 :        999 :                 nownum--;
     249                 :            : 
     250                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     251                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     252                 :            :             }
     253                 :            : 
     254                 :          1 :             nownum--;
     255                 :            : 
     256                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     257                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     258                 :            : 
     259                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     260                 :            :         }
     261                 :            : 
     262                 :            :         { // test reverse_iterator prefix++
     263                 :          1 :             unsigned int nownum = maxnum;
     264                 :            : 
     265         [ +  + ]:       1001 :             for(btree_type::reverse_iterator i = map.rbegin();
     266                 :            :                 i != map.rend(); ++i)
     267                 :            :             {
     268                 :       1000 :                 nownum--;
     269                 :            : 
     270                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     271                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     272                 :            :             }
     273                 :            : 
     274                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     275                 :            :         }
     276                 :            : 
     277                 :            :         { // test reverse_iterator prefix--
     278                 :          1 :             unsigned int nownum = 0;
     279                 :            : 
     280                 :          1 :             btree_type::reverse_iterator i;
     281 [ -  + ][ +  + ]:       1000 :             for(i = --map.rend(); i != map.rbegin(); --i)
     282                 :            :             {
     283                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     284                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     285                 :            : 
     286                 :        999 :                 nownum++;
     287                 :            :             }
     288                 :            : 
     289                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     290                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     291                 :            : 
     292                 :          1 :             nownum++;
     293                 :            : 
     294                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     295                 :            :         }
     296                 :            : 
     297                 :            :         { // test const_reverse_iterator prefix++
     298                 :          1 :             unsigned int nownum = maxnum;
     299                 :            : 
     300         [ +  + ]:       1001 :             for(btree_type::const_reverse_iterator i = map.rbegin();
     301                 :            :                 i != map.rend(); ++i)
     302                 :            :             {
     303                 :       1000 :                 nownum--;
     304                 :            : 
     305                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     306                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     307                 :            :             }
     308                 :            : 
     309                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     310                 :            :         }
     311                 :            : 
     312                 :            :         { // test const_reverse_iterator prefix--
     313                 :          1 :             unsigned int nownum = 0;
     314                 :            : 
     315                 :          1 :             btree_type::const_reverse_iterator i;
     316 [ -  + ][ +  + ]:       1000 :             for(i = --map.rend(); i != map.rbegin(); --i)
     317                 :            :             {
     318                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     319                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     320                 :            : 
     321                 :        999 :                 nownum++;
     322                 :            :             }
     323                 :            : 
     324                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     325                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     326                 :            : 
     327                 :          1 :             nownum++;
     328                 :            : 
     329                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     330                 :            :         }
     331                 :            : 
     332                 :            :         // postfix
     333                 :            : 
     334                 :            :         { // test iterator postfix++
     335                 :          1 :             unsigned int nownum = 0;
     336                 :            : 
     337         [ +  + ]:       1001 :             for(btree_type::iterator i = map.begin();
     338                 :            :                 i != map.end(); i++)
     339                 :            :             {
     340                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     341                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     342                 :            : 
     343                 :       1000 :                 nownum++;
     344                 :            :             }
     345                 :            : 
     346                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     347                 :            :         }
     348                 :            : 
     349                 :            :         { // test iterator postfix--
     350                 :          1 :             unsigned int nownum = maxnum;
     351                 :            : 
     352                 :          1 :             btree_type::iterator i;
     353 [ -  + ][ +  + ]:       1000 :             for(i = --map.end(); i != map.begin(); i--)
     354                 :            :             {
     355                 :        999 :                 nownum--;
     356                 :            : 
     357                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     358                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     359                 :            :             }
     360                 :            : 
     361                 :          1 :             nownum--;
     362                 :            : 
     363                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     364                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     365                 :            : 
     366                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     367                 :            :         }
     368                 :            : 
     369                 :            :         { // test const_iterator postfix++
     370                 :          1 :             unsigned int nownum = 0;
     371                 :            : 
     372         [ +  + ]:       1001 :             for(btree_type::const_iterator i = map.begin();
     373                 :            :                 i != map.end(); i++)
     374                 :            :             {
     375                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     376                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     377                 :            : 
     378                 :       1000 :                 nownum++;
     379                 :            :             }
     380                 :            : 
     381                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     382                 :            :         }
     383                 :            : 
     384                 :            :         { // test const_iterator postfix--
     385                 :          1 :             unsigned int nownum = maxnum;
     386                 :            : 
     387                 :          1 :             btree_type::const_iterator i;
     388 [ -  + ][ +  + ]:       1000 :             for(i = --map.end(); i != map.begin(); i--)
     389                 :            :             {
     390                 :        999 :                 nownum--;
     391                 :            : 
     392                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     393                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     394                 :            :             }
     395                 :            : 
     396                 :          1 :             nownum--;
     397                 :            : 
     398                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     399                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     400                 :            : 
     401                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     402                 :            :         }
     403                 :            : 
     404                 :            :         { // test reverse_iterator postfix++
     405                 :          1 :             unsigned int nownum = maxnum;
     406                 :            : 
     407         [ +  + ]:       1001 :             for(btree_type::reverse_iterator i = map.rbegin();
     408                 :            :                 i != map.rend(); i++)
     409                 :            :             {
     410                 :       1000 :                 nownum--;
     411                 :            : 
     412                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     413                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     414                 :            :             }
     415                 :            : 
     416                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     417                 :            :         }
     418                 :            : 
     419                 :            :         { // test reverse_iterator postfix--
     420                 :          1 :             unsigned int nownum = 0;
     421                 :            : 
     422                 :          1 :             btree_type::reverse_iterator i;
     423 [ -  + ][ +  + ]:       1000 :             for(i = --map.rend(); i != map.rbegin(); i--)
     424                 :            :             {
     425                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     426                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     427                 :            : 
     428                 :        999 :                 nownum++;
     429                 :            :             }
     430                 :            : 
     431                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     432                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     433                 :            : 
     434                 :          1 :             nownum++;
     435                 :            : 
     436                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     437                 :            :         }
     438                 :            : 
     439                 :            :         { // test const_reverse_iterator postfix++
     440                 :          1 :             unsigned int nownum = maxnum;
     441                 :            : 
     442         [ +  + ]:       1001 :             for(btree_type::const_reverse_iterator i = map.rbegin();
     443                 :            :                 i != map.rend(); i++)
     444                 :            :             {
     445                 :       1000 :                 nownum--;
     446                 :            : 
     447                 :       1000 :                 CPPUNIT_ASSERT( nownum == i->first );
     448                 :       1000 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     449                 :            :             }
     450                 :            : 
     451                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     452                 :            :         }
     453                 :            : 
     454                 :            :         { // test const_reverse_iterator postfix--
     455                 :          1 :             unsigned int nownum = 0;
     456                 :            : 
     457                 :          1 :             btree_type::const_reverse_iterator i;
     458 [ -  + ][ +  + ]:       1000 :             for(i = --map.rend(); i != map.rbegin(); i--)
     459                 :            :             {
     460                 :        999 :                 CPPUNIT_ASSERT( nownum == i->first );
     461                 :        999 :                 CPPUNIT_ASSERT( nownum * 3 == i->second );
     462                 :            : 
     463                 :        999 :                 nownum++;
     464                 :            :             }
     465                 :            : 
     466                 :          1 :             CPPUNIT_ASSERT( nownum == i->first );
     467                 :          1 :             CPPUNIT_ASSERT( nownum * 3 == i->second );
     468                 :            : 
     469                 :          1 :             nownum++;
     470                 :            : 
     471                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     472                 :          1 :         }
     473                 :          1 :     }
     474                 :            : 
     475                 :          1 :     void test_iterator4()
     476                 :            :     {
     477                 :            :         typedef stx::btree_set<unsigned int,
     478                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
     479                 :            : 
     480                 :          1 :         btree_type set;
     481                 :            : 
     482                 :          1 :         unsigned int maxnum = 1000;
     483                 :            : 
     484         [ +  + ]:       1001 :         for(unsigned int i = 0; i < maxnum; ++i)
     485                 :            :         {
     486                 :       1000 :             set.insert(i);
     487                 :            :         }
     488                 :            : 
     489                 :            :         { // test iterator prefix++
     490                 :          1 :             unsigned int nownum = 0;
     491                 :            : 
     492         [ +  + ]:       1001 :             for(btree_type::iterator i = set.begin();
     493                 :            :                 i != set.end(); ++i)
     494                 :            :             {
     495                 :       1000 :                 CPPUNIT_ASSERT( nownum == *i );
     496                 :       1000 :                 nownum++;
     497                 :            :             }
     498                 :            : 
     499                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     500                 :            :         }
     501                 :            : 
     502                 :            :         { // test iterator prefix--
     503                 :          1 :             unsigned int nownum = maxnum;
     504                 :            : 
     505                 :          1 :             btree_type::iterator i;
     506         [ +  + ]:       1000 :             for(i = --set.end(); i != set.begin(); --i)
     507                 :            :             {
     508                 :        999 :                 CPPUNIT_ASSERT( --nownum == *i );
     509                 :            :             }
     510                 :            : 
     511                 :          1 :             CPPUNIT_ASSERT( --nownum == *i );
     512                 :            : 
     513                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     514                 :            :         }
     515                 :            : 
     516                 :            :         { // test const_iterator prefix++
     517                 :          1 :             unsigned int nownum = 0;
     518                 :            : 
     519         [ +  + ]:       1001 :             for(btree_type::const_iterator i = set.begin();
     520                 :            :                 i != set.end(); ++i)
     521                 :            :             {
     522                 :       1000 :                 CPPUNIT_ASSERT( nownum++ == *i );
     523                 :            :             }
     524                 :            : 
     525                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     526                 :            :         }
     527                 :            : 
     528                 :            :         { // test const_iterator prefix--
     529                 :          1 :             unsigned int nownum = maxnum;
     530                 :            : 
     531                 :          1 :             btree_type::const_iterator i;
     532         [ +  + ]:       1000 :             for(i = --set.end(); i != set.begin(); --i)
     533                 :            :             {
     534                 :        999 :                 CPPUNIT_ASSERT( --nownum == *i );
     535                 :            :             }
     536                 :            : 
     537                 :          1 :             CPPUNIT_ASSERT( --nownum == *i );
     538                 :            : 
     539                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     540                 :            :         }
     541                 :            : 
     542                 :            :         { // test reverse_iterator prefix++
     543                 :          1 :             unsigned int nownum = maxnum;
     544                 :            : 
     545         [ +  + ]:       1001 :             for(btree_type::reverse_iterator i = set.rbegin();
     546                 :            :                 i != set.rend(); ++i)
     547                 :            :             {
     548                 :       1000 :                 CPPUNIT_ASSERT( --nownum == *i );
     549                 :            :             }
     550                 :            : 
     551                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     552                 :            :         }
     553                 :            : 
     554                 :            :         { // test reverse_iterator prefix--
     555                 :          1 :             unsigned int nownum = 0;
     556                 :            : 
     557                 :          1 :             btree_type::reverse_iterator i;
     558         [ +  + ]:       1000 :             for(i = --set.rend(); i != set.rbegin(); --i)
     559                 :            :             {
     560                 :        999 :                 CPPUNIT_ASSERT( nownum++ == *i );
     561                 :            :             }
     562                 :            : 
     563                 :          1 :             CPPUNIT_ASSERT( nownum++ == *i );
     564                 :            : 
     565                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     566                 :            :         }
     567                 :            : 
     568                 :            :         { // test const_reverse_iterator prefix++
     569                 :          1 :             unsigned int nownum = maxnum;
     570                 :            : 
     571         [ +  + ]:       1001 :             for(btree_type::const_reverse_iterator i = set.rbegin();
     572                 :            :                 i != set.rend(); ++i)
     573                 :            :             {
     574                 :       1000 :                 CPPUNIT_ASSERT( --nownum == *i );
     575                 :            :             }
     576                 :            : 
     577                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     578                 :            :         }
     579                 :            : 
     580                 :            :         { // test const_reverse_iterator prefix--
     581                 :          1 :             unsigned int nownum = 0;
     582                 :            : 
     583                 :          1 :             btree_type::const_reverse_iterator i;
     584         [ +  + ]:       1000 :             for(i = --set.rend(); i != set.rbegin(); --i)
     585                 :            :             {
     586                 :        999 :                 CPPUNIT_ASSERT( nownum++ == *i );
     587                 :            :             }
     588                 :            : 
     589                 :          1 :             CPPUNIT_ASSERT( nownum++ == *i );
     590                 :            : 
     591                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     592                 :            :         }
     593                 :            : 
     594                 :            :         // postfix
     595                 :            : 
     596                 :            :         { // test iterator postfix++
     597                 :          1 :             unsigned int nownum = 0;
     598                 :            : 
     599         [ +  + ]:       1001 :             for(btree_type::iterator i = set.begin();
     600                 :            :                 i != set.end(); i++)
     601                 :            :             {
     602                 :       1000 :                 CPPUNIT_ASSERT( nownum++ == *i );
     603                 :            :             }
     604                 :            : 
     605                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     606                 :            :         }
     607                 :            : 
     608                 :            :         { // test iterator postfix--
     609                 :          1 :             unsigned int nownum = maxnum;
     610                 :            : 
     611                 :          1 :             btree_type::iterator i;
     612         [ +  + ]:       1000 :             for(i = --set.end(); i != set.begin(); i--)
     613                 :            :             {
     614                 :            : 
     615                 :        999 :                 CPPUNIT_ASSERT( --nownum == *i );
     616                 :            :             }
     617                 :            : 
     618                 :          1 :             CPPUNIT_ASSERT( --nownum == *i );
     619                 :            : 
     620                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     621                 :            :         }
     622                 :            : 
     623                 :            :         { // test const_iterator postfix++
     624                 :          1 :             unsigned int nownum = 0;
     625                 :            : 
     626         [ +  + ]:       1001 :             for(btree_type::const_iterator i = set.begin();
     627                 :            :                 i != set.end(); i++)
     628                 :            :             {
     629                 :       1000 :                 CPPUNIT_ASSERT( nownum++ == *i );
     630                 :            :             }
     631                 :            : 
     632                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     633                 :            :         }
     634                 :            : 
     635                 :            :         { // test const_iterator postfix--
     636                 :          1 :             unsigned int nownum = maxnum;
     637                 :            : 
     638                 :          1 :             btree_type::const_iterator i;
     639         [ +  + ]:       1000 :             for(i = --set.end(); i != set.begin(); i--)
     640                 :            :             {
     641                 :        999 :                 CPPUNIT_ASSERT( --nownum == *i );
     642                 :            :             }
     643                 :            : 
     644                 :          1 :             CPPUNIT_ASSERT( --nownum == *i );
     645                 :            : 
     646                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     647                 :            :         }
     648                 :            : 
     649                 :            :         { // test reverse_iterator postfix++
     650                 :          1 :             unsigned int nownum = maxnum;
     651                 :            : 
     652         [ +  + ]:       1001 :             for(btree_type::reverse_iterator i = set.rbegin();
     653                 :            :                 i != set.rend(); i++)
     654                 :            :             {
     655                 :       1000 :                 CPPUNIT_ASSERT( --nownum == *i );
     656                 :            :             }
     657                 :            : 
     658                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     659                 :            :         }
     660                 :            : 
     661                 :            :         { // test reverse_iterator postfix--
     662                 :          1 :             unsigned int nownum = 0;
     663                 :            : 
     664                 :          1 :             btree_type::reverse_iterator i;
     665         [ +  + ]:       1000 :             for(i = --set.rend(); i != set.rbegin(); i--)
     666                 :            :             {
     667                 :        999 :                 CPPUNIT_ASSERT( nownum++ == *i );
     668                 :            :             }
     669                 :            : 
     670                 :          1 :             CPPUNIT_ASSERT( nownum++ == *i );
     671                 :            : 
     672                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     673                 :            :         }
     674                 :            : 
     675                 :            :         { // test const_reverse_iterator postfix++
     676                 :          1 :             unsigned int nownum = maxnum;
     677                 :            : 
     678         [ +  + ]:       1001 :             for(btree_type::const_reverse_iterator i = set.rbegin();
     679                 :            :                 i != set.rend(); i++)
     680                 :            :             {
     681                 :       1000 :                 CPPUNIT_ASSERT( --nownum == *i );
     682                 :            :             }
     683                 :            : 
     684                 :          1 :             CPPUNIT_ASSERT(nownum == 0);
     685                 :            :         }
     686                 :            : 
     687                 :            :         { // test const_reverse_iterator postfix--
     688                 :          1 :             unsigned int nownum = 0;
     689                 :            : 
     690                 :          1 :             btree_type::const_reverse_iterator i;
     691         [ +  + ]:       1000 :             for(i = --set.rend(); i != set.rbegin(); i--)
     692                 :            :             {
     693                 :        999 :                 CPPUNIT_ASSERT( nownum++ == *i );
     694                 :            :             }
     695                 :            : 
     696                 :          1 :             CPPUNIT_ASSERT( nownum++ == *i );
     697                 :            : 
     698                 :          1 :             CPPUNIT_ASSERT(nownum == maxnum);
     699                 :          1 :         }
     700                 :          1 :     }
     701                 :            : 
     702                 :          1 :     void test_iterator5()
     703                 :            :     {
     704                 :            :         typedef stx::btree_set<unsigned int,
     705                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
     706                 :            : 
     707                 :          1 :         btree_type set;
     708                 :            : 
     709                 :          1 :         unsigned int maxnum = 100;
     710                 :            : 
     711         [ +  + ]:        101 :         for(unsigned int i = 0; i < maxnum; ++i)
     712                 :            :         {
     713                 :        100 :             set.insert(i);
     714                 :            :         }
     715                 :            : 
     716                 :            :         {
     717                 :          1 :             btree_type::iterator it;
     718                 :            : 
     719                 :          1 :             it = set.begin();
     720                 :          1 :             it--;
     721                 :          1 :             CPPUNIT_ASSERT( it == set.begin() );
     722                 :            : 
     723                 :          1 :             it = set.begin();
     724                 :          1 :             --it;
     725                 :          1 :             CPPUNIT_ASSERT( it == set.begin() );
     726                 :            : 
     727                 :          1 :             it = set.end();
     728                 :          1 :             it++;
     729                 :          1 :             CPPUNIT_ASSERT( it == set.end() );
     730                 :            : 
     731                 :          1 :             it = set.end();
     732                 :          1 :             ++it;
     733                 :          1 :             CPPUNIT_ASSERT( it == set.end() );
     734                 :            :         }
     735                 :            : 
     736                 :            :         {
     737                 :          1 :             btree_type::const_iterator it;
     738                 :            : 
     739                 :          1 :             it = set.begin();
     740                 :          1 :             it--;
     741                 :          1 :             CPPUNIT_ASSERT( it == set.begin() );
     742                 :            : 
     743                 :          1 :             it = set.begin();
     744                 :          1 :             --it;
     745                 :          1 :             CPPUNIT_ASSERT( it == set.begin() );
     746                 :            : 
     747                 :          1 :             it = set.end();
     748                 :          1 :             it++;
     749                 :          1 :             CPPUNIT_ASSERT( it == set.end() );
     750                 :            : 
     751                 :          1 :             it = set.end();
     752                 :          1 :             ++it;
     753                 :          1 :             CPPUNIT_ASSERT( it == set.end() );
     754                 :            :         }
     755                 :            : 
     756                 :            :         {
     757                 :          1 :             btree_type::reverse_iterator it;
     758                 :            : 
     759                 :          1 :             it = set.rbegin();
     760                 :          1 :             it--;
     761                 :          1 :             CPPUNIT_ASSERT( it == set.rbegin() );
     762                 :            : 
     763                 :          1 :             it = set.rbegin();
     764                 :          1 :             --it;
     765                 :          1 :             CPPUNIT_ASSERT( it == set.rbegin() );
     766                 :            : 
     767                 :          1 :             it = set.rend();
     768                 :          1 :             it++;
     769                 :          1 :             CPPUNIT_ASSERT( it == set.rend() );
     770                 :            : 
     771                 :          1 :             it = set.rend();
     772                 :          1 :             ++it;
     773                 :          1 :             CPPUNIT_ASSERT( it == set.rend() );
     774                 :            :         }
     775                 :            : 
     776                 :            :         {
     777                 :          1 :             btree_type::const_reverse_iterator it;
     778                 :            : 
     779                 :          1 :             it = set.rbegin();
     780                 :          1 :             it--;
     781                 :          1 :             CPPUNIT_ASSERT( it == set.rbegin() );
     782                 :            : 
     783                 :          1 :             it = set.rbegin();
     784                 :          1 :             --it;
     785                 :          1 :             CPPUNIT_ASSERT( it == set.rbegin() );
     786                 :            : 
     787                 :          1 :             it = set.rend();
     788                 :          1 :             it++;
     789                 :          1 :             CPPUNIT_ASSERT( it == set.rend() );
     790                 :            : 
     791                 :          1 :             it = set.rend();
     792                 :          1 :             ++it;
     793                 :          1 :             CPPUNIT_ASSERT( it == set.rend() );
     794                 :          1 :         }
     795                 :          1 :     }
     796                 :            : 
     797                 :          1 :     void test_erase_iterator1()
     798                 :            :     {
     799                 :            :         typedef stx::btree_multimap<int, int,
     800                 :            :             std::less<int>, struct traits_nodebug> btree_type;
     801                 :            : 
     802                 :          1 :         btree_type map;
     803                 :            : 
     804                 :          1 :         const int size1 = 32; 
     805                 :          1 :         const int size2 = 256; 
     806                 :            : 
     807         [ +  + ]:         33 :         for (int i = 0; i < size1; ++i)
     808                 :            :         {
     809         [ +  + ]:       8224 :             for (int j = 0; j < size2; ++j)
     810                 :            :             {
     811                 :       8192 :                 map.insert2(i,j);
     812                 :            :             }
     813                 :            :         }
     814                 :            : 
     815                 :          1 :         CPPUNIT_ASSERT( map.size() == size1 * size2 );
     816                 :            : 
     817                 :            :         // erase in reverse order. that should be the worst case for
     818                 :            :         // erase_iter()
     819                 :            : 
     820         [ +  + ]:         33 :         for (int i = size1-1; i >= 0; --i)
     821                 :            :         {
     822         [ +  + ]:       8224 :             for (int j = size2-1; j >= 0; --j)
     823                 :            :             {
     824                 :            :                 // find iterator
     825                 :       8192 :                 btree_type::iterator it = map.find(i);
     826                 :            :                 
     827 [ +  - ][ +  - ]:      52736 :                 while (it != map.end() && it.key() == i && it.data() != j)
         [ +  + ][ +  + ]
     828                 :      44544 :                     ++it;
     829                 :            : 
     830                 :       8192 :                 CPPUNIT_ASSERT( it.key() == i );
     831                 :       8192 :                 CPPUNIT_ASSERT( it.data() == j );
     832                 :            : 
     833                 :       8192 :                 unsigned int mapsize = map.size();
     834                 :       8192 :                 map.erase(it);
     835                 :       8192 :                 CPPUNIT_ASSERT( map.size() == mapsize - 1 );
     836                 :            :             }
     837                 :            :         }
     838                 :            : 
     839                 :          1 :         CPPUNIT_ASSERT( map.size() == 0 );
     840                 :          1 :     }
     841                 :            : };
     842                 :            : 
     843 [ +  - ][ +  - ]:          3 : CPPUNIT_TEST_SUITE_REGISTRATION( IteratorTest );

Generated by: LCOV version 1.9