macOS Simple Porting of Java to Objective C (Cocoa)

[Amigalander]

Back in college, I wrote a short Java command-line utility that would solve the classic slider puzzle (8 tiles and an empty space). I've recently started learning Objective C and Cocoa and would like to port over my code. This is how it starts in Java:

import java.util.TreeMap;
import java.util.LinkedList;

public class PuzzleBoard
{
	private String gameState;
	private final String GOAL = "123456780";
	LinkedList queue;
	TreeMap marked;
...

Just beginning the port, I've already run into many hurdles...

1) what's the equivalent or alternative to the Java TreeMap in Obj C?
2) what's the equivalent or alternative to the Java LinkedList in Obj C? (I think I can use an NSMutableArray for that, right?)
3) Can you declare constants in a header file in Obj C? If not, where?

Any guidance or help would be appreciated

 

[HiRez]

I've forgotten most of what I ever knew about Java (and it's totally different now than in the early days anyway), but you'd probably want to look at NSTreeController. Objective-C doesn't have a linked list class, although you could make do with NSMutableArray and just add next/previous pointers to your content class (if you need those).

For creating constants, normally I just use a #define preprocessor macro in my implementation file (but at the top, outside of the @implementation/@end block):

#define TWELVE 12

Be sure not to put a semicolon at the end of preprocessor statement lines (unless you want one as part of your macro). If you create these in your project's prefix file, they'll automatically be available to all source files in the project. String constants are created automatically when you assign using the @"" construct:

#define MY_CONST_STRING @"My constant string"

or in the implementation code:

myConstString = @"My constant string";

But note in this case you have to first declare the string in your header file and then assign it in your implementation. Also, in this case it's a constant but there is no "final" about it...it can simply be reassigned as any other variable can be.

 

[Guiyon]

1) what's the equivalent or alternative to the Java TreeMap in Obj C?
2) what's the equivalent or alternative to the Java LinkedList in Obj C? (I think I can use an NSMutableArray for that, right?)
3) Can you declare constants in a header file in Obj C? If not, where?

Any guidance or help would be appreciated

For basic usages, the NSDictionary/NSMutableDictionary (depending on your use) would map over to the java.util.Map and NSArray/NSMutableArray could be used in place of java.util.List. The classes do not map onto each other perfectly but for most purposes they should be fine. As the constants, they can be defined anywhere using a #define statement but the generally acceptable place is in the header file or at the top of the implementation file they are used in. If you want to be REALLY paranoid you can also wrap each define with a #ifndef ... #endif block. #define statements are simply directives to the preprocessor to go through and replace all instances of the define's usage with its value before running the code through the compiler. For example:

#define FOO @"bar"
NSLog( FOO );

will be converted to:

NSLog( @"bar" );

and THEN compiled. This also means that using #defines like you would final variables is out; everything has to have a value when the pre-processor runs (doesn't necessarily have to be a VALID value, though)

Edit:
You could also use the const keyword to get a bit more flexibility; this has a couple caveats of it's own though; for example, there are ways to get around it without the compiler screaming at you.

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char **argv ) {
	const int ci = 427;
	const int *ciptr;
	int *iptr;
	int i = 724;
	
	ciptr = &ci;
	iptr = &i;
	
	/* Is a BAD thing but can be done */
	iptr = (int*)ciptr;
	
	/* Now we can get valid, but undefined behavior */
	*iptr = 0;
	
	return 0;
}

 

[kainjow]

Constants are VERY different from Java, however; they don't really exist.

What about const?

 

[Catfish_Man]

There's no built in Sorted Map I'm aware of. You could use the STL one via ObjC++ I suppose. NSMutableArray will work fine for a list. For constants, either #define or declare static const variables.

 

[MacRumors Guy]

If you use STL's map (it is implemented as a tree) as instance data you need to add the -fobjc-call-cxx-cdtors flag.

EDIT: If you want to avoid the C++ mess you migth consider using the glib library which has a balanced tree implementation. The implementation won't retain and release the objects for you.

 

[Guiyon]

What about const?

Heh, you're right; completely slipped my mind. I usually use the two in very different manners so I didn't really make the connection.

 

[lee1210]

I'm just curious about the data structures in use. Were they picked because of guarantees about access time, etc. or were they picked because they provided functionality that is needed?

What's nice about a balanced tree is that it is very fast to access elements. It can be very slow to insert elements, however, so if you are inserting all of your data at once, then accessing it very many times, this is a good data structure to use. If you will be making frequent modifications, however, it may not be the best due to amortized-N complexity of inserts/deletes.

As for the linked list... that seems to just be a stand in for any dynamic data structure, as any algorithm that can be applied to a (singly) linked list can be used against any data structure over which a forward iterator is available.

If you just love those data structures, you might have a hard time finding matches in the current Foundation and Cocoa libraries. However, if you just need the same functionality these are easily substituted with NSMutableArray and NSMutableDictionary as Guiyon pointed out. In the absence of a perfect hash, access to an NSMutableDictionary will vary based on the means that collisions are handled, but it is likely to be very similar to access to a binary tree. If you are looking for a guarantee of performance, however, you may be out of luck.

