飴屋ぷろじぇくと

 ちょっとカテゴリを分けてみようかなっと。

--.--.--[--] スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2014.11.12[水] FreeBASICの#Macroをテンプレート的に使ってみるテスト2


テンプレートマクロ第二弾。マップの実装です。但しあんまり速い実装ではありません。
マップというのはキーと値のペアを登録してキーを添え字にその値を取得できるクラスのことです。
map.bi
#define Map(T,V) T##_To_##V##_Map

#Macro Declare_Map(Ky,Va)
Type Map(Ky,Va)
Private:
    m_Keys(Any) As Ky
    m_Values(Any) As Va
Public:
    Declare Property Keys(i As Integer) As Ky
    Declare Property Items(i As Integer) As Va
    Declare Sub Clear
    Declare Property Size As Integer
    Declare Function add(k As Ky, v As Va) As Integer
    Declare Function find(k As Ky) As Integer
    Declare Operator [](k As Ky) ByRef As Va
End Type
#EndMacro

#Macro Implement_Map(Ky,Va)
Property Map(Ky,Va).Keys(i As Integer) As Ky
    Return m_Keys(i)
End Property

Property Map(Ky,Va).Items(i As Integer) As Va
    Return m_Values(i)
End Property

Property Map(Ky,Va).Size As Integer
    Return UBound(m_Keys) + 1
End Property

Sub Map(Ky,Va).Clear
    Erase m_Keys
    Erase m_Values
End Sub

Function Map(Ky,Va).add(k As Ky, v As Va) As Integer
    Dim u As Integer = UBound(m_Keys)
    Dim i As Integer
    if u < 0 Then
        Redim PreServe m_Keys(0), m_Values(0)
        m_Keys(0) = k
        m_Values(0) = v
        i = 0
    Else
        Dim n As Integer
        For n = 0 To u
            if m_Keys(n) >= k Then
                Exit For
            End If
        Next
        u = u + 1
        Redim PreServe m_Keys(u), m_Values(u)
        For i = u - 1 To n Step -1
            m_Keys(i + 1) = m_Keys(i)
            m_Values(i + 1) = m_Values(i)
        Next
        m_Keys(n) = k
        m_Values(n) = v
        i = n
    End If
    Return i
End Function

Function Map(Ky,Va).find(k As Ky) As Integer
    Dim u As Integer = UBound(m_Keys)
    Dim s As Integer = 0
    Dim t As Integer = u + 1
    Dim m As Integer = u \ 2
    
    Do While t > s + 1
        If k < m_Keys(m) Then
            t = m
            m = (s + t) \ 2
        ElseIf k > m_Keys(m) Then
            s = m
            m = (s + t) \ 2
        ElseIf k = keys(m) Then
            Return m
        Else
            Exit Do
        End If
    Loop
    Return -1
End Function

Operator Map(Ky,Va).[](k As Ky) ByRef As Va
    Dim n As Integer = find(k)
    if n = -1 Then
        Dim v As Va
        n = add(k, v)
    End If
    Return m_Values(n)
End Operator

#EndMacro


キーと値はキーでソートして格納し、検索はバイナリ検索で行っています。
要素数が膨大になると登録がかなりオーバーヘッドになりますのでもっと速い実装が欲しい場合は二分木のマップやハッシュマップ等を自力で作成するこををお勧めします。

使い方の例:
#include "map.bi"

Declare_Map(String,Long)
Implement_Map(String,Long)

Dim m As Map(String,Long)
Dim i As Integer

' []でアクセスするとそのキーの要素が自動で作られます
m["りんご"] = 45
m["みかん"] = 32
m["ぶどう"] = 210
m["めろん"] = 10000
m["すいか"] = 300
m["いちご"] = 15
m["れもん"] = 14675

'キーと値の列挙はそれぞれ別のインデックス付きプロパティでアクセスします。
For i = 0 To m.Size - 1
    Print m.Keys(i);" ";m.Items(i)
Next

'findメソッドは要素のインデックスを返します
Print m.find("りんご")
Print m.find("みかん")
Print m.find("とまと") '無い場合-1を返します

Print m["れもん"]
Print m["ぶどう"]
Print m["きゃべつ"] '[]アクセスの場合、存在しないキーは読み取りでも自動で作られます

Comment






(編集・削除用)

Trackback

http://utau2009.blog114.fc2.com/tb.php/30-db916f98

この記事にトラックバック(FC2Blog User)

Copyright © 飴屋/菖蒲

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。