Serializing a multidimensional array containing references to NSManagedObjects in Core Data

Question

I have two entities, Chain and Step. Chain has an attribute steps, which may be a multidimensional array of Step entities, for example:

[
  step,
  step,
  step,
  [
    step,
    step
  ],
  step
]

Each Step object has a content property that is a string.

If I were using a relational database, I'd simply store that array as JSON, with each step being the step_id of a particular step.

How would I achieve something similar in Core Data? I gather that I would need to make the Step class conform to the NSCoding Protocol, but what would that look like? How would I make it only store the equivalent of its id, i.e. a reference to itself, in the final value of Chain.steps?

EDIT

A comment below suggests that I include a one-to-many relationship (let's call it nextStep) between Step and other Steps. I would then use this relationship to go from one step to the next in a Chain, and thus the Chain entity would only need to contain the first Step in the sequence. The problem with this is that a Step may belong to more than one Chain, and thus it may not always have the same nextStep value.

Answer 1

I would like to discourage you from serializing and deserializing arrays that include Core Data objects. It is possible, you could transform your arrays to hold the URIRepresentation of the object IDs of your steps, but what happens if you delete a step from the database? Your serialized arrays remain tainted with old objects.

---

Here is my proposal.

https://github.com/LeoNatan/ChainStepsExample

My model is set like this:

Link is an abstract entity.

For ease of use, I have defined the following protocol:

@protocol Link <NSObject>

//This is to make chain traversal easy - all links are guaranteed to have "steps".
- (NSOrderedSet*)steps;

@end

And for creation, I added the following convenience factory methods:

@interface Link : NSManagedObject <Link>

+ (id<Link>)linkWithStepsArray:(NSArray*)stepsArray inContext:(NSManagedObjectContext*)context;
+ (id<Link>)linkWithStepsOrderedSet:(NSOrderedSet*)stepsOrderedSet inContext:(NSManagedObjectContext*)context;
+ (id<Link>)linkWithStep:(Step*)step inContext:(NSManagedObjectContext*)context;

@end

Now, creation of a chain and traversal are very easy.

Step* step1 = [Step newObjectInContext:context];
step1.content = @"Wake up";

Step* step2_1 = [Step newObjectInContext:context];
step2_1.content = @"Go to school";

Step* step2_2 = [Step newObjectInContext:context];
step2_2.content = @"Learn new things";

Step* step3 = [Step newObjectInContext:context];
step3.content = @"Go to sleep";

NSOrderedSet* links = [NSOrderedSet orderedSetWithObjects:[Link linkWithStep:step1 inContext:context], [Link linkWithStepsArray:@[step2_1, step2_2] inContext:context], [Link linkWithStep:step3 inContext:context], nil];
[chain setLinks:links];

And finally traversal:

for(Chain* chain in chains)
{
    NSLog(@"<chain %@>", chain.name);

    for(id<Link> link in chain.links)
    {
        NSLog(@"\t<step>");
        for(Step* step in link.steps)
        {
            NSLog(@"\t\t%@", step.content);
        }
        NSLog(@"\t</step>");
    }

    NSLog(@"</chain>\n\n");
}

This allows you a manageable object graph, which will rebuild itself automatically when a task is removed.

This is a simple example. It only solves one level deep. You could have a relationship between SingleStepLink or MultiStepLink and Link (instead of Step) to have an infinite depth, with leafs having the final relationship with Step.

Answer 2

The short answer:
Given by @Leo Natan: You could build a multi-dimensional array of URIRepresentation for each of the Steps linked to the Chain.
This solution is very hard to maintain (no automatic cascade and such).

The problem:
represent a multi-dimensional array using CoreData framework ...
There is no trivial implementation as CoreData is an object graph persistence layer while you need a data structure that have strict order and might contain node duplication.
Also, you must define what is your use for such a data-structure as you might want to implement and optimise your representation to support specific functionality.

My suggestion:
Since you require "Array"s and "object duplication" you should partially give-up your direct relationship modelling and introduce an intermediary entity (lets call it StepPlaceholder).
This entity will take care of order and duplication if needed.
Since you have not specified your use for such a structure, I thought in terms of optimising read operations and incremental growth.
So, we will store your Steps in a sparse, N-dimensional matrix using a form of NSIndexPath

My model:

The binaryIndexPath property is a serialised NSUInteger C-style array where each index in the array is a dimension index the array matrix (the final position of the Step in the Chain).

The indexPath property is transient and only used as utility to convert index paths to NSData (not necessary, just an example).

Edit:
apparently, There is a byte order issue in my implementation. So, in order to resolve it we must flip the order of bytes in each index prior to saving it to the store.
(This could be averted entirely if we use in-memory sorting, which won't have to much of a performance degradation if any).

The implementation of the setter is:

//byte order correction
NSUInteger flipNSUInteger(NSUInteger input) {
    uint8_t* buff = (uint8_t*)(&input);
    uint8_t tmp;
    size_t size = sizeof(input);
    for (NSUInteger i = 0; i < size/2; ++i) {
        tmp = buff[i];
        buff[i] = buff[size-i-1];
        buff[size-i-1] = tmp;
    }
    return input;
}

- (void) setIndexPath:(NSIndexPath*)indexPath
{
    NSIndexPath* currentIndexPath = [self indexPath];
    if ( currentIndexPath==nil ||
        [currentIndexPath compare:indexPath] != NSOrderedSame)
    {
        [self willChangeValueForKey:@"indexPath"];
        if (indexPath) {
            NSUInteger* bytes = (NSUInteger*)malloc([indexPath length]*sizeof(NSUInteger));
            [indexPath getIndexes:bytes];
            for (NSUInteger i = 0; i < indexPath.length; ++i) {
                bytes[i] = flipNSUInteger(bytes[i]);
            }
            self.binaryIndexPath = [NSData dataWithBytesNoCopy:bytes
                                                        length:[indexPath length]*sizeof(NSUInteger)];
        } else {
            self.binaryIndexPath = nil;
        }
        [self setPrimitiveValue:indexPath forKey:@"indexPath"];
        [self didChangeValueForKey:@"indexPath"];
    }
}

Now, why do we need all that? because we like to sort our StepPlaceholders on the binaryIndexPath blob property.

For example, in your above use-case (suppose only one Step called S is populating the matrix) your index paths would be:

[S : (0)], [S : (1)], [S - (2)], [S - (3,0)], [S - (3,1)], [S - (4)]

The sort order would work like string sorting (MSB compare first).

All that is left to do now is fetch all StepPlaceholders attached to a given chain sorted on the binaryIndexPath property like so:

NSFetchRequest* r = [NSFetchRequest fetchRequestWithEntityName:@"StepPlaceholder"];
r.predicate = [NSPredicate predicateWithFormat:@"chain = %@",self.objectID];
r.relationshipKeyPathsForPrefetching = @[@"step"];
r.sortDescriptors = @[[NSSortDescriptor sortDescriptorWithKey:@"binaryIndexPath"
                                                    ascending:YES]];

The request is optimised to fetch the related Steps along with the placeholders.
I added it as a method on the Chain entity hence the self.objectID.
If this seems unstable for you to sort on a binary property you could also fetch the placeholders and sort them in-memory using the indexPath transient property (not to hard to accomplish).

And now we will produce the multi-dimension array on demand using a class method on Chain:
(along with some additions to NSArray)

static char const* const virtual_last_index_key = "virtual_last_index";
@interface NSArray (lastvirtualindex)
@property (nonatomic,assign) NSUInteger virtualLastIndex;
@end

@implementation NSArray (lastvirtualindex)
- (NSUInteger) virtualLastIndex
{
    return [objc_getAssociatedObject(self, virtual_last_index_key) unsignedIntegerValue];
}

- (void) setVirtualLastIndex:(NSUInteger)virtualLastIndex
{
    objc_setAssociatedObject(self, virtual_last_index_key, @(virtualLastIndex),OBJC_ASSOCIATION_RETAIN_NONATOMIC);
}
@end


+ (NSArray*) buildMultiDimArrayWithSortedPlaceholders:(NSArray*)placeholders
{
    NSMutableArray* map = [NSMutableArray new];
    for (StepPlaceholder* placeholder in placeholders) {
        NSMutableArray* currentMap = map;
        NSUInteger i = 0;
        NSUInteger length = [placeholder.binaryIndexPath length]/(sizeof(NSUInteger));
        const NSUInteger* indexes = [placeholder.binaryIndexPath bytes];
        for (;i < length-1; ++i) {
            if ([currentMap count] &&
                currentMap.virtualLastIndex == indexes[i] &&
                [[currentMap lastObject] isKindOfClass:[Step class]])
            {
                return nil;
            } else if ([currentMap count] == 0 || currentMap.virtualLastIndex != indexes[i]) {
                [currentMap addObject:[NSMutableArray new]];
            }
            currentMap.virtualLastIndex = indexes[i];
            currentMap = currentMap.lastObject;
        }
        [currentMap addObject:[placeholder step]];
        currentMap.virtualLastIndex = indexes[i];
    }
    return map;
}

You can now compose a transient property that IS a multi-dimensional array.

The algorithm is built so you don't have to have consecutive indexes for your objects only a monotonically increasing index path representation.

Disadvantages:
It is not easy to insert a step to an existing mapping (you will need to update the placeholders of all elements in the same array), due to the array data structure.

It is difficult to ensure Step uniqueness in this representation (but since this model must allow for duplications of Steps this should not be much of an issue).

you must bookkeep indexes. deletion of a Step or a StepPlaceholder without properly adjusting the indexes will create "holes" in the index continuity (1,2,7 instead of 1,2,3). the algorithm and representation will not be harmed by holes but its not pretty :)

Advantages:

A real multi-dimensional representation of the data.

Much easier to construct then the relational traversal.

Much more efficient (performance wise) then traversing a set object by object (or dimension by dimension) as other implementations does not have a direct link between Step and the Chain it belongs to, and faulting will occur more often.

Allow a step to be repeated in the same dimension/array.

Sample project could be found HERE

Answer 3

Please consider using CoreData relations, so Chain would have ordered relation to-many to the Step entity, which would have backward relation of type to-one to Chain entity.

Answer 4

How about this? Chain has one-to-many relationship to step entity (e.g. stepsOfChain <-->> chainOfStep), and step also has one-to-many relationship to itself (e.g. stepsOfStep <-->> stepOfStep). The later relationship opens the possibility for storing multiple steps in one entry of stepsOfChain field.

iOS CoreData inverse relationships to itself

Answer 5

my rough idea is that you'll want to create a property of type NSData which deserializes to a bunch of NSArrays of NSManagedObjectID or more arrays, in order to achieve the multidimensional array structure you're speaking of. admittedly this is a quick idea and bound to have edge cases and other issues that come with making a tool (CoreData) do something it wasn't build to do.

¡good luck! :)

