Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm doing a java project. My main structure contains 2 lists with elements of type A the other type B. B itself contains a list of objects which may contain elements of A.

It must be that when an element from list of A is removed it must be removed from all subelements in list B. also if an possible member of list A is added to a B it should also be added to A. And also I need some way to find the parent objects containing an A.

So far I have a "working" implementation - using lots of loops. I am wondering - can you suggest patterns that will help me in this task?


more details.

I think my main issue is boils down to that i have objects A that have multiple parents. And when I add/remove from one parent I need to adjust some other parents.

I can't help but believe such a problem is solved already.


to clarify: I have a main List<A> , and each B contains a List<A>

When a A is removed from the main list it must be removed from all B. But not when it is removed from a B. It's essential that all A used in the application are present in the main list.

share|improve this question
    
I don't think this question can be answered as is. The solution will be very specific to the problem you are trying to solve. I suggest you to either give more details of how you want your structure to work (and that would be more a stackoverflow question), or show us your working implementation for a review (and that would belong to codereview.stackexchange.com). –  barjak Feb 18 '12 at 11:34
    
If "A" has multiple parents of class "B", doesn't that simply mean that "A" has a List<B> in it? Is that what you're looking for? –  S.Lott Feb 18 '12 at 13:15
    
Can you remove the A from any list or just from the main list? –  Sign Feb 18 '12 at 13:43
    
You can remove A from any list. –  bdecaf Feb 18 '12 at 14:14
    
@S.Lott I was considering that. But in this case I have the same problem - taking care that all is in sync when I remove a B –  bdecaf Feb 18 '12 at 14:18
add comment

4 Answers

up vote 2 down vote accepted

I don't think you need any particularly complex pattern for this. Looping through the structures and doing the obvious changes should work (assuming you don't have any concurrency issues)

Some ideas to consider:

  • Make the List<A> objects into a HashMap<A, Set<B>>, where the key is an object of type A and the value is a set of all parent B objects.
  • Then you can easily find all parents of a given A, and if you remove an instance of A then you can quickly find all the B objects that you also need to remove the instance of A from.
  • You will of course need to update this structure whenever you add an A to a B, but this is only an O(1) operation.
  • The B objects should have a remove(A a) function which encapsulates all the code required to remove a given A instance from the internal data structure. This should recursively call a similar remove function in any substructures.
share|improve this answer
add comment

You could do it with weak references. Wrap a List<WeakReference<A>> and and the wrapper has a reference to the master data structure(thinking a set but not sure) that keeps the real references to each A. When you delete from a wrapped structure you remove the weak reference and delete from the set, which should be the only real reference to each A. This has some problems with working with the lists due to having the weed out the dead weak references.

share|improve this answer
1  
+1 for the interesting idea to use weak references (although they can be a bit tricky to get right). To weed out the dead references you can just periodically scan the list. –  mikera Feb 18 '12 at 14:45
    
Great idea. I will try to incorporate it. Though I chose the other answer cause it was more practical for my case. –  bdecaf Feb 19 '12 at 8:41
add comment

for some strange reasone I cannot add comment under your question . So I am going to comment here . Please don't vote this down if you don't like it . I have no choice .

It seems this is very similar to problems in sql database. For example

create table A
(
    id int not null primary key,
    val varchar(20) not null
);

create table B (
    id int not null primary key,
    val varchar(20) not null
);

create table BA (
    b_id int not null ,
    a_id int not null,
    constraint ba_b_fk foreign key (b_id) references B(id),
    constraint ba_a_fk foreign key (a_id) references A(id) on delete CASCADE  ,
    constraint ba_pk primary key (b_id , a_id)
);

drop table ba;

insert a (id, val) values (1 , 'a1');
insert a (id, val) values (2 , 'a2');
insert a (id, val) values (3 , 'a3');
insert a (id, val) values (4 , 'a4');

insert b (id, val) values (1 , 'b1');
insert b (id, val) values (2 , 'b2');

insert ba (b_id , a_id) values (1 , 2);
insert ba (b_id , a_id) values (1 , 3);

delete a where a.id = 2

select * from ba;
--  only ( 1 , 3) left in ba

I am not familiar with java ( but i do work in C# ) . Anyway some pseudo code here that might help . I ran out of time to implement it . ( please note that ATable , BTable are singletons )

class RecA {
    public int id;
    public string val;
    public override bool Equal(object x) { ... }
    public override int GetHashCode() { return ... }
}
class RecB {
    public int id;
    public string b_val;
    public HashSet<A> listA;



}
class ATable extends HashSet<RecA> {

}

class BTable extends HashSet<RecB> {

    public static Dictionary<A, List<B>> dict = new Dictionary<A, List<B>>() ; // to track relationship between BTable and ATable
    public override void Add(RecB) {
    }

    public void addA_to_BTable(RecA) {
        // use the dictionary to track it
    }

    public void delete_A(RecA) {
    }
}
share|improve this answer
    
for some strange reasone I cannot add comment under your question This is because of your current reputation level :) –  James Poulson Feb 18 '12 at 15:27
    
this is an answer not a comment and is in the correct place, you don't put answers as comments just so they can't be downvoted, have confidence and put answers you feel add value, if others don't feel they are correct, you get to learn something as well. –  Jarrod Roberson Feb 18 '12 at 16:42
add comment

If your main list contains only A's that are in some B's, you can compute the main list from the B's you have. (You can later think about caching the main list.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.