Subversion Repositories ao486

/*
 * Copyright (c) 2014, Aleksander Osman
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * * Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 * 
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
package ao486.utils;
 
public class TreePseudoLRU {
 
    static class Node {
        Node(Node l, Node r, int index) {
            this.l = l;
            this.r = r;
            this.index = index;
        }
 
        boolean left;
        int index;
 
        Node l, r;
    }
 
    static int find(Node n) {
        if(n.index != -1) return n.index;
 
        if(n.left) {
            n.left = false;
            return find(n.l);
        }
        else {
            n.left = true;
            return find(n.r);
        }
    }
 
    public static void main(String args[]) throws Exception {
 
        long vals[] = new long[32];
 
        long idx = 0;
 
        for(int i=0; i<vals.length; i++) vals[i] = idx++;
 
        Node n1 = new Node(new Node(null,null, 0), new Node(null,null, 1), -1);
        Node n2 = new Node(new Node(null,null, 2), new Node(null,null, 3), -1);
        Node n3 = new Node(new Node(null,null, 4), new Node(null,null, 5), -1);
        Node n4 = new Node(new Node(null,null, 6), new Node(null,null, 7), -1);
        Node n5 = new Node(new Node(null,null, 8), new Node(null,null, 9), -1);
        Node n6 = new Node(new Node(null,null, 10), new Node(null,null, 11), -1);
        Node n7 = new Node(new Node(null,null, 12), new Node(null,null, 13), -1);
        Node n8 = new Node(new Node(null,null, 14), new Node(null,null, 15), -1);
        Node n9 = new Node(new Node(null,null, 16), new Node(null,null, 17), -1);
        Node n10 = new Node(new Node(null,null, 18), new Node(null,null, 19), -1);
        Node n11 = new Node(new Node(null,null, 20), new Node(null,null, 21), -1);
        Node n12 = new Node(new Node(null,null, 22), new Node(null,null, 23), -1);
        Node n13 = new Node(new Node(null,null, 24), new Node(null,null, 25), -1);
        Node n14 = new Node(new Node(null,null, 26), new Node(null,null, 27), -1);
        Node n15 = new Node(new Node(null,null, 28), new Node(null,null, 29), -1);
        Node n16 = new Node(new Node(null,null, 30), new Node(null,null, 31), -1);
 
        Node m1 = new Node(n1,n2, -1);
        Node m2 = new Node(n3,n4, -1);
        Node m3 = new Node(n5,n6, -1);
        Node m4 = new Node(n7,n8, -1);
        Node m5 = new Node(n9,n10, -1);
        Node m6 = new Node(n11,n12, -1);
        Node m7 = new Node(n13,n14, -1);
        Node m8 = new Node(n15,n16, -1);
 
        Node o1 = new Node(m1,m2, -1);
        Node o2 = new Node(m3,m4, -1);
        Node o3 = new Node(m5,m6, -1);
        Node o4 = new Node(m7,m8, -1);
 
        Node p1 = new Node(o1,o2, -1);
        Node p2 = new Node(o3,o4, -1);
 
        Node q1 = new Node(p1,p2, -1);
 
        int found = 0;
        int count = 10000;
        for(int i=0; i<count; i++) {
            // find minimal
            long min = Long.MAX_VALUE;
            for(int j=0; j<vals.length; j++) if(vals[j] < min) min = vals[j];
 
            int index = find(q1);
            if(vals[index] == min) found++;
 
            vals[index] = idx++;
        }
 
        System.out.println((double)found / (double)count);
    }
 
}