package com.yueyue.wechat.common.utils.algorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

import org.springframework.util.CollectionUtils;

public class LRU {
	private static List<Integer> newList = new ArrayList<Integer>();
	private static ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
	private Integer theArray[];  
	private Integer back;            //定义队尾  
	private Integer currentSize;     //队列中存放元素个数  
	private Integer maxSize=5;       //队列中能存放元素的个数  

	public LRU(){  
		theArray=new Integer[maxSize];  
		back=0;  
		currentSize=0;  
	}  
	public void queue(List<Integer> list){
		if(!CollectionUtils.isEmpty(list)) {
			for(Integer i : list) {
				enQueue(i);
			}
		}else {
			System.out.println("<------------------ null ------------->");
		}
		  
	}  

	public void enQueue(Integer x){   //入队  
		beUsed(x);          //先判断是否已存在该页号，若存在，删除  
		if(currentSize<maxSize){  
			theArray[back]=x;  
			back++;     
			currentSize++;  
		}else if(currentSize==maxSize){
			deque.addLast(theArray[0]);
			newList.add(theArray[0]);
			System.out.println("theArray[0] == "+theArray[0]);
			//满了  
			for(Integer i=0;i<maxSize-1;i++){ 
				theArray[i]=theArray[i+1];  
			}  
			theArray[maxSize-1]=x;  
		}  
		for(Integer i=0;i<currentSize;i++){  
			System.out.print(theArray[i] + ",");  
		}  
		System.out.println();  
	}  
	public void beUsed(Integer x){        //判断是否已存在该页号,若存在，删除已有的  
		for(Integer i=0;i<currentSize;i++){  
			if(theArray[i]==x){  
				for(Integer j=i;j<currentSize-1;j++){  
					theArray[j]=theArray[j+1];  
				}  
				currentSize--;  
				back--;  
			}   
		}  
	}  
	public static void main(String[] args) {  
		LRU lru=new LRU();
		List<Integer> oldList = new ArrayList<Integer>();
		oldList.add(4);
		oldList.add(7);
		oldList.add(0);
		oldList.add(0);
		oldList.add(2);
		oldList.add(3);
		oldList.add(7);
		oldList.add(5);
		oldList.add(1);
		oldList.add(0);
		oldList.add(3);
		oldList.add(2);
		oldList.add(6);
		oldList.add(42);
		oldList.add(41);
		oldList.add(43);
		oldList.add(44);
		oldList.add(54);
		oldList.add(434);
		oldList.add(4);
		lru.queue(oldList);
		List<Integer> list = newList;
		System.out.println("---------------------分割线------------");
		System.out.println(list);
		System.out.println("---------------------分割线------------");
		System.out.println(deque);
		System.out.println(deque.poll());
		System.out.println(deque);
		
	}  

}