Indexing Data (Insertion Sort) for Maps/Linked Lists/Arrays
Posted: Wed Mar 14, 2018 9:46 pm
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?
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