deque.java

来自「java 的源代码」· Java 代码 · 共 760 行 · 第 1/2 页

package com.reddragon2046.base.utilities.data;

import java.util.*;

// Referenced classes of package com.reddragon2046.base.utilities.data:
//            AbstractSequence, DequeIterator, InputIterator, BidirectionalIterator,
//            Algos, ForwardIterator

public class Deque extends AbstractSequence
{

    public Deque()
    {
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
    }

    public Deque(int size)
    {
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
        insert(myStart, size, null);
    }

    public Deque(int size, Object object)
    {
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
        insert(myStart, size, object);
    }

    public Deque(Collection c)
    {
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
        addAll(c);
    }

    public Deque(Deque copy)
    {
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
        addAll(copy);
    }

    public void copy(Deque copy)
    {
        clear();
        addAll(copy);
    }

    public Object clone()
    {
        return new Deque(this);
    }

    public String toString()
    {
        return Algos.toString(this, "ListDeque");
    }

    public int size()
    {
        return myLength;
    }

    public void clear()
    {
        myMap = null;
        myStart = new DequeIterator(this, 0, 0);
        myFinish = new DequeIterator(this, 0, 0);
        myLength = 0;
    }

    public DequeIterator begin()
    {
        return new DequeIterator(myStart);
    }

    public ForwardIterator start()
    {
        return begin();
    }

    public DequeIterator end()
    {
        return new DequeIterator(myFinish);
    }

    public ForwardIterator finish()
    {
        return end();
    }

    public ListIterator listIterator()
    {
        return begin();
    }

    public ListIterator listIterator(int index)
    {
        BidirectionalIterator begin = begin();
        begin.advance(index);
        return begin;
    }

    public void add(int index, Object object)
    {
        ListIterator iter = listIterator(index);
        iter.next();
        iter.set(object);
    }

    public boolean contains(Object object)
    {
        return indexOf(object, myStart, myFinish) != -1;
    }

    public boolean remove(Object object)
    {
        return remove(object, 1) == 1;
    }

    public int removeRange(InputIterator first, InputIterator last)
    {
        if(!(first instanceof DequeIterator) || !(last instanceof DequeIterator))
            throw new IllegalArgumentException("Iterator not a DequeIterator");
        DequeIterator begin = (DequeIterator)first;
        DequeIterator end = (DequeIterator)last;
        if(begin.myDeque != this || end.myDeque != this)
            throw new IllegalArgumentException("Iterator not for this ListDeque");
        int n = begin.distance(end);
        int count = n;
        if(end.distance(myFinish) > myStart.distance(begin))
        {
            copyBackward(myStart, begin, end);
            while(n-- > 0)
                popFront();
        } else
        {
            copy(end, myFinish, begin);
            while(n-- > 0)
                popBack();
        }
        return count;
    }



    private int remove(Iterator first, Iterator last)
    {
        if((first instanceof InputIterator) && (last instanceof InputIterator))
            return removeRange((InputIterator)first, (InputIterator)last);
        else
            throw new IllegalArgumentException("Iterator not for this container");
    }

    public Object get(int index)
    {
        checkIndex(index);
        int blockIndex = myStart.myBlock + index;
        int mapIndex = myStart.myMap;
        if(blockIndex >= 128)
        {
            int jump = blockIndex / 128;
            mapIndex += jump;
            blockIndex %= 128;
        } else
        if(blockIndex < 0)
        {
            int jump = (127 - blockIndex) / 128;
            mapIndex -= jump;
            blockIndex += jump * 128;
        }
        return myMap[mapIndex][blockIndex];
    }

    public int indexOf(Object object)
    {
        return indexOf(object, ((BidirectionalIterator) (myStart)), ((BidirectionalIterator) (myFinish)));
    }

    public int indexOf(Object object, int index)
    {
        checkIndex(index);
        return indexOf(object, ((BidirectionalIterator) (myStart.copy(index))), ((BidirectionalIterator) (myFinish)));
    }

    public int indexOf(Object object, int first, int last)
    {
        if(last < first)
        {
            return -1;
        } else
        {
            checkRange(first, last);
            DequeIterator end = myStart.copy(last + 1);
            return indexOf(object, ((BidirectionalIterator) (myStart.copy(first))), ((BidirectionalIterator) (end)));
        }
    }

