import java.util.concurrent.atomic.AtomicInteger;

public class Filter implements Lock
{
    final private ThreadLocal<Integer> THREAD_ID = new ThreadLocal<Integer>(){
        final private AtomicInteger id = new AtomicInteger(0);
        @Override
        protected Integer initialValue(){
            return id.getAndIncrement();
        }
    };

    final private AtomicInteger[] level ;
    final private AtomicInteger[] victim ;
    final private int n;
    
    public Filter (int n) {
        this.n = n;
        level = new AtomicInteger[n];
        victim = new AtomicInteger[n]; // use 1.. n-1
        for (int i = 0; i < n; i++) {
            level[i] = new AtomicInteger();
            victim[i] = new AtomicInteger();
        }
    }
    
    public void lock() {
        int me = THREAD_ID.get();
        for (int i=1 ; i<n ; i++) { //attempt level 1
            level[me].set(i);
            victim[i].set(me);
            // spin while conflicts exist
            while (exists(me,i)){};
        }
    }
    
    private boolean exists(int me, int i){
        for(int k=0 ; k<n ; k++){
            if(k==me)
                continue;
            
            if(level[k].get()>=i && victim[i].get()==me)
                return true;
        }
        return false;
    }
    
    public void unlock() {
        int me = THREAD_ID.get();
        level[me].set(0);
    }

}