deque.java

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

                for(int m = n - left; m-- > 0;)
                    pushFront(value);

                for(int j = 1; j <= left; j++)
                    pushFront(get(n - 1));

                fill(myStart.copy(n), myStart.copy(n + left), value);
            } else
            {
                for(int j = 1; j <= n; j++)
                    pushFront(get(n - 1));

                DequeIterator i = myStart.copy(n + left);
                copy(myStart.copy(n + n), i, myStart.copy(n));
                fill(myStart.copy(left), i, value);
            }
        } else
        {
            int oldSize = size();
            if(n > right)
            {
                for(int m = n - right; m-- > 0;)
                    pushBack(value);

                for(int j = left; j < oldSize; j++)
                    pushBack(get(j));

                fill(myStart.copy(left), myStart.copy(oldSize), value);
            } else
            {
                int index = oldSize - n;
                for(int j = index; j < oldSize; j++)
                    pushBack(get(j));

                DequeIterator i = myStart.copy(left);
                copyBackward(i, myStart.copy(index), myStart.copy(oldSize));
                fill(i, myStart.copy(left + n), value);
            }
        }
    }

    public void insert(int index, int n, Object value)
    {
        if(n < 0)
        {
            throw new IllegalArgumentException("Attempt to insert a negative n1umber of objects.");
        } else
        {
            checkIndex(index, myLength);
            insert(myStart.copy(index), n, value);
            return;
        }
    }

    public void insert(DequeIterator pos, InputIterator first, InputIterator last)
    {
        if(pos.myDeque != this)
            throw new IllegalArgumentException("Iterator not for this ListDeque");
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        if((first instanceof BidirectionalIterator) && (last instanceof BidirectionalIterator))
        {
            insert(pos, (BidirectionalIterator)first, (BidirectionalIterator)last);
            return;
        }
        DequeIterator posx = new DequeIterator(pos);
        for(InputIterator firstx = (InputIterator)first.clone(); !firstx.equals(last); posx.advance())
            posx.add(firstx.next());

    }

    public void insert(DequeIterator pos, BidirectionalIterator first, BidirectionalIterator last)
    {
        if(pos.myDeque != this)
            throw new IllegalArgumentException("Iterator not for this ListDeque");
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        int n = first.distance(last);
        int left = myStart.distance(pos);
        int right = pos.distance(myFinish);
        if(right > left)
        {
            if(n > left)
            {
                BidirectionalIterator m = (BidirectionalIterator)last.clone();
                m.retreat(left);
                BidirectionalIterator q = (BidirectionalIterator)m.clone();
                for(; !m.equals(first); pushFront(m.get()))
                    m.retreat();

                for(int j = 1; j <= left; j++)
                    pushFront(get(n - 1));

                copy(q, last, myStart.copy(n));
            } else
            {
                for(int j = 1; j <= n; j++)
                    pushFront(get(n - 1));

                copy(myStart.copy(n + n), myStart.copy(n + left), myStart.copy(n));
                copy(first, last, myStart.copy(left));
            }
        } else
        {
            int oldSize = size();
            if(n > right)
            {
                BidirectionalIterator m = (BidirectionalIterator)first.clone();
                m.advance(right);
                BidirectionalIterator q = (BidirectionalIterator)m.clone();
                for(; !m.equals(last); pushBack(m.next()));
                for(int j = left; j < oldSize; j++)
                    pushBack(get(j));

                copy(first, q, myStart.copy(left));
            } else
            {
                int index = oldSize - n;
                for(int j = index; j < oldSize; j++)
                    pushBack(get(j));

                DequeIterator i = myStart.copy(left);
                copyBackward(i, myStart.copy(index), myStart.copy(oldSize));
                copy(first, last, myStart.copy(left));
            }
        }
    }

    public void insert(int index, BidirectionalIterator first, BidirectionalIterator last)
    {
        if(!first.isCompatibleWith(last))
        {
            throw new IllegalArgumentException("iterators not compatible");
        } else
        {
            checkIndex(index, myLength);
            insert(myStart.copy(index), first, last);
            return;
        }
    }

    public Object back()
    {
        if(myLength == 0)
            throw new NoSuchElementException("ListDeque is empty");
        if(myFinish.myBlock > 0)
            return myMap[myFinish.myMap][myFinish.myBlock - 1];
        else
            return myMap[myFinish.myMap - 1][127];
    }

    public Object front()
    {
        if(myLength == 0)
            throw new NoSuchElementException("ListDeque is empty");
        else
            return myMap[myStart.myMap][myStart.myBlock];
    }

    public void pushFront(Object object)
    {
        if(myLength == 0)
        {
            add(object);
            return;
        }
        myLength++;
        if(--myStart.myBlock < 0)
        {
            if(myStart.myMap == 0)
                growMap();
            myMap[--myStart.myMap] = new Object[128];
            myStart.myBlock = 127;
        }
        myMap[myStart.myMap][myStart.myBlock] = object;
    }

    public Object popFront()
    {
        if(myLength == 0)
            throw new NoSuchElementException("ListDeque is empty");
        Object r = get(0);
        if(--myLength == 0)
        {
            clear();
        } else
        {
            r = myMap[myStart.myMap][myStart.myBlock];
            myMap[myStart.myMap][myStart.myBlock++] = null;
            if(myStart.myBlock == 128)
            {
                myMap[myStart.myMap++] = null;
                myStart.myBlock = 0;
            }
        }
        return r;
    }

    public void pushBack(Object object)
    {
        if(myLength++ == 0)
        {
            createMap();
            myMap[myFinish.myMap][myFinish.myBlock++] = object;
        } else
        {
            myMap[myFinish.myMap][myFinish.myBlock++] = object;
            if(myFinish.myBlock == 128)
            {
                if(myFinish.myMap == myMap.length - 1)
                    growMap();
                myMap[++myFinish.myMap] = new Object[128];
                myFinish.myBlock = 0;
            }
        }
    }

    public Object popBack()
    {
        if(myLength == 0)
            throw new NoSuchElementException("ListDeque is empty");
        Object r = get(0);
        if(--myLength == 0)
        {
            clear();
        } else
        {
            if(myFinish.myBlock-- == 0)
            {
                myMap[myFinish.myMap--] = null;
                myFinish.myBlock = 127;
            }
            r = myMap[myFinish.myMap][myFinish.myBlock];
            myMap[myFinish.myMap][myFinish.myBlock] = null;
        }
        return r;
    }

    public void swap(Deque deque)
    {
        DequeIterator tmpStart = myStart;
        myStart = deque.myStart;
        myStart.myDeque = this;
        deque.myStart = tmpStart;
        deque.myStart.myDeque = deque;
        DequeIterator tmpFinish = myFinish;
        myFinish = deque.myFinish;
        myFinish.myDeque = this;
        deque.myFinish = tmpFinish;
        deque.myFinish.myDeque = deque;
        int tmpLength = myLength;
        myLength = deque.myLength;
        deque.myLength = tmpLength;
        Object tmpMap[][] = myMap;
        myMap = deque.myMap;
        deque.myMap = tmpMap;
    }



    public int remove(int first, int last, Object object)
    {
        return removeRange(first, last, object);
    }

    public boolean add(Object object)
    {
        pushBack(object);
        return true;
    }

    int indexOf(Object object, BidirectionalIterator first, BidirectionalIterator last)
    {
        BidirectionalIterator i = (BidirectionalIterator)Algos.find(first, last, object);
        return i.equals(last) ? -1 : myStart.distance(i);
    }

    int lastIndexOf(Object object, BidirectionalIterator first, BidirectionalIterator last)
    {
        BidirectionalIterator i = Algos.lastFind(first, last, object);
        return i.equals(last) ? -1 : myStart.distance(i);
    }

    private void growMap()
    {
        int newMapSize = myMap.length * 2;
        Object tmp[][] = new Object[newMapSize][];
        int i = newMapSize / 4;
        int count = (myFinish.myMap - myStart.myMap) + 1;
        System.arraycopy(((Object) (myMap)), myStart.myMap, ((Object) (tmp)), i, count);
        myStart.myMap = i;
        myFinish.myMap = (i + count) - 1;
        myMap = tmp;
    }

    private void createMap()
    {
        myMap = new Object[1024][];
        int mapIndex = myMap.length / 2;
        myMap[mapIndex] = new Object[128];
        int blockIndex = myMap[mapIndex].length / 2;
        myStart.myBlock = blockIndex;
        myStart.myMap = mapIndex;
        myFinish.myBlock = blockIndex;
        myFinish.myMap = mapIndex;
    }

    private static DequeIterator copy(BidirectionalIterator first, BidirectionalIterator last, DequeIterator result)
    {
        BidirectionalIterator firstx = (BidirectionalIterator)first.clone();
        DequeIterator resultx = (DequeIterator)result.clone();
        for(; !firstx.equals(last); resultx.advance())
            resultx.put(firstx.next());

        return resultx;
    }

    private static void copyBackward(BidirectionalIterator first, BidirectionalIterator last, DequeIterator result)
    {
        BidirectionalIterator lastx = (BidirectionalIterator)last.clone();
        DequeIterator resultx = (DequeIterator)result.clone();
        for(; !first.equals(lastx); resultx.put(lastx.get()))
        {
            resultx.retreat();
            lastx.retreat();
        }

    }

    private static void fill(DequeIterator first, DequeIterator last, Object object)
    {
        for(; !first.equals(last); first.advance())
            first.put(object);

    }

    final Object removeFrom(DequeIterator pos)
    {
        Object old = pos.get();
        DequeIterator tmp = pos.copy(1);
        if(myStart.distance(pos) < pos.distance(myFinish))
        {
            copy(tmp, myFinish, pos);
            popBack();
        } else
        {
            copyBackward(myStart, pos, tmp);
            popFront();
        }
        return old;
    }

    protected final void checkIndex(int index, int limit)
    {
        if(index < 0 || index > limit)
            throw new IndexOutOfBoundsException("Attempt to access index " + index + " when valid range is 0.." + limit);
        else
            return;
    }

    protected final void checkIndex(int index)
    {
        checkIndex(index, myLength - 1);
    }

    protected final void checkRange(int lo, int hi)
    {
        checkIndex(lo, myLength - 1);
        checkIndex(hi, myLength - 1);
    }

    static final int PAGE_SIZE = 1024;
    static final int BLOCK_SIZE = 128;
    DequeIterator myStart;
    DequeIterator myFinish;
    int myLength;
    Object myMap[][];
    static final long serialVersionUID = 0x7174032f22033290L;
}