find Duplicate items in linked list

BackupUser · Post by **BackupUser** » Sun Sep 01, 2002 7:06 am

Restored from previous forum. Originally posted by Fangbeast.

Does anyone have some simple code that will go through items in a linked list and perform a user specified action on them if a duplicate is found?

I tried something for the last 5 hours and my code works in reverse (Be quiet Paul!!!)

I have a list of files and CRC's in a linked list and I want to move the duplicates to another location. Already got the skeleton code up and running but I need some logical person to help me think (Paul, I said be quiet!!)

:)

Fangles

BackupUser · Post by **BackupUser** » Sun Sep 01, 2002 7:24 am

Restored from previous forum. Originally posted by Paul.

BackupUser · Post by **BackupUser** » Sun Sep 01, 2002 12:22 pm

Restored from previous forum. Originally posted by freak.

Well, i'd do the following:

First, sort the List by CRC values.
There's an http://www.reelmediaproductions.com/pb/ ... edlist.zip how to do that.

Now, those items with same CRC should be next to each other, the
rest is easy...

Code: Select all

ResetList(SomeList())
previous.l = 0
While NextElement(SomeList())
  If SomeList()\CRC = previous
    ;
    ; here you have a dublicate...
    ;
  Else
    previous = SomeList()\CRC
  EndIf
Wend

This may not be the best way, but al least, it's some way...

Timo

BackupUser · Post by **BackupUser** » Sun Sep 01, 2002 2:33 pm

Restored from previous forum. Originally posted by merendo.

I'm not sure if this works, but maybe... it does something, but I am not sure if it does what it should do...

Global *pointer ; We need the pointer to be global
Global x,z, value.b

NewList testlist.b()
OpenConsole()

For x = 1 To 10 ; 100 elements
For y = 1 To 10

AddElement(testlist())
testlist() = Random(50)
RandomSeed(GetTickCount_()) ; To get 'real' random figures

Next
Next

z=-1

ClearConsole()
FirstElement(testlist())
*pointer = @testlist() ; Get current element pointer
z + 1 ; z contains the number of the element for comparison
value.b = testlist() ; Get value of current element
Goto maincode ; The first time, the code runs, we don't want the code to go to label

label:
ChangeCurrentElement(testlist(),*pointer) ; Go to the element for comparison
If NextElement(testlist()) ; Go to next element as the current one has already been compared
z + 1
*pointer = @testlist()
Goto maincode
Else
MessageRequester("Message","No more elements found!!!",0)
End
EndIf

maincode:
x = -1
ResetList(testlist())
While NextElement(testlist())
x + 1 ; x is the number of the current element
If value.b = testlist() ; Yes, the element IS dublicate
PrintN("Element : "+Str(x)+" is duplicate with element: "+Str(z))
EndIf
Wend
Goto label

Input()

Cu @ll, merendo
--
I've been hiding - What am I hiding from???

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 1:38 am

Restored from previous forum. Originally posted by Fangbeast.

Thanks, I'll try that. Your code is more advanced than anything I do so cross your fingers.

Fred said I needed to use pointers to learn advanced stuff..

Fangles

Okay, i've been playing with it. Every value in your test code is a duplicate of every other value. How can I change your code (which I don't understand how it works) to suit a linked list structure and compare strings?

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 2:49 am

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by Paul

Good doggy, I had the whip out!

Fangles

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 2:53 am

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by freak

Well, i'd do the following:

Code: Select all

ResetList(SomeList())
previous.l = 0
While NextElement(SomeList())
  If SomeList()\CRC = previous
    ;
    ; here you have a dublicate...
    ;
  Else
    previous = SomeList()\CRC
  EndIf
Wend

The hexadecimal values are strings, they cannot be equated as values so how would I use your example above??? (scratching head)

Fangles

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 9:32 am

Restored from previous forum. Originally posted by Pupil.

Originally posted by Fangbeast
The hexadecimal values are strings, they cannot be equated as values so how would I use your example above??? (scratching head)

Something like this should do the trick(assuming the member 'CRC' in the structure is a string):

Code: Select all

ResetList(SomeList())
previous$ = ""
While NextElement(SomeList())
  If SomeList()\CRC = previous$
    ;
    ; here you have a dublicate...
    ;
  Else
    previous$ = SomeList()\CRC
  EndIf
Wend

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 10:21 am

Restored from previous forum. Originally posted by freak.

> The hexadecimal values are strings, they cannot be equated as values so how would I use your
> example above??? (scratching head)

My code was just an example to tell you what i mean, how could i know, your values are Strings since you never posted your code?

But it should not be that hard to modify (it's not that much code

)...

Timo

--------------------------------
Programming today is a race between software engineers striving to build bigger and
better idiot-proof programs and the universe trying to produce bigger and better idiots.

...So far, the universe is winning.

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 10:47 am

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by freak

> The hexadecimal values are strings, they cannot be equated as values so how would I use your
> example above??? (scratching head)

My code was just an example to tell you what i mean, how could i know, your values are Strings since you never posted your code?

