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  InTree( false ),
109  IntrinsicRank( 0 ),
110  Score( kLowestDefaultScore ),
111  Unit( 0 )
112 {}
113 
114 
116 {
117  Parent = aParent;
118  Type = UNIT;
119 
120  Unit = aUnit;
121  LibId = aParent->LibId;
122 
123  Name = _( "Unit" ) + " " + LIB_PART::SubReference( aUnit, false );
124  Desc = wxEmptyString;
125  MatchName = wxEmptyString;
126 
127  IntrinsicRank = -aUnit;
128 }
129 
130 
132 {
133  wxASSERT( aParent && aAlias );
134 
135  Type = LIBID;
136  Parent = aParent;
137  Name = aAlias->GetName();
138  Desc = aAlias->GetDescription();
139 
140  // Parent node is the library nickname so set the LIB_ID library nickname.
141  IsRoot = aAlias->IsRoot();
142 
143  // Pre-normalized strings for fast case-insensitive matching
144  // Search text spaces out keywords and description to penalize description
145  // matches - earlier matches are worth more.
146  MatchName = aAlias->GetName().Lower();
147  SearchText = (aAlias->GetKeyWords() + " " + Desc).Lower();
148 
149  // Extract default footprint text
150  LIB_PART* part = aAlias->GetPart();
151 
152  wxString footprint;
153 
154  if( part )
155  {
156  LibId = part->GetLibId();
157  footprint = part->GetFootprintField().GetText();
158  }
159 
160  // If a footprint is defined for the part,
161  // add it to the serach string
162  if( !footprint.IsEmpty() )
163  {
164  SearchText += " ";
165  SearchText += footprint.Lower();
166  }
167 
168  if( part->IsMulti() )
169  {
170  for( int u = 1; u <= part->GetUnitCount(); ++u )
171  {
172  AddUnit( u );
173  }
174  }
175 }
176 
177 
179 {
180  CMP_TREE_NODE_UNIT* unit = new CMP_TREE_NODE_UNIT( this, aUnit );
181  unit->InTree = true;
182  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( unit ) );
183  return *unit;
184 }
185 
186 
188 {
189  if( Score <= 0 )
190  return; // Leaf nodes without scores are out of the game.
191 
192  // Keywords and description we only count if the match string is at
193  // least two characters long. That avoids spurious, low quality
194  // matches. Most abbreviations are at three characters long.
195  int found_pos = EDA_PATTERN_NOT_FOUND;
196  int matchers_fired = 0;
197 
198  if( aMatcher.GetPattern() == MatchName )
199  {
200  Score += 1000; // exact match. High score :)
201  }
202  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
203  {
204  // Substring match. The earlier in the string the better.
205  Score += matchPosScore( found_pos, 20 ) + 20;
206  }
207  else if( aMatcher.Find( Parent->MatchName, matchers_fired, found_pos ) )
208  {
209  Score += 19; // parent name matches. score += 19
210  }
211  else if( aMatcher.Find( SearchText, matchers_fired, found_pos ) )
212  {
213  // If we have a very short search term (like one or two letters),
214  // we don't want to accumulate scores if they just happen to be in
215  // keywords or description as almost any one or two-letter
216  // combination shows up in there.
217  if( aMatcher.GetPattern().length() >= 2 )
218  {
219  // For longer terms, we add scores 1..18 for positional match
220  // (higher in the front, where the keywords are).
221  Score += matchPosScore( found_pos, 17 ) + 1;
222  }
223  }
224  else
225  {
226  // No match. That's it for this item.
227  Score = 0;
228  }
229 
230  // More matchers = better match
231  Score += 2 * matchers_fired;
232 }
233 
234 
235 CMP_TREE_NODE_LIB::CMP_TREE_NODE_LIB( CMP_TREE_NODE* aParent, wxString const& aName )
236 {
237  Type = LIB;
238  Name = aName;
239  MatchName = aName.Lower();
240  Parent = aParent;
241  LibId.SetLibNickname( aName );
242 }
243 
244 
246 {
247  CMP_TREE_NODE_LIB_ID* alias = new CMP_TREE_NODE_LIB_ID( this, aAlias );
248  alias->InTree = true;
249  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( alias ) );
250  return *alias;
251 }
252 
253 
255 {
256  Score = 0;
257 
258  for( auto& child: Children )
259  {
260  child->UpdateScore( aMatcher );
261  Score = std::max( Score, child->Score );
262  }
263 }
264 
265 
267 {
268  Type = ROOT;
269 }
270 
271 
273 {
274  CMP_TREE_NODE_LIB* lib = new CMP_TREE_NODE_LIB( this, aName );
275  lib->InTree = true;
276  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( lib ) );
277  return *lib;
278 }
279 
280 
282 {
283  for( auto& child: Children )
284  child->UpdateScore( aMatcher );
285 }
286 
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_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't let them be ...
Part library alias object definition.
bool IsMulti() const
Function IsMulti.
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.
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'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.
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
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.
CMP_TREE_NODE * Parent
Parent node or null.
LIB_PART * GetPart() const
Function GetPart gets the shared LIB_PART.
int SetLibNickname(const UTF8 &aNickname)
Function SetLibNickname.
Definition: lib_id.cpp:219
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
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'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.
bool InTree
Flag indicating whether the node is added to the tree.
int Unit
Actual unit, or zero.
Definition for part library class.
wxString GetKeyWords() const
Node type: unit of component.
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.
Node type: LIB_ID.