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  *
4  * Copyright (C) 2017 Chris Pavlina <pavlina.chris@gmail.com>
5  * Copyright (C) 2014 Henner Zeller <h.zeller@acm.org>
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 <kicad_string.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.
36 static 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.
47 static int matchPosScore(int aPosition, int aMaximum)
48 {
49  return ( aPosition < aMaximum ) ? aMaximum - aPosition : 0;
50 }
51 
52 
54 {
55  for( auto& 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( auto const& node: m_Children )
76  sort_buf.push_back( &*node );
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 
103 int 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  if( aNode1.m_Score != aNode2.m_Score )
109  return aNode1.m_Score - aNode2.m_Score;
110 
111  if( aNode1.m_Parent != aNode2.m_Parent )
112  return 0;
113 
114  return aNode1.m_IntrinsicRank - aNode2.m_IntrinsicRank;
115 }
116 
117 
119  : m_Parent( nullptr ),
120  m_Type( INVALID ),
121  m_IntrinsicRank( 0 ),
122  m_Score( kLowestDefaultScore ),
123  m_Pinned( false ),
124  m_Normalized( false ),
125  m_Unit( 0 ),
126  m_IsRoot( false )
127 {}
128 
129 
131 {
132  static void* locale = nullptr;
133  static wxString namePrefix;
134 
135  // Fetching translations can take a surprising amount of time when loading libraries,
136  // so only do it when necessary.
137  if( Pgm().GetLocale() != locale )
138  {
139  namePrefix = _( "Unit" );
140  locale = Pgm().GetLocale();
141  }
142 
143  m_Parent = aParent;
144  m_Type = UNIT;
145 
146  m_Unit = aUnit;
147  m_LibId = aParent->m_LibId;
148 
149  m_Name = namePrefix + " " + aItem->GetUnitReference( aUnit );
150  m_Desc = wxEmptyString;
151  m_MatchName = wxEmptyString;
152 
153  m_IntrinsicRank = -aUnit;
154 }
155 
156 
158 {
159  m_Type = LIBID;
160  m_Parent = aParent;
161 
163  m_LibId.SetLibItemName( aItem->GetName () );
164 
165  m_Name = aItem->GetName();
166  m_Desc = aItem->GetDescription();
167 
168  m_MatchName = aItem->GetName();
169  m_SearchText = aItem->GetSearchText();
170  m_Normalized = false;
171 
172  m_IsRoot = aItem->IsRoot();
173 
174  if( aItem->GetUnitCount() > 1 )
175  {
176  for( int u = 1; u <= aItem->GetUnitCount(); ++u )
177  AddUnit( aItem, u );
178  }
179 }
180 
181 
183 {
184  LIB_TREE_NODE_UNIT* unit = new LIB_TREE_NODE_UNIT( this, aItem, aUnit );
185  m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( unit ) );
186  return *unit;
187 }
188 
189 
191 {
192  // Update is called when the names match, so just update the other fields.
193 
195 
196  m_Desc = aItem->GetDescription();
197 
198  m_SearchText = aItem->GetSearchText();
199  m_Normalized = false;
200 
201  m_IsRoot = aItem->IsRoot();
202  m_Children.clear();
203 
204  for( int u = 1; u <= aItem->GetUnitCount(); ++u )
205  AddUnit( aItem, u );
206 }
207 
208 
210 {
211  if( m_Score <= 0 )
212  return; // Leaf nodes without scores are out of the game.
213 
214  if( !m_Normalized )
215  {
216  m_MatchName = m_MatchName.Lower();
217  m_SearchText = m_SearchText.Lower();
218  m_Normalized = true;
219  }
220 
221  // Keywords and description we only count if the match string is at
222  // least two characters long. That avoids spurious, low quality
223  // matches. Most abbreviations are at three characters long.
224  int found_pos = EDA_PATTERN_NOT_FOUND;
225  int matchers_fired = 0;
226 
227  if( aMatcher.GetPattern() == m_MatchName )
228  {
229  m_Score += 1000; // exact match. High score :)
230  }
231  else if( aMatcher.Find( m_MatchName, matchers_fired, found_pos ) )
232  {
233  // Substring match. The earlier in the string the better.
234  m_Score += matchPosScore( found_pos, 20 ) + 20;
235  }
236  else if( aMatcher.Find( m_Parent->m_MatchName, matchers_fired, found_pos ) )
237  {
238  m_Score += 19; // parent name matches. score += 19
239  }
240  else if( aMatcher.Find( m_SearchText, matchers_fired, found_pos ) )
241  {
242  // If we have a very short search term (like one or two letters),
243  // we don't want to accumulate scores if they just happen to be in
244  // keywords or description as almost any one or two-letter
245  // combination shows up in there.
246  if( aMatcher.GetPattern().length() >= 2 )
247  {
248  // For longer terms, we add scores 1..18 for positional match
249  // (higher in the front, where the keywords are).
250  m_Score += matchPosScore( found_pos, 17 ) + 1;
251  }
252  }
253  else
254  {
255  // No match. That's it for this item.
256  m_Score = 0;
257  }
258 
259  // More matchers = better match
260  m_Score += 2 * matchers_fired;
261 }
262 
263 
264 LIB_TREE_NODE_LIB::LIB_TREE_NODE_LIB( LIB_TREE_NODE* aParent, wxString const& aName,
265  wxString const& aDesc )
266 {
267  m_Type = LIB;
268  m_Name = aName;
269  m_MatchName = aName.Lower();
270  m_Desc = aDesc;
271  m_Parent = aParent;
272  m_LibId.SetLibNickname( aName );
273 }
274 
275 
277 {
278  LIB_TREE_NODE_LIB_ID* item = new LIB_TREE_NODE_LIB_ID( this, aItem );
279  m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( item ) );
280  return *item;
281 }
282 
283 
285 {
286  m_Score = 0;
287 
288  // We need to score leaf nodes, which are usually (but not always) children.
289 
290  if( m_Children.size() )
291  {
292  for( auto& child: m_Children )
293  {
294  child->UpdateScore( aMatcher );
295  m_Score = std::max( m_Score, child->m_Score );
296  }
297  }
298  else
299  {
300  // No children; we are a leaf.
301  int found_pos = EDA_PATTERN_NOT_FOUND;
302  int matchers_fired = 0;
303 
304  if( aMatcher.GetPattern() == m_MatchName )
305  {
306  m_Score += 1000; // exact match. High score :)
307  }
308  else if( aMatcher.Find( m_MatchName, matchers_fired, found_pos ) )
309  {
310  // Substring match. The earlier in the string the better.
311  m_Score += matchPosScore( found_pos, 20 ) + 20;
312  }
313 
314  // More matchers = better match
315  m_Score += 2 * matchers_fired;
316  }
317 }
318 
319 
321 {
322  m_Type = ROOT;
323 }
324 
325 
326 LIB_TREE_NODE_LIB& LIB_TREE_NODE_ROOT::AddLib( wxString const& aName, wxString const& aDesc )
327 {
328  LIB_TREE_NODE_LIB* lib = new LIB_TREE_NODE_LIB( this, aName, aDesc );
329  m_Children.push_back( std::unique_ptr<LIB_TREE_NODE>( lib ) );
330  return *lib;
331 }
332 
333 
335 {
336  for( auto& child: m_Children )
337  child->UpdateScore( aMatcher );
338 }
339 
void SortNodes()
Sort child nodes quickly and recursively (IntrinsicRanks must have been set).
KIWAY Kiway & Pgm(), KFCTL_STANDALONE
The global Program "get" accessor.
Definition: single_top.cpp:104
int StrNumCmp(const wxString &aString1, const wxString &aString2, bool aIgnoreCase)
Compare two strings with alphanumerical content.
Definition: string.cpp:388
virtual int GetUnitCount() const
For items with units, return the number of units.
Definition: lib_tree_item.h:63
static int matchPosScore(int aPosition, int aMaximum)
static int Compare(LIB_TREE_NODE const &aNode1, LIB_TREE_NODE const &aNode2)
Compare two nodes.
A mix-in to provide polymorphism between items stored in libraries (symbols, aliases and footprints).
Definition: lib_tree_item.h:39
Node type: LIB_ID.
wxString const & GetPattern() const
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Perform the actual search.
int m_IntrinsicRank
The rank of the item before any search terms are applied.
Abstract pattern-matching tool and implementations.
virtual bool IsRoot() const
For items having aliases, IsRoot() indicates the principal item.
Definition: lib_tree_item.h:58
virtual wxString GetSearchText()
Definition: lib_tree_item.h:53
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 * m_Parent
Node type: library.
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
virtual wxString GetDescription()=0
const UTF8 & GetLibNickname() const
Return the logical library name portion of a LIB_ID.
Definition: lib_id.h:97
LIB_TREE_NODE_UNIT & AddUnit(LIB_TREE_ITEM *aItem, int aUnit)
Add a new unit to the component and return it.
void ResetScore()
Initialize score to kLowestDefaultScore, recursively.
static const int EDA_PATTERN_NOT_FOUND
Model class in the component selector Model-View-Adapter (mediated MVC) architecture.
static const unsigned kLowestDefaultScore
Node type: unit of component.
int SetLibItemName(const UTF8 &aLibItemName, bool aTestForRev=true)
Override the library item name portion of the LIB_ID to aLibItemName.
Definition: lib_id.cpp:206
virtual wxString GetName() const =0
LIB_TREE_NODE_LIB & AddLib(wxString const &aName, wxString const &aDesc)
Construct an empty library node, add it to the root, and return it.
int SetLibNickname(const UTF8 &aNickname)
Override the logical library name portion of the LIB_ID to aNickname.
Definition: lib_id.cpp:193
void AssignIntrinsicRanks(bool presorted=false)
Store intrinsic ranks on all children of this node.
see class PGM_BASE
virtual LIB_ID GetLibId() const =0
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 wxString GetLibNickname() const =0
#define _(s)
Definition: 3d_actions.cpp:33
enum TYPE m_Type
LIB_TREE_NODE_ROOT()
Construct the root node.
wxString m_Name
void Update(LIB_TREE_ITEM *aItem)
Update the node using data from a LIB_ALIAS object.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Update the score for this part.
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) override
Update the score for this part.
PTR_VECTOR m_Children
wxString m_Desc
wxString m_SearchText
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 ...
virtual wxString GetUnitReference(int aUnit)
For items with units, return an identifier for unit x.
Definition: lib_tree_item.h:68
wxString m_MatchName