http://developer.apple.com/document...ableDictionary_Class/Reference/Reference.html
Check out this reference to see what is supported by an NSMutableDictionary, and compare to http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeMap.html
for the TreeMap. Chances are unless you are using an odd algorithm that depends very specifically on the structure of the tree, you can adapt it to use the dictionary instead, without much (or any) loss of performance.

Since this is a toy program, it seems like the idea is just to try out an algorithm, and perhaps explore some data structures. As such, it would be best for you to try to adapt what you did before to the "standard" Cocoa data structures rather than try to bend Objective-C/Cocoa to match the behavior of the Java data structures you used previously.

-Lee

 

[Amigalander]

Thanks a ton for the suggestions! As far as the data structures, they were chosen for functionality and simplicity. The amount of data is small, so access time is not a concern.

I used a LinkedList because items were being inserted at the end of the list and removed from the front of the list. I chose NSMutableArray to mimic this behavior as so:

queue = [[NSMutableArray alloc] init];

//pop item as if off a stack:
gameState = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];

//add item to end of list:
[queue insertObject:work atIndex:[queue count]];

The Java Tree was being used to store branches of game states and their derivatives. I'm trying to use NSMutableDictionary for this, but I'm not sure yet if this tree-like operation is going to work.

On a more general not, in porting over this simple app, it seems to me that Java is more readable, clean, and elegant than Obj C is. The same routines seem to need more lines in Obj C to duplicate the functionality in Java. I'm hoping this is because I'm a beginner at Obj C. However, I was a beginner at Java too at the time.

 

[lee1210]

You might want to explain the algorithm a little more, and we might have suggestions of what data structures can be used to implement it. Was the root node of your tree the goal game state? The starting game state? What are the roots? One per valid move? Do you stop generating nodes when a particular state is reached or a cycle in the tree is detected? What are the keys? A string indicating game state? What is the value? A "desirability" rating? Something else? Are you trying to find ANY solution, or the optimal (fewest moves) solution?

