B&S: findByCriteria - pls review

[Derek Canaan]

Hi,
Could someone please review if the following code is ok:

    /*-----------------------findByCriteria------------------------*/
    public long[] findByCriteria(String[] criteria) {
        // Is synch necessary or Set s = new HashSet(); will do?
        // Or would arraylist be faster?
        Set matchList = Collections.synchronizedSet(new HashSet());
        
        // should i validateArguments of criteria here?
        
        // Loop thru criteria[]
        for (int recNo = 1; recNo <= cacheDB.size(); recNo++) {
            boolean found = false;
            Contractor contractor = getContractor(recNo);
            if (contractor.isDeleted() == true) {
                continue; // go to next iteration of recNo-for loop
            } else {
                for (int fieldColumn = 0; 
                        fieldColumn < criteria.length; 
                        fieldColumn++) {
                    String searchValue = criteria[fieldColumn];
                    String fieldColumnValue 
                        = contractor.getFieldValues()[fieldColumn];
                    
                    // If first condition of OR is true, second 
                    // condition is not evaluated
                    // hence in case where searchValue == null,
                    // fieldColumnValue.startsWith(null) is not 
                    // evaluated, otherwise NullPointerException 
                    // is thrown
                    if ((searchValue == null) 
                            || (fieldColumnValue.startsWith(
                                    searchValue))) {
                        found = true;
                    } else {
                        found = false;
                        // no match, hence no need to go on with the 
                        // next column of this recNo. Halts execution
                        // of inner fieldColumn-for loop, and go to the 
                        // next recNo
                        break; 
                    }
                }
                if (found) {
                    matchList.add(new Integer(recNo));
                }
            }
        }
        
        // translate matchList set to arrays of long recNo
        long[] retVal = new long[matchList.size()];
        Iterator it = matchList.iterator();
        int index = 0;
        while (it.hasNext()) {
            retVal[index] = ((Integer)it.next()).intValue();
            index++;
        }
        return retVal;
    }

Q1. Is the code correct? Does it fulfill

// Returns an array of record numbers that match the specified
// criteria. Field n in the database file is described by
// criteria[n]. A null value in criteria[n] matches any field
// value. A non-null value in criteria[n] matches any field
// value that begins with criteria[n]. (For example, "Fred"
// matches "Fred" or "Freddy".)

Did i miss anything?
Q2. Initially a collection type is used to store matching record number. It would be nice to put the matched record number straight into array of long and return that at the end of method. But apriori, we do not know how big the array of long should be initialized to. What type of collection should i use? Set, ArrayList?
Q3. Should the Collection type be synchronized as in code? Is it necessary?
Q4a. Should i validate the criteria argument that it should have the correct number of fields? For B&S, it should have 6 (name, location, specialties, size, rate, and owner).
Q4b. If validate is necessary, the validateArgument method throws a subclass of Runtime exception, but the findByCriteria signature does not throw any exception. In this case, i will not change the signature, but document the possibility of this exception being thrown in javadoc. Is this ok?
Q5. Should i add the synchronized modifier to the findByCriteria method or should i synchronize on the cacheDB mutex?
Thanks in advance,
Derek

[Philippe Maquet]

Hi Derek,
I'll start with your questions and finish with your code excerpt.

Q2. Initially a collection type is used to store matching record number. It would be nice to put the matched record number straight into array of long and return that at the end of method. But apriori, we do not know how big the array of long should be initialized to. What type of collection should i use? Set, ArrayList?

It's OK. But I wouldn't use a Set in this case as your algorithm ensures that you'll never get duplicates. I'd use a HashMap instead of a HashSet, to avoid a useless overhead. ArrayList doesn't suit well for your purpose, IMO.

Q3. Should the Collection type be synchronized as in code? Is it necessary?

No because it's local.

Q4a. Should i validate the criteria argument that it should have the correct number of fields? For B&S, it should have 6 (name, location, specialties, size, rate, and owner).

I would do but in some abstract way. I guess that you store somewhere the number of fields defined in the header. I'd compare that number to the criteria array size.

Q4b. If validate is necessary, the validateArgument method throws a subclass of Runtime exception, but the findByCriteria signature does not throw any exception. In this case, i will not change the signature, but document the possibility of this exception being thrown in javadoc. Is this ok?

You may throw some IllegalArgumentException in that case.

Q5. Should i add the synchronized modifier to the findByCriteria method or should i synchronize on the cacheDB mutex?

It's difficult to answer this question. You may synchronized on "this" or on your cache. The correct answer depends on what you do elsewhere in your code. In this area, consistency is a *must*.
Except for what I already wrote above, your code looks correct. But as you ask for comments, here are two :
I would replace this :

if (contractor.isDeleted() == true) {
    continue; // go to next iteration of recNo-for loop
} else {

by this (shorter and easier to read) :

if ( !contractor.isDeleted()) {

Also, the main loop could be optimized. As a null criteria value stays null for the whole execution, you could copy the non null criteria values in a (smaller) local array before the loop, and avoid testing for null criteria inside the loop (you do it for each record which is useless)).
Best,
Phil.

[Derek Canaan]

Hi Phil,
Thanks. Taking into account your comments, I have changed the main loop to (more optimized):

        for (int recNo = 1; recNo <= cacheDB.size(); recNo++) {
            boolean match = false;
            Contractor contractor = getContractor(recNo);
            if (!contractor.isDeleted()) { // much clearer  :)  
                // find match
                for (int columnNo = 0; 
                        columnNo < criteria.length; 
                        columnNo++) {
                    String searchValue = criteria[columnNo];
                    if (searchValue == null) {
                        match = true;
                        continue;
                    } else {
                        String fieldColumnValue 
                            = contractor.getFieldValues()[columnNo];
                        if (fieldColumnValue.startsWith(
                                searchValue)) {
                            match = true;
                        } else {
                            match = false;
                            // no match, hence halts execution for 
                            // this recNo and go to the next recNo
                            break; 
                        }
                    }
                }
                if (match) {
                    matchList.add(new Integer(recNo));
                }

Q1: Is code ok?

quote:
--------------------------------------------------------------------------------
Q4b. If validate is necessary, the validateArgument method throws a subclass of Runtime exception, but the findByCriteria signature does not throw any exception. In this case, i will not change the signature, but document the possibility of this exception being thrown in javadoc. Is this ok?
--------------------------------------------------------------------------------
[Phil]: You may throw some IllegalArgumentException in that case

Q2. IllegalArgumentException is a Runtime Exception. Should i change the find method signature to throw IllegalArgumentException or just document this exception for this method in javadoc?

[Phil]: I'd use a HashMap instead of a HashSet, to avoid a useless overhead. ArrayList doesn't suit well for your purpose, IMO.

Q3. Can you explain why HashMap is better suited than ArrayList? For HashMap, i need both key and value to add an Object into the Collection. For ArrayList, i can do ArrayList.add(new Integer(recNo)). For HashMap, how do i add the matching recNo? HashMap.put(new Integer(recNo),new Integer(recNo)) ??

You may synchronized on "this" or on your cache. The correct answer depends on what you do elsewhere in your code.

Q4. I am using cache which is populated when the db file was first accessed. The cache will be used for all read-write access. The db file is updated for write access. The find method is not called any other method in Data class. In this case, is it necessary to sync the find method? What do i have to consider?
Q5. My B&S assignment has long for recNo and my cache is an ArrayList. The methods in ArrayList that i use include get(int index) for readRecord, and set(int index, Object element) for updateRecord. This forces me to cast the long recNo to int. By doing so, i am effectively reducing the database storage size from 2^64 to 2^32. Would i be penalized for this design?
Thanks again,
Derek

[Philippe Maquet]

Hi Derek,

Q1: Is code ok?

I don't think you took this into account : "you could copy the non null criteria values in a (smaller) local array before the loop, and avoid testing for null criteria inside the loop". Your code run faster, but it's OK if you keep as you did.
Q2 : just document this exception in javadoc.

Q3. Can you explain why HashMap is better suited than ArrayList? For HashMap, i need both key and value to add an Object into the Collection. For ArrayList, i can do ArrayList.add(new Integer(recNo)). For HashMap, how do i add the matching recNo? HashMap.put(new Integer(recNo),new Integer(recNo)) ??

Sorry, but I was wrong. I thought of an ArrayList indexed by recNo (memory overhead). And my advice to use a HashMap instead of an HashSet wasn't better... Now to reply your question about HashMap.put(), you could pass null as second argument. But the more I think of it, the more I think a simple LinkedList is the right collection to be used. It would just do what you need : storing the matching recNos in the order you find them, and this with the least overhead. Sorry for having misleaded you with the HashMap.

Q4. I am using cache which is populated when the db file was first accessed. The cache will be used for all read-write access. The db file is updated for write access. The find method is not called any other method in Data class. In this case, is it necessary to sync the find method? What do i have to consider?

The only thing I can tell you from your code excerpt is that there is no synchronization at all, which is probably not enough. What does your update(), delete(), create() and read() methods as far as synch is concerned ? What you must do really depends on your design.

Q5. My B&S assignment has long for recNo and my cache is an ArrayList. The methods in ArrayList that i use include get(int index) for readRecord, and set(int index, Object element) for updateRecord. This forces me to cast the long recNo to int. By doing so, i am effectively reducing the database storage size from 2^64 to 2^32. Would i be penalized for this design?

No. Many people here have a full caching system backed by an ArrayList as you do. Anyway, you'd run out of memory far before you reach your db max size.
Best,
Phil.
[ December 16, 2003: Message edited by: Philippe Maquet ]

[joe black]

The spec for my user interface states:
"It must allow the user to search the data for all records, or for records where the name and/or location fields exactly match values specified by the user."
So that means the array of Strings passed into the find() method would only contain values for the name and location and the rest would be null? If this were the case wouldn't it return all records since "A null value in criteria[n] matches any field value.?"
Also, name and/or location must match exactly. Does case matter? How do you use find to make one or the other match exactly since it can return a record where the value begins with criteria[n]?

[Philippe Maquet]

Hi Joe,

So that means the array of Strings passed into the find() method would only contain values for the name and location and the rest would be null?

Yes, that's the way the client should call it. But it has no influence on how the findByCriteria() method should be written.

If this were the case wouldn't it return all records since "A null value in criteria[n] matches any field value.?"

No, because criteria matches are "ANDed" (OK, this "verb" looks weird ).
This thread (and the other link within it) discusses "and/or" in search.
Best,
Phil.

[joe black]

Thanks Phil.

[Derek Canaan]

Hi Phil,

[Phil]I don't think you took this into account : "you could copy the non null criteria values in a (smaller) local array before the loop, and avoid testing for null criteria inside the loop".

Q1: Is this what you mean? Hope examiner don't find it too complex to read?

        // only need to compare criteria[i] that is not null
        // make an array that store indices of all non-null criteria 
        // elements.
        int[] searchIndices = new int[criteria.length];
        int nonNulls = 0;
        for (int i = 0; i < criteria.length; i++) {
            if (criteria[i] != null) {
                searchIndices[nonNulls] = i;
                nonNulls++;
            }
        }
        
        // Loop thru cacheDB and compare parallel fields of 
        // contractor and criteria
        for (int recNo = 1; recNo <= cacheDB.size(); recNo++) {
            boolean match = true;
            Contractor contractor = getContractor(recNo);
            if (!contractor.isDeleted()) {
                for (int j =0; j < nonNulls; j++) {
                    String searchValue = criteria[searchIndices[j]];
                    String recColumnValue 
                        = contractor.getFieldValues()[searchIndices[j]];
                    if (recColumnValue.startsWith(searchValue)) {
                        match = true;
                    } else {
                        match = false; 
                        break; // no match, go to the next recNo
                    }
                }
                if (match) {
                    matchList.add(new Integer(recNo));
                }
            }
        }

Many people here have a full caching system backed by an ArrayList as you do

Some assignments have int recNo, so caching with ArrayList fits in better than long recNo. I'm just a bit worry. But your "approval" made me feel much better

The only thing I can tell you from your code excerpt is that there is no synchronization at all, which is probably not enough. What does your update(), delete(), create() and read() methods as far as synch is concerned ? What you must do really depends on your design.

I plan on having a singleton Data, one RAF, and putting synchronized modifier on update(), delete(), create() and read(). But i probably need to think about it more...
Thanks again,
Derek
Thanks Phil.

[Philippe Maquet]

Hi Derek,

Q1: Is this what you mean?

You got it !

Hope examiner don't find it too complex to read?

It's possible to make it shorter if you want so, but it's not much better (maybe a *little* more efficient, but who knows ?) that what you wrote above, IMO :

        int[] nonNullIndexes = new int[criteria.length];
        int nonNullCriteriaCount = 0;
        for (int i = 0; i < criteria.length; i++) {
            if (criteria[i] != null) {
                nonNullIndexes[nonNullCriteriaCount++] = i;
            }
        }
        // Loop through cacheDB and compare parallel fields of
        // contractor and criteria
        for (int recNo = 1; recNo <= cacheDB.size(); recNo++) {
            Contractor contractor = getContractor(recNo);
            if (!contractor.isDeleted()) {
                boolean match = true;
                for (int j = 0; j < nonNullCriteriaCount; j++) {
                    int testFieldIndex = nonNullIndexes[j];
                    String searchValue = criteria[testFieldIndex];
                    String recColumnValue
                        = contractor.getFieldValues()[testFieldIndex];
                    if (!recColumnValue.startsWith(searchValue)) {
                        match = false;
                        break; // no match, go to the next recNo
                    }
                }
                if (match) {
                    matchList.add(new Integer(recNo));
                }
            }
        }

Best,
Phil.

[Derek Canaan]

Phil, you are a champ