It is currently Wed Dec 11, 2019 5:13 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Indexing Data (Insertion Sort) for Maps/Linked Lists/Arrays
PostPosted: Wed Mar 14, 2018 9:46 pm 
Offline
Enthusiast
Enthusiast

Joined: Fri Jul 14, 2006 8:53 pm
Posts: 654
Location: Malta
Hi guys; without much ado this is an index (you can have more than one) to a PB map keeping the extra data in the index to avoid memory waste

15/3/2018
Updated: V1.1
Multiple indexes can be added and compare function is supplied by user enabling any comparison including multiple fields

19/3/2018
Updated V1.2
- Queue support; keep only an index for the top n or bottom n items in your map or linked list
- Index any element; array/ linked list or map
- Fast delete option for large datasets; mostly practical with queues and frequently changing datasets


Bug: For some reason it does not work if strings are not sized in a structure. Anyone, any idea? Possibly a PB bug?

Code:

; Share and use freely
; Code Written by T. Agius
; Mar/2018

EnableExplicit

Enumeration
   #NDXMAP_WITHFASTDEL  = 1
   #NDXMAP_FIRST        = 1
   #NDXMAP_LAST         = 2
   #NDXMAP_PREV         = 3
   #NDXMAP_NEXT         = 4
   #NDXMAP_PRIME        = 16033
   ;#NDXMAP_PRIME        = 34157
EndEnumeration

Structure stIndex
   *p.Integer
EndStructure