Answer 6

In such scenario, i suggest you have a schema like below one.

StepArray is an abstarct entity.

According to your problem statement, A Chain can have 2 dimensional array of Step objects.A Step can be in multiple Chain objects.

My solution->
You want steps relation to hold both individual Step objects and arrays of Step objects.

Instead of storing like a two dimensional array ,i am storing individual store objects as steps and Step Array as stepArrays.Both are to-many relations.

A Chain object has many-to-many relation with Step object. So, this means you can add as many individual step objects to it. And as step object can be in multiple Chain objects, hence we used to-many relationship of chains from Step to Chain.

A StepArray object has to-many relationship named steps with Step Object.So, those Step objects that are in an array, i want them to store it in StepArray with steps relation.

Any as StepArray are unique then we have to-one relation named chain with Chain Entity.

Answer 7

It looks to me that a Chain can contain both Steps and other Chains (given that a Chain is just a collection of Steps). Is that fair to say?

If that is the case, then you could have a shared abstract entity as the parent, and then define the Chain as having a many-to-many relationship with the abstract entity, which could therefore be either a Step or a Chain (containing Steps).

Of course, whether that model works may depend on how you need to interact with the data.

Answer 8

Create three entities: Chain <-->> StepInChain -->> Step.

Then add a reflexive to-many relationship to StepInChain (i.e., a parent-child StepInChain <-->> StepInChain). You would use this reflexive relationship to represent nested arrays of steps in a chain. To maintain the order of steps you also need an integer index attribute in StepInChain.

Now a step can appear in multiple chains, in any order, and with arbitrary depth.

Note that I left out the reverse relationship from Step to StepInChain to highlight how it's detached from the representation of the chain.