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-2017 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 
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<CMP_TREE_NODE*> sort_buf;
64 
65  for( auto const& node: Children )
66  sort_buf.push_back( &*node );
67 
68  std::sort( sort_buf.begin(), sort_buf.end(),
69  []( CMP_TREE_NODE* a, CMP_TREE_NODE* b ) -> bool
70  { return a->MatchName > b->MatchName; } );
71 
72  for( int i = 0; i < (int) sort_buf.size(); ++i )
73  sort_buf[i]->IntrinsicRank = i;
74 }
75 
76 
78 {
79  std::sort( Children.begin(), Children.end(),
80  []( std::unique_ptr<CMP_TREE_NODE> const& a, std::unique_ptr<CMP_TREE_NODE> const& b )
81  { return Compare( *a, *b ) > 0; } );
82 
83  for( auto& node: Children )
84  {
85  node->SortNodes();
86  }
87 }
88 
89 
90 int CMP_TREE_NODE::Compare( CMP_TREE_NODE const& aNode1, CMP_TREE_NODE const& aNode2 )
91 {
92  if( aNode1.Type != aNode2.Type )
93  return 0;
94 
95  if( aNode1.Score != aNode2.Score )
96  return aNode1.Score - aNode2.Score;
97 
98  if( aNode1.Parent != aNode2.Parent )
99  return 0;
100 
101  return aNode1.IntrinsicRank - aNode2.IntrinsicRank;
102 }
103 
104 
106  : Parent( nullptr ),
107  Type( INVALID ),
108  IntrinsicRank( 0 ),
109  Score( kLowestDefaultScore ),
110  Alias( nullptr ),
111  Unit( 0 )
112 {}
113 
114 
116 {
117  Parent = aParent;
118  Type = UNIT;
119 
120  Unit = aUnit;
121  Alias = aParent->Alias;
122 
123  Name = _( "Unit" ) + " " + LIB_PART::SubReference( aUnit, false );
124  Desc = wxEmptyString;
125  MatchName = wxEmptyString;
126 
127  IntrinsicRank = -aUnit;
128 }
129 
130 
132 {
133  Parent = aParent;
134  Type = ALIAS;
135  Name = aAlias->GetName();
136  Desc = aAlias->GetDescription();
137  Alias = aAlias;
138 
139  // Pre-normalized strings for fast case-insensitive matching
140  // Search text spaces out keywords and description to penalize description
141  // matches - earlier matches are worth more.
142  MatchName = aAlias->GetName().Lower();
143  SearchText = (aAlias->GetKeyWords() + " " + Desc).Lower();
144 
145  // Extract default footprint text
146  LIB_PART* part = aAlias->GetPart();
147 
148  wxString footprint;
149 
150  if( part )
151  {
152  footprint = part->GetFootprintField().GetText();
153  }
154 
155  // If a footprint is defined for the part,
156  // add it to the serach string
157  if( !footprint.IsEmpty() )
158  {
159  SearchText += " ";
160  SearchText += footprint.Lower();
161  }
162 
163  if( aAlias->GetPart()->IsMulti() )
164  {
165  for( int u = 1; u <= aAlias->GetPart()->GetUnitCount(); ++u )
166  {
167  AddUnit( u );
168  }
169  }
170 }
171 
172 
174 {
175  CMP_TREE_NODE_UNIT* unit = new CMP_TREE_NODE_UNIT( this, aUnit );
176  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( unit ) );
177  return *unit;
178 }
179 
180 
182 {
183  if( Score <= 0 )
184  return; // Leaf nodes without scores are out of the game.
185 
186  // Keywords and description we only count if the match string is at
187  // least two characters long. That avoids spurious, low quality
188  // matches. Most abbreviations are at three characters long.
189  int found_pos = EDA_PATTERN_NOT_FOUND;
190  int matchers_fired = 0;
191 
192  if( aMatcher.GetPattern() == MatchName )
193  {
194  Score += 1000; // exact match. High score :)
195  }
196  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
197  {
198  // Substring match. The earlier in the string the better.
199  Score += matchPosScore( found_pos, 20 ) + 20;
200  }
201  else if( aMatcher.Find( Parent->MatchName, matchers_fired, found_pos ) )
202  {
203  Score += 19; // parent name matches. score += 19
204  }
205  else if( aMatcher.Find( SearchText, matchers_fired, found_pos ) )
206  {
207  // If we have a very short search term (like one or two letters),
208  // we don't want to accumulate scores if they just happen to be in
209  // keywords or description as almost any one or two-letter
210  // combination shows up in there.
211  if( aMatcher.GetPattern().length() >= 2 )
212  {
213  // For longer terms, we add scores 1..18 for positional match
214  // (higher in the front, where the keywords are).
215  Score += matchPosScore( found_pos, 17 ) + 1;
216  }
217  }
218  else
219  {
220  // No match. That's it for this item.
221  Score = 0;
222  }
223 
224  // More matchers = better match
225  Score += 2 * matchers_fired;
226 }
227 
228 
229 CMP_TREE_NODE_LIB::CMP_TREE_NODE_LIB( CMP_TREE_NODE* aParent, wxString const& aName )
230 {
231  Type = LIB;
232  Name = aName;
233  MatchName = aName.Lower();
234  Parent = aParent;
235 }
236 
237 
239 {
240  CMP_TREE_NODE_ALIAS* alias = new CMP_TREE_NODE_ALIAS( this, aAlias );
241  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( alias ) );
242  return *alias;
243 }
244 
245 
247 {
248  Score = 0;
249 
250  for( auto& child: Children )
251  {
252  child->UpdateScore( aMatcher );
253  Score = std::max( Score, child->Score );
254  }
255 }
256 
257 
259 {
260  Type = ROOT;
261 }
262 
263 
265 {
266  CMP_TREE_NODE_LIB* lib = new CMP_TREE_NODE_LIB( this, aName );
267  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( lib ) );
268  return *lib;
269 }
270 
271 
273 {
274  for( auto& child: Children )
275  child->UpdateScore( aMatcher );
276 }
277 
LIB_FIELD & GetFootprintField()
Return reference to the footprint field.
wxString Name
Actual name of the part.
wxString Desc
Description to be displayed.
wxString const & GetPattern() const
CMP_TREE_NODE_UNIT & AddUnit(int aUnit)
Add a new unit to the component and return it.
Part library alias object definition.
bool IsMulti() const
Function IsMulti.
Node type: alias.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Perform the actual search.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Update the score for this part.
enum TYPE Type
Node type.
void ResetScore()
Initialize score to kLowestDefaultScore, recursively.
void SortNodes()
Sort child nodes quickly and recursively (IntrinsicRanks must have been set).
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't let them be ...
Abstract pattern-matching tool and implementations.
virtual void UpdateScore(EDA_COMBINED_MATCHER &aMatcher) override
Update the score for this part.
void AssignIntrinsicRanks()
Store intrinsic ranks on all children of this node.
const wxString & GetText() const
Function GetText returns the string associated with the text object.
Definition: eda_text.h:130
wxString GetDescription() const
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
Class LIB_PART defines a library part object.
wxString MatchName
Normalized name for matching.
static const int EDA_PATTERN_NOT_FOUND
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.
CMP_TREE_NODE * Parent
Parent node or null.
LIB_PART * GetPart() const
Function GetPart gets the shared LIB_PART.
int GetUnitCount() const
wxString SearchText
Descriptive text to search.
Implementation of std::make_unique for pre C++14 compilation environments.
const wxString & GetName() const
#define max(a, b)
Definition: auxiliary.h:86
CMP_TREE_NODE_ALIAS & AddAlias(LIB_ALIAS *aAlias)
Construct a new alias node, add it to this library, and return it.
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't let them be ...
static wxString SubReference(int aUnit, bool aAddSeparator=true)
Function SubReference.
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.
LIB_ALIAS * Alias
Actual LIB_ALIAS*, or null.
std::vector< std::unique_ptr< CMP_TREE_NODE > > Children
List of child nodes.
wxString GetKeyWords() const
Node type: unit of component.
CMP_TREE_NODE_ALIAS(CMP_TREE_NODE_ALIAS const &_)=delete
The addresses of CMP_TREE_NODEs are used as unique IDs for the wxDataViewModel, so don't let them be ...
CMP_TREE_NODE_LIB & AddLib(wxString const &aName)
Construct an empty library node, add it to the root, and return it.
int Score
The score of an item resulting from the search algorithm.