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  if( aAlias->GetPart()->IsMulti() )
146  {
147  for( int u = 1; u <= aAlias->GetPart()->GetUnitCount(); ++u )
148  {
149  AddUnit( u );
150  }
151  }
152 }
153 
154 
156 {
157  CMP_TREE_NODE_UNIT* unit = new CMP_TREE_NODE_UNIT( this, aUnit );
158  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( unit ) );
159  return *unit;
160 }
161 
162 
164 {
165  if( Score <= 0 )
166  return; // Leaf nodes without scores are out of the game.
167 
168  // Keywords and description we only count if the match string is at
169  // least two characters long. That avoids spurious, low quality
170  // matches. Most abbreviations are at three characters long.
171  int found_pos = EDA_PATTERN_NOT_FOUND;
172  int matchers_fired = 0;
173 
174  if( aMatcher.GetPattern() == MatchName )
175  {
176  Score += 1000; // exact match. High score :)
177  }
178  else if( aMatcher.Find( MatchName, matchers_fired, found_pos ) )
179  {
180  // Substring match. The earlier in the string the better.
181  Score += matchPosScore( found_pos, 20 ) + 20;
182  }
183  else if( aMatcher.Find( Parent->MatchName, matchers_fired, found_pos ) )
184  {
185  Score += 19; // parent name matches. score += 19
186  }
187  else if( aMatcher.Find( SearchText, matchers_fired, found_pos ) )
188  {
189  // If we have a very short search term (like one or two letters),
190  // we don't want to accumulate scores if they just happen to be in
191  // keywords or description as almost any one or two-letter
192  // combination shows up in there.
193  if( aMatcher.GetPattern().length() >= 2 )
194  {
195  // For longer terms, we add scores 1..18 for positional match
196  // (higher in the front, where the keywords are).
197  Score += matchPosScore( found_pos, 17 ) + 1;
198  }
199  }
200  else
201  {
202  // No match. That's it for this item.
203  Score = 0;
204  }
205 
206  // More matchers = better match
207  Score += 2 * matchers_fired;
208 }
209 
210 
211 CMP_TREE_NODE_LIB::CMP_TREE_NODE_LIB( CMP_TREE_NODE* aParent, wxString const& aName )
212 {
213  Type = LIB;
214  Name = aName;
215  MatchName = aName.Lower();
216  Parent = aParent;
217 }
218 
219 
221 {
222  CMP_TREE_NODE_ALIAS* alias = new CMP_TREE_NODE_ALIAS( this, aAlias );
223  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( alias ) );
224  return *alias;
225 }
226 
227 
229 {
230  Score = 0;
231 
232  for( auto& child: Children )
233  {
234  child->UpdateScore( aMatcher );
235  Score = std::max( Score, child->Score );
236  }
237 }
238 
239 
241 {
242  Type = ROOT;
243 }
244 
245 
247 {
248  CMP_TREE_NODE_LIB* lib = new CMP_TREE_NODE_LIB( this, aName );
249  Children.push_back( std::unique_ptr<CMP_TREE_NODE>( lib ) );
250  return *lib;
251 }
252 
253 
255 {
256  for( auto& child: Children )
257  child->UpdateScore( aMatcher );
258 }
259 
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.
wxString GetDescription() const
bool Find(const wxString &aTerm, int &aMatchersTriggered, int &aPosition)
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.