1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.search.query;
import com.yahoo.prelude.query.*;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/**
* The root node of a query tree. This is always present above the actual semantic root to ease query manipulation,
* especially replacing the actual semantic root, but does not have any search semantics on its own.
*
* <p>To ease recursive manipulation of the query tree, this is a composite having one child, which is the actual root.
* <ul>
* <li>Setting the root item (at position 0, either directly or though the iterator of this, works as expected.
* Setting at any other position is disallowed.
* <li>Removing the root is allowed and causes this to be a null query.
* <li>Adding an item is only allowed if this is currently a null query (having no root)
* </ul>
*
* <p>This is also the home of accessor methods which eases querying into and manipulation of the query tree.</p>
*
* @author Arne Bergene Fossaa
*/
public class QueryTree extends CompositeItem {
public QueryTree(Item root) {
setRoot(root);
}
public void setIndexName(String index) {
if (getRoot() != null)
getRoot().setIndexName(index);
}
public ItemType getItemType() {
throw new RuntimeException("Packet type access attempted. A query tree has no packet code. " +
"This is probably a misbehaving searcher.");
}
public String getName() { return "ROOT"; }
public int encode(ByteBuffer buffer) {
if (getRoot() == null) return 0;
return getRoot().encode(buffer);
}
// Let's not pollute toString() by adding "ROOT"
protected void appendHeadingString(StringBuilder sb) {
}
/** Returns the query root. This is null if this is a null query. */
public Item getRoot() {
if (getItemCount() == 0) return null;
return getItem(0);
}
public final void setRoot(Item root) {
if (root == this) throw new IllegalArgumentException("Cannot make a root point at itself");
if (root == null) throw new IllegalArgumentException("Root must not be null, use NullItem instead.");
if (root instanceof QueryTree) throw new IllegalArgumentException("Do not use a new QueryTree instance as a root.");
if (this.getItemCount() == 0) // initializing
super.addItem(root);
else
setItem(0, root); // replacing
}
@Override
public boolean equals(Object o) {
if( !(o instanceof QueryTree)) return false;
return super.equals(o);
}
/** Returns a deep copy of this */
@Override
public QueryTree clone() {
QueryTree clone = (QueryTree) super.clone();
fixClonedConnectivityReferences(clone);
return clone;
}
private void fixClonedConnectivityReferences(QueryTree clone) {
// TODO!
}
@Override
public void addItem(Item item) {
if (getItemCount() == 0)
super.addItem(item);
else
throw new RuntimeException("Programming error: Cannot add multiple roots");
}
@Override
public void addItem(int index, Item item) {
if (getItemCount() == 0 && index == 0)
super.addItem(index, item);
else
throw new RuntimeException("Programming error: Cannot add multiple roots, have '" + getRoot() + "'");
}
/** Returns true if this represents the null query */
public boolean isEmpty() {
return getRoot() instanceof NullItem || getItemCount() == 0;
}
// -------------- Facade
/**
* Modifies this query to become the current query RANK with the given item.
*
* @return the resulting root item in this
*/
public Item withRank(Item item) {
var result = new RankItem();
result.addItem(getRoot());
result.addItem(item);
setRoot(result);
return result;
}
/**
* Modifies this query to become the current query AND the given item.
*
* @return the resulting root item in this
*/
public Item and(Item item) {
Item result = and(getRoot(), item);
setRoot(result);
return result;
}
private Item and(Item a, Item b) {
if (a == null || a instanceof NullItem) {
return b;
}
else if (b == null || b instanceof NullItem) {
return a;
}
else if (a instanceof NotItem notItemA && b instanceof NotItem notItemB) {
NotItem combined = new NotItem();
combined.addPositiveItem(and(notItemA.getPositiveItem(), notItemB.getPositiveItem()));
notItemA.negativeItems().forEach(item -> combined.addNegativeItem(item));
notItemB.negativeItems().forEach(item -> combined.addNegativeItem(item));
return combined;
}
else if (a instanceof NotItem notItem){
notItem.addPositiveItem(b);
return a;
}
else if (b instanceof NotItem notItem){
notItem.addPositiveItem(a);
return notItem;
}
else if (a instanceof AndItem) {
((AndItem)a).addItem(b);
return a;
}
else {
AndItem andItem = new AndItem();
andItem.addItem(a);
andItem.addItem(b);
return andItem;
}
}
/** Returns a flattened list of all positive query terms under the given item */
public static List<IndexedItem> getPositiveTerms(Item item) {
List<IndexedItem> items = new ArrayList<>();
getPositiveTerms(item,items);
return items;
}
private static void getPositiveTerms(Item item, List<IndexedItem> terms) {
if (item instanceof NotItem notItem) {
getPositiveTerms(notItem.getPositiveItem(), terms);
} else if (item instanceof PhraseItem phraseItem) {
terms.add(phraseItem);
} else if (item instanceof CompositeItem compositeItem) {
for (Iterator<Item> i = compositeItem.getItemIterator(); i.hasNext();) {
getPositiveTerms(i.next(), terms);
}
} else if (item instanceof TermItem termItem) {
terms.add(termItem);
}
}
/**
* Returns the total number of items in this query tree.
*/
public int treeSize() {
if (isEmpty()) return 0;
return countItemsRecursively(getItemIterator().next());
}
private int countItemsRecursively(Item item) {
int children = 0;
if (item instanceof CompositeItem composite) {
for (ListIterator<Item> i = composite.getItemIterator(); i.hasNext(); ) {
children += countItemsRecursively(i.next());
}
}
return children + 1;
}
}
|
