Parse JSON to a tree structure

Question

I'm working on a project that requires a tableView list of categorized grocery items. Each category can have n depth. The JSON response from the API looks like this.

"items":[
{
  "id":"5366f8d3e4b0e44dc2d4a6fb",
  "name":"String Cheese"
  "description":"Sargento String Cheese",
  "categorization":[
    [
      "Dairy",
      "Cheese"
    ]
  ]
},
{
  "id":"5366f8d3e4b0e44dc2d1a6fb",
  "name":"Budlight 6-pk"
  "description":"Budlight 12-pk",
  "categorization":[
    [
      "Beverages",
      "Alcohol",
      "Beer"
    ]
  ]
}
]

Right now I'm creating Item objects from the item dictionaries and storing them in a mutable array like below.

NSArray *itemsArray = [response objectForKey:items];

NSMutableArray *itemsMutableArray = [[NSMutableArray alloc] init];
for(NSDictionary *itemDict in itemsArray){
    Item *itemObj = [[Item alloc] initWithDictionary:itemDict]
    [itemsMutableArray addObject:itemObj];
}

I would like to loop through itemsMutableArray and create a tree data structure that has a path from the root to each of the items. Then, I would like to be able to use the tree as a datasource for tableViews in each level of category.

Here's what my Item class header looks like.

@interface Item : NSObject

@property (nonatomic, strong) NSString *id;
@property (nonatomic, strong) NSString *name;
@property (nonatomic, strong) NSString *description;
@property (nonatomic, strong) NSArray  *categorization;

@end

...and the implementation

#import "Item.h"

@implementation Item

- (id)initWithDictionary:(NSDictionary *)objDictionary{
    if (self = [super init]) {
        self.id = [objDictionary valueForKey:@"id"];
        self.name = [objDictionary valueForKey:@"name"];
        self.description = [objDictionary valueForKey:@"description"];
        self.categorization = [objDictionary valueForKey:@"categorization"];
    }
    return self;
}

@end

I am not very familiar with tree data structures and recursion. I would greatly appreciate any help on how to approach this. Thanks!

Answer 1

If you need simple node tree data structure. How about this way? Hope this little help.

Header

@interface ItemCategory : NSObject

@property (nonatomic, strong) NSString *name;
@property (nonatomic) ItemCategory *parent;
@property (nonatomic, strong) NSMutableArray *children;

-(id)initWithName:(NSString *)n parent:(ItemCategory *)p;
@end

@interface CategoryTree : NSObject

@property (nonatomic, strong) ItemCategory *root;

-(ItemCategory *)_getChildCategory:(ItemCategory *)category name:(NSString *)name;
-(ItemCategory *)_addChildCategory:(ItemCategory *)category name:(NSString *)name;
-(void)_dumpCategory:(ItemCategory *)category depth:(int)depth;

-(void)dump;
-(ItemCategory *)getCategory:(NSArray *)arr;
-(void)addCategory:(NSArray *)arr;

@end

Source

@implementation CategoryTree
@synthesize root;

-(id)init {
    if (self = [super init]) {
        root = [[ItemCategory alloc] initWithName:@"root" parent:nil];
    }
    return self;
}

-(ItemCategory *)_getChildCategory:(ItemCategory *)category name:(NSString *)name {
    for (ItemCategory *child in category.children)
        if ([child.name isEqualToString:name])
            return child;

    return nil;
}

-(ItemCategory *)_addChildCategory:(ItemCategory *)category name:(NSString *)name {
    ItemCategory *child = [self _getChildCategory:category name:name];
    if (child)
        return child;
    child = [[ItemCategory alloc] initWithName:name parent:category];
    [category.children addObject:child];

    return child;
}

-(void)_dumpCategory:(ItemCategory *)category depth:(int)depth{
    NSString *parentStr = @"";
    ItemCategory *parent = category.parent;
    while (parent) {
        parentStr = [NSString stringWithFormat:@"%@%@%@", parent.name, parentStr.length > 0 ? @">" : @"", parentStr];
        parent = parent.parent;
    }
    NSLog(@"%@%@%@", parentStr, parentStr.length > 0 ? @">" : @"", category.name);

    for (ItemCategory *child in category.children) {

        [self _dumpCategory:child depth:depth + 1];
    }
}

