• Stars
    star
    114
  • Rank 308,031 (Top 7 %)
  • Language
    Objective-C
  • License
    MIT License
  • Created about 10 years ago
  • Updated about 10 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Persistent data structures in Objective-C

Persistent Data Structures for Objective-C

The goal of this project is to implement persistent data structures for Objective-C. Right now, there are Vector, Set and HashMap.

Install

With CocoaPods, as easy as adding

pod 'Persistent'

to your Podfile.

Usage

Vector

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.

Examples

#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];

HashMap

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.

Examples

#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];

Set

It's just a proxy on top of AAPersistentHashMap, implementing set functionality on top of persistent hash map.

Examples

#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];

Converting nested stuctures to persistent ones and back to regular ones

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);

Nested CRUD

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 work

So, 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"]}

Performance

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.

HashMap / Set

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)

Vector

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)

Not really production ready

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.

Reading

More Repositories

1

vim-ruby-debugger

Vim plugin for debugging Ruby applications (using ruby-debug-ide gem)
Vim Script
435
star
2

tixi

Ascii charts editor
JavaScript
427
star
3

liftosaur

Weightlifting tracker app for coders
TypeScript
186
star
4

aws-cdk-lambda-typescript-starter

AWS CDK TypeScript skeleton starter for SSR app on Lambda and DynamoDB
TypeScript
27
star
5

page_versioning

Extension for the Radiant CMS. Allows you to save and review all changes of the pages, snippets and layouts.
Ruby
26
star
6

jquery-ui-tree

Widget for jQuery UI. Adds nested expanded/collapsed tree with drag'n'drop support.
JavaScript
19
star
7

perfection

Skeleton of a nice dev environment for ClojureScript
Clojure
17
star
8

debugger-xml

XML interface for 'debugger' gem, compatible with ruby-debug-ide
Ruby
17
star
9

crossdart

Cross-reference of Dart packages
Dart
13
star
10

dartdocs.org

Generates the Dart documentation for all the packages in pub
Dart
12
star
11

crossdart-chrome-extension

Crossdart Chrome Extension, adds "Go to Declaration" and "Find Usages" to Dart projects on Github.
JavaScript
12
star
12

radiant-truncate-extension

Adds truncate tag to Radiant for truncating data within the tag.
Ruby
8
star
13

radiant-webservices-extension

Extension for the Radiant CMS. It adds webservices radiant tags that allows to make remote queries to your webservices and paste results on the pages.
Ruby
7
star
14

radiant-route-handler-extension

RadiantCMS extension. If static page with given URL doesn't exist, it will try to open some special page and send some special params to there.
Ruby
6
star
15

solutions_grid

Ruby On Rails plugin, implementing AJAXed grid with sorting, filtering and paginating.
Ruby
6
star
16

crosshub-chrome-extension

Adds 'Go to definition' and 'Find Usages' functionality to TypeScript projects on Github
JavaScript
6
star
17

squilder

Type-safe SQL builder in Dart
Dart
4
star
18

mintik

A minimal example of a Quiescent app
Clojure
4
star
19

radiant-date-converter-extension

RadiantCMS extension. Adds tag <r:date_converter> for converting date from one format to another
Ruby
4
star
20

radiant-file-content-extension

An extension for RadiantCMS. Adds tag <r:file_content> for inserting contents of external files.
Ruby
3
star
21

ormapper.dart

Lightweight ORM based on Squilder
Dart
3
star
22

qunit_test

Generator and rake task for testing of JavaScript by QUnit
JavaScript
3
star
23

lens-shmens

TypeScript introspectable lens library, with ability to create "recordings" - delayed lens execution.
TypeScript
2
star
24

radiant-cache-observer

Run script after every clear of cache
2
star
25

radiant-random-number-extension

RadiantCMS extension. Adds the tag <r:random_number> for generating random number in given range.
Ruby
2
star
26

lens.dart

Uber simple functional lenses builder in Dart
Dart
2
star
27

selenium-on-rails

Fork of stable version of Selenium on Rails for Rails 2.1
2
star
28

fudge_form

Ruby
2
star
29

rails_foreign_keys

Fork of Foreign Key Schema Dumper Plugin, but only with MySQL and fixed for working with Rails 2.1
2
star
30

12_hour_time

Fork of rails plugin that adds AM/PM time formatting to DateHelper
2
star
31

human_attribute_override

Fork of Human Attribute Override plugin for Rails. The plugin allows humanized versions of attributes to be overridden with custom strings.
Ruby
2
star
32

yatro

Yet Another Typesafe Router
TypeScript
1
star
33

vimfiles

My .vim files
JavaScript
1
star
34

crossdart-server

Crossdart server
Dart
1
star
35

ar_query_source

Puts the source line of the SQL query after the query in logs
Ruby
1
star