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

keirS · Sep 14, 2018

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:

B4X:

#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 String) As 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:

B4X:

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:

B4X:

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:

B4X:

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 :

B4X:

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

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

Attachments

Similar Threads