sc/inc/mtvfunctions.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  */
   9
  10 #pragma once
  11
  12 #include <cstdlib>
  13 #include <mdds/multi_type_vector/types.hpp>
  14
  15 namespace sc {
  16
  17 template<typename SizeT, typename Ret = bool>
  18 struct FuncElseNoOp
  19 {
  20     Ret operator() (mdds::mtv::element_t, SizeT, SizeT) const
  21     {
  22         return Ret();
  23     }
  24 };
  25
  26 template<typename FuncElem, typename Elem>
  27 struct FuncNotElem
  28 {
  29     FuncElem& func;
  30     FuncNotElem(FuncElem& f) : func(f) {}
  31     bool operator() (size_t s, Elem elem) const
  32     {
  33         return !func(s, elem);
  34     }
  35 };
  36
  37 /**
  38  * Generic algorithm to parse blocks of multi_type_vector either partially
  39  * or fully.
  40  */
  41 template<typename StoreT, typename Func>
  42 typename StoreT::const_iterator
  43 ParseBlock(
  44     const typename StoreT::const_iterator& itPos, const StoreT& rStore, Func& rFunc,
  45     typename StoreT::size_type nStart, typename StoreT::size_type nEnd)
  46 {
  47     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
  48
  49     PositionType aPos = rStore.position(itPos, nStart);
  50     typename StoreT::const_iterator it = aPos.first;
  51     typename StoreT::size_type nOffset = aPos.second;
  52     typename StoreT::size_type nDataSize = 0;
  53     typename StoreT::size_type nTopRow = nStart;
  54
  55     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
  56     {
  57         bool bLastBlock = false;
  58         nDataSize = it->size - nOffset;
  59         if (nTopRow + nDataSize - 1 > nEnd)
  60         {
  61             // Truncate the block.
  62             nDataSize = nEnd - nTopRow + 1;
  63             bLastBlock = true;
  64         }
  65
  66         rFunc(*it, nOffset, nDataSize);
  67
  68         if (bLastBlock)
  69             break;
  70     }
  71
  72     return it;
  73 }
  74
  75 /**
  76  * Non-const variant of the above function. TODO: Find a way to merge these
  77  * two in an elegant way.
  78  */
  79 template<typename StoreT, typename Func>
  80 typename StoreT::iterator
  81 ProcessBlock(const typename StoreT::iterator& itPos, StoreT& rStore, Func& rFunc, typename StoreT::size_type nStart, typename StoreT::size_type nEnd)
  82 {
  83     typedef std::pair<typename StoreT::iterator, typename StoreT::size_type> PositionType;
  84
  85     PositionType aPos = rStore.position(itPos, nStart);
  86     typename StoreT::iterator it = aPos.first;
  87     typename StoreT::size_type nOffset = aPos.second;
  88     typename StoreT::size_type nDataSize = 0;
  89     typename StoreT::size_type nCurRow = nStart;
  90
  91     for (; it != rStore.end() && nCurRow <= nEnd; ++it, nOffset = 0, nCurRow += nDataSize)
  92     {
  93         bool bLastBlock = false;
  94         nDataSize = it->size - nOffset;
  95         if (nCurRow + nDataSize - 1 > nEnd)
  96         {
  97             // Truncate the block.
  98             nDataSize = nEnd - nCurRow + 1;
  99             bLastBlock = true;
 100         }
 101
 102         rFunc(*it, nOffset, nDataSize);
 103
 104         if (bLastBlock)
 105             break;
 106     }
 107
 108     return it;
 109 }
 110
 111 template<typename BlkT, typename ItrT, typename NodeT, typename FuncElem>
 112 void EachElem(NodeT& rNode, size_t nOffset, size_t nDataSize, FuncElem& rFuncElem)
 113 {
 114     ItrT it = BlkT::begin(*rNode.data);
 115     std::advance(it, nOffset);
 116     ItrT itEnd = it;
 117     std::advance(itEnd, nDataSize);
 118     size_t nRow = rNode.position + nOffset;
 119     for (; it != itEnd; ++it, ++nRow)
 120         rFuncElem(nRow, *it);
 121 }
 122
 123 template<typename BlkT, typename ItrT, typename NodeT, typename FuncElem>
 124 void EachElem(NodeT& rNode, FuncElem& rFuncElem)
 125 {
 126     auto it = BlkT::begin(*rNode.data);
 127     auto itEnd = BlkT::end(*rNode.data);
 128     size_t nRow = rNode.position;
 129     for (; it != itEnd; ++it, ++nRow)
 130         rFuncElem(nRow, *it);
 131 }
 132
 133 template<typename BlkT, typename ItrT, typename NodeT, typename FuncElem>
 134 void EachElemReverse(NodeT& rNode, FuncElem& rFuncElem)
 135 {
 136     auto it = BlkT::rbegin(*rNode.data);
 137     auto itEnd = BlkT::rend(*rNode.data);
 138     size_t nRow = rNode.position;
 139     for (; it != itEnd; ++it, ++nRow)
 140         rFuncElem(nRow, *it);
 141 }
 142
 143 template<typename BlkT, typename StoreT, typename FuncElem>
 144 std::pair<typename StoreT::const_iterator, size_t>
 145 CheckElem(
 146     const StoreT& rStore, const typename StoreT::const_iterator& it, size_t nOffset, size_t nDataSize,
 147     FuncElem& rFuncElem)
 148 {
 149     typedef std::pair<typename StoreT::const_iterator, size_t> PositionType;
 150
 151     typename BlkT::const_iterator itData = BlkT::begin(*it->data);
 152     std::advance(itData, nOffset);
 153     typename BlkT::const_iterator itDataEnd = itData;
 154     std::advance(itDataEnd, nDataSize);
 155     size_t nTopRow = it->position + nOffset;
 156     size_t nRow = nTopRow;
 157     for (; itData != itDataEnd; ++itData, ++nRow)
 158     {
 159         if (rFuncElem(nRow, *itData))
 160             return PositionType(it, nRow - it->position);
 161     }
 162
 163     return PositionType(rStore.end(), 0);
 164 }
 165
 166 template<typename StoreT, typename BlkT, typename FuncElem, typename FuncElse>
 167 void ParseElements1(const StoreT& rStore, FuncElem& rFuncElem, FuncElse& rFuncElse)
 168 {
 169     typename StoreT::size_type nTopRow = 0, nDataSize = 0;
 170     typename StoreT::const_iterator it = rStore.begin(), itEnd = rStore.end();
 171     for (; it != itEnd; ++it, nTopRow += nDataSize)
 172     {
 173         nDataSize = it->size;
 174         if (it->type != BlkT::block_type)
 175         {
 176             rFuncElse(it->type, nTopRow, nDataSize);
 177             continue;
 178         }
 179
 180         EachElem<BlkT, typename BlkT::const_iterator>(*it, rFuncElem);
 181     }
 182 }
 183
 184 template<typename StoreT, typename BlkT, typename FuncElem, typename FuncElse>
 185 typename StoreT::const_iterator
 186 ParseElements1(
 187     const typename StoreT::const_iterator& itPos, const StoreT& rStore,
 188     typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 189     FuncElem& rFuncElem, FuncElse& rFuncElse)
 190 {
 191     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 192
 193     PositionType aPos = rStore.position(itPos, nStart);
 194     typename StoreT::const_iterator it = aPos.first;
 195     typename StoreT::size_type nOffset = aPos.second;
 196     typename StoreT::size_type nDataSize = 0;
 197     typename StoreT::size_type nTopRow = nStart;
 198
 199     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 200     {
 201         bool bLastBlock = false;
 202         nDataSize = it->size - nOffset;
 203         if (nTopRow + nDataSize - 1 > nEnd)
 204         {
 205             // Truncate the block.
 206             nDataSize = nEnd - nTopRow + 1;
 207             bLastBlock = true;
 208         }
 209
 210         if (it->type == BlkT::block_type)
 211             EachElem<BlkT, typename BlkT::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 212         else
 213             rFuncElse(it->type, nTopRow, nDataSize);
 214
 215         if (bLastBlock)
 216             break;
 217     }
 218
 219     return it;
 220 };
 221
 222 template<typename StoreT, typename Blk1, typename Blk2, typename FuncElem, typename FuncElse>
 223 typename StoreT::const_iterator
 224 ParseElements2(
 225     const typename StoreT::const_iterator& itPos, const StoreT& rStore, typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 226     FuncElem& rFuncElem, FuncElse& rFuncElse)
 227 {
 228     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 229
 230     PositionType aPos = rStore.position(itPos, nStart);
 231     typename StoreT::const_iterator it = aPos.first;
 232     typename StoreT::size_type nOffset = aPos.second;
 233     typename StoreT::size_type nDataSize = 0;
 234     typename StoreT::size_type nTopRow = nStart;
 235
 236     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 237     {
 238         bool bLastBlock = false;
 239         nDataSize = it->size - nOffset;
 240         if (nTopRow + nDataSize - 1 > nEnd)
 241         {
 242             // Truncate the block.
 243             nDataSize = nEnd - nTopRow + 1;
 244             bLastBlock = true;
 245         }
 246
 247         switch (it->type)
 248         {
 249             case Blk1::block_type:
 250                 EachElem<Blk1, typename Blk1::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 251             break;
 252             case Blk2::block_type:
 253                 EachElem<Blk2, typename Blk2::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 254             break;
 255             default:
 256                 rFuncElse(it->type, nTopRow, nDataSize);
 257         }
 258
 259         if (bLastBlock)
 260             break;
 261     }
 262
 263     return it;
 264 }
 265
 266 template<typename StoreT, typename Blk1, typename Blk2, typename Blk3, typename Blk4, typename FuncElem, typename FuncElse>
 267 typename StoreT::const_iterator
 268 ParseElements4(
 269     const typename StoreT::const_iterator& itPos, const StoreT& rStore, typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 270     FuncElem& rFuncElem, FuncElse& rFuncElse)
 271 {
 272     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 273
 274     PositionType aPos = rStore.position(itPos, nStart);
 275     typename StoreT::const_iterator it = aPos.first;
 276     typename StoreT::size_type nOffset = aPos.second;
 277     typename StoreT::size_type nDataSize = 0;
 278     typename StoreT::size_type nTopRow = nStart;
 279
 280     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 281     {
 282         bool bLastBlock = false;
 283         nDataSize = it->size - nOffset;
 284         if (nTopRow + nDataSize - 1 > nEnd)
 285         {
 286             // Truncate the block.
 287             nDataSize = nEnd - nTopRow + 1;
 288             bLastBlock = true;
 289         }
 290
 291         switch (it->type)
 292         {
 293             case Blk1::block_type:
 294                 EachElem<Blk1, typename Blk1::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 295             break;
 296             case Blk2::block_type:
 297                 EachElem<Blk2, typename Blk2::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 298             break;
 299             case Blk3::block_type:
 300                 EachElem<Blk3, typename Blk3::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 301             break;
 302             case Blk4::block_type:
 303                 EachElem<Blk4, typename Blk4::const_iterator>(*it, nOffset, nDataSize, rFuncElem);
 304             break;
 305             default:
 306                 rFuncElse(it->type, nTopRow, nDataSize);
 307         }
 308
 309         if (bLastBlock)
 310             break;
 311     }
 312
 313     return it;
 314 }
 315
 316 template<typename StoreT, typename BlkT, typename FuncElem, typename FuncElse>
 317 void ProcessElements1(StoreT& rStore, FuncElem& rFuncElem, FuncElse& rFuncElse)
 318 {
 319     typename StoreT::size_type nTopRow = 0, nDataSize = 0;
 320     typename StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
 321     for (; it != itEnd; ++it, nTopRow += nDataSize)
 322     {
 323         nDataSize = it->size;
 324         if (it->type != BlkT::block_type)
 325         {
 326             rFuncElse(it->type, nTopRow, nDataSize);
 327             continue;
 328         }
 329
 330         EachElem<BlkT, typename BlkT::iterator>(*it, rFuncElem);
 331     }
 332 }
 333
 334 /**
 335  * This variant specifies start and end positions.
 336  */
 337 template<typename StoreT, typename BlkT, typename FuncElem, typename FuncElse>
 338 typename StoreT::iterator
 339 ProcessElements1(
 340     const typename StoreT::iterator& itPos, StoreT& rStore,
 341     typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 342     FuncElem& rFuncElem, FuncElse& rFuncElse)
 343 {
 344     typedef std::pair<typename StoreT::iterator, typename StoreT::size_type> PositionType;
 345
 346     PositionType aPos = rStore.position(itPos, nStart);
 347     typename StoreT::iterator it = aPos.first;
 348     typename StoreT::size_type nOffset = aPos.second;
 349     typename StoreT::size_type nDataSize = 0;
 350     typename StoreT::size_type nTopRow = nStart;
 351
 352     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 353     {
 354         bool bLastBlock = false;
 355         nDataSize = it->size - nOffset;
 356         if (nTopRow + nDataSize - 1 > nEnd)
 357         {
 358             // Truncate the block.
 359             nDataSize = nEnd - nTopRow + 1;
 360             bLastBlock = true;
 361         }
 362
 363         if (it->type == BlkT::block_type)
 364             EachElem<BlkT, typename BlkT::iterator>(*it, nOffset, nDataSize, rFuncElem);
 365         else
 366             rFuncElse(it->type, nTopRow, nDataSize);
 367
 368         if (bLastBlock)
 369             break;
 370     }
 371
 372     return it;
 373 };
 374
 375 template<typename StoreT, typename Blk1, typename Blk2, typename FuncElem, typename FuncElse>
 376 void ProcessElements2(StoreT& rStore, FuncElem& rFuncElem, FuncElse& rFuncElse)
 377 {
 378     typename StoreT::size_type nTopRow = 0, nDataSize = 0;
 379     typename StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
 380     for (; it != itEnd; ++it, nTopRow += nDataSize)
 381     {
 382         nDataSize = it->size;
 383         switch (it->type)
 384         {
 385             case Blk1::block_type:
 386                 EachElem<Blk1, typename Blk1::iterator>(*it, rFuncElem);
 387             break;
 388             case Blk2::block_type:
 389                 EachElem<Blk2, typename Blk2::iterator>(*it, rFuncElem);
 390             break;
 391             default:
 392                 rFuncElse(it->type, nTopRow, nDataSize);
 393         }
 394     }
 395 }
 396
 397 template<typename StoreT, typename Blk1, typename Blk2, typename FuncElem, typename FuncElse>
 398 void ProcessElements2Reverse(StoreT& rStore, FuncElem& rFuncElem, FuncElse& rFuncElse)
 399 {
 400     typename StoreT::size_type nTopRow = 0, nDataSize = 0;
 401     typename StoreT::iterator it = rStore.begin(), itEnd = rStore.end();
 402     for (; it != itEnd; ++it, nTopRow += nDataSize)
 403     {
 404         nDataSize = it->size;
 405         switch (it->type)
 406         {
 407             case Blk1::block_type:
 408                 EachElemReverse<Blk1, typename Blk1::iterator>(*it, rFuncElem);
 409             break;
 410             case Blk2::block_type:
 411                 EachElemReverse<Blk2, typename Blk2::iterator>(*it, rFuncElem);
 412             break;
 413             default:
 414                 rFuncElse(it->type, nTopRow, nDataSize);
 415         }
 416     }
 417 }
 418
 419 template<typename StoreT, typename Blk1, typename FuncElem, typename FuncElse>
 420 std::pair<typename StoreT::const_iterator, typename StoreT::size_type>
 421 FindElement1(
 422     const StoreT& rStore, typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 423     FuncElem& rFuncElem, FuncElse& rFuncElse)
 424 {
 425     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 426     typedef std::pair<typename StoreT::size_type, bool> ElseRetType;
 427
 428     PositionType aPos = rStore.position(nStart);
 429     typename StoreT::const_iterator it = aPos.first;
 430     typename StoreT::size_type nOffset = aPos.second;
 431     typename StoreT::size_type nDataSize = 0;
 432     typename StoreT::size_type nTopRow = nStart;
 433
 434     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 435     {
 436         bool bLastBlock = false;
 437         nDataSize = it->size - nOffset;
 438         if (nTopRow + nDataSize - 1 > nEnd)
 439         {
 440             // Truncate the block.
 441             nDataSize = nEnd - nTopRow + 1;
 442             bLastBlock = true;
 443         }
 444
 445         switch (it->type)
 446         {
 447             case Blk1::block_type:
 448             {
 449                 PositionType aRet = CheckElem<Blk1>(rStore, it, nOffset, nDataSize, rFuncElem);
 450                 if (aRet.first != rStore.end())
 451                     return aRet;
 452             }
 453             break;
 454             default:
 455             {
 456                 ElseRetType aRet = rFuncElse(it->type, nTopRow, nDataSize);
 457                 if (aRet.second)
 458                     return PositionType(it, aRet.first);
 459             }
 460         }
 461
 462         if (bLastBlock)
 463             break;
 464     }
 465
 466     return PositionType(rStore.end(), 0);
 467 }
 468
 469 template<typename StoreT, typename Blk1, typename Blk2, typename FuncElem, typename FuncElse>
 470 std::pair<typename StoreT::const_iterator, typename StoreT::size_type>
 471 FindElement2(
 472     const StoreT& rStore, typename StoreT::size_type nStart, typename StoreT::size_type nEnd,
 473     FuncElem& rFuncElem, FuncElse& rFuncElse)
 474 {
 475     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 476     typedef std::pair<typename StoreT::size_type, bool> ElseRetType;
 477
 478     PositionType aPos = rStore.position(nStart);
 479     typename StoreT::const_iterator it = aPos.first;
 480     typename StoreT::size_type nOffset = aPos.second;
 481     typename StoreT::size_type nDataSize = 0;
 482     typename StoreT::size_type nTopRow = nStart;
 483
 484     for (; it != rStore.end() && nTopRow <= nEnd; ++it, nOffset = 0, nTopRow += nDataSize)
 485     {
 486         bool bLastBlock = false;
 487         nDataSize = it->size - nOffset;
 488         if (nTopRow + nDataSize - 1 > nEnd)
 489         {
 490             // Truncate the block.
 491             nDataSize = nEnd - nTopRow + 1;
 492             bLastBlock = true;
 493         }
 494
 495         switch (it->type)
 496         {
 497             case Blk1::block_type:
 498             {
 499                 PositionType aRet = CheckElem<Blk1>(rStore, it, nOffset, nDataSize, rFuncElem);
 500                 if (aRet.first != rStore.end())
 501                     return aRet;
 502             }
 503             break;
 504             case Blk2::block_type:
 505             {
 506                 PositionType aRet = CheckElem<Blk2>(rStore, it, nOffset, nDataSize, rFuncElem);
 507                 if (aRet.first != rStore.end())
 508                     return aRet;
 509             }
 510             break;
 511             default:
 512             {
 513                 ElseRetType aRet = rFuncElse(*it, nOffset, nDataSize);
 514                 if (aRet.second)
 515                     return PositionType(it, aRet.first);
 516             }
 517         }
 518
 519         if (bLastBlock)
 520             break;
 521     }
 522
 523     return PositionType(rStore.end(), 0);
 524 }
 525
 526 // Efficiently set all elements for which the predicate returns true as empty.
 527 template<typename Blk1, typename StoreT, typename FuncElem>
 528 void SetElementsToEmpty1(
 529     StoreT& rStore, FuncElem& rFuncElem)
 530 {
 531     typedef std::pair<typename StoreT::const_iterator, typename StoreT::size_type> PositionType;
 532
 533     for (typename StoreT::iterator it = rStore.begin(); it != rStore.end(); ++it)
 534     {
 535         if (it->type == Blk1::block_type)
 536         {
 537             PositionType firstToEmpty = CheckElem<Blk1>(rStore, it, 0, it->size, rFuncElem);
 538             if (firstToEmpty.first != rStore.end())
 539             {
 540                 typename StoreT::size_type nFirstOffset = firstToEmpty.second;
 541                 typename StoreT::size_type nRemainingDataSize = it->size - nFirstOffset;
 542                 FuncNotElem<FuncElem, typename Blk1::value_type> notFuncElem(rFuncElem);
 543                 PositionType lastToEmpty = CheckElem<Blk1>(rStore, it, nFirstOffset, nRemainingDataSize,
 544                     notFuncElem);
 545                 typename StoreT::size_type nLastOffset = lastToEmpty.first != rStore.end()
 546                     ? lastToEmpty.second - 1 : it->size - 1;
 547                 it = rStore.set_empty(it, it->position + nFirstOffset, it->position + nLastOffset);
 548                 // The returned iterator points to the empty elements block.
 549                 assert(it->type == sc::element_type_empty);
 550             }
 551         }
 552     }
 553 }
 554
 555 }
 556
 557 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */