The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Object reference loops

I'm trying to design the objects for a new application. I'm running into the problem that the natual design that pops into my head seems to involve a circular refence between objects.
The two objects involved are items and shelves. Every item is on exactly one shelf, but each shelf may have many items. Given a shelf object, I need to be able to easily find out which items are on that shelf. And given an item object, I need to be able to easily find the shelf that it's on.
The obvious thing (to me) is that each shelf object contain a list of item objects (or references/pointers thereto) for the items on that shelf. And every item object contain a shelf object (or reference/pointer thereto) for the shelf it's on. But this is circular: the shelf points to the item which points to the shelf which points to the item, etc., etc., etc.
My first question is, is this really bad? It intuitively feels bad to me. But it also feels like the most natual solution to the problem in real world terms.
If it is bad, is there a common pattern that can be used as an alternative. I would really like to avoid doing something like storing a "shelf ID" in the object and then having to go somewhere else to lookup what that shelf ID actually refers to (and it seems like that would only mask the problem anyway).

Wednesday, August 24, 2005
"My first question is, is this really bad?"

Not really; I think it's quite common.

"It intuitively feels bad to me."

Why?  The only way to have a bidirectional linking between shelves and items is to do this way.

The only problem you'll have with circular references is if you're developing for a platform that reference counts objects (like VB).  Even then, there are solutions to that problem as well -- you just have to be a bit more explicit about cleaning up.
Almost H. Anonymous Send private email
Wednesday, August 24, 2005
In OO this is perfectly normal, in my opinion.  If you are thinking of how this gets stored in a relation DB, then you would not want x-refs in each table.  You would either give a book a shelf ID or keep a bookID<->shelfID table. 

What language are you doing this in -- do you have garbage collection or refcounts.  With refcounted systems, you sometimes have to worry that circular refs will never be freed because there is always a reference out there.  Garbage collectors deal with this.
Lou Franco Send private email
Wednesday, August 24, 2005
> I'm running into the problem that the natual design
> that pops into my head seems to involve a circular
> refence between objects.

I think it's fine. Life is circular. For all the reasons usually site you shouldn't be circular unless you need to, but if that's the best design then don't let the zealots scare you off.
son of parnas
Wednesday, August 24, 2005
Not ok. In general, strong entities (those that can exist independent of other entities in the system) should not depend on other entities.

Association between strong entities should be implemented by association classes that refer to all association members.

Item sits on shelf. Item can exist without shelf.
Shelf holds items. Shelf can exist without items.

!!!! Item does not have shelf. Shelf does not have items!!!

The item and the shelf are associated for a limited time in the Item/Shelf relationship. That relationship may have extra attributes that are meaningful only withtin the association context, e.g. an inventory tag which details when the item was stored, by whom, etc.

This should be modelled as:
StorageRecord {
  Shelf storageShelf;
  Item storedItem;
  Timestamp dateStored;
  String storedBy;

That makes the Item and Shelf independent, as they should be as strong entities. Dependecies are resolved by the association class StorageRecord, which is a weak entity since it cannot exist without either a shelf or an item. Referrential integriy is inforced at construction time.

The dependecy graph should always be a DAG (direct acyclical graph, ie no loops). Non-dag depdencies result in fragile software which is expensive to maintain.
Dino Send private email
Wednesday, August 24, 2005
Lists of items can be empty, references to shelves can be null.  In the real world items and shelves can exist without each other, but in software sometimes they can't.  It's a tradeoff that you have to make based on what you are doing, but it's not automatic that circular references are bad in OO.  I think in relational space, I feel differently -- there's a tradition in the x-ref table and plenty of support in SQL and tools that it's a natural way to go.
Louis Franco Send private email
Wednesday, August 24, 2005
If you are using C++, already has a solution for this.  At least, I think the solution would work for you; it worked for me in a similar circumstance.  Check it out:
Chris in Edmonton Send private email
Wednesday, August 24, 2005
This is perfectly fine IMHO, although you may run into the reference counting problem metntioned by others.  One other problem that you may encounter is a consistency problem.  Without putting in some extra code to ensure consistency, you could easily wind up in a situation where a Shelf thinks it contains a certain item, but the Item thinks it's on a different Shelf.  You should probably include some code in whatever methods maintain the Shelf/Item relationship to enforce this kind of consistency rule...
Wednesday, August 24, 2005
It's a very common construct in OO programming.  The trick is when you're storing those items in a database.  When you get the shelf out, you have to get its items out, but when you get an item out, you also have to get its shelf.  If you're not careful, you can end up with recursion and run out of stack space.

The way to avoid this is to have an object map of some sort, so that when you're loading a given object (based on its key in the database, probably) you first look for it in the object map, and then get it from the database (and put it in the object map) if it's not there.

Martin Fowler's _Patterns of Enterprise Architecture_ is an excellent reference on these types of OO constructs.  You might also look into object-relational mapping software, which is intended to automatically handle a lot of these problems.
Kyralessa Send private email
Wednesday, August 24, 2005
While I don't think circular references are usually problems in the abstract, I'd think items shouldn't have references to their shelves. Conceptually, shelves contain items; that's their job. But I don't think it's a part of an item's definition on what shelf it lies on.

Now, I do think you can memoize ("cache") a lookup, so when you want to know what shelf some book's sitting on, it might pull it out of a table rather than search through some list of shelves.

Of course, it's up to you.
Tayssir John Gabbour Send private email
Wednesday, August 24, 2005
When I said "it might pull it out of a table," I meant a hashtable or whatever else provides better performance than a search through shelves.
Tayssir John Gabbour Send private email
Wednesday, August 24, 2005
though on first thought you might want to be able to know which shelf the item is on from the item itself, how did you get the item in the first place?

you could find an item by going to each shelf and searching it, or by going to a master index of all items - which could include information about what shelf it's on.

from a relational DB point of view each item would know where it is because it can only be in one spot, and DB's don't handle dynamic lists of things well in 1 row.
from general programing point of view, you don't want to search all books to find just the ones on a specific shelf, so you make a shelf store links to just the items it contains.

talking about how to store things without knowing the interface for accessing them is all just hypothetical

Wednesday, August 24, 2005
It's OK - it is not really circular, it's just a bi-directional hierarchical relationship.

It can be made really neat, as long as you put a clear distinction between "contains" and "refers". (Strong and weak links, in other terms.) E.g., if the shelf "contains" an object, it's the shelf's responsibility to keep track of it, include and exclude it in its list of on-shelf objects, but it's then not the object's responsibility to keep track of whether it is included in the shelf's list, and its "shelf" reference should be assigned by the shelf, never by the object itself. This way, the bi-directional relationship is not symmetrical: the shelf has a strong grasp on the object, but the object merely is informed on which shelf it is. As long as the responsibilities of who assigns objects to shelves are made clear, you won't have problems with it.
Thursday, August 25, 2005
I agree with the poster who said that items shouldn't know about what shelves they are on. In a world that consists solely of shelves and items this might need to be case, however shift your worldview. There is nothing wrong with introducing the concept of an "inventory" - this is how a shop might operate afterall.

I maintain another datastructure which mapped item to shelf. It's not masking the problem imho, it's creating a more elegant solution.
Adrian Send private email
Friday, August 26, 2005
I just made the same design (mine were build targets and their dependencies). It's a legit design (hey lots of things know who their parents are). Make sure you really need the children's references to their parents however (I needed them in my design because the parents were observers of the children).

The main problems you'll run into with this design are upon construction/destruction. As thoroughly explained above, if you have some sort of automatic object construction, you need to know what's going to ensure you don't load the whole tree when you don't want to. On the destruction end, reference counting memory management needs to be handled delicately. Most garabage collectors say they can handle orphan refrence cycles. I didn't fully trust mine so I put a few lines of code where destruction of the child implies nulling the parent reference, and destruction of the parent implies destruction of the children. Better safe than sorry.
YaYaYa Send private email
Friday, August 26, 2005
You could even go so far as to follow say the model applied to eclipse and it's plugins such that the objects need to manage their own registration/dergistration of wanting to be told about certain things.

On construction a view registers that it wants to be told when the selected document changes. It could also register as a provider of change information and notify everybody else if the document needs to be changed.

Sunday, August 28, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz