current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

Is there a better approach to do the below in Java, without using external libraries.

I need to model group/child (tree like) structure of int (primitive). In Json

[{1,1}, {1,2}, {2,1},{3,1}]

I need to support addition/removal of elements (element is a pair {group, child} ) without duplication.

I am thinking of, keeping a data structure like.

ArrayList<HashMap<Integer,Integer>>

To add.

Iterate through ArrayList, check HashMap key and value against the value to insert, and insert if not exist.

To delete:

Iterate through ArrayList, check HashMap key and value against the value to delete, and delete if exist.

Is there a better data structure/approach with standard library.

As per one of the answer below, I made a class like this. Please let me know anything to watchout. I am expecting (and going to try out) arraylist would handle add/remove correctly by using the equal method in KeyValue class. thanks.

 static class KeyValue {
        int groupPos;
        int childPos;

        KeyValue(int groupPos, int childPos) {
            this.groupPos = groupPos;
            this.childPos = childPos;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            KeyValue keyValue = (KeyValue) o;

            if (childPos != keyValue.childPos) return false;
            if (groupPos != keyValue.groupPos) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = groupPos;
            result = 31 * result + childPos;
            return result;
        }
    }
share|improve this question
    
In response to edit - Set (e.g. TreeSet (requires your class to extend java.lang.Comparable or a Comparator class given as input) / HashSet) would handle add/remove operations more efficiently than ArrayList. –  Dukeling Feb 7 '13 at 17:37
    
in equals() instead of if (o == null || getClass() != o.getClass()) return false; use if(! (o instanceof KeyValue)) return false; –  Bimalesh Jha Feb 7 '13 at 17:41

5 Answers 5

up vote 2 down vote accepted

If I understand what you're trying to do, this may be simpler:

TreeMap<Integer,TreeSet<Integer>>
  or
HashMap<Integer,HashSet<Integer>>

So, rather than

[{1,1}, {1,2}, {2,1}, {3,1}]

you'd have

[{1, {1, 2}},
 {2, {1}},
 {3, {1}}]

Note that all 4 of the above classes automatically handles eliminating duplicates.

To add:

TreeMap<Integer, TreeSet<Integer>> map;
TreeSet<Integer> set = map.get(group);
if (set == null) // create it if it doesn't exist
{
  set = new TreeSet<Integer>();
  map.put(group, set);
}
set.add(child);

To remove:

TreeMap<Integer, TreeSet<Integer>> map;
TreeSet<Integer> set = map.get(group);
set.remove(child);
if (set.isEmpty()) // remove it if it is now empty
  map.remove(group);
share|improve this answer
    
thanks. I didn't do much Java, so never heard TreeMap and TreeSet. Will checkout. THanks –  bsr Feb 7 '13 at 17:16
    
+1 thanks for the implementation. I like this approach. Will accept after test it. thanks again –  bsr Feb 7 '13 at 17:51
up vote 1 down vote

You may write a class with name KeyValue with two properties to hold group and child. Add KeyValue Objects to ArrayList. For CRUD operations, you may implement equals and compare in your KeyValue pair class.

share|improve this answer
    
hashCode() should also be implemented when equals() is overridden. –  Bimalesh Jha Feb 7 '13 at 17:24
    
A more efficient implementation would be to use Set<KeyValue> (e.g. HashSet<KeyValue> or TreeSet<KeyValue>) instead of ArrayList<KeyValue>. –  Dukeling Feb 7 '13 at 17:30
    
thanks. please see my edit and let me know what u think. –  bsr Feb 7 '13 at 17:34
up vote 0 down vote

Instead of HashMap, use a class called Pair with two fields {group,child} which will implement Comparable interface. Then implement/override its equals(), hashCode() and compareTo() methods. Then use either a List<Pair> or Set<Pair> depending on your needs to hold them. Having compareTo() implemented gives you the flexibility to sort Pairs easily too.

share|improve this answer
up vote 0 down vote

I am new to the Data Structure world but I think we can use this based on the assumption that no two Set Objects will be similar

Set validSet=new HashSet(); // Use Generics here

HashSet will provide a constant time for add/delete/contains

SomeObject{
     Integer parent ;
     Integer child;
     //define equals method based on your requirement
}
share|improve this answer
up vote 0 down vote

Going By your Question i think that You want to show this line 

[{1,1}, {1,2}, {2,1},{3,1}]

as

Group 1-> 1 , 2 (from first two pair)
Group 2-> 1(from third pair)
Group 3-> 1 (from fourth pair)

The data structure that suites most for storing this hierarchy is : 

Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>();

Where the key part of map stores the group Number. And the value part of map is storing TreeSet which stores the children of that group.
As Example of code:

import java.util.HashMap;
import java.util.ListIterator;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class  TreeLike
{
    public static void main(String[] args) 
    {
        Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>();
        int groups[] = {1,2,3,4,5,6,7};
        //To add new group in map
        for (int i = 0 ; i < groups.length; i++)
        {
            Set<Integer> child = new TreeSet<Integer>();
            child.add(1);child.add(2);child.add(3);child.add(4);child.add(5);
            map.put(groups[i],child);
        }
        //To add new child(8) to a group (say group 1)
        Set<Integer> child = map.get(1);
        if (child != null)
        {
            child.add(8);
            map.put(1,child);
        }

        //To remove a child (say child 4) from group 3
        child = map.get(3);
        if (child != null)
        {
            child.remove(4);
            map.put(1,child);
        }
        //To Iterate through all trees
        Set<Map.Entry<Integer,Set<Integer>>> entrySet = map.entrySet();
        Iterator<Map.Entry<Integer,Set<Integer>>> iterator = entrySet.iterator();
        while (iterator.hasNext())
        {
            Map.Entry<Integer,Set<Integer>> entry = iterator.next();
            int group = entry.getKey();
            Set<Integer> children = entry.getValue();
            System.out.println("Group "+group+" children-->"+children);
        }
    }
}
share|improve this answer

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.