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

Discussion in 'iOS Libraries' started by keirS, Mar 4, 2018.

  1. keirS

    keirS Well-Known Member Licensed User

    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:

    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:

    Code:
    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:


    Code:
    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.
     

    Attached Files:

    JohnCody, Erel and MarcoRome like this.
  2. keirS

    keirS Well-Known Member Licensed User

    This library has been replaced with a B4X Class
     
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