    public int lastIndexOf(Object object)
    {
        return lastIndexOf(object, ((BidirectionalIterator) (begin())), ((BidirectionalIterator) (end())));
    }

    public int lastIndexOf(Object object, int index)
    {
        checkIndex(index);
        return lastIndexOf(object, ((BidirectionalIterator) (myStart.copy(index))), ((BidirectionalIterator) (end())));
    }

    public int lastIndexOf(Object object, int first, int last)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            DequeIterator end = myStart.copy(last + 1);
            return lastIndexOf(object, ((BidirectionalIterator) (myStart.copy(first))), ((BidirectionalIterator) (end)));
        }
    }

    public Object remove(int index)
    {
        checkIndex(index);
        return removeFrom(myStart.copy(index));
    }

    public void removeRange(int first, int last)
    {
        if(last < first)
        {
            return;
        } else
        {
            checkRange(first, last);
            remove(myStart.copy(first), myStart.copy(last + 1));
            return;
        }
    }

    public Object set(int index, Object object)
    {
        checkIndex(index);
        int blockIndex = myStart.myBlock + index;
        int mapIndex = myStart.myMap;
        if(blockIndex >= 128)
        {
            int jump = blockIndex / 128;
            mapIndex += jump;
            blockIndex %= 128;
        } else
        if(blockIndex < 0)
        {
            int jump = (127 - blockIndex) / 128;
            mapIndex -= jump;
            blockIndex += jump * 128;
        }
        Object old = myMap[mapIndex][blockIndex];
        myMap[mapIndex][blockIndex] = object;
        return old;
    }

    public boolean containsAll(Collection c)
    {
        return this != c ? super.containsAll(c) : true;
    }

    public boolean addAll(Collection c)
    {
        return this != c ? super.addAll(c) : false;
    }

    public boolean addAll(int index, Collection c)
    {
        if(this != c)
            return super.addAll(index, c);
        if(myLength == 0)
        {
            return false;
        } else
        {
            super.addAll(index, new Deque(c));
            return true;
        }
    }

    public boolean removeAll(Collection c)
    {
        if(this == c)
        {
            clear();
            return true;
        } else
        {
            return super.removeAll(c);
        }
    }

    public boolean retainAll(Collection c)
    {
        return this != c ? super.retainAll(c) : false;
    }

    public void copy(Collection c)
    {
        if(this == c)
            return;
        if(c instanceof Deque)
        {
            Deque deque = (Deque)c;
            if(myLength >= deque.myLength)
            {
                DequeIterator begin = copy(((BidirectionalIterator) (deque.myStart)), ((BidirectionalIterator) (deque.myFinish)), myStart);
                remove(begin, myFinish);
            } else
            {
                DequeIterator end = deque.myStart.copy(myLength);
                copy(((BidirectionalIterator) (deque.myStart)), ((BidirectionalIterator) (end)), myStart);
                for(DequeIterator iter = end; iter.hasNext(); iter.advance())
                    add(iter.get());

            }
        } else
        {
            clear();
            super.addAll(c);
        }
    }

    public DequeIterator insert(DequeIterator pos, Object value)
    {
        if(pos.myDeque != this)
            throw new IllegalArgumentException("Iterator not for this ListDeque");
        if(pos.equals(myStart))
        {
            pushFront(value);
            return new DequeIterator(myStart);
        }
        if(pos.equals(myFinish))
        {
            pushBack(value);
            return myFinish.copy(-1);
        }
        int index = myStart.distance(pos);
        if(pos.distance(myFinish) > index)
        {
            pushFront(myStart.get());
            copy(myStart.copy(2), myStart.copy(index + 1), myStart.copy(1));
            DequeIterator i = myStart.copy(index);
            i.put(value);
            return i;
        } else
        {
            DequeIterator i2 = myFinish.copy(-1);
            pushBack(i2.get());
            DequeIterator i = myStart.copy(index);
            copyBackward(i, myFinish.copy(-2), myFinish.copy(-1));
            i.put(value);
            return i;
        }
    }

    public void insert(DequeIterator pos, int n, Object value)
    {
        if(n < 0)
            throw new IllegalArgumentException("Attempt to insert a negative number of objects");
        if(pos.myDeque != this)
            throw new IllegalArgumentException("Iterator not for this ListDeque");
        if(n == 0)
            return;
        int left = myStart.distance(pos);
        int right = pos.distance(myFinish);
        if(right > left)
        {
            if(n > left)
            {