The goal of this project is to implement persistent data structures for Objective-C. Right now, there are Vector, Set and HashMap.
With CocoaPods, as easy as adding
pod 'Persistent'to your Podfile.
For now, it's a port of Clojure's PersistentVector and Dart's Persistent Vector. It's a persistent bit-partitioned vector trie, and it uses the same optimizations, which are used in Clojure and Dart - tails and transients.
Basically there are addObject:/removeLastObject and objectAtIndex:/replaceObjectAtIndex:withObject: operations, and also withTransient method, which allows you to temporarily make the vector mutable and make modifications without creating instances every single time you make operations on it.
It doesn't have methods for inserting/removing elements in the middle of the vector. Unfortunately, you have to do that in a slow way - by creating a new vector from the scratch with (or - for deletion - without) the element.
#import "AAPersistent.h"
/// Initialization
AAPersistentVector *vector1 = [[AAPersistentVector alloc] init];
// But if you need a persistent empty vector, better use the pre-created empty one.
AAPersistentVector *vector2 = [AAPersistentVector empty];
// Or you can load an array into it during initialization:
AAPersistentVector *vector = [[AAPersistentVector alloc] initWithArray:@[@1, @2, @3]];
/// CRUD operations
[vector objectAtIndex:1]; // => @2
vector = [vector addObject:@4]; // => vector with @1, @2, @3, @4
vector = [vector replaceObjectAtIndex:2 withObject:@5]; // => vector with @1, @2, @5, @4
vector = [vector removeLastObject]; // => vector with @1, @2, @5
/// Convert to NSArray
[vector toArray]; // => @[@1, @2, @5]
/// Iterating
// With Fast Enumeration
for (id value in vector) {
// going to iterate through values with `value` = @1, @2 and @5
}
// With Iterator
id<AAIIterator> iterator = [vector iterator];
while (iterator) {
[iterator first]; // => @1, @2 and @5
iterator = [iterator next];
}
// With each (fastest way)
[vector each:^(id value) {
// going to iterate through values with `value` = @1, @2 and @5
}];
/// Transients
// Efficiently add 100 objects to the vector. Will be ~10 times faster than
// adding without transient
[vector withTransient:^(AATransientVector *transient) {
for (NSUInteger i = 0; i < 100; i += 1) {
transient = [transient addObject:@(i)];
}
return transient;
}];
// You can also do that without a block, if you want
AATransientVector *transientVector = [vector asTransient];
for (NSUInteger i = 0; i < 100; i += 1) {
transientVector = [transientVector addObject:@(i)];
}
vector = [transientVector asPersistent];It's also a port of Clojure's PersistentHashMap. It's a Hash Array Mapped Trie based data structure, just persistent and with some optimizations (transients) - the same optimizations Clojure's Hash Map has.
Main methods are objectForKey:, setObject:forKey, and removeObjectForKey:, allowing you to add, modify, read and delete keys and values from the map.
Also, it has the withTransient method too, allowing to make bulk operations with the map faster.
#import "AAPersistent.h"
/// Initialization
AAPersistentHashMap *map1 = [[AAPersistentHashMap alloc] init];
// But if you need a persistent empty map, better use the pre-created empty one.
AAPersistentHashMap *map2 = [AAPersistentHashMap empty];
// Or you can load a dictionary into it during initialization:
AAPersistentHashMap *map = [[AAPersistentHashMap alloc]
initWithDictionary:@{@1: @2, @3: @4}
];
/// CRUD operations
[map objectForKey:@1]; // => @2
map = [map setObject:@6 forKey:@5]; // => map with @1: @2, @3: @4, @5: @6
map = [map removeObjectForKey:@3]; // => map with @1: @2, @5: @6
/// Convert to NSDictionary
[map toDictionary]; // => @{@1: @2, @5: @6}
/// Iterating
// With Fast Enumeration
for (id value in map) {
// going to iterate through values with `value` = @1 and @5
}
// With Iterator
id<AAIIterator> iterator = [map iterator];
while (iterator) {
[iterator first]; // => @[@1, @2] and @[@5, @6]
iterator = [iterator next];
}
// With each (fastest way)
[map each:^(id key, id value) {
// going to iterate through keys and values
}];
/// Transients
// Efficiently set 100 objects in the map. Will be ~10 times faster than
// adding without transient
[map withTransient:^(AATransientHashMap *transient) {
for (NSUInteger i = 0; i < 100; i += 1) {
transient = [transient setObject:@(i + 1) forKey:@(i)];
}
return transient;
}];
// You can also do that without a block, if you want
AATransientHashMap *transientMap = [map asTransient];
for (NSUInteger i = 0; i < 100; i += 1) {
transientMap = [transientMap setObject:@(i + 1) forKey:@(i)];
}
map = [transientMap asPersistent];It's just a proxy on top of AAPersistentHashMap, implementing set functionality on top of persistent hash map.
#import "AAPersistent.h"
/// Initialization
AAPersistentSet *set1 = [[AAPersistentSet alloc] init];
// But if you need a persistent empty vector, better use the pre-created empty one.
AAPersistentSet *set2 = [AAPersistentSet empty];
// Or you can load an array into it during initialization:
AAPersistentSet *set = [[AAPersistentSet alloc]
initWithSet:[NSSet setWithObjects:@1, @2, @3, nil]
];
/// CRUD operations
[set containsObject:@1]; // => YES
set = [set addObject:@4]; // => set with @1, @2, @3, @4
set = [set addObject:@3]; // => set with @1, @2, @3, @4
set = [set removeObject:@3]; // => set with @1, @2, @4
/// Convert to NSSet
[set toSet]; // => NSSet with @1, @2 and @4
/// Iterating
// With Fast Enumeration
for (id value in set) {
// going to iterate through values with `value` = @1, @2 and @4
}
// With Iterator
id<AAIIterator> iterator = [set iterator];
while (iterator) {
[iterator first]; // => @1, @2 and @4
iterator = [iterator next];
}
// With each (fastest way)
[set each:^(id value) {
// going to iterate through values with `value` = @1, @2 and @4
}];
/// Transients
// Efficiently add 100 objects to the set. Will be ~10 times faster than
// adding without transient
[set withTransient:^(AATransientSet *transient) {
for (NSUInteger i = 0; i < 100; i += 1) {
transient = [transient addObject:@(i)];
}
return transient;
}];
// You can also do that without a block, if you want
AATransientSet *transientVector = [set asTransient];
for (NSUInteger i = 0; i < 100; i += 1) {
transientVector = [transientVector addObject:@(i)];
}
set = [transientVector asPersistent];There are 2 functions, defined in "AAPersistentFunctions.h" - persist and unpersist. They allow to convert regular nested arrays/dictionaries/sets into persistent vectors/maps/sets, like this:
AAPersistentHashMap *map = (AAPersistentHashMap *)persist(
@{@"foo": @"bar", @"bla": @[@"zoo", @{@"abc": @"def"}]}
);and also back:
NSDictionary *dict = (NSDictionary *)unpersist(map);It is often your data structures look like a tree (or JSON structure), with nested dictionaries and arrays. Since the structures are immutable, you cannot simply do something like:
AAPersistentHashMap *map = (AAPersistentHashMap *)persist(
@{@"foo": @"bar", @"bla": @[@"zoo", @{@"abc": @"def"}]}
);
map[@"bla"][1][@"abc"] = @"new_value"; // Obviously won't workSo, there are convenience methods objectAt:, insertAt:withValue:, setAt:withValue, addAt:withValue and removeAt: exactly for these cases.
It works like this:
/// objectAt:
AAPersistentHashMap *map = (AAPersistentHashMap *)persist(
@{@"foo": @"bar", @"bla": @[@"zoo", @{@"abc": @"def"}]}
);
AAPersistentHashMap *map1;
NSString *value = [map objectAt:@[@"bla", @1, @"abc"]]; // => @"def"
/// insertAt:withValue:
map1 = [map insertAt:@[@"bla", @1, @"abc"] withValue:@"new one"];
// Map1 is @{@"foo": @"bar", @"bla": @[@"zoo", @{@"abc": @"new one"}]}
// It surely also works for vector, but very unefficient if inserted not at the last position
map1 = [map insertAt:@[@"bla", @0] withValue:@"new one"];
// Map1 is @{@"foo": @"bar", @"bla": @[@"new_one", @"zoo", @{@"abc": @"def"}]}
/// removeAt:withValue:
map2 = [map removeAt:@[@"bla", @1, @"abc"]];
// Map2 is @{@"foo": @"bar", @"bla": @[@"zoo"]}
// It surely also works for vector, but very unefficient if removed not at the last position
map1 = [map removeAt:@[@"bla", @0]];
// Map1 is @{@"foo": @"bar", @"bla": @[@{@"abc": @"def"}]}
/// setAt:withValue:
/// It's the same as insertAt:withValue for hashMap for a vector, but slightly different for a vector.
/// For vector, it replaces the value at the index instead of inserting a new one
map1 = [map setAt:@[@"bla", @0] withValue:@"new one"];
// Map1 is @{@"foo": @"bar", @"bla": @[@"new_one", @{@"abc": @"def"}]}
/// addAt:withValue:
/// It only works for vectors, just adds a value to the end
map1 = [map addAt:@[@"bla"] withValue:@"new one"];
// Map1 is @{@"foo": @"bar", @"bla": @[@"zoo", @{@"abc": @"def"}, @"new one"]}Tested in a pretty naive way - made the following operations with 1000000 records and compared the results. Used transients for persistent data structures where possible. I tested on my MacbookPro i7 2.7GHz with 16GB RAM.
It's slower than NSMutableDictionary:
- ~20x (6.893s / 0.329s) for setObject:ForKey:
- ~15x (3.853s / 0.233s) for objectForKey:
- ~15x (1.243s / 0.074s) for iteration (with for-in for NSMutableDictionary and
each:for AAPersistentHashMap)
It's slower than NSMutableArray:
- ~100x (4.074s / 0.048s) for addObject:
- ~100x (1.169s / 0.011s) for objectForKey:
- ~120x (5.24s / 0.042s) for iteration (with for-in for NSMutableDictionary and
each:for AAPersistentVector)
These data structures are not really production ready, they are not thoroughly tested so far. But you are more than encouraged to try it out and tell me if you find any bugs or want any additional features :) Pull Requests are also very welcomed.