Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Steven Simpson <ss@domain.invalid>
Newsgroups: comp.lang.java.help
Subject: Re: How to remove duplicate values in an array.
Date: Sun, 13 Oct 2013 10:00:30 +0100
Organization: A noiseless patient Spider
Lines: 84
Message-ID: <e24qia-k76.ln1@s.simpson148.btinternet.com>
References: <ca6512ad-67f1-43e1-8aea-a8a7b5641872@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: mx05.eternal-september.org; posting-host="0ef16cf1115fedaca10789f7363c106d"; logging-data="23690"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX199rAULd3Vp1jlroC//SJS0umn2P2AE5DE="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0
In-Reply-To: <ca6512ad-67f1-43e1-8aea-a8a7b5641872@googlegroups.com>
Cancel-Lock: sha1:JziYC71/akPhan6ppgyuQRMwfXw=
Xref: csiph.com comp.lang.java.help:2802

On 13/10/13 06:18, miss.smileyfish@gmail.com wrote:
> I have some code to build an object elementData that stores a list of ints in an array and also keeps track of a boolean unique that determines if duplicates are allowed in a list. I have written a small method to search out duplicates and remove them, but for some reason it is not working. I am not sure if the problem is with the method itself or the placement of the call to the removeDuplicates method.
>
>     // post: places the value in the correct place based on ascending order
>     public void add(int value) {
>        size++;
>        if (size == 1) {
>           elementData[0] = value;
(I'm not sure you need this branch.  binarySearch would have to quickly 
yield -1, position would take the value 0, the shifting loop would have 
zero iterations, and the value would be assigned to position zero.)
>        } else {
>           int position =  Arrays.binarySearch(elementData, 0, size - 1, value);
>           if (position < 0 ) {
>              position = (-position) - 1;
>           }
>           for (int i = size - 1; i > position; i--) {
>              elementData[i] = elementData[i - 1];
>           }
>           elementData[position] = value;
>           if (unique) {
>              removeDuplicates();
>           }

You're evidently relying on the sequence being sorted, and ensuring it 
too - so your removeDuplicates could be limited to looking for them only 
where the insertion just took place.  Better still, detect a 
non-negative from binarySearch, and don't bother inserting.

>        }
>     }
>        
>     //post: removes any duplicate values from the list
>     private void removeDuplicates() {
>        for(int i = size - 1; i < 0; i--) {

Surely, i > 0?

>           if (elementData[i] == elementData[i - 1]){
>              remove(i);
>           }
>        }
>     }
>     // pre : 0 <= index < size() (throws IndexOutOfBoundsException if not)
>     // post: removes value at the given index, shifting subsequent values left
>     public void remove(int index) {
>        checkIndex(index);
>        for (int i = index; i < size - 1; i++) {
>           elementData[i] = elementData[i + 1];
>        }
>        size--;
>     }


Do you need the result to be sorted, or are you just using that to help 
remove duplicates?  If it's incidental, you could just add values to a 
HashSet<Integer>.

If sorting is important, but you want to keep duplicates, you could use 
a TreeMap:

   SortedMap<Integer, Integer> map = new TreeMap<>();

   void add(int value) {
     Integer count = map.get(value);
     if (count == null) count = 0;
     count++;
     map.put(value, count);
   }

To sort but avoid duplicates:

   SortedSet<Integer> set = Collections.newSetFromMap(new TreeMap<Integer, Boolean>());

   void add(int value) {
     set.add(value);
   }

Or use unsorted collections, and sort after.


-- 
ss at comp dot lancs dot ac dot uk