/**************************************************************
 * 
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 * 
 *************************************************************/



#ifndef ARY_SORTEDIDS_HXX
#define ARY_SORTEDIDS_HXX


// USED SERVICES
#include <algorithm>
#include <cosv/tpl/range.hxx>




namespace ary
{


/** Implementation of a set of children to an entity in the Autodoc
    repository. The children are sorted.

    @tpl COMPARE
    Needs to provide types:
        entity_base_type
        id_type
        key_type

    and functions:
        static entity_base_type &
                        EntityOf_(
                            id_type             i_id );
        static const key_type &
                        KeyOf_(
                            const entity_type & i_entity );
        static bool     Lesser_(
                            const key_type &    i_1,
                            const key_type &    i_2 );
*/
template<class COMPARE>
class SortedIds
{
  public:
    typedef typename COMPARE::id_type                   element_t;
    typedef typename COMPARE::key_type                  key_t;
    typedef std::vector<element_t>                      data_t;
    typedef typename data_t::const_iterator             const_iterator;
    typedef typename data_t::iterator                   iterator;
    typedef csv::range<const_iterator>                  search_result_t;

    // LIFECYCLE
    explicit            SortedIds(
                            std::size_t         i_reserve = 0 );
                        ~SortedIds();

    // OPERATIONS
    void                Add(
                            element_t           i_elem );
    // INQUIRY
    const_iterator      Begin() const;
    const_iterator      End() const;

    element_t           Search(
                            const key_t &       i_key ) const;
    search_result_t     SearchAll(
                            const key_t &       i_key ) const;
    const_iterator      LowerBound(
                            const key_t &       i_key ) const;

  private:
    typedef typename COMPARE::entity_base_type      entity_t;

    // Locals
    iterator            LowerBound(
                            const key_t &       i_key );

    static const key_t  &
                        KeyOf_(
                            element_t           i_child );
    template <class ITER>
    static ITER         impl_LowerBound_(
                            ITER                i_begin,
                            ITER                i_end,
                            const key_t &       i_key );

    // DATA
    data_t              aData;
};




// IMPLEMENTATION
template<class COMPARE>
inline const typename SortedIds<COMPARE>::key_t &
SortedIds<COMPARE>::KeyOf_(element_t i_child)
{
    return COMPARE::KeyOf_(COMPARE::EntityOf_(i_child));
}

template<class COMPARE>
SortedIds<COMPARE>::SortedIds(std::size_t i_reserve)
    :   aData()
{
    if (i_reserve > 0)
        aData.reserve(i_reserve);
}

template<class COMPARE>
SortedIds<COMPARE>::~SortedIds()
{
}

template<class COMPARE>
void
SortedIds<COMPARE>::Add(element_t i_elem)
{
    aData.insert(   LowerBound( KeyOf_(i_elem) ),
                    i_elem );
}

template<class COMPARE>
inline typename SortedIds<COMPARE>::const_iterator
SortedIds<COMPARE>::Begin() const
{
    return aData.begin();
}

template<class COMPARE>
inline typename SortedIds<COMPARE>::const_iterator
SortedIds<COMPARE>::End() const
{
    return aData.end();
}

template<class COMPARE>
typename SortedIds<COMPARE>::element_t
SortedIds<COMPARE>::Search(const key_t & i_key) const
{
    const_iterator
        ret = LowerBound(i_key);
    return ret != aData.end() AND NOT COMPARE::Lesser_(i_key, KeyOf_(*ret))
            ?   *ret
            :   element_t(0);
}

template<class COMPARE>
typename SortedIds<COMPARE>::search_result_t
SortedIds<COMPARE>::SearchAll(const key_t & i_key) const
{
    const_iterator
        r1 = LowerBound(i_key);
    const_iterator
        r2 = r1;
    while (     r2 != aData.end()
            AND NOT COMPARE::Lesser_(i_key, KeyOf_(*r2)) )
    {
        ++r2;
    }

    return csv::make_range(r1,r2);
}

template<class COMPARE>
inline typename SortedIds<COMPARE>::const_iterator
SortedIds<COMPARE>::LowerBound(const key_t & i_key) const
{
    return impl_LowerBound_( aData.begin(),
                             aData.end(),
                             i_key );
}

template<class COMPARE>
inline typename SortedIds<COMPARE>::iterator
SortedIds<COMPARE>::LowerBound(const key_t & i_key)
{
    return impl_LowerBound_( aData.begin(),
                             aData.end(),
                             i_key );
}

template<class COMPARE>
template <class ITER>
ITER
SortedIds<COMPARE>::impl_LowerBound_( ITER            i_begin,
                                      ITER            i_end,
                                      const key_t &   i_key )
{
    ITER i1 = i_begin;
    ITER i2 = i_end;

    for ( ITER it = i1 + (i2-i1)/2;
          i1 != i2;
          it = i1 + (i2-i1)/2 )
    {
        if ( COMPARE::Lesser_(KeyOf_(*it), i_key) )
        {
            i1 = it;
            ++i1;
        }
        else
        {
            i2 = it;
        }
    }   // end for

    return i1;
}




}   // namespace ary
#endif