summaryrefslogtreecommitdiff
path: root/autodoc/source/ary/inc/sortedids.hxx
diff options
context:
space:
mode:
Diffstat (limited to 'autodoc/source/ary/inc/sortedids.hxx')
-rw-r--r--autodoc/source/ary/inc/sortedids.hxx237
1 files changed, 237 insertions, 0 deletions
diff --git a/autodoc/source/ary/inc/sortedids.hxx b/autodoc/source/ary/inc/sortedids.hxx
new file mode 100644
index 000000000000..9bebaa9b19a5
--- /dev/null
+++ b/autodoc/source/ary/inc/sortedids.hxx
@@ -0,0 +1,237 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2000, 2010 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org. If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 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