ラボ/LRU

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
|
!
-
|
|
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
!
 
 
 
 
 
 
 
 
 
-
|
|
!
 
 
 
 
 
 
 
-
|
|
!
-
|
!
 
 
-
|
|
!
-
|
!
 
 
 
 
 

/*
################################################################################
#                                                                              #
#         データ構造：MRU(Least Recently Used)                                 #
#         リスト構造の一種でアクセス頻度の最も少ない要素へのアクセスを         #
#         素早くできるようにしたデータ構造。                                   #
#                                                                              #
################################################################################
*/
 
#module "SLinkedListLRU"
    /*--------------------------------------------------------------------*
     *                     片方向リンクリストの初期化                     *
     *--------------------------------------------------------------------*/
    #deffunc SLink_init int i
        mref res , 64
        if i < 1 : res = -1 : goto *@f
 
        n = i
 
        dim _value  , n+2
        dim _next   , n+2
 
        repeat n+1
            _next(cnt) = cnt+1
        loop
        _next(n+1)  = -1
 
        head        = 0
        tail        = head
        new         = _next(tail)
 
        res         = n
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストに要素を挿入する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_addlru int i
 
        if n = 0 : res = -1 : goto *@f
 
        ; 挿入位置を求める
        q = head
        p = _next(head)
 
        repeat
            if (p = new) | (i = _value(p)) : break
            q = p
            p = _next(p)
        loop
 
        ; リストがいっぱい、もしくは無効なリスト
        if _next(p) = -1 : res = -1 : goto *@f
 
        _value(p)   = i     ; ダミー
        if p = new : tail = _next(tail)
 
        if p ! tail{
            _next(q)    = _next(p)
            _next(p)    = _next(tail)
            _next(tail) = p
        }
 
        tail    = p
        new     = _next(tail)
 
        ; 挿入した直前の要素のインデックス（無意味）
        res = q
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストの要素を削除する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_del int i
        ; 空のリスト
        if head = tail : res = -1 : goto *@f
 
        ; 削除位置を求める
        q = head
        p = _next(head)
 
        repeat
            if (p = new) | (_value(p) = i) : break
            q = p
            p = _next(p)
        loop
 
        if p = new : res = -1 : goto *@f
 
        ; 末尾処理
        if p = tail{
            tail    = q
            new     = p
        }
        else{
            _next(q)    = _next(p)
            _next(p)    = _next(tail)
            _next(tail) = p
            new         = _next(tail)
        }
 
        ; 削除した要素のインデックス（無意味）
        res = p
*@
        return
 
    /*--------------------------------------------------------------------*
     *                    リンクリストの要素を表示する                    *
     *--------------------------------------------------------------------*/
    #deffunc SLink_disp
 
        p = _next(head)
        s = "[ "
        repeat
            if p = new : res = cnt : break
            s += "" + _value(p) + " "
            p = _next(p)
        loop
        s += "]" + ":" + res + "/" + n
        mes s
        return 
#global
 
/******************************************************************************
 *                           Ｓ　Ａ　Ｍ　Ｐ　Ｌ　Ｅ                           *
 ******************************************************************************/
 
#define LISTSIZE    6
    font "ＭＳ ゴシック",12
    randomize
    cmd = ""
    input cmd,,,3
    SLink_init LISTSIZE
    if stat = -1{
        dialog "リストの初期化に失敗しました．",1,"終了確認" : end
    }
 
    onkey gosub *enter
    stop
 
*enter
    if iparam ! 13 : goto *@f
 
    ; 入力ボックスチェック
    getstr num,cmd,1
    if num = ""{
        cmd = "" : objprm 0,cmd
        goto *@f
    }
 
    num = int(num)
 
    c = peek(cmd,0)
 
    switch c
        case '+' :  SLink_addlru num
                    if stat ! -1{
                        title " "+num+" を挿入しました．"
                        SLink_disp
                    }
                    else{
                        title "リストがいっぱいです．"
                    }
                    swbreak
        case '-' :  SLink_del num
                    if stat ! -1{
                        title " "+num+" を削除しました．"
                        SLink_disp
                    }
                    else{
                        title "リストが空です．"
                    }
                    swbreak
    swend
    cmd = "" : objprm 0,cmd
*@
    return