/*
 * pList.java		v0.02
 *
 * A general purpose array based list,
 * with similar operations to Perl list.
 * 
 * (c) 2008, Alex S, Particle
 */

import java.util.*;

/**
 * A general purpose array based list,
 * with similar operations to Perl lists.
 *
 * O(1) push, pop, shift, unshift, etc.
 * supports negative indexes (just like perl).
 *
 * For an array based queue, push, then shift. (or unshift and then pop).
 */
public class pList {

    protected Object[] arr;
    protected int len,mask,start,end;

    /**
     * make an empty list of minimal length.
     */
    public pList(){
        arr = new Object[len=8];
        mask = len - 1;
        start = end = 0;
    }

    /**
     * simpler version of array-to-list
     */
    public pList(Object[] a){
        this(a,0,a.length);
    }

    /**
     * make a list from an array
     */
    public pList(Object[] a,int start,int length){
        this();
        for(int i=start;i<length;i++){
            push(a[i]);
        }
    }

    /**
     * make a list from java.util.Vector
     */
    public pList(Vector v){
        this();
        Enumeration e = v.elements();
        while(e.hasMoreElements()){
            push(e.nextElement());
        }
    }
    
    /**
     * copy constructor.
     */
    public pList(pList v){
        this();
        for(int i=0,j=v.size();i<j;i++){
            push(v.get(i));
        }
    }

    /**
     * dump keys,values into a list.
     */
    public pList(Hashtable h){
        this();
        Enumeration e = h.keys();
        while(e.hasMoreElements()){
            String s = (String)e.nextElement();
            push(s);
            push(h.get(s));
        }
    }

    /**
     * make a copy of this list (identical to copy constructor).
     */
    public pList dup(){
        return new pList(this);
    }

    /**
     * check if list is empty
     */
    public boolean isEmpty(){
        return start == end;
    }

    /**
     * get size of list
     */
    public int size(){
        return (end - start + len) & mask;
    }

    /**
     * clear the list (keeps capacity the same).
     */
    public void clear(){
        start = end = 0;
        for(int i=0;i<len;i++)
            arr[i] = null;
    }

    /**
     * ensures that we can store at least n elements.
     */
    private void ensureCapacity(int n){
        // do we want to grow this list?
        if(len <= n){
            // find the next size.
            int nsiz = len;
            while(nsiz <= n){
                nsiz <<= 1;     // shift left (ie: multiply by 2)
            }
            Object[] narr = new Object[nsiz];
            int oldsiz = size();

            // copy old elements into new array
            if(start < end){
                System.arraycopy(arr,start,narr,0,end - start);
            }else if(start > end){
                System.arraycopy(arr,start,narr,0,len - start);
                System.arraycopy(arr,0,narr,len - start,end);
            }
            start = 0;
            end = oldsiz;
            arr = narr;
            len = nsiz;
            mask = len - 1;
        }
    }
    
    /**
     * get an element at that location
     */
    public Object get(int n){
        int siz = size();
        if(n >= siz)
            return null;
        if(n >= 0){
            return arr[(start + n) & mask];
        }else if(n >= -siz){
            return arr[(end + n + len) & mask];
        }
        return null;
    }

    /**
     * push an element at the end of the list
     */
    public void push(Object o){
        ensureCapacity(size() + 1);
        arr[end] = o;
        end = (end + 1) & mask;
    }

    /**
     * remove element from top
     */
    public Object pop(){
        if(isEmpty())
            return null;
        end = (end - 1 + len) & mask;
        Object o = arr[end];
        arr[end] = null;
        return o;
    }

    /**
     * insert elements at beginning of list.
     */
    public void unshift(Object o){
        ensureCapacity(size() + 1);
        start = (start - 1 + len) & mask;
        arr[start] = o;
    }

    /**
     * remove elements from beginning of list.
     */
    public Object shift(){
        if(isEmpty())
            return null;
        Object o = arr[start];
        arr[start] = null;
        start = (start + 1) & mask;
        return o;
    }

    /**
     * set an element of the list
     */
    public void set(int n,Object o){
        if(n >= 0){
            ensureCapacity(n + 1);
            int idx = (start + n) & mask;
            arr[idx] = o;
            if(size() <= n)
                end = (idx + 1) & mask;
        }else if(n >= -size()){
            arr[(end + n + len) & mask] = o;
        }else{
            throw new ArrayIndexOutOfBoundsException(n);
        }
    }

    /**
     * catenate all array elements delimited by "delim"
     */
    public String join(String delim){
        StringBuffer sb = new StringBuffer();
        // append all elements separated by delim.
        if(start < end){
            for(int i=start;i<end;i++){
                sb.append(arr[i]);
                sb.append(delim);
            }
        }else if(start > end){
            for(int i=start;i < arr.length;i++){
                sb.append(arr[i]);
                sb.append(delim);
            }
            for(int i=0;i < end;i++){
                sb.append(arr[i]);
                sb.append(delim);
            }
        }
        if(sb.length() > 0){
            sb.setLength(sb.length() - delim.length());
        }
        return sb.toString();
    }

    /**
     * split a string by some regular expression.
     * depends on JDK support for regular expresions.
     */
    public static pList split(String regex,String str){
        //String[] a = str.split(regex);
        return new pList();
    }

    /**
     * cut out the sublist from s to end.
     */
    public void splice(int s){
        while(size() > s)
            pop();
    }

    /**
     * cut out the sublist from s to e.
     */
    public void splice(int s,int e){
        int n = s+e;
        pList l = new pList();
        while(size() > n)
            l.push(pop());
        while(size() > s)
            pop();
        while(l.size() > 0)
            push(l.pop());
    }

    /**
     * cut out the sublist from s to e, and replace with l.
     */
    public void splice(int s,int e,pList l){
        int n = s+e;
        pList m = new pList();
        while(size() > n)
            m.push(pop());
        while(size() > s)
            pop();
        while(l.size() > 0)
            push(l.shift());
        while(m.size() > 0)
            push(m.pop());        
    }

    /**
     * pair off the list into key value pairs.
     */
    public Hashtable toHash(){
        Hashtable h = new Hashtable();
        for(int i=0,j=size();i<j;i+=2){
            Object k = (String)get(i);
            Object v = get(i+1);
            h.put(k,v);
        }
        if(size() % 2 > 0)
            h.put(get(-1),"");
        return h;
    }

    /**
     * return a vector thing
     */
    public Vector toVector(){
        Vector v = new Vector();
        for(int i=0;i<size();i++)
            v.addElement(get(i));
        return v;
    }

    /**
     * return a csv string.
     */
    public String toString(){
        return join(",");
    }
}