autodoc/source/ary/inc/sortedids.hxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: sortedids.hxx,v $
  10  * $Revision: 1.3 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 #ifndef ARY_SORTEDIDS_HXX
  32 #define ARY_SORTEDIDS_HXX
  33
  34
  35 // USED SERVICES
  36 #include <algorithm>
  37 #include <cosv/tpl/range.hxx>
  38
  39
  40
  41
  42 namespace ary
  43 {
  44
  45
  46 /** Implementation of a set of children to an entity in the Autodoc
  47     repository. The children are sorted.
  48
  49     @tpl COMPARE
  50     Needs to provide types:
  51         entity_base_type
  52         id_type
  53         key_type
  54
  55     and functions:
  56         static entity_base_type &
  57                         EntityOf_(
  58                             id_type             i_id );
  59         static const key_type &
  60                         KeyOf_(
  61                             const entity_type & i_entity );
  62         static bool     Lesser_(
  63                             const key_type &    i_1,
  64                             const key_type &    i_2 );
  65 */
  66 template<class COMPARE>
  67 class SortedIds
  68 {
  69   public:
  70     typedef typename COMPARE::id_type                   element_t;
  71     typedef typename COMPARE::key_type                  key_t;
  72     typedef std::vector<element_t>                      data_t;
  73     typedef typename data_t::const_iterator             const_iterator;
  74     typedef typename data_t::iterator                   iterator;
  75     typedef csv::range<const_iterator>                  search_result_t;
  76
  77     // LIFECYCLE
  78     explicit            SortedIds(
  79                             std::size_t         i_reserve = 0 );
  80                         ~SortedIds();
  81
  82     // OPERATIONS
  83     void                Add(
  84                             element_t           i_elem );
  85     // INQUIRY
  86     const_iterator      Begin() const;
  87     const_iterator      End() const;
  88
  89     element_t           Search(
  90                             const key_t &       i_key ) const;
  91     search_result_t     SearchAll(
  92                             const key_t &       i_key ) const;
  93     const_iterator      LowerBound(
  94                             const key_t &       i_key ) const;
  95
  96   private:
  97     typedef typename COMPARE::entity_base_type      entity_t;
  98
  99     // Locals
 100     iterator            LowerBound(
 101                             const key_t &       i_key );
 102
 103     static const key_t  &
 104                         KeyOf_(
 105                             element_t           i_child );
 106     template <class ITER>
 107     static ITER         impl_LowerBound_(
 108                             ITER                i_begin,
 109                             ITER                i_end,
 110                             const key_t &       i_key );
 111
 112     // DATA
 113     data_t              aData;
 114 };
 115
 116
 117
 118
 119 // IMPLEMENTATION
 120 template<class COMPARE>
 121 inline const typename SortedIds<COMPARE>::key_t &
 122 SortedIds<COMPARE>::KeyOf_(element_t i_child)
 123 {
 124     return COMPARE::KeyOf_(COMPARE::EntityOf_(i_child));
 125 }
 126
 127 template<class COMPARE>
 128 SortedIds<COMPARE>::SortedIds(std::size_t i_reserve)
 129     :   aData()
 130 {
 131     if (i_reserve > 0)
 132         aData.reserve(i_reserve);
 133 }
 134
 135 template<class COMPARE>
 136 SortedIds<COMPARE>::~SortedIds()
 137 {
 138 }
 139
 140 template<class COMPARE>
 141 void
 142 SortedIds<COMPARE>::Add(element_t i_elem)
 143 {
 144     aData.insert(   LowerBound( KeyOf_(i_elem) ),
 145                     i_elem );
 146 }
 147
 148 template<class COMPARE>
 149 inline typename SortedIds<COMPARE>::const_iterator
 150 SortedIds<COMPARE>::Begin() const
 151 {
 152     return aData.begin();
 153 }
 154
 155 template<class COMPARE>
 156 inline typename SortedIds<COMPARE>::const_iterator
 157 SortedIds<COMPARE>::End() const
 158 {
 159     return aData.end();
 160 }
 161
 162 template<class COMPARE>
 163 typename SortedIds<COMPARE>::element_t
 164 SortedIds<COMPARE>::Search(const key_t & i_key) const
 165 {
 166     const_iterator
 167         ret = LowerBound(i_key);
 168     return ret != aData.end() AND NOT COMPARE::Lesser_(i_key, KeyOf_(*ret))
 169             ?   *ret
 170             :   element_t(0);
 171 }
 172
 173 template<class COMPARE>
 174 typename SortedIds<COMPARE>::search_result_t
 175 SortedIds<COMPARE>::SearchAll(const key_t & i_key) const
 176 {
 177     const_iterator
 178         r1 = LowerBound(i_key);
 179     const_iterator
 180         r2 = r1;
 181     while (     r2 != aData.end()
 182             AND NOT COMPARE::Lesser_(i_key, KeyOf_(*r2)) )
 183     {
 184         ++r2;
 185     }
 186
 187     return csv::make_range(r1,r2);
 188 }
 189
 190 template<class COMPARE>
 191 inline typename SortedIds<COMPARE>::const_iterator
 192 SortedIds<COMPARE>::LowerBound(const key_t & i_key) const
 193 {
 194     return impl_LowerBound_( aData.begin(),
 195                              aData.end(),
 196                              i_key );
 197 }
 198
 199 template<class COMPARE>
 200 inline typename SortedIds<COMPARE>::iterator
 201 SortedIds<COMPARE>::LowerBound(const key_t & i_key)
 202 {
 203     return impl_LowerBound_( aData.begin(),
 204                              aData.end(),
 205                              i_key );
 206 }
 207
 208 template<class COMPARE>
 209 template <class ITER>
 210 ITER
 211 SortedIds<COMPARE>::impl_LowerBound_( ITER            i_begin,
 212                                       ITER            i_end,
 213                                       const key_t &   i_key )
 214 {
 215     ITER i1 = i_begin;
 216     ITER i2 = i_end;
 217
 218     for ( ITER it = i1 + (i2-i1)/2;
 219           i1 != i2;
 220           it = i1 + (i2-i1)/2 )
 221     {
 222         if ( COMPARE::Lesser_(KeyOf_(*it), i_key) )
 223         {
 224             i1 = it;
 225             ++i1;
 226         }
 227         else
 228         {
 229             i2 = it;
 230         }
 231     }   // end for
 232
 233     return i1;
 234 }
 235
 236
 237
 238
 239 }   // namespace ary
 240 #endif