what structure should I use? (Java programming)

My CS ethics professor taught us that we should go find help if we get stuck rather than waste time thinking in circles. So here I am. I’m helping my brother in IT (and starting my code portfolio) by writing a program that will sort out some files containing a user and what programs they have installed.

I wrote a program in C++ that reads a folder in the registry and outputs a file UserName.txt and then lists the programs they have installed.

Now, in java becuse is less of a bitch about file I/O than C++, I’m coding a program to read those files and re-sort it into one large output file with a list of ALL the installed software follwed by a comma seperated list of the users that have that software installed on thier computers. My code to read the files works, but I am having trouble finding and/or creating an appropriate structure to hold this data before it is written to the output file.

I have already tried creating a bastardized linked list with a Node class containing a string for the program name and a string array for the users.

I’ve found the structures in java.util inneffective because they appear to be intended to hold data of a single type NOT a class that contains more than one type of data.

I.E.: List.find(“somestringname”)

NOT List.find(MyDataObject.programName = “program”)

I need an alternative or a means of accessing the data in the second form. I need to be able to access the entire dataset by JUST the program name. I do not need to search by users, that can be handled earlier in the process.

Can anyone suggest any appropritate structure, syntax, or plan of attack??

If it matters I’m a CS major at Kent State. Thanks to high school AP testing into DataStructures, I’ve been in classes coving theory for almost two years instead of coding classes, I’m a bit rusty. This project is already GPL’d and free-as-in-beer because I had to read/alter some GPL’d code to understand how the registry reader works.

Let me see if I understand: you have a bunch of keys (program names), each with an associated value (list of userids). You want to do (fast?) lookups by for the values by the keys, and probably mutate the value to add a new userid.

The hard part is adding to the list of associated values on each pass. HashMap would mostly do what you want, but updating the list of userids associated to a program would be rather rude, something like:



HashMap hm = new HashMap();

while(/*There's still stuff to do*/)
{
   String nextProg = //Get the next program...
   String nextUser = //...and the associated userid

   ArrayList userids = (ArrayList)(hm.get(nextProg));
   userids.add(nextUser);
   hm.put(hm.remove(prog), userids);
}


…only with more typecasting.

Override the “equals” method in your node class.


class node {
     String programName;
     ArrayList userIds;
     boolean equals(Object n)  {
        node n1 = (Node) n;
        if (n.programName == programName) {
            return true;
       } else {
            return false;
       }
}


The linkedList class just searches through the objects until one returns true on their equals call (which is called implicitly whenever you do (Object1 == Object2) type stuff). You override equals, you get to specify what it means to be equal.

-lv

I would follow Taran’s approach: a single Map of many ArrayList objects, with the following tweaks:

Use a TreeMap for the main Map. That way, your programs are automatically sorted as they are added to the Map (if that’s useful).

For each new program+user, call get(program) on the Map. If no ArrayList is found, create one and add it to the Map using put(program, list).

Regardless, once you have a reference to a particular program’s ArrayList, just add the user to that list. The final line of Taran’s code is not necessary since a reference to the self-same ArrayList is already in the Map. It is now a simple exercise to loop through the neatly-sorted keys of the TreeMap, get their ArrayLists, and turn those lists into comma-delimited strings.

Pure genius. Thanks for the tips, I’ll be sure to give you credit for helping me in the readme and/or in my code comments.

Below is an implementation that I (coincidentally) wrote this morning. It wraps a HashMap of ArrayLists, and adds a few convenience methods. Might be of some use…



/**
 * Implements a HashMap of ArrayLists. An object can be added to the hmCategories and if
 * the category doesn't already exist then it will create it.
 */
public class CategoryMap
{

    // ---- Member Variables --------------------------------------------------
    HashMap hmCategories = new HashMap();
    
    // ---- Methods -----------------------------------------------------------
    /**
     * adds a given item to a given category
     *
     * @param category
     * @param item
     */
    public void add(Object category, Object item)
    {
        if (!hmCategories.containsKey(category))
        {
            List list = new ArrayList();
            hmCategories.put(category, list);
        }
        ((ArrayList)hmCategories.get(category)).add(item);
    }

    /**
     *
     * @param category
     * @return the list for a given category
     */
    public List get(Object category)
    {
        if (!hmCategories.containsKey(category))
        {
            return new ArrayList();
        }
        return (ArrayList)hmCategories.get(category);
    }

    /**
     *
     * @return the amount of categories in the hmCategories
     */
    public int size()
    {
        return hmCategories.size();
    }

    /**
     * @param category
     * @return the amount of items in a given category
     */
    public int size(Object category)
    {
        return ((ArrayList)hmCategories.get(category)).size();
    }

    /**
     *
     * @return a category iterator
     */
    public Iterator categoryIterator()
    {
        return hmCategories.keySet().iterator();
    }
}


You could change the underlying implementation to use a TreeMap if order is important. I might find myself doing that at a later date.
Remember, it is a first draft and usual disclaimers apply…

Fez.