slist.java

java 的源代码

    public int remove(Object object, int count)
    {
        return removeNode(myHead, null, object, count);
    }



    public int remove(Iterator first, Iterator last, Object object)
    {
        if(!(first instanceof SListIterator) || !(last instanceof SListIterator))
            throw new IllegalArgumentException("Iterator not a SListIterator");
        SListIterator begin = (SListIterator)first;
        SListIterator end = (SListIterator)last;
        if(begin.getList() != this || end.getList() != this)
            throw new IllegalArgumentException("Iterator not for this SList");
        else
            return removeNode(begin.getNode(), end.getNode(), object, myLength);
    }

    public int removeRange(int first, int last, Object object)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            return removeNode(nodeAt(first), nodeAt(last + 1), object, myLength);
        }
    }



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

    public int replace(Object oldValue, Object newValue)
    {
        return Algos.replace(begin(), end(), oldValue, newValue);
    }

    public int replace(SListIterator first, SListIterator last, Object oldValue, Object newValue)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        else
            return Algos.replace(first, last, oldValue, newValue);
    }

    public int replace(int first, int last, Object oldValue, Object newValue)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            return Algos.replace(iteratorAt(first), iteratorAt(last + 1), oldValue, newValue);
        }
    }

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

    public int count(SListIterator first, SListIterator last, Object object)
    {
        return Algos.count(first, last, object);
    }

    public int count(int first, int last, Object object)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            return Algos.count(iteratorAt(first), iteratorAt(last + 1), object);
        }
    }

    public SListIterator find(Object object)
    {
        return (SListIterator)Algos.find(begin(), end(), object);
    }

    public SListIterator find(Object object, SListIterator first, SListIterator last)
    {
        return (SListIterator)Algos.find(first, last, object);
    }

    public void splice(SListIterator pos, SList list)
    {
        splice(pos.getNode(), list);
    }

    public void splice(int index, SList list)
    {
        checkIndex(index, myLength);
        if(myLength == 0)
            swap(list);
        else
            splice(nodeAt(index), list);
    }

    public void splice(SListIterator to, SList list, SListIterator from)
    {
        splice(to.getNode(), list, from.getNode());
    }

    public void splice(int to, SList list, int from)
    {
        checkIndex(to);
        list.checkIndex(from);
        splice(nodeAt(to), list, list.nodeAt(from));
    }

    public void splice(SListIterator pos, SList list, SListIterator first, SListIterator last)
    {
        splice(pos.getNode(), list, first.getNode(), last.getNode());
    }

    public void splice(int pos, SList list, int first, int last)
    {
        checkIndex(pos, myLength);
        list.checkRange(first, last);
        splice(nodeAt(pos), list, list.nodeAt(first), list.nodeAt(last + 1));
    }

    public void unique()
    {
        if(myLength < 2)
            return;
        SListNode previous = myHead;
        for(SListNode node = myHead.getNext(); node != null; node = node.getNext())
            if(node.getObject() != null ? node.getObject().equals(previous.getObject()) : previous.getObject() == null)
            {
                previous.setNext(node.getNext());
                node.deactivate();
                myLength--;
                if(node == myTail)
                    myTail = previous;
            } else
            {
                previous = node;
            }

    }

    public void reverse()
    {
        if(myLength < 2)
            return;
        SListNode node = myHead;
        myHead = myTail;
        myTail = node;
        SListNode next = node.getNext();
        node.setNext(null);
        SListNode current;
        for(; next != null; next = current)
        {
            current = next.getNext();
            next.setNext(node);
            node = next;
        }

    }

    private void splice(SListNode begin, SList list)
    {
        if(this == list || list.myLength == 0)
            return;
        SListNode previous = null;
        for(SListNode node = myHead; node != begin; node = node.getNext())
            previous = node;

        if(previous == null)
            myHead = list.myHead;
        else
            previous.setNext(list.myHead);
        if(begin == null)
            myTail = list.myTail;
        else
            list.myTail.setNext(begin);
        myLength += list.myLength;
        list.clear();
    }

    private void splice(SListNode insertNode, SList list, SListNode newNode)
    {
        if(insertNode == newNode || insertNode == newNode.getNext())
            return;
        list.removeNode(newNode);
        SListNode previous = null;
        for(SListNode node = myHead; node != insertNode; node = node.getNext())
            previous = node;

        if(previous == null)
            myHead = newNode;
        else
            previous.setNext(newNode);
        if(insertNode == null)
            myTail = newNode;
        newNode.setNext(insertNode);
        newNode.activate();
        myLength++;
    }

    private void splice(SListNode pos, SList list, SListNode begin, SListNode pastEnd)
    {
        if(begin == pastEnd)
            return;
        if(list == this)
        {
            SListNode tmp = begin;
            if(pos == begin || pos == pastEnd)
                return;
            for(; tmp != pastEnd; tmp = tmp.getNext())
                if(pos == tmp)
                    throw new NoSuchElementException("Tried to splice into an overlapping area.");

        }
        list.removeNode(begin, pastEnd);
        SListNode previous = null;
        for(SListNode node = myHead; node != pos; node = node.getNext())
            previous = node;

        if(previous == null)
            myHead = begin;
        else
            previous.setNext(begin);
        SListNode end = begin;
        end.activate();
        int n;
        for(n = 1; end.getNext() != pastEnd; n++)
        {
            end.activate();
            end = end.getNext();
        }

        if(pos == null)
            myTail = end;
        end.setNext(pos);
        myLength += n;
    }

    final SListNode insert(SListNode target, Object object)
    {
        SListNode previous = null;
        for(SListNode node = myHead; node != target; node = node.getNext())
            previous = node;

        SListNode newNode = new SListNode(object, target);
        if(previous == null)
            myHead = newNode;
        else
            previous.setNext(newNode);
        if(target == null)
            myTail = newNode;
        myLength++;
        return newNode;
    }

    private void insert(SListNode target, int n, Object object)
    {
        SListNode previous = null;
        SListNode newNode = null;
        myLength += n;
        for(SListNode node = myHead; node != target; node = node.getNext())
            previous = node;

        while(--n >= 0)
        {
            newNode = new SListNode(object);
            if(previous == null)
                myHead = newNode;
            else
                previous.setNext(newNode);
            previous = newNode;
        }
        newNode.setNext(target);
        if(target == null)
            myTail = newNode;
    }

    final Object removeNode(SListNode target)
    {
        SListNode previous = null;
        for(SListNode node = myHead; node != target; node = node.getNext())
            previous = node;

        if(previous == null)
        {
            if(target == myHead)
                myHead = target.getNext();
            else
                throw new IllegalArgumentException("node to remove is not in list");
        } else
        {
            previous.setNext(target.getNext());
        }
        if(target == myTail)
            myTail = previous;
        target.deactivate();
        myLength--;
        return target.getObject();
    }

    final int removeNode(SListNode begin, SListNode end)
    {
        SListNode previous = null;
        for(SListNode node = myHead; node != begin; node = node.getNext())
            previous = node;

        if(previous == null)
        {
            if(begin == myHead)
                myHead = end;
            else
                throw new IllegalArgumentException("attempt to remove node that doesn't exist");
        } else
        {
            previous.setNext(end);
        }
        if(end == null)
            myTail = previous;
        int n = 0;
        for(SListNode current = begin; current != end;)
        {
            current = current.getNext();
            n++;
        }

        myLength -= n;
        return n;
    }

    final int removeNode(SListNode first, SListNode last, Object object, int maximum)
    {
        if(maximum <= 0)
            return 0;
        int n = 0;
        SListNode previous = null;
        SListNode badNode = null;
        SListNode node;
        for(node = myHead; node != first; node = node.getNext())
            previous = node;

        for(; maximum > 0 && node != last; node = node.getNext())
            if(node.getObject() != null ? node.getObject().equals(object) : object == null)
            {
                if(previous == null)
                    myHead = node.getNext();
                else
                    previous.setNext(node.getNext());
                if(node == myTail)
                    myTail = previous;
                node.deactivate();
                if(badNode == null)
                    badNode = node;
                n++;
                maximum--;
            } else
            {
                previous = node;
                if(badNode != null)
                {
                    SListNode bnode;
                    for(; badNode != node; badNode = bnode)
                    {
                        bnode = badNode.getNext();
                        badNode.setNext(node);
                    }

                    badNode = null;
                }
            }

        myLength -= n;
        return n;
    }

    final SListIterator iteratorAt(int index)
    {
        return new SListIterator(this, nodeAt(index));
    }

    final SListNode nodeAt(int index)
    {
        SListNode node;
        for(node = myHead; index-- > 0; node = node.getNext());
        return node;
    }

    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);
    }

    private void writeObject(ObjectOutputStream stream)
        throws IOException
    {
        stream.defaultWriteObject();
        stream.writeInt(size());
        for(Iterator iter = begin(); iter.hasNext(); stream.writeObject(iter.next()));
    }

    private void readObject(ObjectInputStream stream)
        throws IOException, ClassNotFoundException
    {
        stream.defaultReadObject();
        clear();
        for(int count = stream.readInt(); count-- > 0;)
            add(stream.readObject());

    }

    public void dump()
    {
        System.out.println("========size=" + size());
        for(SListIterator iter = begin(); iter.hasNext(); iter.advance())
            iter.dump();

        System.out.println("========");
    }

    private transient SListNode myHead;
    private transient SListNode myTail;
    private transient int myLength;
}