compile("com.google.guava:guava:20.0")

class SequenceNode<T> {
    int sequence;
    double key;
    T value;
    int maxLength;
    SequenceNode<T> next;

    SequenceNode(T value,int max,int sequence,double key){
        this.value = value;
        this.maxLength = max;
        this.sequence = sequence;
        this.key = key;
    }

    SequenceNode<T> insertAndOrder(T poi,double key) {
        //1. new node is less than head
        if(this.key >= key){
            //if full , then will remove last one 
            if(isFull()){
                removeLast();
            }
            SequenceNode<T> newHead = new SequenceNode<T>(poi,maxLength,1,key);
            newHead.next = this;
            autoIncreaseSequence(newHead);
            return newHead;
        }else{
            SequenceNode<T> insertPoint = findInsertPoint(key);
            if(insertPoint != null){
                if(isFull()){
                    removeLast();
                }
                SequenceNode<T> newNode = new SequenceNode<T>(poi,maxLength,insertPoint.sequence+1,key);
                newNode.next = insertPoint.next;
                insertPoint.next = newNode;
                autoIncreaseSequence(newNode);
            }
        }

        return this;
    }

    private SequenceNode<T> findInsertPoint(double key) {
        //this is head, just skip. begin to compare from next node
        SequenceNode<T> current = this;
        SequenceNode<T> before = null;
        while(current.next != null){
            before = current;
            current = current.next;
            if(current.key >= key){
                return before;
            }
        }

        if(!isFull()){
            return current;
        }
        return null;
    }

    private void autoIncreaseSequence(SequenceNode<T> point) {
        SequenceNode<T> current = point.next ;
        while(current != null){
            current.sequence =  current.sequence+1;
            current = current.next;
        }
    }

    private boolean isFull() {
        return getLastSequence() == maxLength;
    }

    private void removeLast() {
        SequenceNode<T> current = this;
        SequenceNode<T> secondLast = null;
        while(current.next != null){
            secondLast = current;
            current = current.next;
        }
        current = null;
        secondLast.next = null;
    }

    private int getLastSequence() {

        SequenceNode<T> last = this;
        while(last.next != null){
            last = last.next;
        }
        return last.sequence;
    }

    public int getSequence(){
        return this.sequence;
    }

    public T getVaue(){
        return value;
    }

    public List<T> convertToList(){
        List<T> list = new ArrayList<T>();
        SequenceNode<T> current = this;
        list.add(current.getVaue());
        while(current.next != null){
            current = current.next;
            list.add(current.getVaue());
        }
        return list;
    }
}