1: //========================================================================================
     2: //  TickerQueue.java
     3: //    en:Sort of a simple task scheduler
     4: //    ja:簡易タスクスケジューラのようなもの
     5: //  Copyright (C) 2003-2019 Makoto Kamada
     6: //
     7: //  This file is part of the XEiJ (X68000 Emulator in Java).
     8: //  You can use, modify and redistribute the XEiJ if the conditions are met.
     9: //  Read the XEiJ License for more details.
    10: //  https://stdkmd.net/xeij/
    11: //========================================================================================
    12: 
    13: package xeij;
    14: 
    15: import java.lang.*;  //Boolean,Character,Class,Comparable,Double,Exception,Float,IllegalArgumentException,Integer,InterruptedException,Long,Math,Number,Object,Runnable,SecurityException,String,StringBuilder,System
    16: import java.util.*;  //ArrayList,Arrays,Calendar,GregorianCalendar,HashMap,Map,Map.Entry,TimeZone,Timer,TimerTask,TreeMap
    17: 
    18: public class TickerQueue {
    19: 
    20:   public static final boolean TKQ_USE_TICKER0 = true;  //true=tkqTicker0を使う
    21:   public static final int TKQ_MASK = 255;  //キューに入れられるティッカーの数の上限。2の累乗-1に限る
    22: 
    23: 
    24:   //class Ticker
    25:   //  ティッカー
    26:   public static class Ticker {
    27:     public Ticker () {
    28:       time = Long.MAX_VALUE;  //キューに入っていない
    29:     }
    30:     protected long time;  //このティッカーを呼び出す時刻。キューに入っていないときLong.MAX_VALUE。番兵はLong.MAX_VALUE。外部から書き換えないこと
    31:     //  tickが呼び出された時点でthisはキューから削除されている
    32:     //  tickの中でtkqAddを呼び出してthisまたは他のティッカーをキューに追加できる
    33:     //  tickの中でtkqRemoveを呼び出して他のティッカーをキューから削除できる
    34:     //  tickの中でtkqRemoveAllを呼び出してすべてのティッカーをキューから削除できる
    35:     //  tickの中でtkqRunを呼び出してはならない
    36:     protected void tick () {
    37:     }
    38:   }  //class Ticker
    39: 
    40: 
    41:   //tkqArray
    42:   //  tkqArray[tkqHead]が先頭(timeが最小)
    43:   //  tkqArray[tkqTail-1&TKQ_MASK]が末尾(timeが最大)
    44:   //  tkqArray[tkqTail]はtimeがLong.MAX_VALUEの番兵
    45:   //  先頭から末尾までtimeの昇順(timeが同じときは追加順)で隙間なく並べる
    46:   //  配列の末尾で先頭に折り返す
    47:   //  未使用領域は不定
    48:   public static final Ticker[] tkqArray = new Ticker[TKQ_MASK + 1];  //キューに入っているティッカーの配列
    49:   public static int tkqHead;  //先頭の位置。キューが空のときはtkqHead==tkqTailすなわち番兵の位置
    50:   public static int tkqTail;  //末尾の直後の位置すなわち番兵の位置
    51:   public static Ticker tkqTicker0;  //先頭のティッカー。tkqArray[tkqHead]のコピー。キューが空のときは番兵
    52:   public static long tkqTime0;  //先頭のtime。tkqArray[tkqHead].timeのコピー。キューが空のときは番兵のtimeすなわちLong.MAX_VALUE
    53: 
    54: 
    55:   //tkqInit ()
    56:   //  初期化
    57:   public static void tkqInit () {
    58:     //tkqArray = new Ticker[TKQ_MASK + 1];
    59:     if (TKQ_USE_TICKER0) {
    60:       tkqTicker0 = tkqArray[tkqTail = tkqHead = 0] = new Ticker ();  //先頭の位置と番兵の位置と番兵と先頭のティッカー
    61:     } else {
    62:       tkqArray[tkqTail = tkqHead = 0] = new Ticker ();  //先頭の位置と番兵の位置と番兵と先頭のティッカー
    63:     }
    64:     tkqTime0 = tkqTicker0.time = Long.MAX_VALUE;  //番兵のtimeと先頭のtime
    65:   }
    66: 
    67:   //tkqRun (currentTime)
    68:   //  先頭のティッカーを取り除いてからtickを呼び出すことをtimeがcurrentTime以下のティッカーがなくなるまで繰り返す
    69:   //  currentTime==Long.MAX_VALUEは指定不可
    70:   public static void tkqRun (long currentTime) {
    71:     if (TKQ_USE_TICKER0) {
    72:       while (tkqTime0 <= currentTime) {  //timeがcurrentTime以下のティッカーがある
    73:         Ticker ticker0 = tkqTicker0;  //先頭のティッカー
    74:         tkqTime0 = (tkqTicker0 = tkqArray[tkqHead = tkqHead + 1 & TKQ_MASK]).time;  //次回の先頭の位置と次回の先頭のティッカーと次回の先頭のtime。キューが空になるとtkqTime0が番兵のtimeのLong.MAX_VALUEになって止まる
    75:         ticker0.time = Long.MAX_VALUE;  //キューに入っていない
    76:         ticker0.tick ();  //先頭のtickを呼び出す。ここでtkqAddやtkqRemoveが呼び出される場合があるのでその前にキューを更新しておく
    77:       }
    78:     } else {
    79:       if (tkqTime0 <= currentTime) {  //timeがcurrentTime以下のティッカーがある
    80:         Ticker nextTicker0 = tkqArray[tkqHead];  //次回の先頭のティッカー
    81:         do {
    82:           Ticker ticker0 = nextTicker0;  //先頭のティッカー
    83:           tkqTime0 = (nextTicker0 = tkqArray[tkqHead = tkqHead + 1 & TKQ_MASK]).time;  //次回の先頭の位置と次回の先頭のティッカーと次回の先頭のtime。キューが空になるとtkqTime0が番兵のtimeのLong.MAX_VALUEになって止まる
    84:           ticker0.time = Long.MAX_VALUE;  //キューに入っていない
    85:           ticker0.tick ();  //先頭のtickを呼び出す。ここでtkqAddやtkqRemoveが呼び出される場合があるのでその前にキューを更新しておく
    86:         } while (tkqTime0 <= currentTime);  //timeがcurrentTime以下のティッカーがある
    87:       }
    88:     }
    89:   }  //tkqRun(long)
    90: 
    91:   //tkqAdd (newTicker, newTime)
    92:   //  ティッカーをキューに追加する
    93:   //  既にキューに入っているときは取り除いてからから入れ直す
    94:   public static void tkqAdd (Ticker newTicker, long newTime) {
    95:     if (newTicker.time != Long.MAX_VALUE) {  //既にキューに入っている
    96:       tkqRemove (newTicker);  //取り除く
    97:     }
    98:     newTicker.time = newTime;
    99:     int count = tkqTail - tkqHead & TKQ_MASK;  //キューに入っているティッカーの数。番兵を含まない
   100:     if (count == TKQ_MASK) {  //キューが一杯で追加できない
   101:       throw new Error ("tkqAdd: overflow");
   102:     }
   103:     if (count == 0 || newTime < tkqTime0) {  //先頭に追加するとき
   104:       //  timeがnewTimeと等しいか小さいティッカーが1つもない
   105:       if (TKQ_USE_TICKER0) {
   106:         tkqTicker0 = tkqArray[tkqHead = tkqHead - 1 & TKQ_MASK] = newTicker;  //先頭の位置と先頭のティッカー
   107:       } else {
   108:         tkqArray[tkqHead = tkqHead - 1 & TKQ_MASK] = newTicker;  //先頭の位置と先頭のティッカー
   109:       }
   110:       tkqTime0 = newTime;  //先頭のtime
   111:       return;
   112:     }
   113:     //先頭に追加しないとき
   114:     //  timeがnewTimeと等しいか小さいティッカーが少なくとも1つある
   115:     //  newTime==tkqTime0のときも追加順の制約で追加する位置は先頭にならない
   116:     //timeがnewTimeよりも大きい最小を探す
   117:     int l = 0;
   118:     int r = count;
   119:     while (l < r) {
   120:       int m = l + r >> 1;
   121:       if (tkqArray[m + tkqHead & TKQ_MASK].time <= newTime) {
   122:         l = m + 1;
   123:       } else {
   124:         r = m;
   125:       }
   126:     }
   127:     //  l=timeがnewTimeよりも大きい最小のオフセット。すべて大きければ0、すべて小さいか等しければcount
   128:     //newTickerを入れるための隙間を空ける
   129:     //  timeがnewTimeよりも大きい最小が前半にあるときは小さいか等しい方を手前に、後半にあるときは大きい方を後ろにずらす
   130:     if (l << 1 < count) {  //timeがnewTimeよりも大きい最小が前半にあるとき
   131:       l = l - 1 + tkqHead & TKQ_MASK;  //隙間を空ける位置。最後の移動元。timeがnewTimeよりも大きい最小のティッカーの直前の位置
   132:       r = tkqHead = tkqHead - 1 & TKQ_MASK;  //先頭の直前の位置。最初の移動先
   133:       while (l != r) {  //最後の移動元が移動先になる前に終了する
   134:         int m = r + 1 & TKQ_MASK;  //移動元。移動先の直後
   135:         tkqArray[r] = tkqArray[m];  //移動元から移動先へ、隙間を空ける位置に近い大きい方から先頭に近い小さい方へ移す
   136:         r = m;  //今回の移動元にできた隙間を次回の移動先にする。先頭に近い小さい方から隙間を空ける位置に近い大きい方へ進む
   137:       }
   138:     } else {  //timeがnewTimeよりも大きい最小が後半にあるとき
   139:       l = l + tkqHead & TKQ_MASK;  //隙間を空ける位置。最後の移動元。timeがnewTimeよりも大きい最小のティッカーの位置
   140:       r = tkqTail = tkqTail + 1 & TKQ_MASK;  //番兵の直後の位置。最初の移動先
   141:       while (l != r) {  //最後の移動元が移動先になる前に終了する
   142:         int m = r - 1 & TKQ_MASK;  //移動元。移動先の直前
   143:         tkqArray[r] = tkqArray[m];  //移動元から移動先へ、隙間を空ける位置に近い小さい方から番兵に近い大きい方へ移す
   144:         r = m;  //今回の移動元にできた隙間を次回の移動先にする。番兵に近い大きい方から隙間を空ける位置に近い小さい方へ進む
   145:       }
   146:     }
   147:     //できた隙間にnewTickerを入れる
   148:     //  追加する位置が先頭ではないのでtkqTicker0とtkqTime0は変化しない
   149:     tkqArray[l] = newTicker;
   150:   }  //tkqAdd(Ticker,long)
   151: 
   152:   //tkqRemove (oldTicker)
   153:   //  ティッカーをキューから削除する
   154:   //  キューに入っていないときは何もしない
   155:   public static void tkqRemove (Ticker oldTicker) {
   156:     long oldTime = oldTicker.time;
   157:     if (oldTime == Long.MAX_VALUE) {  //キューに入っていない
   158:       return;
   159:     }
   160:     oldTicker.time = Long.MAX_VALUE;
   161:     if (tkqHead == tkqTail) {  //キューが空
   162:       return;
   163:     }
   164:     if (TKQ_USE_TICKER0) {
   165:       if (tkqTicker0 == oldTicker) {  //先頭から削除するとき
   166:         tkqTime0 = (tkqTicker0 = tkqArray[tkqHead = tkqHead + 1 & TKQ_MASK]).time;  //先頭の位置と先頭のティッカーと先頭のtime
   167:         return;
   168:       }
   169:     } else {
   170:       if (tkqArray[tkqHead] == oldTicker) {  //先頭から削除するとき
   171:         tkqTime0 = tkqArray[tkqHead = tkqHead + 1 & TKQ_MASK].time;  //先頭の位置と先頭のtime
   172:         return;
   173:       }
   174:     }
   175:     //先頭から削除しないとき
   176:     int count = tkqTail - tkqHead & TKQ_MASK;  //キューに入っているティッカーの数。番兵を含まない
   177:     //timeがoldTimeと等しいか大きい最小のティッカーを探す
   178:     int l = 0;
   179:     int r = count;
   180:     while (l < r) {
   181:       int m = l + r >> 1;
   182:       if (tkqArray[m + tkqHead & TKQ_MASK].time < oldTime) {
   183:         l = m + 1;
   184:       } else {
   185:         r = m;
   186:       }
   187:     }
   188:     //  l=timeがoldTimeと等しいか大きい最小のティッカーのオフセット。すべて等しいか大きければ0、すべて小さければcount
   189:     //oldTickerを探す
   190:     //  timeが等しいティッカーが複数あるときその中からoldTickerを探さなければならない
   191:     while (l < count && tkqArray[l + tkqHead & TKQ_MASK] != oldTicker) {
   192:       l++;
   193:     }
   194:     if (l == count) {  //見つからなかった
   195:       return;
   196:     }
   197:     //  l=oldTickerのオフセット。先頭は除外してあるので0ではない
   198:     //oldTickerを削除してできた隙間を詰める
   199:     //  oldTickerが前半にあるときは小さいか等しい方を後ろに、後半にあるときは等しいか大きい方を手前にずらす
   200:     if (l << 1 < count) {  //oldTickerが前半にあるとき
   201:       r = l + tkqHead & TKQ_MASK;  //詰める位置。最初の移動先
   202:       l = tkqHead & TKQ_MASK;  //先頭の位置。最後の移動元
   203:       tkqHead = tkqHead + 1 & TKQ_MASK;
   204:       while (l != r) {  //最後の移動元が移動先になる前に終了する
   205:         int m = r - 1 & TKQ_MASK;  //移動元。移動先の直前
   206:         tkqArray[r] = tkqArray[m];  //移動元から移動先へ、先頭に近い小さい方から詰める位置に近い大きい方へ移す
   207:         r = m;  //今回の移動元にできた隙間を次回の移動先にする。詰める位置に近い大きい方から先頭に近い小さい方へ進む
   208:       }
   209:     } else {  //oldTickerが後半にあるとき
   210:       r = l + tkqHead & TKQ_MASK;  //詰める位置。最初の移動先
   211:       l = tkqTail & TKQ_MASK;  //番兵の位置。最後の移動元
   212:       tkqTail = tkqTail - 1 & TKQ_MASK;
   213:       while (l != r) {  //最後の移動元が移動先になる前に終了する
   214:         int m = r + 1 & TKQ_MASK;  //移動元。移動先の直後
   215:         tkqArray[r] = tkqArray[m];  //移動元から移動先へ、番兵に近い大きい方から詰める位置に近い小さい方へ移す
   216:         r = m;  //今回の移動元にできた隙間を次回の移動先にする。詰める位置に近い小さい方から番兵に近い大きい方へ進む
   217:       }
   218:     }
   219:     //  削除する位置が先頭ではないのでtkqTicker0とtkqTime0は変化しない
   220:   }  //tkqRemove(Ticker)
   221: 
   222:   //tkqRemoveAll ()
   223:   //  すべてのティッカーをキューから削除する
   224:   public static void tkqRemoveAll () {
   225:     while (tkqHead != tkqTail) {
   226:       if (TKQ_USE_TICKER0) {
   227:         tkqRemove (tkqTicker0);
   228:       } else {
   229:         tkqRemove (tkqArray[tkqHead]);
   230:       }
   231:     }
   232:   }  //tkqRemoveAll()
   233: 
   234: 
   235:   //テスト
   236: 
   237:   public static class TestTicker extends Ticker {
   238:     private int value;
   239:     private TestTicker (int value) {
   240:       this.value = value;
   241:     }
   242:     @Override protected void tick () {
   243:       System.out.print (time);
   244:       System.out.print ('(');
   245:       System.out.print (value);
   246:       System.out.print (')');
   247:       System.out.print (' ');
   248:     }
   249:   }  //class TestTicker
   250: 
   251:   public static void tkqTest () {
   252:     tkqInit ();
   253:     TestTicker[] tickers = new TestTicker[100];
   254:     for (int i = 0; i < 100; i++) {
   255:       tickers[i] = new TestTicker (i);
   256:     }
   257:     //正順に追加
   258:     System.out.println ("test 1");
   259:     for (int i = 0; i < 100; i++) {
   260:       tkqAdd (tickers[i], i);
   261:     }
   262:     tkqRun (100);
   263:     System.out.println ();
   264:     //逆順に追加
   265:     System.out.println ("test 2");
   266:     for (int i = 100 - 1; i >= 0; i--) {
   267:       tkqAdd (tickers[i], i);
   268:     }
   269:     tkqRun (100);
   270:     System.out.println ();
   271:     //ランダムに追加
   272:     System.out.println ("test 3");
   273:     for (int i = 0; i < 100; i++) {
   274:       tkqAdd (tickers[i], (int) (Math.random () * 100));
   275:     }
   276:     tkqRun (100);
   277:     System.out.println ();
   278:     //偶数だけ削除
   279:     System.out.println ("test 4");
   280:     for (int i = 0; i < 100; i++) {
   281:       tkqAdd (tickers[i], i);
   282:     }
   283:     for (int i = 0; i < 100; i += 2) {
   284:       tkqRemove (tickers[i]);
   285:     }
   286:     tkqRun (100);
   287:     System.out.println ();
   288:     //奇数だけ削除
   289:     System.out.println ("test 5");
   290:     for (int i = 0; i < 100; i++) {
   291:       tkqAdd (tickers[i], i);
   292:     }
   293:     for (int i = 1; i < 100; i += 2) {
   294:       tkqRemove (tickers[i]);
   295:     }
   296:     tkqRun (100);
   297:     System.out.println ();
   298:     //50個入れた状態で50個追加して50個消費することを10回繰り返す
   299:     {
   300:       System.out.println ("test 6");
   301:       int t = 0;
   302:       for (int i = 0; i < 50; i++) {
   303:         tkqAdd (tickers[i], t++);
   304:       }
   305:       for (int j = 0; j < 5; j++) {
   306:         for (int i = 0; i < 50; i++) {
   307:           tkqAdd (tickers[50 + i], t++);
   308:         }
   309:         tkqRun (t - 50 - 1);
   310:         System.out.println ();
   311:         for (int i = 0; i < 50; i++) {
   312:           tkqAdd (tickers[i], t++);
   313:         }
   314:         tkqRun (t - 50 - 1);
   315:         System.out.println ();
   316:       }
   317:     }
   318:   }  //tkqTest ()
   319: 
   320: 
   321: }  //class TickerQueue
   322: 
   323: 
   324: