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 <eda_pattern_match.h>
25 #include <lib_tree_item.h>
26 #include <utility>
27 #include <pgm_base.h>
28 #include <kicad_string.h>
29 
30 // Each node gets this lowest score initially, without any matches applied.
31 // Matches will then increase this score depending on match quality. This way,
32 // an empty search string will result in all components being displayed as they
33 // have the minimum score. However, in that case, we avoid expanding all the
34 // nodes asd the result is very unspecific.
35 static const unsigned kLowestDefaultScore = 1;
36 
37 
38 // Creates a score depending on the position of a string match. If the position
39 // is 0 (= prefix match), this returns the maximum score. This degrades until
40 // pos == max, which returns a score of 0; Evertyhing else beyond that is just
41 // 0. Only values >= 0 allowed for position and max.
42 //
43 // @param aPosition is the position a string has been found in a substring.
44 // @param aMaximum is the maximum score this function returns.
45 // @return position dependent score.
46 static int matchPosScore(int aPosition, int aMaximum)
47 {
48  return ( aPosition < aMaximum ) ? aMaximum - aPosition : 0;
49 }
50 
51 
53 {
54  for( auto& child: Children )
55  child->ResetScore();
56 
58 }
59 
60 
62 {
63  std::vector<LIB_TREE_NODE*> sort_buf;
64 
65  if( presorted )
66  {
67  int max = Children.size() - 1;
68 
69  for( int i = 0; i <= max; ++i )
71  }
72  else
73  {
74  for( auto const& node: Children )
75  sort_buf.push_back( &*node );
76 
77  std::sort( sort_buf.begin(), sort_buf.end(),
78  []( LIB_TREE_NODE* a, LIB_TREE_NODE* b ) -> bool
79  { return StrNumCmp( a->Name, b->Name, true ) > 0; } );
80 
81  for( int i = 0; i < (int) sort_buf.size(); ++i )
82  sort_buf[i]->IntrinsicRank = i;
83  }
84 }
85 
86 
88 {
89  std::sort( Children.begin(), Children.end(),
90  []( std::unique_ptr<LIB_TREE_NODE>& a, std::unique_ptr<LIB_TREE_NODE>& b )
91  {
92  return Compare( *a, *b ) > 0;
93  } );
94 
95  for( std::unique_ptr<LIB_TREE_NODE>& node: Children )
96  node->SortNodes();
97 }
98 
99 
100 int LIB_TREE_NODE::Compare( LIB_TREE_NODE const& aNode1, LIB_TREE_NODE const& aNode2 )
101 {
102  if( aNode1.Type != aNode2.Type )
103  return 0;
104 
105  if( aNode1.Score != aNode2.Score )
106  return aNode1.Score - aNode2.Score;
107 
108  if( aNode1.Parent != aNode2.Parent )
109  return 0;
110 
111  return aNode1.IntrinsicRank - aNode2.IntrinsicRank;
112 }
113 
114 
116  : Parent( nullptr ),
117  Type( INVALID ),
118  IntrinsicRank( 0 ),
119  Score( kLowestDefaultScore ),
120  Normalized( false ),
121  Unit( 0 ),
122  IsRoot( false )
123 {}
124 
125 
127 {
128  static void* locale = nullptr;
129  static wxString namePrefix;
130 
131  // Fetching translations can take a surprising amount of time when loading libraries,
132  // so only do it when necessary.
133  if( Pgm().GetLocale() != locale )
134  {
135  namePrefix = _( "Unit" );
136  locale = Pgm().GetLocale();
137  }
138 
139  Parent = aParent;
140  Type = UNIT;
141 
142  Unit = aUnit;
143  LibId = aParent->LibId;
144 
145  Name = namePrefix + " " + aItem->GetUnitReference( aUnit );
146  Desc = wxEmptyString;
147  MatchName = wxEmptyString;
148 
149  IntrinsicRank = -aUnit;
150 }
151 
152 
154 {
155  Type = LIBID;
156  Parent = aParent;
157 
158  LibId.SetLibNickname( aItem->GetLibNickname() );
159  LibId.SetLibItemName( aItem->GetName () );
160 
161  Name = aItem->GetName();
162  Desc = aItem->GetDescription();
163 
164  MatchName = aItem->GetName();
165  SearchText = aItem->GetSearchText();
166  Normalized = false;
167 
168  IsRoot = aItem->IsRoot();
169 
170  if( aItem->GetUnitCount() > 1 )
171  {
172  for( int u = 1; u <= aItem->GetUnitCount(); ++u )
173  AddUnit( aItem, u );
174  }
175 }
176 
177 
179 {
180  LIB_TREE_NODE_UNIT* unit = new LIB_TREE_NODE_UNIT( this, aItem, aUnit );
181  Children.push_back( std::unique_ptr<LIB_TREE_NODE>( unit ) );
182  return *unit;
183 }
184 
185 
187 {
188  // Update is called when the names match, so just update the other fields.
189 
191 
192  Desc = aItem->GetDescription();
193 
194  SearchText = aItem->GetSearchText();
195  Normalized = false;
196 
197  IsRoot = aItem->IsRoot();
198  Children.clear();
199 
200  for( int u = 1; u <= aItem->GetUnitCount(); ++u )
201  AddUnit( aItem, u );
202 }
203 
204 
206 {
207  if( Score <= 0 )
208  return; // Leaf nodes without scores are out of the game.
209 
210  if( !Normalized )
211  {
212  MatchName = MatchName.Lower();
213  SearchText = SearchText.Lower();
214  Normalized = true;
215  }
216 
217  // Keywords and description we only count if the match string is at
218  // least two characters long. That avoids spurious, low quality
219  // matches. Most abbreviations are at three characters long.
220  int found_pos = EDA_PATTERN_NOT_FOUND;
221  int matchers_fired = 0;
222 
223  if( aMatcher.GetPattern() == MatchName )
224  {
225  Score += 1000; // exact match. High score :)
226  }
227  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
228  {
229  // Substring match. The earlier in the string the better.
230  Score += matchPosScore( found_pos, 20 ) + 20;
231  }
232  else if( aMatcher.Find( Parent->MatchName, matchers_fired, found_pos ) )
233  {
234  Score += 19; // parent name matches. score += 19
235  }
236  else if( aMatcher.Find( SearchText, matchers_fired, found_pos ) )
237  {
238  // If we have a very short search term (like one or two letters),
239  // we don't want to accumulate scores if they just happen to be in
240  // keywords or description as almost any one or two-letter
241  // combination shows up in there.
242  if( aMatcher.GetPattern().length() >= 2 )
243  {
244  // For longer terms, we add scores 1..18 for positional match
245  // (higher in the front, where the keywords are).
246  Score += matchPosScore( found_pos, 17 ) + 1;
247  }
248  }
249  else
250  {
251  // No match. That's it for this item.
252  Score = 0;
253  }
254 
255  // More matchers = better match
256  Score += 2 * matchers_fired;
257 }
258 
259 
260 LIB_TREE_NODE_LIB::LIB_TREE_NODE_LIB( LIB_TREE_NODE* aParent, wxString const& aName,
261  wxString const& aDesc )
262 {
263  Type = LIB;
264  Name = aName;
265  MatchName = aName.Lower();
266  Desc = aDesc;
267  Parent = aParent;
268  LibId.SetLibNickname( aName );
269 }
270 
271 
273 {
274  LIB_TREE_NODE_LIB_ID* item = new LIB_TREE_NODE_LIB_ID( this, aItem );
275  Children.push_back( std::unique_ptr<LIB_TREE_NODE>( item ) );
276  return *item;
277 }
278 
279 
281 {
282  Score = 0;
283 
284  // We need to score leaf nodes, which are usually (but not always) children.
285 
286  if( Children.size() )
287  {
288  for( auto& child: Children )
289  {
290  child->UpdateScore( aMatcher );
291  Score = std::max( Score, child->Score );
292  }
293  }
294  else
295  {
296  // No children; we are a leaf.
297  int found_pos = EDA_PATTERN_NOT_FOUND;
298  int matchers_fired = 0;
299 
300  if( aMatcher.GetPattern() == MatchName )
301  {
302  Score += 1000; // exact match. High score :)
303  }
304  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
305  {
306  // Substring match. The earlier in the string the better.
307  Score += matchPosScore( found_pos, 20 ) + 20;
308  }
309 
310  // More matchers = better match
311  Score += 2 * matchers_fired;
312  }
313 }
314 
315 
317 {
318  Type = ROOT;
319 }
320 
321 
322 LIB_TREE_NODE_LIB& LIB_TREE_NODE_ROOT::AddLib( wxString const& aName, wxString const& aDesc )
323 {
324  LIB_TREE_NODE_LIB* lib = new LIB_TREE_NODE_LIB( this, aName, aDesc );
325  Children.push_back( std::unique_ptr<LIB_TREE_NODE>( lib ) );
326  return *lib;
327 }
328 
329 
331 {
332  for( auto& child: Children )
333  child->UpdateScore( aMatcher );
334 }
335 
void SortNodes()
Sort child nodes quickly and recursively (IntrinsicRanks must have been set).
int StrNumCmp(const wxString &aString1, const wxString &aString2, bool aIgnoreCase)
Compare two strings with alphanumerical content.
Definition: string.cpp:354
PTR_VECTOR Children
List of child nodes.
enum TYPE Type
Node type.
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
bool Normalized
Support for lazy normalization.
Node type: LIB_ID.
wxString const & GetPattern() const
PGM_BASE & Pgm()
The global Program "get" accessor.
Definition: kicad.cpp:65
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Perform the actual search.
LIB_TREE_NODE * Parent
Parent node or null.
int Score
The score of an item resulting from the search algorithm.
Abstract pattern-matching tool and implementations.
virtual bool IsRoot() const
For items having aliases, IsRoot() indicates the principal item.
Definition: lib_tree_item.h:54
virtual wxString GetSearchText()
Definition: lib_tree_item.h:49
LIB_TREE_NODE_LIB_ID & AddItem(LIB_TREE_ITEM *aItem)
Construct a new alias node, add it to this library, and return it.
wxString MatchName
Normalized name for matching.
VTBL_ENTRY wxLocale * GetLocale()
Definition: pgm_base.h:234
Node type: library.
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
const UTF8 & GetLibNickname() const
Return the logical library name portion of a LIB_ID.
Definition: lib_id.h:97
LIB_ID LibId
LIB_ID determined by the parent library nickname and alias name.
LIB_TREE_NODE_UNIT & AddUnit(LIB_TREE_ITEM *aItem, int aUnit)
Add a new unit to the component and return it.
virtual const wxString & GetDescription()=0
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
#define _(s)
Node type: unit of component.
wxString Desc
Description to be displayed.
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
LIB_TREE_NODE_LIB & AddLib(wxString const &aName, wxString const &aDesc)
Construct an empty library node, add it to the root, and return it.
wxString SearchText
Descriptive text to search.
int SetLibNickname(const UTF8 &aNickname)
Override the logical library name portion of the LIB_ID to aNickname.
Definition: lib_id.cpp:193
virtual int GetUnitCount()
For items with units, return the number of units.
Definition: lib_tree_item.h:59
virtual const wxString & GetName() const =0
wxString Name
Actual name of the part.
bool IsRoot
Indicates if the symbol is a root symbol instead of an alias.
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 max(a, b)
Definition: auxiliary.h:86
int Unit
Actual unit, or zero.
size_t i
Definition: json11.cpp:649
LIB_TREE_NODE_ROOT()
Construct the root node.
int IntrinsicRank
The rank of the item before any search terms are applied.
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.
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:64