Structure stIndexDetails Align #PB_Structure_AlignC
   Name.s
   iCurrSize.i
   iMaxStart.i
   iExpandSize.i
   iQueue.i
   iPos.i
   fnCompare.i
   Array arIndex.stIndex(1)
   CompilerIf #NDXMAP_WITHFASTDEL = 1
      Map mapIndexKeys.i( #NDXMAP_PRIME )
   CompilerEndIf

EndStructure 

Global NewMap        mapIndexMap.stIndexDetails(128)

Macro                ndxmapChangeIndex( indexname )
   FindMapElement( mapIndexMap(), indexname )
EndMacro

Macro                ndxmapElement()
   mapIndexMap()\arIndex( mapIndexMap()\iPos )\p
EndMacro

Macro                ndxmapChangePos( newpos )
   Select newpos
      Case #NDXMAP_FIRST
         mapIndexMap()\iPos = 0
         
      Case #NDXMAP_LAST
         mapIndexMap()\iPos = mapIndexMap()\iCurrSize - 1
         
      Case #NDXMAP_NEXT
         If mapIndexMap()\iPos < ( mapIndexMap()\iCurrSize - 1 )
            mapIndexMap()\iPos + 1
         EndIf
         
      Case #NDXMAP_PREV
         If mapIndexMap()\iPos > 0
            mapIndexMap()\iPos - 1
         EndIf
         
   EndSelect
EndMacro

Procedure            ndxmapCreateIndex( IndexName.s, SizeStart.i, fnCompare, Increment.i = 5000, qSize.i = 0 )
   
   If FindMapElement( mapIndexMap(), IndexName )
      ProcedureReturn -1
   EndIf
   
   AddMapElement( mapIndexMap(), IndexName )
   With mapIndexMap()
      \iCurrSize     = 0
      \iExpandSize   = Increment
      \iMaxStart     = SizeStart
      \fnCompare     = fnCompare
      \iQueue        = qSize
      \Name          = IndexName + "|"
   EndWith
   
   ReDim mapIndexMap()\arIndex( SizeStart + 2 )

EndProcedure

Procedure            ndxmapAdd( *p.Integer )
   
   Protected         iLow.i, iHigh.i, iMid.i
   
   If mapIndexMap()\iCurrSize > 0
      iHigh = mapIndexMap()\iCurrSize
     
      While iLow  <  iHigh
     
         If CallFunctionFast( mapIndexMap()\fnCompare, *p,  mapIndexMap()\arIndex( iLow )\p ) <= 0
            Break
         ElseIf CallFunctionFast( mapIndexMap()\fnCompare, *p,  mapIndexMap()\arIndex( iHigh  -  1 )\p ) >= 0
            iLow  =  iHigh
            Break
         Else
            iMid  =  (iLow  +  iHigh)  >>  1
         EndIf
         
         If CallFunctionFast( mapIndexMap()\fnCompare, mapIndexMap()\arIndex( iMid )\p, *p ) < 0
            iLow  =  iMid  +  1
         Else
            iHigh  =  iMid
         EndIf
      Wend
     
      MoveMemory( @mapIndexMap()\arIndex( iLow ), @mapIndexMap()\arIndex( iLow + 1 ), @mapIndexMap()\arIndex( mapIndexMap()\iCurrSize ) - @mapIndexMap()\arIndex( iLow ) )
   EndIf
   
   mapIndexMap()\arIndex( iLow )\p  = *p
   
   CompilerIf #NDXMAP_WITHFASTDEL = 1   
      AddMapElement( mapIndexMap()\mapIndexKeys(), Str( *p ), #PB_Map_NoElementCheck )
      mapIndexMap()\mapIndexKeys() = iLow
   CompilerEndIf
   
   If mapIndexMap()\iQueue
      If mapIndexMap()\iCurrSize < mapIndexMap()\iQueue
         mapIndexMap()\iCurrSize + 1
      EndIf
   Else
      mapIndexMap()\iCurrSize  +  1
     
      If mapIndexMap()\iCurrSize  >  mapIndexMap()\iMaxStart
          mapIndexMap()\iMaxStart + mapIndexMap()\iExpandSize
          ReDim mapIndexMap()\arIndex( mapIndexMap()\iMaxStart + 2 )
      EndIf
   EndIf
   
EndProcedure

Procedure            ndxmapDelete( *p.Integer )
   Protected         i, j
   
   j = mapIndexMap()\iCurrSize - 1
   
   CompilerIf #NDXMAP_WITHFASTDEL = 1
      If FindMapElement( mapIndexMap()\mapIndexKeys(), Str( *p ) )
         i = mapIndexMap()\mapIndexKeys()
         DeleteMapElement( mapIndexMap()\mapIndexKeys() )
         ;Debug "[DEL=>" + Str( *p ) + " -- " + Str( i )
      Else   
         ProcedureReturn -1
      EndIf   
   CompilerElse   
      For i = 0 To j
         If *p = mapIndexMap()\arIndex( i )\p
            Break
         EndIf
      Next
   CompilerEndIf   
   
   If i < j
      MoveMemory( @mapIndexMap()\arIndex( i + 1 ), @mapIndexMap()\arIndex( i ), @mapIndexMap()\arIndex( mapIndexMap()\iCurrSize ) - @mapIndexMap()\arIndex( i + 1 ) )
   EndIf
   
   mapIndexMap()\iCurrSize - 1
   
EndProcedure

Macro          ndxmapResetIndex( keyname )
   
   ndxmapChangeIndex( keyname )
   mapIndexMap()\iCurrSize = 0
   CompilerIf #NDXMAP_WITHFASTDEL = 1
      ClearMap( mapIndexMap()\mapIndexKeys() )
   CompilerEndIf   
   ;ReDim mapIndexMap()\arIndex( 1 )
   ;ReDim mapIndexMap()\arIndex( mapIndexMap()\iMaxStart )
   
EndMacro


; - End Index Module
;---------------------

CompilerIf #PB_Compiler_IsMainFile

; -----------------------
; Test Code
; -----------------------

#MaxSize = 25

Structure stTest
   sText.s{24}
   iNum.q
   dTest.d
EndStructure

Global            gszBuild.s     = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Global            gLimit

Procedure         CreateRandomData( Size, ptrData )

  Protected       i, j
  Protected       code.s
  Protected       *ptr.CHARacter
 
  *ptr = ptrData
 
  For i = 1 To Size
    j = Random ( gLimit ) + 1
    *ptr\c = Asc( Mid ( gszBuild, j, 1 ) )
    *ptr + SizeOf( Character )
  Next i

EndProcedure     

Procedure         CompareDouble( *p1.stTest, *p2.stTest )
   If *p1\dTest < *p2\dTest
      ProcedureReturn -1
   ElseIf *p1\dTest > *p2\dTest
      ProcedureReturn 1
   EndIf   
   
   ProcedureReturn 0
EndProcedure

Procedure         CompareString( *p1.stTest, *p2.stTest )
   If CompareMemoryString( @*p1\sText, @*p2\sText, #PB_String_NoCase ) = #PB_String_Lower
      ProcedureReturn -1
   ElseIf CompareMemoryString( @*p1\sText, @*p2\sText, #PB_String_NoCase ) = #PB_String_Greater
      ProcedureReturn 1
   EndIf   
   
   ProcedureReturn 0
EndProcedure


Global NewMap mapTest.stTest(#MaxSize)

Define *ptr, *p.stTest,  iIndex.i, sTookString.s
Define j, szText.s

   gLimit = Len( gszBuild )
   ndxmapCreateIndex( "Double", 15000, @CompareDouble(), 20, 10 )
   ndxmapCreateIndex( "String", 15000, @CompareString() )
   
   For iIndex  =  0 To #MaxSize
      *ptr  =  AddMapElement( mapTest(), "Key-"  +  Str(iIndex + 1) )
     
      j = Random(20, 6)
      szText = Space(j)
      CreateRandomData( j, @szText )
      mapTest()\sText   = szText
      mapTest()\iNum    =  Random( 9999999, 100 )
      mapTest()\dTest   = Random(10000, 10)  /  Random(1000, 100)   
     
      Debug "["  +  Str(iIndex)  +  "] Text="  +  mapTest()\sText  +  " ["  +  Str( mapTest()\iNum )  +  "] --> "  +  FormatNumber( mapTest()\dTest, 2 )
      ndxmapChangeIndex( "Double" )
      ndxmapAdd( *ptr )
      ndxmapChangeIndex( "String" )
      ndxmapAdd( *ptr )
   Next
   
   iIndex = 0
   
   Debug "==[Double]===================================="
   ndxmapChangeIndex( "Double" )
   
   For iIndex  =  0 To mapIndexMap()\iCurrSize - 1
      *p.stTest  =  mapIndexMap()\arIndex( iIndex )\p
      Debug "["  +  Str(iIndex)  +  "] sText="  +  *p\sText  +  " ["  +  Str( *p\iNum )  +  "] --> "  +  FormatNumber( *p\dTest, 2 )
   Next
   
   ndxmapChangeIndex( "String" )
   
   ForEach mapTest()
      iIndex + 1
      If Mod( iIndex, 5 ) = 0
         ndxmapDelete( @mapTest() )
         DeleteMapElement( mapTest() )
      EndIf   
   Next
   
   Debug "==[String]===================================="
   ndxmapChangeIndex( "String" )
   
   For iIndex  =  0 To mapIndexMap()\iCurrSize - 1
      *p.stTest  =  mapIndexMap()\arIndex( iIndex )\p
      Debug "["  +  Str(iIndex)  +  "] sText="  +  *p\sText  +  " ["  +  Str( *p\iNum )  +  "] --> "  +  FormatNumber( *p\dTest, 2 )
   Next
   
CompilerEndIf   


_________________
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net


Last edited by kinglestat on Mon Mar 19, 2018 9:39 am, edited 4 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Indexing Maps (Keeping a map sorted)
PostPosted: Thu Mar 15, 2018 1:14 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Wed Feb 01, 2012 3:30 pm
Posts: 753
Location: Nottinghamshire UK
Hi kinglestat If Ive interpreted what you are trying to achieve! With the same 950 items in 100 timed loop`s, your version on the 100th loop hits 3-4 seconds below with a linked list copied as the map is filled and then sorted with SortStructuredList() on the 100th iteration hits 129 millsecs on my system appox 28 times faster
Zebuddi. :)

Code:
; Share and use freely
;
EnableExplicit

#MaxSize = 950 ; number in datasection for the test. 

Structure STINDEX
   dValue.d
   *ptr.Integer
EndStructure

Structure stTest
   skey.s
   sText.s
   iNum.q
EndStructure

;{ Zebuddi -----------------------------------------------------------------------
Global giCurrSize.i = 0
;} --------------------------------------------------------------------------------


Procedure ndxInsertElement( Array Arr.STINDEX(1), dValue.d, *ptr.Integer )
   Protected iIndex.i
   Protected iLow.i, iHigh.i, iMid.i
   Protected iTempLow.i
   
   If giCurrSize
      iHigh  =  giCurrSize
      
      While iLow  <  iHigh
         If dValue  <=  Arr( iLow )\dValue
            Break
         ElseIf dValue   >=   Arr( iHigh  -  1 )\dValue
            iLow  =  iHigh
            Break
         Else
            iMid  =  (iLow  +  iHigh)  >>  1
         EndIf
         
         If Arr( iMid )\dValue  <  dValue
            iLow  =  iMid  +  1
         Else
            iHigh  =  iMid
         EndIf
      Wend
      
      For iIndex  =  giCurrSize To iLow  +  1 Step  - 1
         Arr( iIndex )\dValue  =  Arr( iIndex  -  1 )\dValue
         Arr( iIndex )\ptr  =  Arr( iIndex  -  1 )\ptr
      Next
   EndIf
   
   Arr( iLow )\dValue  =  dValue
   Arr( iLow )\ptr  =  *ptr
   giCurrSize  +  1
   
   ;    If giCurrSize  >  #MaxSize
   ;       #MaxSize  +  5000
   ;       ReDim Arr.STINDEX( #MaxSize  +  4 )
   ;    EndIf
   ;    
   ;    Debug "-------------"
   
EndProcedure



Global NewMap mapTest.stTest(#MaxSize)
Global NewList listTest.stTest()
Define *ptr, *p.stTest,  iIndex.i, dDouble.d, sTookString.s, giTestLoop.i

For giTestLoop =  1 To 100
   
   giCurrSize = 0
      
   Dim arIndex.STINDEX( #MaxSize ) ; Originally --- Global Dim arIndex.stIndex( giMaxSize + 4)
   
   If MapSize(mapTest())
      ClearMap(mapTest())
      ClearList(listTest())
   EndIf   
   
   Restore test
   ElapsedMilliseconds()
   For iIndex  =  0 To #MaxSize
      
      AddElement(listTest())
      *ptr  =  AddMapElement( mapTest(), "Key-"  +  Str(iIndex + 1) )      : listTest()\skey = MapKey(mapTest())
      
      Read.s mapTest()\sText                                     : listTest()\sText = mapTest()\sText
      
      mapTest()\iNum  =  Random( 9999999, 100 )                      : listTest()\iNum = mapTest()\iNum
      
      dDouble.d  =  Random(10000, 10)  /  Random(1000, 100) 
      ;Debug "["  +  Str(iIndex)  +  "] Text="  +  mapTest()\sText  +  " ["  +  Str( mapTest()\iNum )  +  "] --> "  +  FormatNumber( dDouble, 2 )
      ;ndxInsertElement( arIndex(), dDouble, *ptr )
   Next
   
   ;Debug "======================================"
   SortStructuredList(listTest(), #PB_Sort_Ascending, OffsetOf(stTest\iNum), TypeOf(stTest\iNum))
   Define e =  ElapsedMilliseconds()
   FreeArray(arIndex())
   
   If e > 1000
      sTookString +  Str(giTestLoop) + ". Took: " + StrF((ElapsedMilliseconds() / 1000), 2) + " Sec's" + #CRLF$
   Else
      sTookString +  Str(giTestLoop) + ". Took: " + Str(ElapsedMilliseconds()) + " ms" + #CRLF$
   EndIf   
Next

Debug sTookString
CallDebugger
DataSection
   test:
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s         "Malta",       "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s          "Norway"
   Data.s          "Norway"
EndDataSection


Yours: in second post --->

_________________
malleo, caput, bang. Ego, comprehendunt in tempore


Top
 Profile  
Reply with quote  
 Post subject: Re: Indexing Maps (Keeping a map sorted)
PostPosted: Thu Mar 15, 2018 1:14 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Wed Feb 01, 2012 3:30 pm
Posts: 753
Location: Nottinghamshire UK
Yours to test:

Code:
; Share and use freely
;
EnableExplicit

#MaxSize = 950

Structure STINDEX
   dValue.d
   *ptr.Integer
EndStructure

Structure stTest
   sText.s
   iNum.q
EndStructure

;{ Zebuddi -----------------------------------------------------------------------
Global giCurrSize.i = 0
;} --------------------------------------------------------------------------------


Procedure ndxInsertElement( Array Arr.STINDEX(1), dValue.d, *ptr.Integer )
   Protected iIndex.i
   Protected iLow.i, iHigh.i, iMid.i
   Protected iTempLow.i
   
   If giCurrSize
      iHigh  =  giCurrSize
      
      While iLow  <  iHigh
         If dValue  <=  Arr( iLow )\dValue
            Break
         ElseIf dValue   >=   Arr( iHigh  -  1 )\dValue
            iLow  =  iHigh
            Break
         Else
            iMid  =  (iLow  +  iHigh)  >>  1
         EndIf
         
         If Arr( iMid )\dValue  <  dValue
            iLow  =  iMid  +  1
         Else
            iHigh  =  iMid
         EndIf
      Wend

      For iIndex  =  giCurrSize To iLow  +  1 Step  - 1
         Arr( iIndex )\dValue  =  Arr( iIndex  -  1 )\dValue
         Arr( iIndex )\ptr  =  Arr( iIndex  -  1 )\ptr
      Next
   EndIf
   
   Arr( iLow )\dValue  =  dValue
   Arr( iLow )\ptr  =  *ptr
   giCurrSize  +  1
   
;    If giCurrSize  >  #MaxSize
;       #MaxSize  +  5000
;       ReDim Arr.STINDEX( #MaxSize  +  4 )
;    EndIf
;    
;    Debug "-------------"
   
EndProcedure


   
Global NewMap mapTest.stTest(#MaxSize)

Define *ptr, *p.stTest,  iIndex.i, dDouble.d, sTookString.s, giTestLoop.i

For giTestLoop =  1 To 100
   giCurrSize = 0
   ElapsedMilliseconds()
   
   Dim arIndex.STINDEX( #MaxSize ) ; Originally --- Global Dim arIndex.stIndex( giMaxSize + 4)
   
   If MapSize(mapTest())
      ClearMap(mapTest())
   EndIf   

   Restore test
   For iIndex  =  0 To #MaxSize
      *ptr  =  AddMapElement( mapTest(), "Key-"  +  Str(iIndex + 1) )
      Read.s mapTest()\sText
      mapTest()\iNum  =  Random( 9999999, 100 )
      dDouble.d  =  Random(10000, 10)  /  Random(1000, 100) 
      ;Debug "["  +  Str(iIndex)  +  "] Text="  +  mapTest()\sText  +  " ["  +  Str( mapTest()\iNum )  +  "] --> "  +  FormatNumber( dDouble, 2 )
      ndxInsertElement( arIndex(), dDouble, *ptr )
   Next
   
   ;Debug "======================================"
   
   For iIndex  =  0 To #MaxSize
      *p.stTest  =  arIndex( iIndex )\ptr
      ;Debug "["  +  Str(iIndex)  +  "] sText="  +  *p\sText  +  " ["  +  Str( *p\iNum )  +  "] --> "  +  FormatNumber( arIndex( iIndex )\dValue, 2 )
   Next
   FreeArray(arIndex())
   Define e =  ElapsedMilliseconds()
   If e > 1000
      sTookString +  Str(giTestLoop) + ". Took: " + StrF((ElapsedMilliseconds() / 1000), 2) + " Sec's" + #CRLF$
   Else
      sTookString +  Str(giTestLoop) + ". Took: " + StrF(ElapsedMilliseconds(),2 ) + " ms" + #CRLF$
   EndIf   
      
      
   ;CallDebugger
   ;ClearDebugOutput()
Next

Debug sTookString
CallDebugger
DataSection   
   test:
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
      Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Malta",          "London",       "Brazil",         "USA"
   Data.s         "UK",          "Italy",       "Rome",          "Vatican"
   Data.s         "Switzerland",    "Argentina",    "Algeria",          "Naples"
   Data.s         "France",       "Paris",       "Spain",          "Madrid"
   Data.s         "Finland",      "Turkey",       "Lisbon",          "Portugal"
   Data.s         "Norway"
   Data.s         "Norway"
EndDataSection

_________________
malleo, caput, bang. Ego, comprehendunt in tempore


Top
 Profile  
Reply with quote  
 Post subject: Re: Indexing Maps (Keeping a map sorted)
PostPosted: Thu Mar 15, 2018 5:33 am 
Offline
Enthusiast
Enthusiast

Joined: Thu Apr 14, 2011 6:07 pm
Posts: 341
Based on what i understood :D here is a module implementation (with slight changes no need to pass a pointer to .integer ) :

Code:

DeclareModule IndexedMap
   
    Declare ndxInsertElement( value.d, addr.i )
    Declare.i AddrOfElement(I)
    Declare.d ValueOfElement(I)
EndDeclareModule

Module IndexedMap
    EnableExplicit
    Structure    stIndex
        value.d
        addr.i
    EndStructure
   
   
    Global MaxSize     = 17000
    Global CurrSize    = 0
   
    Global Dim arIndex.stIndex( MaxSize + 4 )
   
    Procedure         ndxInsertElement( value.d, addr.i )
       
        Protected         i
        Protected         Low, High, Mid
        Protected         TempLow
       
        If CurrSize
            High  = CurrSize
           
            While Low < High
                If value <= arIndex( Low )\value
                    Break
                ElseIf Value >= arIndex( High - 1 )\value
                    Low = High
                    Break
                Else
                    Mid = (Low + High) >> 1
                EndIf
               
                If arIndex( Mid )\value < value
                    Low = Mid + 1
                Else
                    High = Mid
                EndIf
            Wend
           
            MoveMemory( @arIndex(Low), @arIndex(Low + 1 ), @arIndex(CurrSize) - @arIndex(Low) )
           
            ;For i = CurrSize To Low + 1 Step -1
            ;   arIndex( i )\value      = arIndex( i - 1 )\value
            ;   arIndex( i )\ptr        = arIndex( i - 1 )\ptr
            ;Next 
        EndIf
       
        arIndex( Low )\value          = value
        arIndex( Low )\addr           = addr
        CurrSize + 1
       
        If CurrSize > MaxSize
            MaxSize + 5000
            ReDim arIndex.stIndex( MaxSize + 4 )
        EndIf
       
        Debug "-------------"
       
    EndProcedure
   
    Procedure.i AddrOfElement(I)
        ProcedureReturn arIndex( I )\addr
    EndProcedure
   
    Procedure.d ValueOfElement(I)
        ProcedureReturn arIndex( I )\value
    EndProcedure
   
EndModule


;--- TEST
UseModule IndexedMap

Structure   stTest
   text.s
   num.q
EndStructure   


Global NewMap  mapTest.stTest()
Global         temp.stTest   

For i = 1 To 20
   *ptr = AddMapElement( mapTest(), "Key-" + Str(i) )
   Read.s mapTest()\text
   mapTest()\num = Random( 9999999, 100 )
   d.d = Random(10000,10) / Random(1000, 100)
   
   Debug "[" + Str(i) + "] text=" + mapTest()\text + " [" + Str( mapTest()\num ) + "] --> " + FormatNumber(  d, 2 )
   ndxInsertElement( d, *ptr )
   
Next

Debug "======================================"

For i = 0 To 19
   ;*p.stTest = arIndex( i )\ptr
   ;Debug "[" + Str(i) + "] text=" + *p\text + " [" + Str( *p\num ) + "] --> " + FormatNumber(  arIndex( i )\value, 2 )

   *p.stTest = AddrOfElement(i)
   Debug "[" + Str(i) + "] text=" + *p\text + " [" + Str( *p\num ) + "] --> " + FormatNumber(  ValueOfElement( i ), 2 )
Next

DataSection
   
   Data.s         "Malta", "London", "Brazil"
   Data.s         "USA", "UK", "Italy", "Rome", "Vatican"
   Data.s         "Switzerland", "Argentina", "Algeria", "Naples"
   Data.s         "France", "Paris", "Spain", "Madrid", "Finland"
   Data.s         "Turkey", "Lisbon", "Portugal", "Norway"
   
   
   
EndDataSection



Top
 Profile  
Reply with quote  
 Post subject: Re: Indexing Maps (Keeping a map sorted)
PostPosted: Thu Mar 15, 2018 6:02 am 
Offline
Enthusiast
Enthusiast

Joined: Fri Jul 14, 2006 8:53 pm
Posts: 654
Location: Malta
@Zebuddi123

First of all, thanks for the input
There is already a small optimization which I had already posted but you missed which replaces the update loop

Code:
MoveMemory( @Arr(iLow), @Arr(iLow + 1 ), @Arr(giCurrSize) - @Arr(iLow) )


But I suspect you are missing the point. The object of the index (that is why it is called index) is to keep it sorted while elements are added; If a user has the luxury to get the data all at once, he can always sort later.
You will also find that with large datasets (which I use) sorting becomes very slow. So if you want to test, you need to add your sortstructuredlist in the loop too and you will see that the timings become very similar till you go very large, then the sort slows down a lot.

_________________
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net


Last edited by kinglestat on Thu Mar 15, 2018 6:08 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Indexing Maps (Keeping a map sorted)
PostPosted: Thu Mar 15, 2018 6:03 am 
Offline
Enthusiast
Enthusiast

Joined: Fri Jul 14, 2006 8:53 pm
Posts: 654
Location: Malta
Thanks said
Though what I meant was more in line with having the same module, and re-using it to create more indexes
But its a start

_________________
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye