nathanday / ndtrie Goto Github PK
View Code? Open in Web Editor NEWAn implementation of a trie in Objective-C, NDTrie contains an immutable version NDTrie and a mutable version NDMutableTrie
License: Other
An implementation of a trie in Objective-C, NDTrie contains an immutable version NDTrie and a mutable version NDMutableTrie
License: Other
Using a Interpolation search to find each child node would be quicker than the current binary search.
Each node currently has two mallocs, one for the node and one for its array of children, the node and children can be merge into a single malloc.
Implicit conversion from BOOL to init.
Use of functions that have not been previously declared, need to be changed to static.
hi, how to serialize and deserialize a very big Trie?
I found that search is very fast, but build the trie is very slow when there are 235886 words(/usr/share/dict/words) .
I am trying to create a trie of words listed in a txt file. My file size is 6 MB. Library is not allowing to create a trie of contents from this file, so I tried cut it short. Now this library creates trie only upto 1.5 MB file only.
Would like to see more tests for tries in different states.
Just add a flag so all keys are converted to lower case.
Sometime you want to have more than one way to find the same object, some way to handle the duplicates would be nice, either everyUniqueObject... version of the everyObject... methods or perhaps a setObject:froKeys: equivalent which took multiple keys.
It's not clear what license this uses.
Maybe I misunderstand how Trie is commonly defined, however, I think NDTrie has incorrectly operation in method removeObjectForKey.
I wrote some simple unit tests. So take a look at those comments in code.
@implementation NDTrieTests
{
NDMutableTrie *_trie;
}
- (void)setUp
{
[super setUp];
NDMutableTrie *trie = [NDMutableTrie trie];
[trie addString:@"12"];
[trie addString:@"1234"];
_trie = trie;
}
- (void)tearDown
{
[super tearDown];
}
- (void)testRemoveKey
{
[_trie addString:@"123"];
NSLog(@"trie: %@", _trie); // trie: { 12, 123, 1234 }
[_trie removeObjectForKey:@"1234"]; // incorrectly removes all objects...
id object = [_trie objectForKey:@"1234"];
STAssertNil(object, @"no object for 1234");
object = [_trie objectForKey:@"12"];
STAssertEqualObjects(object, @"12", @"Got object for 12"); // fail..
object = [_trie objectForKey:@"123"];
STAssertEqualObjects(object, @"123", @"Got object for 123"); // fail..
NSLog(@"testRemoveKey: %@", _trie);
// testRemoveKey: { }
// where it should be { 12, 123 }
}
- (void)testRemoveKeyHasChildren
{
[_trie addString:@"123"];
NSLog(@"trie: %@", _trie); // trie: { 12, 123, 1234 }
[_trie removeObjectForKey:@"123"]; // has no effect...
id object = [_trie objectForKey:@"123"];
STAssertNil(object, @"no object for 123"); // fail..
object = [_trie objectForKey:@"1234"];
STAssertEqualObjects(object, @"1234", @"Got object for 1234");
NSLog(@"testRemoveKeyHasChildren: %@", _trie);
// testRemoveKeyHasChildren: { 12, 123, 1234 }
// where it should be { 12, 1234 }
}
@end
It looks like OBJC2 doesn't get recognized on the iPhone simulator, beats me why, and it falls to the implementation without NSFastEnumerations - which isn't building. I get the following errors, amongst others:
/NDTrie.m:159:0 /NDTrie.m:159: error: too few arguments to function 'setObjectForKey'
/NDTrie.m:516:0 /NDTrie.m:516: warning: class 'NDTrie' does not fully implement the 'NSFastEnumeration' protocol
If I just remove the checks for OBJC2_ and remove the legacy code, it builds and works.
Also, I found the following post which might help understand why this is happening on the Simulator (last one on the page):
http://discussions.apple.com/thread.jspa?threadID=1952943
The "prefix" methods (e.g. -everyObjectForKeyWithPrefix:
) appear not to work properly when the trie is created as case insensitive. For example, in the test project's main.m (function testSetOne()
) replace line 34 from:
NDTrie* theTrie = [NDTrie trieWithArray:theTestTrueStrings];
to:
NDTrie* theTrie = [[NDTrie alloc] initWithCaseInsensitive:YES array:theTestTrueStrings];
This should not change the behavior of the test cases (in particular, theTestTrueStrings
contains only lowercase strings), but in fact the following assertions will fail:
-everyObjectForKeyWithPrefix:
);-objectEnumeratorForKeyWithPrefix:
);Inspecting the return values, it appears as though the prefix checking no longer works, and only full string matches succeed. For example, in line 57 theTempArray
contains @[ "cat" ] instead of @[@"cat", @"caterpillar", @"catalog"] as expected.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.