Comments (2)
I have implemented a fix. The fix is in
ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl.scanForKeysAtStartOf
Input.
Here's a code snippet of the method with the fix wrapped in comments. Look for
// beth tirado
for the fix
protected KeyValuePair<O> computeNext() {
outer_loop: while (charsMatched < documentLength) {
Node nextNode = currentNode.getOutgoingEdge(input.charAt(charsMatched));
if (nextNode == null) {
// Next node is a dead end...
//noinspection UnnecessaryLabelOnBreakStatement
break outer_loop;
}
currentNode = nextNode;
CharSequence currentNodeEdgeCharacters = currentNode.getIncomingEdge();
// beth tirado: Submitted bug http://code.google.com/p/concurrent-trees/issues/detail?id=6
// this is the fix.
if (currentNodeEdgeCharacters.length() + charsMatched > documentLength) {
// this node can't be a match becasue it is too long
return endOfData();
}
// beth tirado: end fix
int charsMatchedThisEdge = 0;
for (int i = 0, j = Math.min(currentNodeEdgeCharacters.length(), documentLength - charsMatched); i < j; i++) {
if (currentNodeEdgeCharacters.charAt(i) != input.charAt(charsMatched + i)) {
// Found a difference in chars between character in key and a character in current node.
// Current node is the deepest match (inexact match)....
break outer_loop;
}
charsMatchedThisEdge++;
}
if (charsMatchedThisEdge == currentNodeEdgeCharacters.length()) {
// All characters in the current edge matched, add this number to total chars matched...
charsMatched += charsMatchedThisEdge;
if (currentNode.getValue() != null) {
return new KeyValuePairImpl<O>(CharSequences.toString(input.subSequence(0, charsMatched)), currentNode.getValue());
}
}
}
return endOfData();
}
};
Original comment by [email protected]
on 7 Oct 2013 at 1:33
from concurrent-trees.
Hi Beth, yes you are correct, this was a bug.
Thanks for identifying this and especially for supplying a patch. I have
applied your patch, which fixes it.
I've released it as concurrent-trees 2.1.1, it should sync to Maven central in
a few hours.
Original comment by [email protected]
on 7 Oct 2013 at 9:03
- Changed state: Fixed
from concurrent-trees.
Related Issues (10)
- Deploy to Maven central HOT 2
- Expose API to get longest prefix match / "closest" keys HOT 11
- New types of tree: ConcurrentPermutermTree, ConcurrentWildcardTree for wildcard queries HOT 2
- Can we make the trees serializable? HOT 3
- Expose API to get longest prefix match HOT 1
- Support 8-bit encoded strings HOT 1
- Add tree.size() methods HOT 3
- add tree.contains()-method HOT 5
- ConcurrentSuffixTree.getKeysEndingWith(x) returns null when x is empty HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from concurrent-trees.