One reason you may be seeing "more code" at this point (which isn't always worse) is that you are, as you said, trying to port something. It may be that you will end up with less code if you step back to the level of the algorithm you are trying to implement, and play to Objective-Cs strengths rather than trying to play to java's strengths in objective-c, since you wrote this in java already. It may be the case that since Java has such an extensive library of objects, utilities, etc. that you don't have to write as much code to solve this because a lot of the supporting code was already written for you. In the general case, however, i don't think that Objective-C is more verbose than Java.

Readable is subjective, and you are coming from a place where Java is more familiar to you than Objective-C.

Clean is somewhat subjective, and you may be writing less clean code in Objective-C than you did in Java for various reasons.

Elegant is subjective, and if you are gunning for elegant code before you have a working solution, you are approaching the problem wrong.

I consider the three things you detailed above, along with memory use, and runtime, all things that should be optimized after you've successfully implemented your algorithm. Obviously poor design decisions can be made early on, before you have a working solution, and this can be difficult to correct later on. However, premature optimization can lead to more bugs that you have to spend a significant time correcting later.

Give us some more information and we'll try to point you in the right direction in terms of design and data structures to use (and how).

-Lee

 

[Amigalander]

Lee, you bring up excellent points. I believe the exercise was designed by the instructor with a Java solution preconceived. That's probably why my porting to Obj C isn't "clean" or "elegant." Also, I can't "think" in Obj C, at least not yet, like I used to be able to "think" in Java or even C++ many years ago.

The algorithm works by taking the starting state, for example, "120453786," checking it against GOAL ("123456780"), and inserting it in the tree. The tree stores checked states, starting with the startstate as the root, like this in my Obj C port:

//the start state has no parent (null)

[marked setObject:[NSNull null] forKey:startState];

Just to clarify, "120453786" physically represents this:

|―――――――――――|
| 1 | 2 |   |
|―――|―――|―――|
| 4 | 5 | 3 |
|―――|―――|―――|
| 7 | 8 | 6 |
|―――――――――――|

The slide() method then creates all possible moves. So for example, from the above you can slide the "2" tile to the right to make "102453786" or you can slide the "3" tile up to make "123450786." Those 2 derived states are checked against the tree to verify they are actually new and not repeats. Then they're put into the queue to be later used to make new derived states from. Like this in my Obj C port:

if([marked objectForKey:work] == nil)   //means does not exist in tree
  {
    [queue addObject:work];      //inserts object at end
    [marked setObject:gameState forKey:work];
  }

So the 2 new items for the tree are the 2 new derives states ("102453786" and "123450786") as keys with the originating state as the value ("120453786"). I think. This is where I'm somewhat confused. I'm actually not sure why a Tree was used in Java.

Anyways, here's one of the Java methods which explains the purpose of the data structures.

//**************************************************************************\\
//***  Uses breadth first search method to find the GOAL game state.     ***\\
//***  Any game state in the tree has been checked already, while the    ***\\
//***  states in the LinkedList (queue) represent our "frontier."        ***\\
//**************************************************************************\\
public String solve()
{
  queue.addLast(startState);                             //begin the "frontier"
  marked.put(startState, null);          //the start state has no parent (null)
  while(!queue.isEmpty())
  {
    gameState = (String)queue.removeFirst();
    if(gameState.equals(GOAL))  return "Solution is " + makeSolution();
    slide();                        //make the new game states by moving tiles
  }
  return "Solution is impossible!";       //the queue is empty; GOAL not found
}

Once the GOAL is found, then makeSolution() comes into play. And that's where the Tree(?) is used to follow a sequence of game states that lead from start to GOAL to provide the solution.

 

[lee1210]

i won't say that this is the most ideal solution to this, but you could build an NSMutableDictionary that uses an NSString with the board state as its keys and an NSArray that contains a derived type that has the tile to be moved (its direction is implicit) and an NSString of the resulting game state. The length of the NSArray is the number of valid moves (2,3, or 4). You could then approach the problem in about the same way, checking if a game state is already in the dictionary with

NSString *state = @"021437658";
NSArray *validMoves = [boardStates objectForKey:state];
if(validMoves == nil) {
  //New board state, add it
} else {
  //Board state already exists
}

You may be able to simplify this and avoid using a new class by simply storing NSNumbers with the tile numbers to be moved in your NSArray that is the value in your NSMutableDictionary. It should be easy to just calculate the new board state based on the number (just swapping 0 and the number chosen).

I am sort of curious to implement this now, but may not get a chance to in the next few days.

-Lee

Edit: I just realized that this idea doesn't give you "links" from one state to another, so it probably doesn't work out. Using derived types it would be easier to keep a link to the "parent" board so once you found the goal you could walk back up to find the moves made.

 

[Krevnik]

So the 2 new items for the tree are the 2 new derives states ("102453786" and "123450786") as keys with the originating state as the value ("120453786"). I think. This is where I'm somewhat confused. I'm actually not sure why a Tree was used in Java.

TreeMap is used in this case simply because it is an easy dictionary object with good performance on a large number of objects. NSMutableDictionary is the closest match to TreeMap for the purposes of this algorithm. One thing to note about the core data types in CoreFoundation/AppKit is that the back-end implementation is different depending on the size of the data set. They provide classes based on the relationships of data, not the implementation (like C++ and Java do).

From what I can tell, the idea is that you give it a key (the board state), and it gives back a list of derivative values. This makes sense since any time you get back to state A, the derivatives are the same. Use an NSMutableDictionary and you should be fine.

EDIT: I reread the post, and the object value is the parent. This makes perfect sense now.

NSMutableDictionary contains a list of possible board states. The key is a state, and the value is the previous state. The algorithm is basically a search from the top node of a tree, to the bottom, keeping track of only the optimal paths between the various states (since you only add a particular key once, the first time you put it in, the fastest route has been found). The linked list is used to queue board states to visit.

- Queue Initial State
- Add Initial state into dictionary, with a null value.
- Start Loop:
- Dequeue a state
- Is state our goal? If so, we have a solution.
- Calculate each derivative state and do the following if state is not in the dictionary:
- Queue derivative state
- Add derivative state to dictionary, with currently dequeued state as the value.

The core idea is that because you are doing a exhaustive search of a tree, level-by-level, the first time you discover a particular state, that is the fastest way from the initial game state, to that state. Any states you run into later are slower, and ignored. So by walking this dictionary (not really a tree, just a series of references in an array) backwards, you have the fastest possible solution.

 

[Amigalander]

Ah, nice. Thank you for that explanation. So since each entry in the dictionary has an object value which is actually the value of it's "parent" game board, connections can be made between them all like a tree. And it happens to also be the shortest possible connection because the tree was built by checking all possible derivative states, and once a goal is found, it was found using the most direct path. I think

I have my text version working now!!! (using NSLog for output). Thank you!

Now I'd like to expand on this and make a GUI

 

[Krevnik]

You can jump around like a tree, but really it boils down to a hash table of some kind. The internal implementation (TreeMap, HashMap, etc) is just a matter of taste and performance.

Since the algorithm only records the parent (specifically, the parent closest to the initial state), by walking back from the solution, you are guaranteed to have the shortest, most direct route from the initial state to the solution.

Rather clever, and ingenious algorithm, but if I was the professor, I would have tried to do a better job of describing the logic in the algorithm.

 

[Amigalander]

He probably did describe it, but it was many years ago. I've been out of practice since then, so I've forgotten most. In my app comments, I mentioned it was using a breadth first search, but I can't completely remember what that is.

 

[Krevnik]

He probably did describe it, but it was many years ago. I've been out of practice since then, so I've forgotten most. In my app comments, I mentioned it was using a breadth first search, but I can't completely remember what that is.

Search from the root node of a tree to the leaves, searching each level completely before moving onto the next.

In this particular implementation that you have though, there are a lot of shortcuts that make it a little murky for someone coming at this fresh after a few years. But yes, it is a breadth-first search, despite not actually having a tree data set being searched.