KiCad PCB EDA Suite
cmp_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-2018 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 <cmp_tree_model.h>
23 
24 #include <class_library.h>
25 #include <eda_pattern_match.h>
26 #include <make_unique.h>
27 #include <utility>
28 #include <pgm_base.h>
29 
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: Children )
56  child->ResetScore();
57 
59 }
60 
61 
63 {
64  std::vector<CMP_TREE_NODE*> sort_buf;
65 
66  for( auto const& node: Children )
67  sort_buf.push_back( &*node );
68 
69  std::sort( sort_buf.begin(), sort_buf.end(),
70  []( CMP_TREE_NODE* a, CMP_TREE_NODE* b ) -> bool
71  { return a->MatchName > b->MatchName; } );
72 
73  for( int i = 0; i < (int) sort_buf.size(); ++i )
74  sort_buf[i]->IntrinsicRank = i;
75 }
76 
77 
79 {
80  std::sort( Children.begin(), Children.end(),
81  []( std::unique_ptr<CMP_TREE_NODE> const& a, std::unique_ptr<CMP_TREE_NODE> const& b )
82  { return Compare( *a, *b ) > 0; } );
83 
84  for( auto& node: Children )
85  {
86  node->SortNodes();
87  }
88 }
89 
90 
91 int CMP_TREE_NODE::Compare( CMP_TREE_NODE const& aNode1, CMP_TREE_NODE const& aNode2 )
92 {
93  if( aNode1.Type != aNode2.Type )
94  return 0;
95 
96  if( aNode1.Score != aNode2.Score )
97  return aNode1.Score - aNode2.Score;
98 
99  if( aNode1.Parent != aNode2.Parent )
100  return 0;
101 
102  return aNode1.IntrinsicRank - aNode2.IntrinsicRank;
103 }
104 
105 
107  : Parent( nullptr ),
108  Type( INVALID ),
109  IntrinsicRank( 0 ),
111  SearchTextNormalized( false ),
112  Unit( 0 ),
113  IsRoot( false )
114 {}
115 
116 
118 {
119  static void* locale = nullptr;
120  static wxString namePrefix;
121 
122  // Fetching translations can take a surprising amount of time when loading libraries,
123  // so only do it when necessary.
124  if( Pgm().GetLocale() != locale )
125  {
126  namePrefix = _( "Unit" );
127  locale = Pgm().GetLocale();
128  }
129 
130  Parent = aParent;
131  Type = UNIT;
132 
133  Unit = aUnit;
134  LibId = aParent->LibId;
135 
136  Name = namePrefix + " " + LIB_PART::SubReference( aUnit, false );
137  Desc = wxEmptyString;
138  MatchName = wxEmptyString;
139 
140  IntrinsicRank = -aUnit;
141 }
142 
143 
145 {
146  wxASSERT( aParent && aAlias );
147 
148  Type = LIBID;
149  Parent = aParent;
150  Update( aAlias );
151 }
152 
153 
155 {
156  CMP_TREE_NODE_UNIT* unit = new CMP_TREE_NODE_UNIT( this, aUnit );
157  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( unit ) );
158  return *unit;
159 }
160 
161 
163 {
164  Name = aAlias->GetName();
165  Desc = aAlias->GetDescription();
166 
167  // Parent node is the library nickname so set the LIB_ID library nickname.
168  IsRoot = aAlias->IsRoot();
169 
170  // Pre-normalized strings for fast case-insensitive matching
171  // Search text spaces out keywords and description to penalize description
172  // matches - earlier matches are worth more.
173  MatchName = aAlias->GetName().Lower();
174  SearchText = (aAlias->GetKeyWords() + " " + Desc);
175 
176  // Extract default footprint text
177  LIB_PART* part = aAlias->GetPart();
178 
179  wxString footprint;
180 
181  if( part )
182  {
183  LibId = part->GetLibId();
185  footprint = part->GetFootprintField().GetText();
186  }
187 
188  // If a footprint is defined for the part,
189  // add it to the serach string
190  if( !footprint.IsEmpty() )
191  {
192  SearchText += " ";
193  SearchText += footprint;
194  }
195 
196  Children.clear();
197 
198  if( part && part->IsMulti() )
199  {
200  for( int u = 1; u <= part->GetUnitCount(); ++u )
201  AddUnit( u );
202  }
203 
204  SearchTextNormalized = false;
205 }
206 
207 
209 {
210  if( Score <= 0 )
211  return; // Leaf nodes without scores are out of the game.
212 
213  if( !SearchTextNormalized )
214  {
215  SearchText = SearchText.Lower();
216  SearchTextNormalized = true;
217  }
218 
219  // Keywords and description we only count if the match string is at
220  // least two characters long. That avoids spurious, low quality
221  // matches. Most abbreviations are at three characters long.
222  int found_pos = EDA_PATTERN_NOT_FOUND;
223  int matchers_fired = 0;
224 
225  if( aMatcher.GetPattern() == MatchName )
226  {
227  Score += 1000; // exact match. High score :)
228  }
229  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
230  {
231  // Substring match. The earlier in the string the better.
232  Score += matchPosScore( found_pos, 20 ) + 20;
233  }
234  else if( aMatcher.Find( Parent->MatchName, matchers_fired, found_pos ) )
235  {
236  Score += 19; // parent name matches. score += 19
237  }
238  else if( aMatcher.Find( SearchText, matchers_fired, found_pos ) )
239  {
240  // If we have a very short search term (like one or two letters),
241  // we don't want to accumulate scores if they just happen to be in
242  // keywords or description as almost any one or two-letter
243  // combination shows up in there.
244  if( aMatcher.GetPattern().length() >= 2 )
245  {
246  // For longer terms, we add scores 1..18 for positional match
247  // (higher in the front, where the keywords are).
248  Score += matchPosScore( found_pos, 17 ) + 1;
249  }
250  }
251  else
252  {
253  // No match. That's it for this item.
254  Score = 0;
255  }
256 
257  // More matchers = better match
258  Score += 2 * matchers_fired;
259 }
260 
261 
263  wxString const& aName, wxString const& aDesc )
264 {
265  Type = LIB;
266  Name = aName;
267  MatchName = aName.Lower();
268  Desc = aDesc;
269  Parent = aParent;
270  LibId.SetLibNickname( aName );
271 }
272 
273 
275 {
276  CMP_TREE_NODE_LIB_ID* alias = new CMP_TREE_NODE_LIB_ID( this, aAlias );
277  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( alias ) );
278  return *alias;
279 }
280 
281 
283 {
284  Score = 0;
285 
286  for( auto& child: Children )
287  {
288  child->UpdateScore( aMatcher );
289  Score = std::max( Score, child->Score );
290  }
291 }
292 
293 
295 {
296  Type = ROOT;
297 }
298 
299 
300 CMP_TREE_NODE_LIB& CMP_TREE_NODE_ROOT::AddLib( wxString const& aName, wxString const& aDesc )
301 {
302  CMP_TREE_NODE_LIB* lib = new CMP_TREE_NODE_LIB( this, aName, aDesc );
303  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( lib ) );
304  return *lib;
305 }
306 
307 
309 {
310  for( auto& child: Children )
311  child->UpdateScore( aMatcher );
312 }
313 
LIB_FIELD & GetFootprintField()
Return reference to the footprint field.
wxString Name
Actual name of the part.
wxString Desc
Description to be displayed.
CMP_TREE_NODE_LIB & AddLib(wxString const &aName, wxString const &aDesc)
Construct an empty library node, add it to the root, and return it.
wxString const & GetPattern() const
CMP_TREE_NODE_LIB_ID(CMP_TREE_NODE_LIB_ID const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don&#39;t let them be ...
Part library alias object definition.
bool IsMulti() const
bool SearchTextNormalized
Support for lazy normalization.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Update the score for this part.
const LIB_ID & GetLibId() const
enum TYPE Type
Node type.
CMP_TREE_NODE_LIB_ID & AddAlias(LIB_ALIAS *aAlias)
Construct a new alias node, add it to this library, and return it.
PGM_BASE & Pgm()
The global Program "get" accessor.
Definition: kicad.cpp:66
void ResetScore()
Initialize score to kLowestDefaultScore, recursively.
void SortNodes()
Sort child nodes quickly and recursively (IntrinsicRanks must have been set).
bool IsRoot
Indicates if the symbol is a root symbol instead of an alias.
LIB_ID LibId
LIB_ID determined by the parent library nickname and alias name.
CMP_TREE_NODE_UNIT(CMP_TREE_NODE_UNIT const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don&#39;t let them be ...
Abstract pattern-matching tool and implementations.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Update the score for this part.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Perform the actual search.
bool IsRoot() const
void AssignIntrinsicRanks()
Store intrinsic ranks on all children of this node.
VTBL_ENTRY wxLocale * GetLocale()
Definition: pgm_base.h:175
const wxString & GetText() const
Function GetText returns the string associated with the text object.
Definition: eda_text.h:128
wxString GetDescription() const
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
Define a library symbol object.
wxString MatchName
Normalized name for matching.
static const int EDA_PATTERN_NOT_FOUND
CMP_TREE_NODE_UNIT & AddUnit(int aUnit)
Add a new unit to the component and return it.
static int matchPosScore(int aPosition, int aMaximum)
Node type: library.
Model class in the component selector Model-View-Adapter (mediated MVC) architecture.
CMP_TREE_NODE_ROOT()
Construct the root node.
int SetLibItemName(const UTF8 &aLibItemName, bool aTestForRev=true)
Override the library item name portion of the LIB_ID to aLibItemName.
Definition: lib_id.cpp:232
CMP_TREE_NODE * Parent
Parent node or null.
LIB_PART * GetPart() const
Get the shared LIB_PART.
int SetLibNickname(const UTF8 &aNickname)
Override the logical library name portion of the LIB_ID to aNickname.
Definition: lib_id.cpp:219
int GetUnitCount() const
wxString SearchText
Descriptive text to search.
see class PGM_BASE
Implementation of std::make_unique for pre C++14 compilation environments.
const wxString & GetName() const
#define max(a, b)
Definition: auxiliary.h:86
void Update(LIB_ALIAS *aAlias)
Update the node using data from a LIB_ALIAS object.
PTR_VECTOR Children
List of child nodes.
CMP_TREE_NODE_LIB(CMP_TREE_NODE_LIB const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don&#39;t let them be ...
size_t i
Definition: json11.cpp:597
static wxString SubReference(int aUnit, bool aAddSeparator=true)
int IntrinsicRank
The rank of the item before any search terms are applied.
static const unsigned kLowestDefaultScore
static int Compare(CMP_TREE_NODE const &aNode1, CMP_TREE_NODE const &aNode2)
Compare two nodes.
int Unit
Actual unit, or zero.
Definition for part library class.
wxString GetKeyWords() const
Node type: unit of component.
int Score
The score of an item resulting from the search algorithm.
Node type: LIB_ID.