KiCad PCB EDA Suite
lib_tree_model.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *lib_tree_model
4 * Copyright (C) 2017 Chris Pavlina <[email protected]>
5 * Copyright (C) 2014 Henner Zeller <[email protected]>
6 * Copyright (C) 2014-2019 KiCad Developers, see AUTHORS.txt for contributors.
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <lib_tree_model.h>
23
24#include <algorithm>
25#include <eda_pattern_match.h>
26#include <lib_tree_item.h>
27#include <utility>
28#include <pgm_base.h>
29#include <string_utils.h>
30
31// Each node gets this lowest score initially, without any matches applied.
32// Matches will then increase this score depending on match quality. This way,
33// an empty search string will result in all components being displayed as they
34// have the minimum score. However, in that case, we avoid expanding all the
35// nodes asd the result is very unspecific.
36static const unsigned kLowestDefaultScore = 1;
37
38
39// Creates a score depending on the position of a string match. If the position
40// is 0 (= prefix match), this returns the maximum score. This degrades until
41// pos == max, which returns a score of 0; Evertyhing else beyond that is just
42// 0. Only values >= 0 allowed for position and max.
43//
44// @param aPosition is the position a string has been found in a substring.
45// @param aMaximum is the maximum score this function returns.
46// @return position dependent score.
47static int matchPosScore(int aPosition, int aMaximum)
48{
49 return ( aPosition < aMaximum ) ? aMaximum - aPosition : 0;
50}
51
52
54{
55 for( std::unique_ptr<LIB_TREE_NODE>& child: m_Children )
56 child->ResetScore();
57
59}
60
61
63{
64 std::vector<LIB_TREE_NODE*> sort_buf;
65
66 if( presorted )
67 {
68 int max = m_Children.size() - 1;
69
70 for( int i = 0; i <= max; ++i )
71 m_Children[i]->m_IntrinsicRank = max - i;
72 }
73 else
74 {
75 for( std::unique_ptr<LIB_TREE_NODE>& child: m_Children )
76 sort_buf.push_back( child.get() );
77
78 std::sort( sort_buf.begin(), sort_buf.end(),
79 []( LIB_TREE_NODE* a, LIB_TREE_NODE* b ) -> bool
80 {
81 return StrNumCmp( a->m_Name, b->m_Name, true ) > 0;
82 } );
83
84 for( int i = 0; i < (int) sort_buf.size(); ++i )
85 sort_buf[i]->m_IntrinsicRank = i;
86 }
87}
88
89
91{
92 std::sort( m_Children.begin(), m_Children.end(),
93 []( std::unique_ptr<LIB_TREE_NODE>& a, std::unique_ptr<LIB_TREE_NODE>& b )
94 {
95 return Compare( *a, *b ) > 0;
96 } );
97
98 for( std::unique_ptr<LIB_TREE_NODE>& node: m_Children )
99 node->SortNodes();
100}
101
102
103int LIB_TREE_NODE::Compare( LIB_TREE_NODE const& aNode1, LIB_TREE_NODE const& aNode2 )
104{
105 if( aNode1.m_Type != aNode2.m_Type )
106 return 0;
107
108 // Recently used sorts at top
109 if( aNode1.m_Name.StartsWith( wxT( "-- " ) ) )
110 return 1;
111 else if( aNode2.m_Name.StartsWith( wxT( "-- " ) ) )
112 return 0;
113
114 // Pinned nodes go next
115 if( aNode1.m_Pinned && !aNode2.m_Pinned )
116 return 1;
117 else if( aNode2.m_Pinned && !aNode1.m_Pinned )
118 return -1;
119
120 if( aNode1.m_Parent != aNode2.m_Parent )
121 return 0;
122
123 return aNode1.m_IntrinsicRank - aNode2.m_IntrinsicRank;
124}
125
126
128 : m_Parent( nullptr ),
129 m_Type( INVALID ),
130 m_IntrinsicRank( 0 ),
131 m_Score( kLowestDefaultScore ),
132 m_Pinned( false ),
133 m_Normalized( false ),
134 m_Unit( 0 ),
135 m_IsRoot( false )
136{}
137
138
140{
141 static void* locale = nullptr;
142 static wxString namePrefix;
143
144 // Fetching translations can take a surprising amount of time when loading libraries,
145 // so only do it when necessary.
146 if( Pgm().GetLocale() != locale )
147 {
148 namePrefix = _( "Unit" );
149 locale = Pgm().GetLocale();
150 }
151
152 m_Parent = aParent;
153 m_Type = UNIT;
154
155 m_Unit = aUnit;
156 m_LibId = aParent->m_LibId;
157
158 m_Name = namePrefix + " " + aItem->GetUnitReference( aUnit );
159
160 if( aItem->HasUnitDisplayName( aUnit ) )
161 {
162 m_Desc = aItem->GetUnitDisplayName( aUnit );
163 }
164 else
165 {
166 m_Desc = wxEmptyString;
167 }
168
169 m_MatchName = wxEmptyString;
170
171 m_IntrinsicRank = -aUnit;
172}
173
174
176{
177 m_Type = LIBID;
178 m_Parent = aParent;
179
181 m_LibId.SetLibItemName( aItem->GetName() );
182
183 m_Name = aItem->GetName();
184 m_Desc = aItem->GetDescription();
185 m_Footprint = aItem->GetFootprint();
186
187 aItem->GetChooserFields( m_Fields );
188
189 m_MatchName = aItem->GetName();
190 m_SearchText = aItem->GetSearchText();
191 m_Normalized = false;
192
193 m_IsRoot = aItem->IsRoot();
194
195 if( aItem->GetUnitCount() > 1 )
196 {
197 for( int u = 1; u <= aItem->GetUnitCount(); ++u )
198 AddUnit( aItem, u );
199 }
200}
201
202
204{
205 LIB_TREE_NODE_UNIT* unit = new LIB_TREE_NODE_UNIT( this, aItem, aUnit );
206 m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( unit ) );
207 return *unit;
208}
209
210
212{
214 m_LibId.SetLibItemName( aItem->GetName() );
215
216 m_Name = aItem->GetName();
217 m_Desc = aItem->GetDescription();
218 m_MatchName = aItem->GetName();
219
220 aItem->GetChooserFields( m_Fields );
221
222 m_SearchText = aItem->GetSearchText();
223 m_Normalized = false;
224
225 m_IsRoot = aItem->IsRoot();
226 m_Children.clear();
227
228 for( int u = 1; u <= aItem->GetUnitCount(); ++u )
229 AddUnit( aItem, u );
230}
231
232
233void LIB_TREE_NODE_LIB_ID::UpdateScore( EDA_COMBINED_MATCHER& aMatcher, const wxString& aLib )
234{
235 if( m_Score <= 0 )
236 return; // Leaf nodes without scores are out of the game.
237
238 if( !m_Normalized )
239 {
241 m_SearchText = m_SearchText.Lower();
242 m_Normalized = true;
243 }
244
245 if( !aLib.IsEmpty() && m_Parent->m_MatchName != aLib )
246 {
247 m_Score = 0;
248 return;
249 }
250
251 // Keywords and description we only count if the match string is at
252 // least two characters long. That avoids spurious, low quality
253 // matches. Most abbreviations are at three characters long.
254 int found_pos = EDA_PATTERN_NOT_FOUND;
255 int matchers_fired = 0;
256
257 if( aMatcher.GetPattern() == m_MatchName )
258 {
259 m_Score += 1000; // exact match. High score :)
260 }
261 else if( aMatcher.Find( m_MatchName, matchers_fired, found_pos ) )
262 {
263 // Substring match. The earlier in the string the better.
264 m_Score += matchPosScore( found_pos, 20 ) + 20;
265 }
266 else if( aMatcher.Find( m_Parent->m_MatchName, matchers_fired, found_pos ) )
267 {
268 m_Score += 19; // parent name matches. score += 19
269 }
270 else if( aMatcher.Find( m_SearchText, matchers_fired, found_pos ) )
271 {
272 // If we have a very short search term (like one or two letters),
273 // we don't want to accumulate scores if they just happen to be in
274 // keywords or description as almost any one or two-letter
275 // combination shows up in there.
276 if( aMatcher.GetPattern().length() >= 2 )
277 {
278 // For longer terms, we add scores 1..18 for positional match
279 // (higher in the front, where the keywords are).
280 m_Score += matchPosScore( found_pos, 17 ) + 1;
281 }
282 }
283 else
284 {
285 // No match. That's it for this item.
286 m_Score = 0;
287 }
288
289 // More matchers = better match
290 m_Score += 2 * matchers_fired;
291}
292
293
295 wxString const& aDesc )
296{
297 m_Type = LIB;
298 m_Name = aName;
299 m_MatchName = aName.Lower();
300 m_Desc = aDesc;
301 m_Parent = aParent;
302 m_LibId.SetLibNickname( aName );
303}
304
305
307{
308 LIB_TREE_NODE_LIB_ID* item = new LIB_TREE_NODE_LIB_ID( this, aItem );
309 m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( item ) );
310 return *item;
311}
312
313
314void LIB_TREE_NODE_LIB::UpdateScore( EDA_COMBINED_MATCHER& aMatcher, const wxString& aLib )
315{
316 m_Score = 0;
317
318 // We need to score leaf nodes, which are usually (but not always) children.
319
320 if( m_Children.size() )
321 {
322 for( std::unique_ptr<LIB_TREE_NODE>& child: m_Children )
323 {
324 child->UpdateScore( aMatcher, aLib );
325 m_Score = std::max( m_Score, child->m_Score );
326 }
327 }
328 else
329 {
330 // No children; we are a leaf.
331
332 if( !aLib.IsEmpty() )
333 {
334 m_Score = m_MatchName == aLib ? 1000 : 0;
335 return;
336 }
337
338 int found_pos = EDA_PATTERN_NOT_FOUND;
339 int matchers_fired = 0;
340
341 if( aMatcher.GetPattern() == m_MatchName )
342 {
343 m_Score += 1000; // exact match. High score :)
344 }
345 else if( aMatcher.Find( m_MatchName, matchers_fired, found_pos ) )
346 {
347 // Substring match. The earlier in the string the better.
348 m_Score += matchPosScore( found_pos, 20 ) + 20;
349 }
350
351 // More matchers = better match
352 m_Score += 2 * matchers_fired;
353 }
354}
355
356
358{
359 m_Type = ROOT;
360}
361
362
363LIB_TREE_NODE_LIB& LIB_TREE_NODE_ROOT::AddLib( wxString const& aName, wxString const& aDesc )
364{
365 LIB_TREE_NODE_LIB* lib = new LIB_TREE_NODE_LIB( this, aName, aDesc );
366 m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( lib ) );
367 return *lib;
368}
369
370
371void LIB_TREE_NODE_ROOT::UpdateScore( EDA_COMBINED_MATCHER& aMatcher, const wxString& aLib )
372{
373 for( std::unique_ptr<LIB_TREE_NODE>& child: m_Children )
374 child->UpdateScore( aMatcher, aLib );
375}
376
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
const wxString & GetPattern() const
int SetLibItemName(const UTF8 &aLibItemName)
Override the library item name portion of the LIB_ID to aLibItemName.
Definition: lib_id.cpp:109
int SetLibNickname(const UTF8 &aNickname)
Override the logical library name portion of the LIB_ID to aNickname.
Definition: lib_id.cpp:98
const UTF8 & GetLibNickname() const
Return the logical library name portion of a LIB_ID.
Definition: lib_id.h:87
A mix-in to provide polymorphism between items stored in libraries (symbols, aliases and footprints).
Definition: lib_tree_item.h:40
virtual wxString GetUnitReference(int aUnit)
For items with units, return an identifier for unit x.
Definition: lib_tree_item.h:78
virtual wxString GetLibNickname() const =0
virtual bool HasUnitDisplayName(int aUnit)
For items with units, return true if a display name is set for x.
Definition: lib_tree_item.h:88
virtual wxString GetFootprint()
For items with footprint fields.
Definition: lib_tree_item.h:68
virtual bool IsRoot() const
For items having aliases, IsRoot() indicates the principal item.
Definition: lib_tree_item.h:63
virtual wxString GetName() const =0
virtual wxString GetDescription()=0
virtual LIB_ID GetLibId() const =0
virtual wxString GetSearchText()
Definition: lib_tree_item.h:58
virtual int GetUnitCount() const
For items with units, return the number of units.
Definition: lib_tree_item.h:73
virtual wxString GetUnitDisplayName(int aUnit)
For items with units, return a display name for unit x.
Definition: lib_tree_item.h:83
virtual void GetChooserFields(std::map< wxString, wxString > &aColumnMap)
Retrieves a key/value map of the fields on this item that should be exposed to the library browser/ch...
Definition: lib_tree_item.h:56
Node type: LIB_ID.
LIB_TREE_NODE_UNIT & AddUnit(LIB_TREE_ITEM *aItem, int aUnit)
Add a new unit to the component and return it.
void Update(LIB_TREE_ITEM *aItem)
Update the node using data from a LIB_ALIAS object.
LIB_TREE_NODE_LIB_ID(LIB_TREE_NODE_LIB_ID const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don't let them be ...
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher, const wxString &aLib) override
Perform the actual search.
Node type: library.
LIB_TREE_NODE_LIB_ID & AddItem(LIB_TREE_ITEM *aItem)
Construct a new alias node, add it to this library, and return it.
LIB_TREE_NODE_LIB(LIB_TREE_NODE_LIB const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don't let them be ...
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher, const wxString &aLib) override
Update the score for this part.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher, const wxString &aLib) override
Update the score for this part.
LIB_TREE_NODE_ROOT()
Construct the root node.
LIB_TREE_NODE_LIB & AddLib(wxString const &aName, wxString const &aDesc)
Construct an empty library node, add it to the root, and return it.
Node type: unit of component.
LIB_TREE_NODE_UNIT(LIB_TREE_NODE_UNIT const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don't let them be ...
Model class in the component selector Model-View-Adapter (mediated MVC) architecture.
void SortNodes()
Sort child nodes quickly and recursively (IntrinsicRanks must have been set).
enum TYPE m_Type
std::map< wxString, wxString > m_Fields
PTR_VECTOR m_Children
wxString m_SearchText
wxString m_Footprint
LIB_TREE_NODE * m_Parent
void ResetScore()
Initialize score to kLowestDefaultScore, recursively.
int m_IntrinsicRank
The rank of the item before any search terms are applied.
static int Compare(LIB_TREE_NODE const &aNode1, LIB_TREE_NODE const &aNode2)
Compare two nodes.
void AssignIntrinsicRanks(bool presorted=false)
Store intrinsic ranks on all children of this node.
wxString m_MatchName
#define _(s)
Abstract pattern-matching tool and implementations.
static const int EDA_PATTERN_NOT_FOUND
@ INVALID
Definition: kiface_ids.h:32
static const unsigned kLowestDefaultScore
static int matchPosScore(int aPosition, int aMaximum)
see class PGM_BASE
KIWAY Kiway & Pgm(), KFCTL_STANDALONE
The global Program "get" accessor.
Definition: single_top.cpp:111
wxString UnescapeString(const wxString &aSource)