Line data    Source code

       1             : // Copyright (c) 2011-2023  Made to Order Software Corp.  All Rights Reserved
       2             : //
       3             : // https://snapwebsites.org/project/snapdev
       4             : // contact@m2osw.com
       5             : //
       6             : // This program is free software: you can redistribute it and/or modify
       7             : // it under the terms of the GNU General Public License as published by
       8             : // the Free Software Foundation, either version 3 of the License, or
       9             : // (at your option) any later version.
      10             : //
      11             : // This program is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : //
      16             : // You should have received a copy of the GNU General Public License
      17             : // along with this program.  If not, see <https://www.gnu.org/licenses/>.
      18             : //
      19             : // Based on: http://stackoverflow.com/questions/236129/split-a-string-in-c#1493195
      20             : //
      21             : #pragma once
      22             : 
      23             : /** \file
      24             :  * \brief Template used to remove duplicates in a container.
      25             :  *
      26             :  * Some containers, such as a vector, allow for duplicates. This function
      27             :  * implements an algorithm to remove duplicates.
      28             :  *
      29             :  * We offer several solutions to the problem of removing duplicates:
      30             :  *
      31             :  * \li The default algorithm which sorts the values first; this is the
      32             :  * \em normal algorithm for such a feature.
      33             :  * \li Consider using a container that automatically sorts such as
      34             :  * `std::set<T>` and `std::map<T,bool>`.
      35             :  * \li There are unsorted versions of containers that you may be able
      36             :  * to use for the purpose.
      37             :  */
      38             : 
      39             : // C++
      40             : //
      41             : #include    <algorithm>
      42             : 
      43             : 
      44             : 
      45             : namespace snapdev
      46             : {
      47             : 
      48             : 
      49             : /** \brief Remove duplicates in the unsorted container.
      50             :  *
      51             :  * This function goes through the elements of your container and first
      52             :  * sorts and then eliminates duplicates.
      53             :  *
      54             :  * This function works well with vectors.
      55             :  *
      56             :  * \note
      57             :  * Maps and sets are already sorted and already do not include duplicates.
      58             :  * In other words, this function is useless for such containers.
      59             :  *
      60             :  * \warning
      61             :  * On return, the elements in the container are sorted.
      62             :  *
      63             :  * \tparam ContainerT  The type of container to de-dup.
      64             :  * \param[in,out] container  The container where duplicates get removed.
      65             :  *
      66             :  * \return The reference to the input container (NOT A COPY).
      67             :  *
      68             :  * \sa sorted_remove_duplicates()
      69             :  * \sa unsorted_remove_duplicates()
      70             :  */
      71             : template<typename ContainerT>
      72          21 : ContainerT & sort_and_remove_duplicates(ContainerT & container)
      73             : {
      74          21 :     std::sort(container.begin(), container.end());
      75             : 
      76          42 :     container.erase(std::unique(
      77             :                           container.begin()
      78             :                         , container.end())
      79          42 :                     , container.end());
      80             : 
      81          21 :     return container;
      82             : }
      83             : 
      84             : 
      85             : /** \brief Remove duplicates in the sorted container.
      86             :  *
      87             :  * This function goes through the elements of your container and eliminates
      88             :  * duplicates. The input must be sorted for the algorithm to work properly.
      89             :  *
      90             :  * \note
      91             :  * Maps and sets are already sorted and already do not include duplicates.
      92             :  * In other words, this function is useless for such containers.
      93             :  *
      94             :  * \tparam ContainerT  The type of container to de-dup.
      95             :  * \param[in,out] container  The container where duplicates get removed.
      96             :  *
      97             :  * \return The reference to the input container (NOT A COPY).
      98             :  *
      99             :  * \sa sort_and_remove_duplicates()
     100             :  */
     101             : template<typename ContainerT>
     102          41 : ContainerT & sorted_remove_duplicates(ContainerT & container)
     103             : {
     104          72 :     container.erase(std::unique(
     105             :                           container.begin()
     106             :                         , container.end())
     107          62 :                     , container.end());
     108             : 
     109          41 :     return container;
     110             : }
     111             : 
     112             : 
     113             : /** \brief Function to replace duplicate objects.
     114             :  *
     115             :  * This function goes through the items of a container and overwrite
     116             :  * entries as duplicates are found.
     117             :  *
     118             :  * \warning
     119             :  * Like std::unique(), this function does not itself remove anything.
     120             :  * You must make sure to use the std::erase() to remove the last few
     121             :  * items. This is done by the unsorted_remove_duplicates() function.
     122             :  *
     123             :  * \rparam ForwardIterator  The type of iterator from your container.
     124             :  * \param[in] first  Forward iterator to the container's first element.
     125             :  * \param[in] end  Forward iterator to the container's last element + 1.
     126             :  *
     127             :  * \return The new end of your container.
     128             :  *
     129             :  * \sa https://stackoverflow.com/questions/49863158/c-remove-duplicate-values-from-a-vector-without-sorting
     130             :  * \sa unsorted_remove_duplicates()
     131             :  */
     132             : template<typename ForwardIterator>
     133           4 : ForwardIterator remove_duplicates(ForwardIterator first, ForwardIterator end)
     134             : {
     135           4 :     auto new_end(first);
     136         326 :     for(auto current(first); current != end; ++current)
     137             :     {
     138         322 :         if(std::find(first, new_end, *current) == new_end)
     139             :         {
     140         240 :             if(new_end != current)
     141             :             {
     142         158 :                 *new_end = *current;
     143             :             }
     144         240 :             ++new_end;
     145             :         }
     146             :     }
     147             : 
     148           4 :     return new_end;
     149             : }
     150             : 
     151             : 
     152             : /** \brief Remove duplicates without sorting the container.
     153             :  *
     154             :  * This function goes through the elements of your container and eliminates
     155             :  * duplicates. The input does not have to be sorted and the returned function
     156             :  * does not change the order.
     157             :  *
     158             :  * The algorithm is O(n^2). If sorting is okay, then use the
     159             :  * sort_and_remove_duplicates() directly.
     160             :  *
     161             :  * \tparam ContainerT  The type of container to de-dup.
     162             :  * \param[in,out] container  The container where duplicates get removed.
     163             :  *
     164             :  * \return The reference to the input container (NOT A COPY).
     165             :  *
     166             :  * \sa remove_duplicates()
     167             :  */
     168             : template<typename ContainerT>
     169           4 : ContainerT & unsorted_remove_duplicates(ContainerT & container)
     170             : {
     171           8 :     container.erase(remove_duplicates(
     172             :                           container.begin()
     173             :                         , container.end())
     174           8 :                     , container.end());
     175             : 
     176           4 :     return container;
     177             : }
     178             : 
     179             : 
     180             : 
     181             : } // namespace snapdev
     182             : // vim: ts=4 sw=4 et