nathanday / ndtrie Goto Github PK

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:

• line 57 (testing -everyObjectForKeyWithPrefix:);
• line 60 (ditto);
• line 210 (testing -objectEnumeratorForKeyWithPrefix:);
• line 220 (ditto).

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.