B4J Library [B4X] Sorted Map Class (with source code)

Discussion in 'B4J Libraries & Classes' started by keirS, Sep 14, 2018.

Tags:
  1. keirS

    keirS Well-Known Member Licensed User

    This is an implementation of a sorted map using a red black self balancing binary search tree. It replaces the B4J TreeMap Library and the B4I Sorted Map Library. The .zip file includes demonstration / test programs for B4A,B4I and B4J.

    If you want to understand what the SortedMap class is doing then I recommend looking a this very helpful visualization tool which was of invaluable help in coding and debugging this.

    Documentation:

    SortedMap

    Author: KeirS
    Version: 1

    SortedMap

    • Functions:
      • CeilingKey (Key As Object) As Object
        Returns the least key greater than or equal to the given key, or null if there is no such key.
      • Class_Globals As String
      • Clear As String
        Clears all items of the map
      • ComparatorMap (Comparator As Object, SubToCall As String) As SortedMap
        Returns a TreeMap with the keys ordered by the comparator sub.
      • ContainsKey (Key As Object) As Boolean
        Tests whether there is an item with the given key.
      • FirstKey As Object
        Returns the first (lowest) key currently in this map.
      • FloorKey (Key As Object) As Object
        Returns the greatest key less than or equal to the given key, or null if there is no such key.
      • Get (Key As Object) As Object
        Returns the value of the item with the given Key.
      • getSize As Int
        Returns the number of items stored in the map.
      • HeadMap (Key As Object, Inclusive As Boolean) As SortedMap
        Returns a view of the portion of this map whose keys are less than (or equal to if inclusive) the passed Key
      • HigherKey (Key As Object) As Object
        Returns the least key strictly greater than the given key, or null if there is no such key.
      • Initialize (Comparator As Object, SubToCall As String) As String
      • IsInitialized As Boolean
        Tests whether the object has been initialized.
      • LastKey As Object
        Returns the last (highest) key currently in this map.
      • LowerKey (Key As Object) As Object
        Returns the greatest key less than the given key, or null if there is no such key.
      • Put (Key As Object, Value As Object) As String
        Puts a key/value pair in the map, overwriting the previous item with this key (if such exists).
      • Remove (Key As Object) As String
        Removes the Key form The Map
      • Submap (FromKey As Object, ToKey As Object, Inclusive As Boolean) As SortedMap
        Returns a TreMmap of the portion of this map whose keys range from fromKey to toKey.
        The range Is inclusive of the Key values If inclusive Is True
      • TailMap (Key As Object, Inclusive As Boolean) As SortedMap
        Returns a TreeMap of the portion of this map whose keys are greater than (or equal to if inclusive) fromKey.
    • Properties:
      • Size As Int [read only]
        Returns the number of items stored in the map.
    SortedMapNavigator

    • Functions:
      • Class_Globals As String
      • Close As String
        Deregiser
      • getKey As Object
        Get the current Key
      • getValue As Object
        Get The Current Value
      • Initialize (MapToIterate As SortedMap, IterationDirection As Int) As String
        Initalize the iterator. Pass Iterator.MAP_ITERATE_ASCENDING or Iterator.MAP_ITERATE_DECENDING for the direction to It
      • IsInitialized As Boolean
        Tests whether the object has been initialized.
      • MoveNext As Boolean
        Move To The Next Position In The Map.
      • MovePrev As Boolean
        Move to the previous entry. Returns True if succesful.
      • Reset As String
        Reset Map to start position
    • Properties:
      • Key As Object [read only]
        Get the current Key
      • Value As Object [read only]
        Get The Current Value

    Test Program:

    Code:
    #Region Project Attributes 
        
    #MainFormWidth: 600
        
    #MainFormHeight: 600 
        
    #LibraryName: SortedMap
        
    #LibraryVersion:  1.0
        
    #LibraryAuthor: KeirS
    #End Region
    Sub Process_Globals
        
    Private fx As JFX
        
    Private MainForm As Form
        
    Dim RBMap As SortedMap
        
    Dim SubMap As  SortedMap
        
    Dim HeadMap As  SortedMap
        
    Dim TailMap As  SortedMap
        
    Dim MapNavigator As SortedMapNavigator
        
    Dim Sorts As MapSorts
    End Sub
    Sub AppStart (Form1 As Form, Args() As String)
        MainForm = Form1
        
    'MainForm.RootPane.LoadLayout("Layout1") 'Load the layout file.
        MainForm.Show
        
    'RBMap.Initialize(Me,"ReverseSort")
         
        
    '******************************************************************************************************'
        '*                                                                                                      *'
        '* Random Map test. Should test all combinations of node roatations and recolouring nodes              *'
        '*                                                                                                      *
        '******************************************************************************************************'
        Sorts.Initialize
       
        
    Log("****Start Random Map Test****")
        
    Dim RndMap As SortedMap
        RndMap.Initialize(Sorts,
    "IntSort")
        
    For cntr = 1 To 1000
            
    Dim Key As Int = Rnd(0,1000000000)
            
    Log("Add: " & Key)
            
    If RndMap.Size > 0 Then
                
    Do While RndMap.ContainsKey(Key) = True
                    Key = 
    Rnd(0,1000000000)
                
    Loop
                RndMap.Put(Key,Key)
            
    Else
                RndMap.Put(Key,Key)
            
    End If
        
    Next
     
        
    Log("****Finisehed  Random Map Test***")
        MapToLog(RndMap)
             
        
    '******************************************************************************************************'
        '*                                                                                                      *'
        '* Test SotedMap Methods                                                                              *'
        '*                                                                                                      *
        '******************************************************************************************************'
       
        RBMap.Initialize(
    Null,Null)
        RBMap.Put(
    "D","D")
        RBMap.Put(
    "A","A")
        RBMap.Put(
    "C","C")
        RBMap.Put(
    "E","E")
        RBMap.Put(
    "G","G")
        RBMap.Put(
    "B","B")
        RBMap.Put(
    "F","F")
        
    Log("****Start SotedMap Methods Test****")
        
    'get Map with keys B To F inclusive
        SubMap = RBMap.SubMap("B","F",True)
        
    Log("Keys Between B And F Inclsuive")
        MapToLog(SubMap)
        
    'get Map with keys <= F
        HeadMap = RBMap.HeadMap("F",True)
        
    Log("Keys <= F")
        MapToLog(HeadMap)
        
    'get Map with keys >= G
        TailMap = RBMap.TailMap("F",True)
        
    Log("Keys >= F")
        MapToLog(TailMap)
        
    Dim s As String = RBMap.LowerKey("F")
        
    Log("First Key Lower Than F: " & s)
        s = RBMap.FloorKey(
    "C")
        
    Log("First Key Lower Than or Equal To C: " & s)
        s = RBMap.HigherKey(
    "F")
        
    Log("First Key Higher Than F: " & s)
        s = RBMap.CeilingKey(
    " ")
        
    Log("First Key Higher Than Space: " & s)
        s = RBMap.FirstKey
        
    Log("First Key In Map: " & s)
        s = RBMap.LastKey
        
    Log("Last Key In Map: " & s)
        
    Log("Map Contains G: " & RBMap.ContainsKey("G"))
        
    Log("Map Contains Z: " & RBMap.ContainsKey("Z"))
        
    'Initalize the Navigator
        Log(" ")
       
        
    Log("****ComparatorMap Test****")
        
    Dim RndMap2 As SortedMap
        RndMap2.Initialize(Sorts,
    "IntSort")
        
    For cntr = 1 To 10
            
    Dim Key As Int = Rnd(0,1000)
            
    Log(Key)
            
    If RndMap2.Size > 0 Then
                
    Do While RndMap2.ContainsKey(Key) = True
                    Key = 
    Rnd(0,1000)
                
    Loop
                RndMap2.Put(Key,Key)
            
    Else
                RndMap2.Put(Key,Key)
            
    End If
        
    Next
        
    Log("Forward Sort")
        MapToLog(RndMap2)
        
    Dim RndMap3 As SortedMap = RndMap2.ComparatorMap(Sorts,"ReverseIntSort")
        
    Log("Reverse Sort:")
        MapToLog(RndMap3)
        
    Log("****Finisehed  Comparator Map Test***")
       
        
    Log("****End Of SotedMap Methods Test****")
       
       
        
    '******************************************************************************************************'
        '*                                                                                                      *'
        '* Test SortedMapNavigator                                                                            *'
        '*                                                                                                      *
        '******************************************************************************************************'
       
        
    Log("***************************************")
        
    Log(" ")
        
    Log("Navigating Tree Forward")
        
    Log(" ")
        
    Log("***************************************")
        MapNavigator.Initialize(RBMap,MapIterator.MAP_ITERATE_ASCENDING)
        
    Do While MapNavigator.MoveNext = True
            
    Log(MapNavigator.Key)
        
    Loop
        
    Log("**************END********************")
       
        
    Log(" ")
       
        
    Log("***************************************")
        
    Log(" ")
        
    Log("Navigating Tree In Reverse")
        
    Log(" ")
        
    Log("***************************************")
       
        
    'Reached The End so go back to the begginng
       
        
    Do While MapNavigator.MovePrev = True
            
    Log(MapNavigator.Key)
        
    Loop
        
    Log("**************END********************")
       
        
    Log("***************************************")
        
    Log(" ")
        
    Log("Delete And Add Navigation Test")
        
    Log(" ")
        
    Log("***************************************")
        MapNavigator.Close
        
    Dim MapNavigator As SortedMapNavigator
       
        RBMap.Put(
    "H","New H")
        RBMap.Put(
    "J","New J")
        MapNavigator.Initialize(RBMap,MapIterator.MAP_ITERATE_ASCENDING)
       
        
    Dim MapAdd  As Boolean = False
        
    Do While MapNavigator.MoveNext() = True
            
    If MapNavigator.Key = "H" Then
                RBMap.Put(
    "I","I")
                MapAdd = 
    True
                
    Log(MapNavigator.Key)
            
    Else
                
    Log(MapNavigator.Key)
            
    End If
            
    If MapAdd = True And  MapNavigator.Key <> "H"  Then
                
    Log("Key Added: " & MapNavigator.Key)
                MapAdd = 
    False
            
    End If
        
    Loop
       
       
        
    '
        MapToLog(RBMap)
        
    Dim MapNavigator As SortedMapNavigator
        MapNavigator.Initialize(RBMap,MapIterator.MAP_ITERATE_ASCENDING)
        
    Do While MapNavigator.MoveNext() = True
            
    If MapNavigator.Key = "I" Then
                RBMap.Remove(
    "J")
                
    Log("J Removed")
                MapAdd = 
    True
                
    Log(MapNavigator.Key)
            
    Else
                
    Log(MapNavigator.Key)
            
    End If
        
    Loop
       
        RBMap.Remove(
    "C")
        MapToLog(RBMap)
        
    Log("**************END********************")
       
       
    End Sub
    'function to output mam to a log
    Sub MapToLog(M As SortedMap)
        
    Dim Nav As SortedMapNavigator
        
    Dim Cntr As Int = 0
        Nav.Initialize(M,MapIterator.MAP_ITERATE_ASCENDING)
        
    Do While Nav.MoveNext()
            Cntr = Cntr + 
    1 
            
    Log("Key Value " & Cntr & ": " & Nav.Key)
           
        
    Loop
        Nav.Close
    End Sub
    'Return true to allow the default exceptions handler to handle the uncaught exception.
    Sub Application_Error (Error As Exception, StackTrace As StringAs Boolean
        
    Return True
    End Sub


    Custom Sorting:

    You can write your own custom sort routines. These need to be in a class. The test program uses the MapSorts class:

    Code:
    Sub Class_Globals
       
    End Sub
    'Initializes the object. You can add parameters to this method if needed.
    Public Sub Initialize
    End Sub
    Public Sub ReverseSort(Key1 As Object,Key2 As Object) As Int
        
    Dim Key1S As String = Key1
        
    Dim Key2S As String = Key2
        
    Return Key2S.CompareTo(Key1S) 
    End Sub
    'custom sort function for random map test
    Public Sub IntSort(Key1 As Object,Key2 As Object) As Int
        
    Dim Key1i As Int = Key1
        
    Dim Key2i As Int = Key2
       
        
    If Key1i > Key2i Then
            
    Return 1
        
    Else If Key1i < Key2i Then
            
    Return -1
        
    Else
            
    Return 0
        
    End If
    End Sub
    Public Sub ReverseIntSort(Key1 As Object,Key2 As Object) As Int
        
    Dim Key1i As Int = Key1
        
    Dim Key2i As Int = Key2
       
        
    If Key1i > Key2i Then
            
    Return -1
        
    Else If Key1i < Key2i Then
            
    Return 1
        
    Else
            
    Return 0
        
    End If
    End Sub
    The SortedMap is initialized with the class instance and the sort method:
    Code:
    Dim Sorts As MapSorts
    Dim RndMap As SortedMap
        RndMap.Initialize(Sorts,
    "IntSort")
        
    For cntr = 1 To 1000
            
    Dim Key As Int = Rnd(0,1000000000)
            
    Log("Add: " & Key)
            
    If RndMap.Size > 0 Then
                
    Do While RndMap.ContainsKey(Key) = True
                    Key = 
    Rnd(0,1000000000)
                
    Loop
                RndMap.Put(Key,Key)
            
    Else
                RndMap.Put(Key,Key)
            
    End If
        
    Next
    Iterating Over A Map:

    The SortedMapNavigator class is used to sort over the map (as shown in the example code). It implements a very basic notification system with the SortedMap class so it can deal with additions and deletions to the Map.

    In the SortedMap class:

    Code:
    Private Sub RegisterNavigator(Nanvigator As SortedMapNavigator)
        NavigatorList.Add(Nanvigator)
    End Sub
    Private Sub DeregisterNavigator(Nanvigator As SortedMapNavigator)
        
    Dim NavPosition As Int = NavigatorList.IndexOf(Nanvigator)
        
    If NavPosition >= 0 Then
            NavigatorList.RemoveAt(NavPosition)
        
    End If
    End Sub
    Private Sub InformNavigatorsDeletion(DeletedNode As TreeNode)
        
    For Each Nav As SortedMapNavigator In NavigatorList
            
    CallSub2(Nav,"NodeDeleted",DeletedNode)
           
        
    Next
       
    End Sub
    Private Sub InformNavigatorsAdd()
        
    For Each Nav As SortedMapNavigator In NavigatorList
            
    CallSub(Nav,"NodeAdded")
           
        
    Next
       
    End Sub
    In the SortedMapNavigatorClass :
    Code:
    rivate Sub NodeDeleted(DeletedNode As TreeNode)
        
    If PrevPositionNode = DeletedNode Then
            
    If Direction = ITERATE_ASCENDING Then
                NextPositionNode = InOrderPredescessor(DeletedNode)
           
    Else
                NextPositionNode = InOrderSuccessor(DeletedNode)
           
    End If
        
    Else If NextPositionNode = DeletedNode Then 
            
    If Direction = ITERATE_ASCENDING Then
                NextPositionNode = InOrderSuccessor(DeletedNode)
            
    Else
                NextPositionNode = InOrderPredescessor(DeletedNode)
           
    End If
        
    Else If CurrentPositionNode = DeletedNode Then
            MoveNext
        
    End If
    End Sub
    Private Sub NodeAdded()
        
    If Direction = ITERATE_ASCENDING Then
            PrevPositionNode = InOrderPredescessor(CurrentPositionNode)
            NextPositionNode = InOrderSuccessor(CurrentPositionNode)
        
    Else
            PrevPositionNode = InOrderSuccessor(CurrentPositionNode)
            NextPositionNode = InOrderPredescessor(CurrentPositionNode)
        
    End If
       
    End Sub
     

    Attached Files:

    Erel, OliverA and inakigarm like this.
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice