KiCad PCB EDA Suite
Loading...
Searching...
No Matches
kicad_algo.h
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2019 CERN
5 * Copyright (C) 2019-2023 KiCad Developers, see AUTHORS.TXT for contributors.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 3
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-3.0.html
20 * or you may search the http://www.gnu.org website for the version 3 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
25#ifndef INCLUDE_CORE_KICAD_ALGO_H_
26#define INCLUDE_CORE_KICAD_ALGO_H_
27
28#include <algorithm>
29#include <functional> // std::function
30#include <utility> // std::pair
31#include <vector>
32#include <wx/debug.h> // wxCHECK_MSG
33
34namespace alg
35{
44template <typename _Type, typename _Function>
45void run_on_pair( std::pair<_Type, _Type>& __pair, _Function __f )
46{
47 __f( __pair.first );
48 __f( __pair.second );
49}
50
61template <typename _InputIterator, typename _Function>
62void adjacent_pairs( _InputIterator __first, _InputIterator __last, _Function __f )
63{
64 if( __first != __last )
65 {
66 _InputIterator __follow = __first;
67 ++__first;
68 for( ; __first != __last; ++__first, ++__follow )
69 __f( *__follow, *__first );
70 }
71}
72
83template <typename _InputIterator, typename _Function>
84void for_all_pairs( _InputIterator __first, _InputIterator __last, _Function __f )
85{
86 if( __first != __last )
87 {
88 _InputIterator __follow = __first;
89 ++__first;
90 for( ; __first != __last; ++__first, ++__follow )
91 for( _InputIterator __it = __first; __it != __last; ++__it )
92 __f( *__follow, *__it );
93 }
94}
95
99template <class _Container, typename _Value>
100bool contains( const _Container& __container, _Value __value )
101{
102 return std::find( __container.begin(), __container.end(), __value ) != __container.end();
103}
104
112template <typename _Type, typename _Value>
113bool pair_contains( const std::pair<_Type, _Type> __pair, _Value __value )
114{
115 return __pair.first == static_cast<_Type>( __value )
116 || __pair.second == static_cast<_Type>( __value );
117}
118
128template <class T>
129bool within_wrapped_range( T __val, T __minval, T __maxval, T __wrap )
130{
131 wxCHECK_MSG( __wrap > 0, false, wxT( "Wrap must be positive!" ) );
132
133 while( __maxval >= __wrap )
134 __maxval -= __wrap;
135
136 while( __maxval < 0 )
137 __maxval += __wrap;
138
139 while( __minval >= __wrap )
140 __minval -= __wrap;
141
142 while( __minval < 0 )
143 __minval += __wrap;
144
145 while( __val < 0 )
146 __val += __wrap;
147
148 while( __val >= __wrap )
149 __val -= __wrap;
150
151 if( __maxval > __minval )
152 return __val >= __minval && __val <= __maxval;
153 else
154 return __val >= __minval || __val <= __maxval;
155}
156
164template <class _Container, typename _Value>
165void delete_matching( _Container& __c, _Value __value )
166{
167 __c.erase( std::remove( __c.begin(), __c.end(), __value ), __c.end() );
168}
169
173template <class _Container, class _Function>
174void delete_if( _Container& __c, _Function&& __f )
175{
176 __c.erase( std::remove_if( __c.begin(), __c.end(), std::forward<_Function>( __f ) ), __c.end() );
177}
178
182template <class _Container>
183void remove_duplicates( _Container& __c )
184{
185 __c.erase( std::unique( __c.begin(), __c.end() ), __c.end() );
186}
187
188template <class _Container, class _Function>
189void remove_duplicates( _Container& __c, _Function&& __f )
190{
191 __c.erase( std::unique( __c.begin(), __c.end(), std::forward<_Function>( __f ) ), __c.end() );
192}
193
197template <typename T, std::enable_if_t<std::is_integral<T>::value, int> = 0>
198bool signbit( T v )
199{
200 return v < 0;
201}
202
203
204template <typename T>
205T clamp( T min, T value, T max )
206{
207 return std::max( min, std::min( value, max ) );
208}
209
213template <class _Container>
214size_t longest_common_subset( const _Container& __c1, const _Container& __c2 )
215{
216 size_t __c1_size = __c1.size();
217 size_t __c2_size = __c2.size();
218
219 if( __c1_size == 0 || __c2_size == 0 )
220 return 0;
221
222 // Create a 2D table to store the lengths of common subsets
223 std::vector<std::vector<size_t>> table( __c1_size + 1, std::vector<size_t>( __c2_size + 1, 0 ) );
224
225 size_t longest = 0;
226
227 for( size_t i = 1; i <= __c1_size; ++i )
228 {
229 for( size_t j = 1; j <= __c2_size; ++j )
230 {
231 if( __c1[i - 1] == __c2[j - 1] )
232 {
233 table[i][j] = table[i - 1][j - 1] + 1;
234 longest = std::max( longest, static_cast<size_t>( table[i][j] ) );
235 }
236 }
237 }
238
239 return longest;
240}
241
242} // namespace alg
243
244#endif /* INCLUDE_CORE_KICAD_ALGO_H_ */
Definition: kicad_algo.h:35
void delete_if(_Container &__c, _Function &&__f)
Deletes all values from __c for which __f returns true.
Definition: kicad_algo.h:174
void remove_duplicates(_Container &__c)
Deletes all duplicate values from __c.
Definition: kicad_algo.h:183
T clamp(T min, T value, T max)
Definition: kicad_algo.h:205
void delete_matching(_Container &__c, _Value __value)
Covers for the horrifically named std::remove and std::remove_if (neither of which remove anything).
Definition: kicad_algo.h:165
bool signbit(T v)
Integral version of std::signbit that works all compilers.
Definition: kicad_algo.h:198
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:100
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
Definition: kicad_algo.h:113
bool within_wrapped_range(T __val, T __minval, T __maxval, T __wrap)
Test if __val lies within __minval and __maxval in a wrapped range.
Definition: kicad_algo.h:129
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
Definition: kicad_algo.h:45
void adjacent_pairs(_InputIterator __first, _InputIterator __last, _Function __f)
Apply a function to every sequential pair of elements of a sequence.
Definition: kicad_algo.h:62
void for_all_pairs(_InputIterator __first, _InputIterator __last, _Function __f)
Apply a function to every possible pair of elements of a sequence.
Definition: kicad_algo.h:84
size_t longest_common_subset(const _Container &__c1, const _Container &__c2)
Returns the length of the longest common subset of values between two containers.
Definition: kicad_algo.h:214