import java.util.* ;
class Program {
public static void main
( String [ ] args
) { String [ ] data
= { "red" ,
"green" ,
"blue" ,
"red" ,
"yellow" ,
"red" ,
"black" ,
"red" ,
"blue" ,
"white" ,
"green" } ; final int size = 4 ;
System .
out .
println ( "\n ##### Teste com FIFO #####" ) ; fifo( size, data) ;
System .
out .
println ( "\n ##### Teste com LRU #####" ) ; lru( size, data) ;
System .
out .
println ( "\n ##### Teste com LFU #####" ) ; lfu( size, data) ;
}
static void fifo
( final int size,
final String [ ] data
) { ArrayDeque< String> cache = new ArrayDeque<> ( ) ;
int misses = 0 , hit = 0 , access = 0 ;
if ( ! cache.contains ( d) ) {
if ( cache.size ( ) < size) {
cache.add ( d) ;
} else {
cache.remove ( ) ;
cache.add ( d) ;
}
misses++;
} else {
hit++;
}
access++;
System .
out .
printf ( "access: %d, hit: %d, misses: %d >>> %s\n [ " , access, hit, misses, d
) ;
}
}
static void lru
( final int size,
final String [ ] data
) { ArrayDeque< String> cache = new ArrayDeque<> ( ) ;
int misses = 0 , hit = 0 , access = 0 ;
if ( ! cache.contains ( d) ) {
if ( cache.size ( ) < size) {
cache.add ( d) ;
} else {
cache.remove ( ) ;
cache.add ( d) ;
}
misses++;
} else {
cache.remove ( d) ;
cache.add ( d) ;
hit++;
}
access++;
System .
out .
printf ( "access: %d, hit: %d, misses: %d >>> %s\n [ " , access, hit, misses, d
) ;
}
}
static void lfu
( final int size,
final String [ ] data
) { class DataWrapper implements Comparable< DataWrapper> {
private int frequency;
this .data = data;
incrementFrequency( ) ;
}
void incrementFrequency( ) {
this .frequency ++;
}
@Override
public boolean equals
( Object o
) { DataWrapper dw = ( DataWrapper) o;
return dw.data .equals ( this .data ) ;
}
@Override
public int compareTo( DataWrapper o) {
if ( this .frequency > o.frequency )
return 1 ;
else if ( this .frequency < o.frequency )
return - 1 ;
else
return 0 ;
}
@Override
return data;
}
}
List< DataWrapper> cache = new ArrayList<> ( ) ;
List< DataWrapper> temp = new ArrayList<> ( ) ;
int misses = 0 , hit = 0 , access = 0 ;
for ( String d
: data
) temp.
add ( new DataWrapper
( d
) ) ;
for ( DataWrapper d : temp) {
if ( ! cache.contains ( d) ) {
if ( cache.size ( ) < size) {
cache.add ( d) ;
} else {
cache.remove ( 0 ) ;
cache.add ( d) ;
}
misses++;
} else {
cache.get ( cache.indexOf ( d) ) .incrementFrequency ( ) ;
hit++;
}
access++;
System .
out .
printf ( "access: %d, hit: %d, misses: %d >>> %s\n [ " , access, hit, misses, d
) ;
for ( DataWrapper x
: cache
) System .
out .
printf ( "%s(%d) " , x, x.
frequency ) ;
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgUHJvZ3JhbSB7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgU3RyaW5nW10gZGF0YSA9IHsicmVkIiwgImdyZWVuIiwgImJsdWUiLCAicmVkIiwgInllbGxvdyIsICJyZWQiLCAiYmxhY2siLCAicmVkIiwgImJsdWUiLCAid2hpdGUiLCAiZ3JlZW4ifTsKICAgICAgICBmaW5hbCBpbnQgc2l6ZSA9IDQ7CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiXG4jIyMjIyBUZXN0ZSBjb20gRklGTyAjIyMjIyIpOwogICAgICAgIGZpZm8oc2l6ZSwgZGF0YSk7CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiXG4jIyMjIyBUZXN0ZSBjb20gTFJVICMjIyMjIik7CiAgICAgICAgbHJ1KHNpemUsIGRhdGEpOwoKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlxuIyMjIyMgVGVzdGUgY29tIExGVSAjIyMjIyIpOwogICAgICAgIGxmdShzaXplLCBkYXRhKTsKICAgIH0KCiAgICBzdGF0aWMgdm9pZCBmaWZvKGZpbmFsIGludCBzaXplLCBmaW5hbCBTdHJpbmdbXSBkYXRhKSB7CiAgICAgICAgQXJyYXlEZXF1ZTxTdHJpbmc+IGNhY2hlID0gbmV3IEFycmF5RGVxdWU8PigpOwoKICAgICAgICBpbnQgbWlzc2VzID0gMCwgaGl0ID0gMCwgYWNjZXNzID0gMDsKCiAgICAgICAgZm9yIChTdHJpbmcgZCA6IGRhdGEpIHsKICAgICAgICAgICAgaWYgKCFjYWNoZS5jb250YWlucyhkKSkgewogICAgICAgICAgICAgICAgaWYgKGNhY2hlLnNpemUoKSA8IHNpemUpIHsKICAgICAgICAgICAgICAgICAgICBjYWNoZS5hZGQoZCk7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIGNhY2hlLnJlbW92ZSgpOwogICAgICAgICAgICAgICAgICAgIGNhY2hlLmFkZChkKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBtaXNzZXMrKzsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGhpdCsrOwogICAgICAgICAgICB9CgogICAgICAgICAgICBhY2Nlc3MrKzsKCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCJhY2Nlc3M6ICVkLCBoaXQ6ICVkLCBtaXNzZXM6ICVkID4+PiAlc1xuWyAiLCBhY2Nlc3MsIGhpdCwgbWlzc2VzLCBkKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGZvciAoU3RyaW5nIHggOiBjYWNoZSkgU3lzdGVtLm91dC5wcmludCh4ICsgIiAiKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiXSIpOwogICAgICAgIH0KICAgIH0KCiAgICBzdGF0aWMgdm9pZCBscnUoZmluYWwgaW50IHNpemUsIGZpbmFsIFN0cmluZ1tdIGRhdGEpIHsKICAgICAgICBBcnJheURlcXVlPFN0cmluZz4gY2FjaGUgPSBuZXcgQXJyYXlEZXF1ZTw+KCk7CgogICAgICAgIGludCBtaXNzZXMgPSAwLCBoaXQgPSAwLCBhY2Nlc3MgPSAwOwoKICAgICAgICBmb3IgKFN0cmluZyBkIDogZGF0YSkgewogICAgICAgICAgICBpZiAoIWNhY2hlLmNvbnRhaW5zKGQpKSB7CiAgICAgICAgICAgICAgICBpZiAoY2FjaGUuc2l6ZSgpIDwgc2l6ZSkgewogICAgICAgICAgICAgICAgICAgIGNhY2hlLmFkZChkKTsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgY2FjaGUucmVtb3ZlKCk7CiAgICAgICAgICAgICAgICAgICAgY2FjaGUuYWRkKGQpOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIG1pc3NlcysrOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgY2FjaGUucmVtb3ZlKGQpOwogICAgICAgICAgICAgICAgY2FjaGUuYWRkKGQpOwoKICAgICAgICAgICAgICAgIGhpdCsrOwogICAgICAgICAgICB9CgogICAgICAgICAgICBhY2Nlc3MrKzsKCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCJhY2Nlc3M6ICVkLCBoaXQ6ICVkLCBtaXNzZXM6ICVkID4+PiAlc1xuWyAiLCBhY2Nlc3MsIGhpdCwgbWlzc2VzLCBkKTsKCiAgICAgICAgICAgIGZvciAoU3RyaW5nIHggOiBjYWNoZSkgU3lzdGVtLm91dC5wcmludCh4ICsgIiAiKTsKCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiXSIpOwogICAgICAgIH0KICAgIH0KCiAgICBzdGF0aWMgdm9pZCBsZnUoZmluYWwgaW50IHNpemUsIGZpbmFsIFN0cmluZ1tdIGRhdGEpIHsKICAgICAgICBjbGFzcyBEYXRhV3JhcHBlciBpbXBsZW1lbnRzIENvbXBhcmFibGU8RGF0YVdyYXBwZXI+IHsKICAgICAgICAgICAgcHJpdmF0ZSBmaW5hbCBTdHJpbmcgZGF0YTsKICAgICAgICAgICAgcHJpdmF0ZSBpbnQgZnJlcXVlbmN5OwoKICAgICAgICAgICAgRGF0YVdyYXBwZXIoU3RyaW5nIGRhdGEpIHsKICAgICAgICAgICAgICAgIHRoaXMuZGF0YSA9IGRhdGE7CiAgICAgICAgICAgICAgICBpbmNyZW1lbnRGcmVxdWVuY3koKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgdm9pZCBpbmNyZW1lbnRGcmVxdWVuY3koKSB7CiAgICAgICAgICAgICAgICB0aGlzLmZyZXF1ZW5jeSsrOwogICAgICAgICAgICB9CgogICAgICAgICAgICBAT3ZlcnJpZGUKICAgICAgICAgICAgcHVibGljIGJvb2xlYW4gZXF1YWxzKE9iamVjdCBvKSB7CiAgICAgICAgICAgICAgICBEYXRhV3JhcHBlciBkdyA9IChEYXRhV3JhcHBlcikgbzsKICAgICAgICAgICAgICAgIHJldHVybiBkdy5kYXRhLmVxdWFscyh0aGlzLmRhdGEpOwogICAgICAgICAgICB9CgogICAgICAgICAgICBAT3ZlcnJpZGUKICAgICAgICAgICAgcHVibGljIGludCBjb21wYXJlVG8oRGF0YVdyYXBwZXIgbykgewogICAgICAgICAgICAgICAgaWYgKHRoaXMuZnJlcXVlbmN5ID4gby5mcmVxdWVuY3kpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgICAgICAgICBlbHNlIGlmICh0aGlzLmZyZXF1ZW5jeSA8IG8uZnJlcXVlbmN5KQogICAgICAgICAgICAgICAgICAgIHJldHVybiAtMTsKICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgQE92ZXJyaWRlCiAgICAgICAgICAgIHB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CiAgICAgICAgICAgICAgICByZXR1cm4gZGF0YTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgTGlzdDxEYXRhV3JhcHBlcj4gY2FjaGUgPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICBMaXN0PERhdGFXcmFwcGVyPiB0ZW1wID0gbmV3IEFycmF5TGlzdDw+KCk7CgogICAgICAgIGludCBtaXNzZXMgPSAwLCBoaXQgPSAwLCBhY2Nlc3MgPSAwOwoKICAgICAgICBmb3IgKFN0cmluZyBkIDogZGF0YSkgdGVtcC5hZGQobmV3IERhdGFXcmFwcGVyKGQpKTsKCiAgICAgICAgZm9yIChEYXRhV3JhcHBlciBkIDogdGVtcCkgewogICAgICAgICAgICBpZiAoIWNhY2hlLmNvbnRhaW5zKGQpKSB7CiAgICAgICAgICAgICAgICBpZiAoY2FjaGUuc2l6ZSgpIDwgc2l6ZSkgewogICAgICAgICAgICAgICAgICAgIGNhY2hlLmFkZChkKTsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgY2FjaGUucmVtb3ZlKDApOwogICAgICAgICAgICAgICAgICAgIGNhY2hlLmFkZChkKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBtaXNzZXMrKzsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGNhY2hlLmdldChjYWNoZS5pbmRleE9mKGQpKS5pbmNyZW1lbnRGcmVxdWVuY3koKTsKICAgICAgICAgICAgICAgIGhpdCsrOwogICAgICAgICAgICB9CgogICAgICAgICAgICBDb2xsZWN0aW9ucy5zb3J0KGNhY2hlKTsKICAgICAgICAgICAgYWNjZXNzKys7CgogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiYWNjZXNzOiAlZCwgaGl0OiAlZCwgbWlzc2VzOiAlZCA+Pj4gJXNcblsgIiwgYWNjZXNzLCBoaXQsIG1pc3NlcywgZCk7CgoJZm9yIChEYXRhV3JhcHBlciB4IDogY2FjaGUpIFN5c3RlbS5vdXQucHJpbnRmKCIlcyglZCkgIiwgeCwgeC5mcmVxdWVuY3kpOwoKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJdIik7CiAgICAgICAgfQogICAgfQp9
stdout
##### Teste com FIFO #####
access: 1, hit: 0, misses: 1 >>> red
[ red ]
access: 2, hit: 0, misses: 2 >>> green
[ red green ]
access: 3, hit: 0, misses: 3 >>> blue
[ red green blue ]
access: 4, hit: 1, misses: 3 >>> red
[ red green blue ]
access: 5, hit: 1, misses: 4 >>> yellow
[ red green blue yellow ]
access: 6, hit: 2, misses: 4 >>> red
[ red green blue yellow ]
access: 7, hit: 2, misses: 5 >>> black
[ green blue yellow black ]
access: 8, hit: 2, misses: 6 >>> red
[ blue yellow black red ]
access: 9, hit: 3, misses: 6 >>> blue
[ blue yellow black red ]
access: 10, hit: 3, misses: 7 >>> white
[ yellow black red white ]
access: 11, hit: 3, misses: 8 >>> green
[ black red white green ]
##### Teste com LRU #####
access: 1, hit: 0, misses: 1 >>> red
[ red ]
access: 2, hit: 0, misses: 2 >>> green
[ red green ]
access: 3, hit: 0, misses: 3 >>> blue
[ red green blue ]
access: 4, hit: 1, misses: 3 >>> red
[ green blue red ]
access: 5, hit: 1, misses: 4 >>> yellow
[ green blue red yellow ]
access: 6, hit: 2, misses: 4 >>> red
[ green blue yellow red ]
access: 7, hit: 2, misses: 5 >>> black
[ blue yellow red black ]
access: 8, hit: 3, misses: 5 >>> red
[ blue yellow black red ]
access: 9, hit: 4, misses: 5 >>> blue
[ yellow black red blue ]
access: 10, hit: 4, misses: 6 >>> white
[ black red blue white ]
access: 11, hit: 4, misses: 7 >>> green
[ red blue white green ]
##### Teste com LFU #####
access: 1, hit: 0, misses: 1 >>> red
[ red(1) ]
access: 2, hit: 0, misses: 2 >>> green
[ red(1) green(1) ]
access: 3, hit: 0, misses: 3 >>> blue
[ red(1) green(1) blue(1) ]
access: 4, hit: 1, misses: 3 >>> red
[ green(1) blue(1) red(2) ]
access: 5, hit: 1, misses: 4 >>> yellow
[ green(1) blue(1) yellow(1) red(2) ]
access: 6, hit: 2, misses: 4 >>> red
[ green(1) blue(1) yellow(1) red(3) ]
access: 7, hit: 2, misses: 5 >>> black
[ blue(1) yellow(1) black(1) red(3) ]
access: 8, hit: 3, misses: 5 >>> red
[ blue(1) yellow(1) black(1) red(4) ]
access: 9, hit: 4, misses: 5 >>> blue
[ yellow(1) black(1) blue(2) red(4) ]
access: 10, hit: 4, misses: 6 >>> white
[ black(1) white(1) blue(2) red(4) ]
access: 11, hit: 4, misses: 7 >>> green
[ white(1) green(1) blue(2) red(4) ]