[Gambas-user] I need a hint on how to deleted duplicate items in a array

[Tobias Boege]

On Tue, 27 Jun 2017, Fernando Cabral wrote:
> Hi
> 
> I have a sorted array that may contain several repeated items scattered all
> over.
> 
> I have to do two different things at different times:
> a) Eliminate the duplicates leaving a single specimen from each repeated
> item;
> b) Eliminate the duplicates but having a count of the original number.
> 
> So, if I have, say
> 
> A
> B
> B
> C
> D
> D
> 
> In the first option, I want to have
> A
> B
> C
> D
> In the second option, I want to have
> 1 A
> 2 B
> 1 C
> 2 D
> 
> Any hints on how to do this using some Gambas buit in method?
> 
> Note; Presently I have been doing it using external calls to
> the utilities sort and uniq.
> 

Your first sentence is a bit confusing. First you say that your array is
sorted but then you say that duplicates may be scattered across the array.
There are notions of order (namely *preorder*) which are so weak that this
could happen, but are you actually dealing with a preorder on your items?
What are your items, anyway?

When I hear "sorted", I think of a partial order and if you have a partial
order, then sorted implies that duplicates are consecutive! Anyway, I don't
want to bore you with elementary concepts of order theory. There are ways
to handle preorders, partial orders and every stronger notion of order,
of course, from within Gambas. You simply have to ask a better question,
by giving more details.

If you have a sorting where duplicates are consecutive, the solution is
very easy: just go through the array linearly and kick out these consecutive
duplicates (which is precisely what uniq does), e.g. for integers:

  Dim aInts As Integer[] = ...
  Dim iInd, iLast As Integer

  If Not aInts.Count Then Return
  iLast = aInts[0]
  iInd = 1
  While iInd < aInts.Count
    If aInts[iInd] = iLast Then ' consecutive duplicate
      aInts.Remove(iInd, 1)
    Else
      iLast = aInts[iInd]
      Inc iInd
    Endif
  Wend

Note that the way I wrote it to get the idea across is not a linear-time
operation (it depends on the complexity of aInts.Remove()), but you can
achieve linear performance by writing better code. Think of it as an
exercise. (Of course, you can't hope to be more efficient than linear
time in a general situation.)

The counting task is solved with a similar pattern, but while you kick
an element out, you also increment a dedicated counter:

  Dim aInts As Integer[] = ...
  Dim aDups As New Integer[]
  Dim iInd, iLast As Integer

  If Not aInts.Count Then Return
  iLast = aInts[0]
  iInd = 1
  aDups.Add(0)
  While iInd < aInts.Count
    If aInts[iInd] = iLast Then ' consecutive duplicate
      aInts.Remove(iInd, 1)
      Inc aDups[aDups.Max]
    Else
      iLast = aInts[iInd]
      aDups.Add(0)
      Inc iInd
    Endif
  Wend

After this executed, the array aInts will not contain duplicates (supposing
it was sorted before) and aDups[i] will contain the number of duplicates of
the item aInts[i] that were removed.

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk