B4i Library [Beta/Preview] SortedMap; A Sorted Collection

Introduction:

This collection is very similar to the Java TreeMap collection I wrapped for B4j and B4A a while back. However this version is written completely in B4X. It's based on a red black self balancing binary search tree. If you want to understand how this works take look at this superb visualization tool which was of invaluable help in coding this.

As the collection is tree based it's very easy and fast to return portions of the Map based on the key values as shown in the example code.

Documentation:

SortedMap

Author: Keirs (Copyright 2018)
Version: 0.0009

• SortedMap
  • Functions:
    • CeilingKey (Key As NSObject*) As NSObject*
      Returns the least key greater than or equal to the given key, or null if there is no such key.
    • Class_Globals As NSString*
      
    • Clear As NSString*
      Removes all of the mappings from this map.
    • ContainsKey (Key As NSObject*) As BOOL
      Tests whether there is an item with the given key.
    • FirstKey As NSObject*
      Returns the first (lowest) key currently in this map.
    • FloorKey (Key As NSObject*) As NSObject*
      Returns the greatest key less than or equal to the given key, or null if there is no such key.
    • Get (Key As NSObject*) As NSObject*
      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 NSObject*, Inclusive As BOOL) As B4i_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 NSObject*) As NSObject*
      Returns the least key strictly greater than the given key, or null if there is no such key.
    • Initialize (ba As B4I*) As NSString*
      Initializes the object. You can add parameters to this method if needed.
    • IsInitialized As BOOL
      Tests whether the object has been initialized.
    • LastKey As NSObject*
      Returns the last (highest) key currently in this map.
    • ListInOrder As NSString*
      
    • ListInorderFromNode (Node As B4i_treenode*) As NSString*
      
    • LowerKey (Key As NSObject*) As NSObject*
      Returns the greatest key less than the given key, or null if there is no such key.
    • Put (Key As NSObject*, Value As NSObject*) As NSString*
      Puts a key/value pair in the map, overwriting the previous item with this key (if such exists).
    • Remove (Key As NSObject*) As NSString*
      Removes the Key form The Map
    • Submap (FromKey As NSObject*, ToKey As NSObject*, Inclusive As BOOL) As B4i_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 NSObject*, Inclusive As BOOL) As B4i_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.
• SortedMapIterator
  • Fields:
    • MAP_ITERATE_ASCENDING As Int
      
    • MAP_ITERATE_DECENDING As Int
  • Functions:
    • Process_Globals As NSString*
      Static code module
• SortedMapNavigator
  • Functions:
    • Class_Globals As NSString*
      
    • Initialize (ba As B4I*, MapToIterate As B4i_sortedmap*, IterationDirection As Int) As NSString*
      Initalize the iterator. Pass Iterator.MAP_ITERATE_ASCENDING or Iterator.MAP_ITERATE_DECENDING for the direction to It
    • IsInitialized As BOOL
      Tests whether the object has been initialized.
    • MoveNext As BOOL
      Move To The Next Position In The Map.
    • MovePrev As BOOL
      Move to the previous entry. Returns True if succesful.
    • Reset As NSString*
      Reset Map to start position
  • Properties:
    • Key As NSObject* [read only]
      Get the current Key
    • Value As NSObject* [read only]
      Get The Current Value

Sample Code:

Sub Process_Globals
    'These global variables will be declared once when the application starts.
    'Public variables can be accessed from all modules.
    Public App As Application
    Public NavControl As NavigationController
    Private Page1 As Page
    Dim RBMap As SortedMap
    Dim SubMap As  SortedMap
    Dim HeadMap As  SortedMap
    Dim TailMap As  SortedMap
    Dim MapNavigator As SortedMapNavigator  
End Sub
  
Private Sub Application_Start (Nav As NavigationController)
    'SetDebugAutoFlushLogs(True) 'Uncomment if program crashes before all logs are printed.
    NavControl = Nav
    Page1.Initialize("Page1")
    Page1.Title = "Page 1"
    Page1.RootPanel.Color = Colors.White
    NavControl.ShowPage(Page1)
    RBMap.Initialize
    '
    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")
  
  
    '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("***************************************")
    Log(" ")
    Log("Navigating Tree Forward")
    Log(" ")
    Log("***************************************")
    MapNavigator.Initialize(RBMap,SortedMapIterator.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********************")
  
  
'Remove Key E
  
    RBMap.Remove("E")
  
    Log("***************************************")
    Log(" ")
    Log("Key E Removed")
    Log(" ")
    Log("*************************************")
  
    MapToLog(RBMap)
  
End Sub
Sub MapToLog(M As SortedMap)
    Dim Nav As SortedMapNavigator
    Nav.Initialize(M,SortedMapIterator.MAP_ITERATE_ASCENDING)
    Do While Nav.MoveNext()
        Log(Nav.Key)
    Loop
  
End Sub
Private Sub Page1_Resize(Width As Int, Height As Int)
  
End Sub
Private Sub Application_Background
  
End Sub

Log Results:

Application_Start
Keys Between B And F Inclsuive
B
C
D
E
F
Class (b4i_sortedmapnavigator) instance released.
Keys <= F
A
B
C
D
E
F
Class (b4i_sortedmapnavigator) instance released.
Keys >= F
F
G
Class (b4i_sortedmapnavigator) instance released.
First Key Lower Than F: E
First Key Lower Than or Equal To C: C
First Key Higher Than F: G
First Key Higher Than Space: A
First Key In Map: A
Last Key In Map: G
Map Contains G: true
Map Contains Z: false

***************************************

Navigating Tree Forward

***************************************
A
B
C
D
E
F
G
**************END********************

***************************************

Navigating Tree In Reverse

***************************************
G
F
E
D
C
B
A
**************END********************
Class (b4i_treenode) instance released.
***************************************

Key E Removed

*************************************
A
B
C
D
F
G

Iteration And The SortedMapNavigator:

Use the SortedMapNavigator to iterate over the map (see example code). It is important to note that putting or removing an entry whilst using the navigator will potentially break the navigator. Updating a value will work (putting an existing key).

This may change in the final release as it is possible to implement a solution that does not break navigation.

SortedMapNavigator works a bit like the SQL ResultSet in that when you initialize it's starting position is before the first entry in the map.


Keys and Sorting:

Private Sub CompareKey(Key1 As Object,Key2 As Object) As Int
  
      Dim Key1S As String = Key1
      Dim Key2S As String = Key2
      Return Key1S.CompareTo(Key2S)
  
  
End Sub

The above is the Sub used to sort the Map. You can use anything as a Key which can be cast to a String.


Installing:

Download the zip file and unzip. Copy the content of the Libs folder to your B4i Additional Libraries folder. To run the test program you will have to change the package name to match your provision app id.

 

[keirS]

This library has been replaced with a B4X Class