package com.planet_ink.coffee_mud.core.collections;
import java.io.Serializable;
import java.util.*;
/*
Copyright 2012-2016 Bo Zimmerman
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
public class CMList<K> implements Serializable, Cloneable, Iterable<K>, Collection<K>, Deque<K>, List<K>, Queue<K>
{
private static final long serialVersionUID = -4174213459327144471L;
private static final Random rand=new Random(System.currentTimeMillis());
private class CMListNode
{
public K obj;
public boolean active=false;
public CMListNode next=null;
public CMListNode prev=null;
public CMListNode randNext=null;
public CMListNode randPrev=null;
public CMListNode(K obj) { this.obj=obj;}
}
private volatile CMListNode randNode=null;
private volatile CMListNode head=null;
private volatile CMListNode tail=null;
private volatile int size=0;
public CMList()
{
}
public CMList(final Enumeration<K> E)
{
if(E!=null)
for(;E.hasMoreElements();)
add(E.nextElement());
}
public CMList(final Iterator<K> E)
{
if(E!=null)
for(;E.hasNext();)
add(E.next());
}
public CMList(final Set<K> E)
{
if(E!=null)
for(final K o : E)
add(o);
}
public synchronized void addAll(Enumeration<K> E)
{
if(E!=null)
for(;E.hasMoreElements();)
add(E.nextElement());
}
public synchronized void addAll(K[] E)
{
if(E!=null)
for(final K e : E)
add(e);
}
public synchronized void addAll(Iterator<K> E)
{
if(E!=null)
for(;E.hasNext();)
add(E.next());
}
public synchronized void removeAll(Enumeration<K> E)
{
if(E!=null)
for(;E.hasMoreElements();)
remove(E.nextElement());
}
public synchronized void removeAll(Iterator<K> E)
{
if(E!=null)
for(;E.hasNext();)
remove(E.next());
}
public synchronized void removeAll(List<K> E)
{
if(E!=null)
for(final K o : E)
remove(o);
}
public LinkedList<K> toLinkedList()
{
final LinkedList<K> L=new LinkedList<K>();
for (final K k : this)
L.add(k);
return L;
}
public Vector<K> toVector()
{
final Vector<K> V=new Vector<K>(size());
for (final K k : this)
V.add(k);
return V;
}
private CMListNode findFirstNode(final Object arg0)
{
CMListNode curr=head;
while(curr!=null)
{
if(curr.active)
{
if(arg0 == null)
{
if(curr.obj==null)
return curr;
}
else
if(arg0.equals(curr.obj))
return curr;
}
curr=curr.next;
}
return null;
}
private CMListNode findLastNode(final Object arg0)
{
CMListNode curr=tail;
while(curr!=null)
{
if(curr.active)
{
if(arg0 == null)
{
if(curr.obj==null)
return curr;
}
else
if(arg0.equals(curr.obj))
return curr;
}
curr=curr.prev;
}
return null;
}
private synchronized void removeNode(final CMListNode here)
{
if((here == null)||(!here.active))
return;
here.active=false;
size--;
final CMListNode next=here.next;
final CMListNode prev=here.prev;
if(head == here)
head=next;
if(tail == here)
tail=prev;
if(prev != null)
prev.next=next;
if(next != null)
next.prev=prev;
final CMListNode randNext=here.randNext;
final CMListNode randPrev=here.randPrev;
if(randNode == here)
{
if(here.randNext == here)
randNode = null;
else
randNode=here.randNext;
}
if(randPrev != null)
randPrev.randNext=randNext;
if(randNext != null)
randNext.randPrev=randPrev;
// in time, garbage collector will make all right again.
// in time.
}
private synchronized CMListNode addAfter(final CMListNode here, final K arg1)
{
final CMListNode newNode=new CMListNode(arg1);
if(here == null)
{
newNode.next=head;
head=newNode;
if(newNode.next!=null)
newNode.next.prev=newNode;
if(tail==null)
tail=newNode;
}
else
{
newNode.next=here.next;
here.next=newNode;
newNode.prev=here;
if(newNode.next!=null)
newNode.next.prev=newNode;
if(tail==here)
tail=newNode;
}
if(randNode==null)
{
randNode=newNode;
newNode.randNext=newNode;
newNode.randPrev=newNode;
}
else
if(rand.nextDouble()<0.5)
{
newNode.randNext=randNode;
newNode.randPrev=randNode.randPrev;
randNode.randPrev=newNode;
newNode.randPrev.randNext=newNode;
randNode = newNode;
}
else
{
newNode.randPrev=randNode;
newNode.randNext=randNode.randNext;
randNode.randNext.randPrev=newNode;
randNode.randNext=newNode;
}
size++;
newNode.active=true;
return newNode;
}
private CMListNode nodeBefore(int arg0)
{
if((head == null) || (arg0 == 0))
return null;
else
{
CMListNode curr=head;
for(int i=1;i<arg0;i++)
if(curr.next!=null)
{
if(!curr.active)
i--;
curr=curr.next;
}
return curr;
}
}
private CMListNode nodeAt(int arg0)
{
if((arg0<0)||(arg0>=size))
return null;
else
{
CMListNode curr;
int i;
int ch;
if((arg0==size-1) || (arg0 > size/2))
{
curr=tail;
i=size-1;
ch=-1;
}
else
{
curr=head;
i=0;
ch=1;
}
while(curr != null)
{
if(i==arg0)
{
if(!curr.active)
i=i+(ch*-1);
else
break;
}
else
i=i+ch;
curr=curr.next;
}
return curr;
}
}
@Override
public synchronized void add(int arg0, K arg1)
{
addAfter(nodeBefore(arg0),arg1);
}
@Override
public synchronized boolean add(K arg0)
{
addAfter(tail,arg0);
return true;
}
@Override
public synchronized boolean addAll(Collection<? extends K> arg0)
{
for (final K name : arg0)
if(!add(name))
return false;
return true;
}
@Override
public synchronized boolean addAll(int arg0, Collection<? extends K> arg1)
{
CMListNode curr=nodeBefore(arg0);
for (final K name : arg1)
curr=addAfter(curr,name);
return true;
}
@Override
public synchronized void addFirst(K arg0)
{
addAfter(null,arg0);
}
@Override
public synchronized void addLast(K arg0)
{
addAfter(tail,arg0);
}
@Override
public synchronized void clear()
{
head=null;
tail=null;
randNode=null;
size=0;
}
public synchronized K getNextRandom()
{
final CMListNode node=randNode;
if(node == null)
return null;
randNode=node.randNext;
return node.obj;
}
public synchronized K getPreviousRandom()
{
final CMListNode node=randNode;
if(node == null)
return null;
randNode=node.randPrev;
return node.obj;
}
public synchronized CMList<K> copyOf()
{
final CMList<K> newList=new CMList<K>();
CMListNode curr=tail;
while(curr!=null)
{
if(curr.active)
newList.addAfter(null, curr.obj);
curr=curr.prev;
}
return newList;
}
@Override
public boolean contains(Object arg0)
{
return findFirstNode(arg0) != null;
}
public boolean containsFromEnd(Object arg0)
{
return findLastNode(arg0) != null;
}
public Enumeration<K> elements()
{
final CMListNode firstNode=nodeAt(0);
return new Enumeration<K>()
{
private CMListNode nextNode = firstNode;
private void makeNext()
{
if(nextNode != null)
{
nextNode=nextNode.next;
while((nextNode != null)&&(!nextNode.active))
nextNode=nextNode.next;
}
}
@Override public boolean hasMoreElements() { return nextNode != null; }
@Override
public K nextElement()
{
if(!hasMoreElements())
throw new NoSuchElementException();
final K obj=nextNode.obj;
makeNext();
return obj;
}
};
}
@Override
public Iterator<K> descendingIterator()
{
final CMListNode firstNode=nodeAt(size-1);
return new Iterator<K>()
{
private CMListNode nextNode = firstNode;
private CMListNode lastNode = null;
private void makeNext()
{
if(nextNode != null)
{
nextNode=nextNode.prev;
while((nextNode != null)&&(!nextNode.active))
nextNode=nextNode.prev;
}
}
@Override public boolean hasNext() { return nextNode != null; }
@Override
public K next()
{
if(!hasNext())
throw new NoSuchElementException();
lastNode=nextNode;
final K obj=nextNode.obj;
makeNext();
return obj;
}
@Override
public void remove()
{
removeNode(lastNode);
}
};
}
@Override
public K element()
{
return getFirst();
}
@Override
public K get(int arg0)
{
final CMListNode node = nodeAt(arg0);
if(node == null)
throw new NoSuchElementException();
return node.obj;
}
@Override
public K getFirst()
{
final CMListNode node = nodeAt(0);
if(node != null)
return node.obj;
throw new NoSuchElementException();
}
@Override
public K getLast()
{
final CMListNode node = nodeAt(size-1);
if(node != null)
return node.obj;
throw new NoSuchElementException();
}
@Override
public int indexOf(Object arg0)
{
for(final ListIterator<K> o=listIterator();o.hasNext();)
{
if(o.next()==arg0)
return o.previousIndex();
}
return -1;
}
@Override
public int lastIndexOf(Object arg0)
{
int i=size-1;
for(final Iterator<K> o=descendingIterator();o.hasNext();)
{
if(o.next()==arg0)
return i;
i--;
}
return -1;
}
@Override
public ListIterator<K> listIterator(final int arg0)
{
final CMListNode firstNode=nodeAt(arg0);
return new ListIterator<K>()
{
private CMListNode lastNode = null;
private CMListNode nextNode = firstNode;
private int nextIndex = arg0;
private CMListNode prevNode = null;
private void makeNext()
{
if(nextNode != null)
{
prevNode=nextNode;
nextIndex++;
nextNode=nextNode.next;
while((nextNode != null)&&(!nextNode.active))
nextNode=nextNode.next;
}
}
private void makePrev()
{
if(prevNode != null)
{
nextNode=prevNode;
nextIndex--;
prevNode=prevNode.prev;
while((prevNode != null)&&(!prevNode.active))
prevNode=prevNode.prev;
}
}
@Override public boolean hasNext() { return nextNode != null; }
@Override
public K next()
{
if(!hasNext())
throw new NoSuchElementException();
lastNode=nextNode;
final K obj=nextNode.obj;
makeNext();
return obj;
}
@Override
public void remove()
{
removeNode(lastNode);
}
@Override
public void add(K arg0)
{
addAfter(prevNode,arg0);
}
@Override public boolean hasPrevious() { return prevNode != null; }
@Override
public int nextIndex()
{
if(!hasNext())
return size;
return nextIndex;
}
@Override
public K previous()
{
if(!hasPrevious())
throw new NoSuchElementException();
lastNode=prevNode;
final K obj=prevNode.obj;
makePrev();
return obj;
}
@Override
public int previousIndex()
{
if(!hasPrevious())
return -1;
return nextIndex-1;
}
@Override
public void set(K arg0)
{
if(lastNode == null)
throw new IllegalStateException();
lastNode.obj=arg0;
}
};
}
@Override
public synchronized boolean offer(K arg0)
{
return add(arg0);
}
@Override
public synchronized boolean offerFirst(K arg0)
{
addFirst(arg0);
return true;
}
@Override
public synchronized boolean offerLast(K arg0)
{
addLast(arg0);
return true;
}
@Override
public K peek()
{
return peekFirst();
}
@Override
public K peekFirst()
{
if(size == 0)
return null;
return head.obj;
}
@Override
public K peekLast()
{
if(size == 0)
return null;
return head.obj;
}
@Override
public synchronized K poll()
{
if(size == 0)
return null;
return removeFirst();
}
@Override
public synchronized K pollFirst()
{
if(size == 0)
return null;
return removeFirst();
}
@Override
public synchronized K pollLast()
{
if(size == 0)
return null;
return removeLast();
}
@Override
public synchronized K pop()
{
return removeFirst();
}
@Override
public synchronized void push(K arg0)
{
addFirst(arg0);
}
@Override
public synchronized K remove()
{
return removeFirst();
}
@Override
public synchronized K remove(int arg0)
{
final CMListNode node=nodeAt(arg0);
if(node == null)
throw new NoSuchElementException();
removeNode(node);
return node.obj;
}
@Override
public synchronized boolean remove(Object arg0)
{
return removeFirstOccurrence(arg0);
}
@Override
public synchronized K removeFirst()
{
final CMListNode node=nodeAt(0);
if(node == null)
throw new NoSuchElementException();
removeNode(node);
return node.obj;
}
@Override
public synchronized boolean removeFirstOccurrence(Object arg0)
{
final CMListNode node = findFirstNode(arg0);
if(node == null)
return false;
removeNode(node);
return true;
}
@Override
public synchronized K removeLast()
{
final CMListNode node=nodeAt(size-1);
if(node == null)
throw new NoSuchElementException();
removeNode(node);
return node.obj;
}
@Override
public synchronized boolean removeLastOccurrence(Object arg0)
{
final CMListNode node = findLastNode(arg0);
if(node == null)
return false;
removeNode(node);
return true;
}
@Override
public synchronized K set(int arg0, K arg1)
{
final CMListNode node = nodeAt(arg0);
if(node == null)
throw new NoSuchElementException();
final K oldObj=node.obj;
node.obj=arg1;
return oldObj;
}
@Override
public int size()
{
return size;
}
@Override
public synchronized Object[] toArray()
{
final Object[] result = new Object[size];
int i = 0;
for (CMListNode e = head; e != null; e = e.next)
result[i++] = e.obj;
return result;
}
@SuppressWarnings("unchecked")
@Override
public synchronized <T> T[] toArray(T[] arg0)
{
if (arg0.length < size)
arg0 = (T[])java.lang.reflect.Array.newInstance(arg0.getClass().getComponentType(), size);
int i = 0;
final Object[] result = arg0;
for (CMListNode e = head; e != null; e = e.next)
result[i++] = e.obj;
if (arg0.length > size)
arg0[size] = null;
return arg0;
}
@Override
public Iterator<K> iterator()
{
return listIterator();
}
@Override
public boolean equals(Object arg0)
{
return this==arg0;
}
@Override
public int hashCode()
{
int hashCode = 1;
final Iterator<K> i = iterator();
while (i.hasNext())
{
final K obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;
}
@Override
public ListIterator<K> listIterator()
{
return listIterator(0);
}
@Override
public List<K> subList(int arg0, int arg1)
{
final CMList<K> newList=new CMList<K>();
for(final ListIterator<K> l=listIterator();l.hasNext();)
{
final K obj=l.next();
if((l.previousIndex() >=arg0) && (l.previousIndex() < arg1))
newList.add(obj);
}
return newList;
}
@Override
public boolean containsAll(Collection<?> c)
{
for(final Object o : c)
if(!contains(o))
return false;
return true;
}
@Override
public boolean isEmpty()
{
return size==0;
}
@Override
public synchronized boolean removeAll(Collection<?> c)
{
if(c.size()==0)
return true;
boolean success=false;
for (final Object name : c)
success=remove(name)||success;
return success;
}
@Override
public synchronized boolean retainAll(Collection<?> c)
{
boolean modified = false;
for(final Iterator<K> e = iterator();e.hasNext();)
{
final Object o=e.next();
if((o!=null)&&(!c.contains(o)))
{
e.remove();
modified=true;
}
}
return modified;
}
@Override
public String toString()
{
final Iterator<K> i = iterator();
if (! i.hasNext())
return "[]";
final StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;)
{
final K e = i.next();
sb.append(e == this ? "(this Collection)" : e);
if (! i.hasNext())
return sb.append(']').toString();
sb.append(", ");
}
}
}
