Indexing Data (Insertion Sort) for Maps/Linked Lists/Arrays

Share your advanced PureBasic knowledge/code with the community.
kinglestat
Enthusiast
Enthusiast
Posts: 732
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:

Indexing Data (Insertion Sort) for Maps/Linked Lists/Arrays

Post by kinglestat »

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: Select all


; 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   

Last edited by kinglestat on Mon Mar 19, 2018 9:39 am, edited 4 times in total.
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net
User avatar
Zebuddi123
Enthusiast
Enthusiast
Posts: 794
Joined: Wed Feb 01, 2012 3:30 pm
Location: Nottinghamshire UK
Contact:

Re: Indexing Maps (Keeping a map sorted)

Post by Zebuddi123 »

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: Select all

; 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
User avatar
Zebuddi123
Enthusiast
Enthusiast
Posts: 794
Joined: Wed Feb 01, 2012 3:30 pm
Location: Nottinghamshire UK
Contact:

Re: Indexing Maps (Keeping a map sorted)

Post by Zebuddi123 »

Yours to test:

Code: Select all

; 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
said
Enthusiast
Enthusiast
Posts: 342
Joined: Thu Apr 14, 2011 6:07 pm

Re: Indexing Maps (Keeping a map sorted)

Post by said »

Based on what i understood :D here is a module implementation (with slight changes no need to pass a pointer to .integer ) :

Code: Select all


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

kinglestat
Enthusiast
Enthusiast
Posts: 732
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:

Re: Indexing Maps (Keeping a map sorted)

Post by kinglestat »

@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: Select all

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.
Last edited by kinglestat on Thu Mar 15, 2018 6:08 am, edited 1 time in total.
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net
kinglestat
Enthusiast
Enthusiast
Posts: 732
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:

Re: Indexing Maps (Keeping a map sorted)

Post by kinglestat »

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
Post Reply