But it should not be that hard to modify (it's not that much code )...

Timo

--------------------------------
Programming today is a race between software engineers striving to build bigger and
better idiot-proof programs and the universe trying to produce bigger and better idiots.

...So far, the universe is winning.

Timo, as Paul will probably tell you (he tells me), I don't usually know what I am doing (ROFL)

Fangles

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 11:15 am

Restored from previous forum. Originally posted by Pupil.

Hi Fangbeast, feast on this piece of code for a while:

Code: Select all

Structure CRCListType
  Length.l
  FileName.s
  CRC.s
EndStructure


NewList testlist.CRCListType()

Declare SortLinkedList()
Declare CheckDuplicates()

; Read in some checksum values
For i = 0 To 11
  Read tmpdata.s
  AddElement(testlist())
  testlist()\CRC = tmpdata
  testlist()\Length = i
Next

CheckDuplicates()

; Just to see the sorted list of elements
ResetList(testlist())
msg$ = "Content:"+Chr(10)
While NextElement(testlist())
  msg$ + testlist()\CRC + Chr(10)
Wend
MessageRequester("", msg$,0)

End

; Some predefined CRC data for testing purpose.
DataSection
  Data.s "ffeeddcc", "efdfcfbf", "ddeeffaa", "ffeeddcc", "efdfcfbf", "aaaaaaaa"
  Data.s "ffeeddcc", "efdfcfbf", "ddeeffaa", "ffeeddcc", "efdfcfbf", "aaaaaaaa"
EndDataSection


Procedure SortLinkedList()
  ResetList(testlist())
  NextElement(testlist())
  *listendsorted = testlist()
  If *listendsorted
    Repeat
      If NextElement(testlist())
        *listnext.CRCListType = testlist() ; Object to sort
        ResetList(testlist())
        quit = 0
        While quit = 0
          If NextElement(testlist())
            If LCase(testlist()\CRC) > LCase(*listnext\CRC) ; Sort criteria
              quit = 1
            ElseIf testlist() = *listendsorted
              quit = 2
            EndIf
          EndIf
        Wend
        If quit = 1
          InsertElement(testlist())
        ElseIf quit = 2
          AddElement(testlist())
          *listendsorted = testlist()
        EndIf
          testlist()\Length = *listnext\Length
          testlist()\FileName = *listnext\FileName
          testlist()\CRC = *listnext\CRC
          ChangeCurrentElement(testlist(), *listnext)
          DeleteElement(testlist())
      Else
        finished = 1
      EndIf
    Until finished = 1
  EndIf  
EndProcedure

Procedure CheckDuplicates()
  SortLinkedList()
  ResetList(testlist())
  If NextElement(testlist())
    *ptr.CRCListType = @testlist()
    Repeat
      If NextElement(testlist())
        If *ptr\CRC = testlist()\CRC ; found duplicate!
            ; do what you want with the duplictes here..
          MessageRequester("Info", "Found duplicates with CRC:$"+testlist()\CRC,0)
        Else
          *ptr = @testlist()
        EndIf
      Else
        quit = #TRUE
      EndIf
    Until quit = #TRUE
  EndIf
EndProcedure

BackupUser · Post by **BackupUser** » Mon Sep 02, 2002 12:12 pm

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by Pupil

Hi Fangbeast, feast on this piece of code for a while:

Code: Select all

[/quote]

Thanks Pupil, I really needed that/ been struggling all afternoon with a good way of doing this and managed to lock up the compiler several times.

Pity not many people use the IncrediMail mailer for which my package is written or it could become a good community project :)

Okay, back to work for me :):)


Fangles

BackupUser · Post by **BackupUser** » Tue Sep 03, 2002 1:45 am

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by Pupil

Hi Fangbeast, feast on this piece of code for a while:

Pupil, I incorporated your example into my code and tested it for several hours with 16,300 objects and it works perfectly. For a change, even I didn't screw it up

Freak and Merendo, thank you for your valuable examples to get me started, I wasn't getting anywhere on my own.

You folks are great!!

Fangles

BackupUser · Post by **BackupUser** » Tue Sep 03, 2002 9:50 am

Restored from previous forum. Originally posted by Pupil.

Originally posted by Fangbeast
Pupil, I incorporated your example into my code and tested it for several hours with 16,300 objects and it works perfectly. For a change, even I didn't screw it up

Just out of curiosity, how fast is it with that many objects? Instant, few sec, minutes?

BackupUser · Post by **BackupUser** » Tue Sep 03, 2002 11:57 pm

Restored from previous forum. Originally posted by Fangbeast.

Originally posted by Pupil

Originally posted by Fangbeast
Pupil, I incorporated your example into my code and tested it for several hours with 16,300 objects and it works perfectly. For a change, even I didn't screw it up
Just out of curiosity, how fast is it with that many objects? Instant, few sec, minutes?

Sorry, it never occurred to me to time it!! When I am using my cataloguing functions with Ring's CAB extract code, I am processing around 20 files per second (file and memory functions) so I would expect the sort routine to be very fast being memory based.

I could put in a timer to check if you are still curious?

Fangles