11 Replies - 5476 Views - Last Post: 19 July 2010 - 10:24 AM Rate Topic: -----

#1 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Can I use ArrayList in a HashMap as a key

Posted 16 July 2010 - 04:18 AM

Hi All,

This is related to my earlier query about LZW. I have declared my HashMap as

public int[] encodeLZWBytes(byte[] inpData){

Map byte_map=new HashMap<ArrayList<Byte>,Integer>();
//do stuff



This is a dictionary that will be constructed dynamically.

Anyway, when I try to check for existence of the sequence bytes in the dictionary, I use the code below ..

ArrayList<Byte> concatB=new ArrayList<Byte>();//Temp AL to store concatinated bytes

//do stuff next

if (byte_map.containsKey(concatB)==true){
//do stuff}



Unfortunately, that line does not seem to get me a boolean value.
For test purpose in my main I have

public static void main(String arg[]){
        LZWBytes lzw = new LZWBytes();
        String h= new String("Hell");
        byte[] b={1,3,5,6,9,127,22,-9,11};
         lzw.encodeLZWBytes(B)/>;
        }



and though it compiles properly, it never find say the first byte - 1. It is however added to concatB. For test purpose, when I do the below, I get the value of 1 out from the arrayList.

for(int i=0;i<concatB.size();i++){
                System.out.println("xx "+concatB.get(i));
            }



Thanks
Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Can I use ArrayList in a HashMap as a key

#2 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 16 July 2010 - 05:17 AM

You can do this, but i would suggest using a subclass of ArrayList, overriding hashCode and equals. For the former, i would use a function of the hashCode of each element and for the latter, and implementation based on each element (Byte) being identical

See the following for a dynamic demo of how HashMap works, and you will be able to use it to test your override implementations and it'll tell you what's happening in the Map

http://technojeeves....ap-log-debugged

This post has been edited by g00se: 16 July 2010 - 05:20 AM

Was This Post Helpful? 0
  • +
  • -

#3 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 04:39 AM

Note really what happend, entered reply and it disappered. Doing it again.

I finally managed to get LZW compression working. I wrote an ArrayWrapper to be used my Hash table, which can then be munipulated as desired. I think this was what g00se refering to in the previous reply.

I have pasted that code here for reference - and feedback to make it better.

I now have another question. I am saving the LZW codewords as short - ie 16 bits. Most of these values are greater than 8 bit but less than the 16 bits that short takes - say 12 bits which is the standard in GIF format. How do I do this in Java - saving it as variable length code and then reading it without any fuss? Do I have to convert the codeword to Strings - which I dont like? I am hoping that this will give me upto 25% extra compression rate.

package myproject;
import java.util.*;

public class ArrayWrapper 
{
  byte[] bytearr;
  
  //assigns the input byte array to prrivate byte array
  public ArrayWrapper(byte[] arr) {
     bytearr = arr;
  }
  
  //Returns the same array as input array arr 
  public byte[] getBytes() {
      return bytearr;
  }
 
  public int hashCode(){
      int sum=0;
      int count=0;
      
      for (count=0;count<bytearr.length;count++){
          sum+=bytearr[count];
      }
      return sum;
  }
  //Used to compare arrays for content values. 
  public boolean equals(Object obj) {

      // Always expect arrayWrapper
      //System.out.println("Top of equals");
      //System.out.println(obj.getClass().getName());
      if(obj instanceof ArrayWrapper == false) {
         return false;
      }
 //System.out.println("Top of equals 2");
     ArrayWrapper targetArrObj = (ArrayWrapper)obj;
    
     byte[] targetArr = targetArrObj.bytearr;
    
     if(bytearr.length != targetArr.length) {    // Different length? No need to compare. Just false
         return false;
     }
    //System.out.println("Top of equals3");
     int i = 0;
     for(; i < bytearr.length; i++) {
         if(bytearr[i] != targetArr[i])      /// Leave the loop if the element in the same index is different.
             break;
     }
    
//  If all elements are identical, then the loop above finished the whole rounds. So, i must be equal to bytearr.length
     return (i == bytearr.length);  
  }
  
  
  
}


Any help or advice very welcome
Thanks
Was This Post Helpful? 0
  • +
  • -

#4 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 05:07 AM

Quote

How do I do this in Java - saving it as variable length code and then reading it without any fuss? Do I have to convert the codeword to Strings - which I dont like?


Hmm. The way you mention would be the only way if the codewords were encodable as UTF-8 - and i'm sceptical that's the case. If any unencodable 'characters' are found, you'll get corrupted data.

If you use char as your data type instead of short (of course unsigned will have to be OK) then you can use the following to see whether the aforementioned is possible:

http://download.orac...isDefined(char)
Was This Post Helpful? 0
  • +
  • -

#5 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 05:23 AM

Hi g00se

Thanks for your help. The data I am compressing is actually a byte array (-128 to 127) so I would say there should be no un-encodable data. I am going to check your suggestion about char and see what that leads me to. I am getting now 49% compression rate (RLE+LZW) and my supervisor wants me to try for 80% rate. Not sure if I can achieve that, but I am going to try Hybrid solution.

Anyway as for char, I suppose I need to figure out how to use unsinged in java. Is it ok just to ad 128 to the byte value or do I have to look shifting bytes and anding them with something? I am not an expert in java and programming does not come to me naturally.

Thanks
Was This Post Helpful? 0
  • +
  • -

#6 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 05:31 AM

Quote

Anyway as for char, I suppose I need to figure out how to use unsinged in java.


Just keep it away from fire. Sorry couldn't resist that. Just do

char c = (char)(b & 0xFF);


But hang on - if the data are bytes, why do you say that some are 12 bits in length?

This post has been edited by g00se: 19 July 2010 - 05:38 AM

Was This Post Helpful? 0
  • +
  • -

#7 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 06:07 AM

Hmm - yes, I may have confused you indeed.

The incoming data is byte array representing each pixel value. Since LZW requires you to build a dictionary based on sequence of input data, I am saving (and sending via the network) the corresponding dictionary hash value (which I have now as Short). So, if my hashmap for say byte[1,7,-9] is code 12, it is 12 I am writing into the file.
My dictionary will have a maximum of 32k enteries (2^16 - signed) with the corresponding short value to each entry. I have pasted in here my encoder ..
/** This method takes in an input data of byte[] arrays
     * and performs the LZW compression algorithm on the stream.
     * The output is an integer code value representation the
     * dictionary index corresponding for it value. The dictionary is
     * stored in a Hash table and first is initialised and then updated
     * dynamically. The LZW codes are saved into a file using DataOoutputStream 
     * @param inpData
     * @return void
     */
    
     public void encodeLZWBytes(byte[] inpData,DataOutputStream dos){
         //Define the variables first.
         Hashtable<ArrayWrapper,Integer> dict = new Hashtable<ArrayWrapper,Integer>();//Dictionary
         //ArrayList<Integer> output_codes=new ArrayList<Integer>(20000);//LZW codes to be written to a file
         int len=inpData.length;
         
         dictInitializeByte(dict);
         /*
         for (int i=0;i<len;i++){
             byte[] inp_tmp= new byte[]{inpData[i]};
             //Wrap inpData in array wrapper which is used to compare keys in Hash
             //and gives true if similar. I needed to write a wrapper because storing
             //an array in a Hash does not facilitate the comparison of arrays - uses 
             //register rathern than actual values to compare.
             ArrayWrapper awp =new ArrayWrapper(inp_tmp);
             Integer hashcode=dict.size();
             if(dict.containsKey(awp)==false){
                 dict.put(awp, hashcode);
             }
         }*/
       
         //Various variable needed to store values temporarly
         int count=0;
         byte[] prevB=null;
         ArrayList<Byte> al_prevB=new ArrayList<Byte>();//previous byte[] in ArrayList
         ArrayList<Byte> al_concatB=new ArrayList<Byte>();//concatinated byte[] in ArrayList.
         byte[] concatB=null;//Corresponding value to al_concatB
         ArrayWrapper awp_concat=null;//Wrapper used to add to /compare to dictionary
         ArrayWrapper awp_prevB=null;//Similar to above
         //END of decleration
        try{
            while(count < len){
                al_concatB.add(inpData[count]);
                concatB=listToArray(al_concatB);
                awp_concat=new ArrayWrapper(concatB);
                
                if (dict.containsKey(awp_concat)==true){ 
                    //concatinated Byte is in dictionary
                    if(count!=0){
                        al_prevB.add(inpData[count]);
                    }else{
                        al_prevB.add(inpData[0]);
                    }
                    
                    if(count==(len-1)){ 
                        //ie it is the last byte in the array which is already in dict.
                        Integer last_out=dict.get(awp_concat);
                        //output_codes.add(last_out); //just output the dictonary code
                        short last_short=last_out.shortValue();
                        dos.writeShort(last_short);
                    }
                }else{
                    prevB=new byte[al_prevB.size()];
                    prevB=listToArray(al_prevB);
                    awp_prevB=new ArrayWrapper(prevB);
                    if(count==(len-1)){
                        //ie entery is the last byte and sequence of bytes not in dictionary
                        //then output the previous concatinated byte code and current
                        //last byte code (hash)
                        len=dict.size();
                        dict.put(awp_concat, len);
                        prevB=listToArray(al_prevB);
                        ArrayWrapper awp_prev=new ArrayWrapper(prevB);
                        byte[] lastVal=new byte[]{inpData[count]};
                        ArrayWrapper awp_last=new ArrayWrapper(lastVal);
                        Integer prev = (Integer)(dict.get(awp_prev));
                        short prev_short=prev.shortValue();                        
                        dos.writeShort(prev_short);
                        //output_codes.add(prev);
                        Integer last = dict.get(awp_last);                   
                        short last_short=last.shortValue();                                                
                        dos.writeShort(last_short);
                        //output_codes.add(last);                    
                    }else{ //not last entery
                        int num= (Integer)(dict.get((awp_prevB)));
                        Integer position = dict.size();
                        short num_short=(short)num;                                                
                        dos.writeShort(num_short);
                        //output_codes.add(num);
                        dict.put(awp_concat, position);
                        //Re-initialise the various variables
                        prevB=null;
                        concatB=null;                
                        al_concatB.clear();
                        al_prevB.clear();                        
                        al_prevB.add(inpData[count]);
                        al_concatB.add(inpData[count]);}
                }count++;//continue till end of byte stream
                dos.flush();
            }           
        dos.close();
        }catch(IOException io){
            io.printStackTrace();
        }        
        //Put the output code to byte Array  
        /*
        int output_len=output_codes.size();
        int[] outputData = new int[output_len];
        for (int i=0;i<output_len;i++){
            outputData[i]=output_codes.get(i);
            //System.out.print(outputData[i]+" ");
        }
        return outputData; //Returned code values that will beused by the decoder.
         */
    }
 

Was This Post Helpful? 0
  • +
  • -

#8 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 06:18 AM

OK, in that case, see the code i last posted
Was This Post Helpful? 0
  • +
  • -

#9 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 08:22 AM

Hi g00se,

Thanks. Another question then. How do I get back the short value from c. I searched the google - but lots of stuff with no clear answer.

so, if I do this
short b =1232;
char c = (char)(b & 0xFF);



I need to get b back later on for decompression. Can you help?

Thanks
Was This Post Helpful? 0
  • +
  • -

#10 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 08:28 AM

Well, you'll be using String, so for String s, s.toCharArray will get you each c. char is actually an unsigned version of short. If you need short, then short s = (short)c;

This post has been edited by g00se: 19 July 2010 - 08:29 AM

Was This Post Helpful? 1
  • +
  • -

#11 jav2000x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 15-July 10

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 10:14 AM

Hi g00se,

Thanks for your help. I tried your suggestion as shown below and used DataOutputStream.writeChars(Character.toString©);

if(outputData[i]<256){
    c =(char)(outputData[i] & 0xFF);
    }else if((outputData[i] >= 256) && (outputData[i] < 4096)){
        c = (char)(outputData[i] & 0xFFF);
                }else{
                    c = (char)(outputData[i]  & 0xFFFF);
                }



and I am getting exactly the same size as the ones saved using dos.writeShort(). Hence, no gain - so looks like VLC is difficult
to achieve using java. I am going to give in now and go with what I have got. Once again, thank you.
Was This Post Helpful? 0
  • +
  • -

#12 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2556
  • View blog
  • Posts: 10,664
  • Joined: 20-September 08

Re: Can I use ArrayList in a HashMap as a key

Posted 19 July 2010 - 10:24 AM

If you're unsigning to char then you can simplify that with the following:

char c = (char)(x & 0xFFFF);


That will be correct irrespective of input.

Once you've got a char[] you must then use OutputStreamWriter set to UTF-8 to write to file

Don't forget that any data written in this way must be checked for encodability as UTF-8 (see above)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1