1 /*******************************************************************
2
3 Part of the Fritzing project - http://fritzing.org
4 Copyright (c) 2007-2014 Fachhochschule Potsdam - http://fh-potsdam.de
5
6 Fritzing is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 Fritzing is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Fritzing. If not, see <http://www.gnu.org/licenses/>.
18
19 ********************************************************************
20
21 $Revision: 6904 $:
22 $Author: irascibl@gmail.com $:
23 $Date: 2013-02-26 16:26:03 +0100 (Di, 26. Feb 2013) $
24
25 ********************************************************************/
26
27
28
29 #include "trienode.h"
30 #include "../debugdialog.h"
31
32 #include <QRegExp>
33 #include <QXmlStreamReader>
34
35
TrieLeaf()36 TrieLeaf::TrieLeaf()
37 {
38 }
39
~TrieLeaf()40 TrieLeaf::~TrieLeaf()
41 {
42 }
43
TrieNode(QChar c)44 TrieNode::TrieNode(QChar c)
45 {
46 m_char = c;
47 m_leafData = NULL;
48 m_isLeaf = false;
49 m_caseInsensitive = false;
50 }
51
~TrieNode()52 TrieNode::~TrieNode()
53 {
54 foreach (TrieNode * node, m_children) {
55 delete node;
56 }
57 m_children.clear();
58 }
59
addString(QString & string,bool caseInsensitive,TrieLeaf * leaf)60 void TrieNode::addString(QString & string, bool caseInsensitive, TrieLeaf * leaf) {
61 if (string.isEmpty()) {
62 m_leafData = leaf;
63 m_isLeaf = true;
64 return;
65 }
66
67 QChar in(string.at(0));
68 QString next = string.remove(0, 1);
69 QChar c0, c1;
70 if (caseInsensitive) {
71 c0 = in.toLower();
72 c1 = in.toUpper();
73 }
74 else {
75 c0 = c1 = in;
76 }
77
78 addStringAux(c0, next, caseInsensitive, leaf);
79
80 if (c0 != c1) {
81 addStringAux(c1, next, caseInsensitive, leaf);
82 }
83 }
84
addStringAux(QChar c,QString & next,bool caseInsensitive,TrieLeaf * leaf)85 void TrieNode::addStringAux(QChar c, QString & next, bool caseInsensitive, TrieLeaf * leaf) {
86 bool gotc = false;
87 foreach (TrieNode * node, m_children) {
88 if (node->matchesChar(c)) {
89 node->addString(next, caseInsensitive, leaf);
90 gotc = true;
91 }
92 }
93
94 if (!gotc) {
95 TrieNode * child = new TrieNode(c);
96 m_children.append(child);
97 child->addString(next, caseInsensitive, leaf);
98 }
99 }
100
matchesChar(QChar c)101 bool TrieNode::matchesChar(QChar c) {
102 return (c == m_char);
103 }
104
matches(QString & string,TrieLeaf * & leaf)105 bool TrieNode::matches(QString & string, TrieLeaf * & leaf)
106 {
107 if (string.isEmpty()) {
108 if (m_isLeaf) {
109 leaf = m_leafData;
110 return true;
111 }
112
113 return false;
114 }
115
116 QChar in(string.at(0));
117 foreach (TrieNode * node, m_children) {
118 if (node->matchesChar(in)) {
119 return node->matches(string.remove(0, 1), leaf);
120 }
121 }
122
123 return false;
124 }
125