-(void)dump {
    [self _dumpCategory:root depth:0];
}

-(ItemCategory *)getCategory:(NSArray *)arr {
    ItemCategory *category = root;
    for (NSString *categoryName in arr) {
        category = [self _getChildCategory:category name:categoryName];
        if (!category)
            return nil;
    }
    return category;
}

-(void)addCategory:(NSArray *)arr {
    if ([self getCategory:arr])
        return;

    ItemCategory *category = root;
    for (NSString *categoryName in arr) {
        ItemCategory *childCategory = [self _getChildCategory:category name:categoryName];
        if (!childCategory) {
            childCategory = [self _addChildCategory:category name:categoryName];
        }
        category = childCategory;
    }
}
@end

Usage

CategoryTree *tree = [[CategoryTree alloc] init];
[tree addCategory:@[@"Dairy", @"Cheese"]];
[tree addCategory:@[@"Dairy", @"Milk"]];
[tree addCategory:@[@"Beverages", @"Alcohol", @"Beer"]];
[tree addCategory:@[@"Beverages", @"Alcohol", @"Wine"]];
[tree addCategory:@[@"Beverages", @"Non-Alcohol", @"Cola"]];
[tree dump];

Result

root
root>Dairy
root>Dairy>Cheese
root>Dairy>Milk
root>Beverages
root>Beverages>Alcohol
root>Beverages>Alcohol>Beer
root>Beverages>Alcohol>Wine
root>Beverages>Non-Alcohol
root>Beverages>Non-Alcohol>Cola

Answer 2

well I have found a way to implement what you need. I do not know how optimised it is since i do not how many items you'll be receiving . The implementation is given below.

You need to start with adding this dictionary in Item.h @property (nonatomic, strong) NSMutableDictionary *catTree;

Next do this to get the tree

[itemsMutableArray enumerateObjectsUsingBlock:^(Item *itm, NSUInteger i,BOOL *stop){
        itm.catTree = [NSMutableDictionary dictionary];
        NSString *dairy = @"",*beverage = @"";
        for (NSArray *catArray in itm.categorization) {
            /*
                Everything below is written assuming the format of the JSON will be "as-is"
             */

            if ([catArray containsObject:@"Dairy"]) {
                //Take everything except Dairy
                NSArray *stripedArray = [catArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"SELF != \"Dairy\""]];
                int i = 0;
                //Loop through the array to get any sub categories.
                while (i < stripedArray.count) {
                    dairy = [dairy stringByAppendingString:[NSString stringWithFormat:(i == stripedArray.count-1)?@"%@ ":@"%@->",stripedArray[i]]]; //Space at the end to account for similar entry in the same category for e.g two dairy products.
                    i++;
                }
            } else  if ([catArray containsObject:@"Beverages"]) {
                NSArray *stripedArray = [catArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"SELF != \"Beverages\""]];
                int i = 0;
                while (i < stripedArray.count) {
                    beverage = [beverage stringByAppendingString:[NSString stringWithFormat:(i == stripedArray.count-1)?@"%@ ":@"%@->",stripedArray[i]]];
                    i++;
                }
            }
        }


        //Set the category tree for every item using a dictionary
        [itm.catTree setValue:dairy forKey:@"Dairy"];
        [itm.catTree setValue:beverage forKey:@"Beverage"];

        NSLog(@"%@",itm.catTree);
    }];

the above code gives the following output for your json

{
    Beverage = "";
    Dairy = "Cheese ";
}
{
    Beverage = "Alcohol->Beer ";
    Dairy = "";
}

For multiple beverages

{
   Beverage = "Alcohol->Beer Alcohol->Wine->Red Soda->Coke ";
   Dairy = "";
}

Hope this helps.