slist.java

java 的源代码

package com.reddragon2046.base.utilities.data;

import java.io.*;
import java.util.*;

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

public class SList extends AbstractSequence
    implements Sequence
{
    static final class SListNode
    {

        SListNode getNext()
        {
            return m_next;
        }

        void setNext(SListNode node)
        {
            m_next = node;
        }

        Object getObject()
        {
            return m_object;
        }

        void setObject(Object object)
        {
            m_object = object;
        }

        boolean isActive()
        {
            return m_isActive;
        }

        void activate()
        {
            m_isActive = true;
        }

        void deactivate()
        {
            m_isActive = false;
        }

        static final long serialVersionUID = 0xb952a8646778b781L;
        private SListNode m_next;
        private Object m_object;
        private boolean m_isActive;

        SListNode(Object object)
        {
            this(object, null);
        }

        SListNode(Object object, SListNode next)
        {
            m_object = object;
            m_next = next;
            m_isActive = true;
        }
    }


    public SList()
    {
        myHead = null;
        myTail = null;
        myLength = 0;
        myHead = null;
        myTail = null;
        myLength = 0;
    }

    public SList(int size)
    {
        this(size, null);
    }

    public SList(int size, Object object)
    {
        myHead = null;
        myTail = null;
        myLength = 0;
        insert(0, size, object);
    }

    public SList(Collection c)
    {
        myHead = null;
        myTail = null;
        myLength = 0;
        addAll(c);
    }

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

    public boolean equals(Object object)
    {
        if(object == this)
            return true;
        else
            return (object instanceof SList) && Algos.equal(this, (SList)object);
    }

    public int hashCode()
    {
        int value = 0;
        for(Iterator i = iterator(); i.hasNext();)
        {
            value *= 31;
            Object obj = i.next();
            if(obj != null)
                value += obj.hashCode();
        }

        return value;
    }

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

    public int size()
    {
        return myLength;
    }

    public void clear()
    {
        myHead = null;
        myTail = null;
        myLength = 0;
    }

    SListNode getHead()
    {
        return myHead;
    }

    public SListIterator begin()
    {
        return new SListIterator(this, myHead);
    }

    public SListIterator end()
    {
        return new SListIterator(this, null);
    }

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

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

    public boolean add(Object object)
    {
        SListNode node = new SListNode(object);
        if(++myLength == 1)
            myHead = node;
        else
            myTail.setNext(node);
        myTail = node;
        return true;
    }

    public void add(int index, Object object)
    {
        checkIndex(index, myLength);
        if(myLength == 0)
            pushFront(object);
        else
            insert(nodeAt(index), object);
    }

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

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

    public Object get(int index)
    {
        checkIndex(index);
        SListNode node;
        for(node = myHead; index-- > 0; node = node.getNext());
        return node.getObject();
    }

    public int indexOf(Object object)
    {
        SListIterator iterator = find(object, begin(), end());
        return iterator.getNode() != null ? iterator.index() : -1;
    }

    public int indexOf(Object object, int index)
    {
        checkIndex(index);
        SListIterator iterator = find(object, iteratorAt(index), end());
        return iterator.getNode() != null ? iterator.index() : -1;
    }

    public int indexOf(Object object, int first, int last)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            SListIterator end = iteratorAt(last + 1);
            SListIterator iterator = find(object, iteratorAt(first), end);
            return iterator.getNode() != end.getNode() ? iterator.index() : -1;
        }
    }

    public Object remove(int index)
    {
        checkIndex(index);
        return removeNode(nodeAt(index));
    }

    public void removeRange(int first, int last)
    {
        remove(first, last);
    }



    public int remove(int first, int last)
    {
        if(last < first)
        {
            return 0;
        } else
        {
            checkRange(first, last);
            return removeNode(nodeAt(first), nodeAt(last));
        }
    }

    public Object set(int index, Object object)
    {
        checkIndex(index);
        return set(nodeAt(index), object);
    }

    final Object set(SListNode node, Object object)
    {
        Object old = node.getObject();
        node.setObject(object);
        return old;
    }

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

    public boolean addAll(Collection c)
    {
        return addAll(myLength, c);
    }

    public boolean addAll(int index, Collection c)
    {
        if(c.size() == 0)
            return false;
        if(this == c)
        {
            splice(index, new SList(c));
        } else
        {
            SListNode previous = null;
            SListNode target;
            for(target = myHead; index-- > 0; target = target.getNext())
                previous = target;

            SListNode newNode = null;
            for(Iterator iter = c.iterator(); iter.hasNext();)
            {
                Object obj = iter.next();
                newNode = new SListNode(obj);
                myLength++;
                if(previous == null)
                    myHead = newNode;
                else
                    previous.setNext(newNode);
                previous = newNode;
            }

            newNode.setNext(target);
            if(target == null)
                myTail = newNode;
        }
        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;
        } else
        {
            clear();
            addAll(c);
            return;
        }
    }

    public SListIterator insert(SListIterator pos, Object object)
    {
        return new SListIterator(this, insert(pos.getNode(), object));
    }

    public void insert(SListIterator pos, int n, Object object)
    {
        insert(pos.getNode(), n, object);
    }

    public void insert(int index, int n, Object object)
    {
        if(n < 0)
            throw new IllegalArgumentException("Attempt to specify a insert a negative number of objects");
        checkIndex(index, myLength);
        if(myLength == 0)
        {
            pushFront(object);
            n--;
        }
        insert(nodeAt(index), n, object);
    }

    public void insert(SListIterator pos, InputIterator first, InputIterator last)
    {
        for(InputIterator firstx = (InputIterator)first.clone(); !firstx.equals(last); insert(pos, firstx.next()));
    }

    public Object back()
    {
        if(myLength == 0)
            throw new NoSuchElementException("SList is empty");
        else
            return myTail.getObject();
    }

    public Object front()
    {
        if(myLength == 0)
            throw new NoSuchElementException("SList is empty");
        else
            return myHead.getObject();
    }

    public Object popBack()
    {
        if(myLength == 0)
            throw new NoSuchElementException("SList is empty");
        SListNode previous = null;
        for(SListNode node = myHead; node != myTail; node = node.getNext())
            previous = node;

        Object r;
        if(previous == null)
        {
            r = myHead.getObject();
            myHead = null;
        } else
        {
            r = previous.getNext().getObject();
            previous.setNext(null);
        }
        myTail = previous;
        myLength--;
        return r;
    }

    public void pushFront(Object object)
    {
        SListNode node = new SListNode(object, myHead);
        myHead = node;
        if(++myLength == 1)
            myTail = node;
    }

    public Object popFront()
    {
        if(myLength == 0)
            throw new NoSuchElementException("Slist is empty");
        Object r = myHead.getObject();
        myHead = myHead.getNext();
        if(--myLength == 0)
            myTail = null;
        return r;
    }

    public void pushBack(Object object)
    {
        add(object);
    }

    public void swap(SList list)
    {
        SListNode tmpHead = myHead;
        myHead = list.myHead;
        list.myHead = tmpHead;
        SListNode tmpTail = myTail;
        myTail = list.myTail;
        list.myTail = tmpTail;
        int tmpLength = myLength;
        myLength = list.myLength;
        list.myLength = tmpLength;
    }