Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
darray_sorted.hpp
Go to the documentation of this file.
1/*
2 * Author: Sven Gothel <sgothel@jausoft.com>
3 * Copyright (c) 1994-2022 Gothel Software e.K.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25#ifndef JAU_DYN_ARRAY_SORTED_HPP_
26#define JAU_DYN_ARRAY_SORTED_HPP_
27
28#include <jau/darray.hpp>
29
30namespace jau {
31
32 /** \addtogroup DataStructs
33 *
34 * @{
35 */
36
37 /**
38 * Extension to darray resulting in a sorted darray via insert().
39 *
40 * In der hier deklarierten Template-Klasse 'darray_sorted' werden die
41 * einzelnen Listen Elemente sofort beim Einfuegen der Groesse nach
42 * sortiert ( In aufsteigender(UP)/absteigender(DOWN) Reihenfolge ).
43 * D.h. die Methode 'fuegeEin' fuegt die Listenelemente mittels
44 * Bisektionierung gleich sortiert ein.
45 *
46 * fuegeEin liefert nun den Index zurueck, den das eingefuegte Element
47 * besitzt, ansonsten npos.
48 * die Listenelemente gleich sortiert eingefuegt werden, mittel Bisektionierung.
49 *
50 * Neu ist die Methode findeElement, welche ebenfalls nach der MEthode der
51 * Bisektionierung arbeitet.
52 *
53 * @tparam Value_type
54 * @tparam Alloc_type
55 * @tparam Size_type
56 * @tparam use_memmove
57 * @tparam use_secmem
58 */
59 template <typename Value_type, typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>,
60 bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>,
61 bool use_secmem = is_enforcing_secmem_v<Value_type>
62 >
63 class darray_sorted : protected darray<Value_type, Size_type, Alloc_type, use_memmove, use_secmem> {
64 public:
66 using typename darray_type::value_type;
67 using typename darray_type::size_type;
68
70 using darray_type::operator[];
72
73 /**
74 * Special value representing maximal value of size_type, used to denote an invalid index position return value, i.e. `no position`.
75 */
77
78 enum order_t { UP, DOWN };
79
80 darray_sorted(order_t order=UP) : darray_type(), m_order(order) { }
81 darray_sorted(const darray_sorted& m) : darray_type(m), m_order(m.m_order) {}
82
84 {
85 m_order=m.m_order;
87 return *this;
88 }
89
91 size_type u=0, o=size()>0 ? size()-1 : 0;
92 size_type i=index_of(a, u, o);
93 if ( npos == i ) {
95 return o;
96 } else {
98 return i;
99 }
100 }
101
102 bool contains(const value_type& x) const noexcept {
103 return npos != index_of(x);
104 }
105
106 /**
107 * Returns index of given element if found or npos
108 * @param x
109 * @return
110 */
111 size_type index_of(const value_type& x) const {
112 size_type u=0, o=size()>0 ? size()-1 : 0;
113 return index_of(x, u, o);
114 }
115
116 private:
117 /**
118 * @param x the desired value_type
119 * @param l lower border (bottom), inclusive
120 * @param h higher border (top), inclusive
121 * @return >= 0 gefunden index, npos nicht gefunden
122 */
123 size_type index_of(const value_type &x, size_type &l, size_type &h) const {
124 size_type i=0;
125
126 if ( size() == 0 ) { return npos; }
127
128 if(m_order==UP) {
129 if( l == h && (*this)[h] < x ) { h++; }
130 else if( (*this)[l] > x ) { h=l; }
131 else if( (*this)[h] < x ) { l=h; h++; }
132 else if( (*this)[l] == x ) { return l; }
133 else if( (*this)[h] == x ) { return h; }
134 } else {
135 if( l == h && (*this)[h] > x ) { h++; }
136 else if( (*this)[l] < x ) { h=l; }
137 else if( (*this)[h] > x ) { l=h; h++; }
138 else if( (*this)[l] == x ) { return l; }
139 else if( (*this)[h] == x ) { return h; }
140 }
141
142 while( h-l > 1 ) {
143 i=(l+h)/2;
144 if ( (*this)[i] < x ) {
145 if ( m_order==UP ) l=i;
146 else h=i;
147 } else if ( (*this)[i] > x ) {
148 if ( m_order==UP ) h=i;
149 else l=i;
150 } else {
151 return i;
152 }
153 }
154 return npos;
155 }
156 order_t m_order;
157 };
158
159 /**@}*/
160
161} /* namespace jau */
162
163#endif /* JAU_DYN_ARRAY_SORTED_HPP_ */
164
165
Extension to darray resulting in a sorted darray via insert().
Size_type size_type
Definition: darray.hpp:166
constexpr size_type size() const noexcept
Like std::vector::size().
Definition: darray.hpp:763
darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem > darray_type
Value_type value_type
Definition: darray.hpp:159
darray_sorted(order_t order=UP)
static constexpr const size_type npos
Special value representing maximal value of size_type, used to denote an invalid index position retur...
size_type insert(const value_type &a)
bool contains(const value_type &x) const noexcept
darray_sorted & operator=(const darray_sorted &m)
darray_sorted(const darray_sorted &m)
size_type index_of(const value_type &x) const
Returns index of given element if found or npos.
Implementation of a dynamic linear array storage, aka vector.
Definition: darray.hpp:148
constexpr darray & operator=(const darray &x)
Like std::vector::operator=(&), assignment.
Definition: darray.hpp:541
Size_type size_type
Definition: darray.hpp:166
constexpr size_type size() const noexcept
Like std::vector::size().
Definition: darray.hpp:763
Value_type value_type
Definition: darray.hpp:159
constexpr iterator insert(const_iterator pos, const value_type &x)
Like std::vector::insert(), copy.
Definition: darray.hpp:996
constexpr iterator erase(const_iterator pos)
Like std::vector::erase(), removes the elements at pos.
Definition: darray.hpp:940
constexpr T max(const T x, const T y) noexcept
Returns the maximum of two integrals (w/ branching) in O(1)
Definition: base_math.hpp:191
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
Definition: backtrace.hpp:32