From a4e4f6732b7506d491e0e3cff7e72d331ef2b56d Mon Sep 17 00:00:00 2001 From: bartimaeusnek <33183715+bartimaeusnek@users.noreply.github.com> Date: Sat, 14 Dec 2019 03:47:57 +0100 Subject: added Self Sorting List Signed-off-by: bartimaeusnek <33183715+bartimaeusnek@users.noreply.github.com> Former-commit-id: 60b2b9cdd5a015030c879bc1b06bb3f3bf8abeaf --- .../ASM/BWCoreStaticReplacementMethodes.java | 14 +- .../bartworks/util/selfsortinglist/SSList.java | 358 +++++++++++++++++++++ .../util/selfsortinglist/SSListIterators.java | 139 ++++++++ .../bartworks/util/selfsortinglist/SSListNode.java | 75 +++++ 4 files changed, 577 insertions(+), 9 deletions(-) create mode 100644 src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSList.java create mode 100644 src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListIterators.java create mode 100644 src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListNode.java (limited to 'src/main/java') diff --git a/src/main/java/com/github/bartimaeusnek/ASM/BWCoreStaticReplacementMethodes.java b/src/main/java/com/github/bartimaeusnek/ASM/BWCoreStaticReplacementMethodes.java index 3f692c176a..d5d35e50a5 100644 --- a/src/main/java/com/github/bartimaeusnek/ASM/BWCoreStaticReplacementMethodes.java +++ b/src/main/java/com/github/bartimaeusnek/ASM/BWCoreStaticReplacementMethodes.java @@ -22,6 +22,7 @@ package com.github.bartimaeusnek.ASM; +import com.github.bartimaeusnek.bartworks.util.selfsortinglist.SSList; import net.minecraft.inventory.InventoryCrafting; import net.minecraft.item.Item; import net.minecraft.item.ItemStack; @@ -30,12 +31,11 @@ import net.minecraft.item.crafting.IRecipe; import net.minecraft.world.World; import java.util.Iterator; -import java.util.LinkedList; import java.util.Optional; public class BWCoreStaticReplacementMethodes { - public static final LinkedList RECENTLYUSEDRECIPES = new LinkedList<>(); + public static final SSList RECENTLYUSEDRECIPES = new SSList<>(); @SuppressWarnings("ALL") public static ItemStack findCachedMatchingRecipe(InventoryCrafting inventoryCrafting, World world) { @@ -81,8 +81,8 @@ public class BWCoreStaticReplacementMethodes { } else { Optional iPossibleRecipe = Optional.empty(); int index = 0; - for (Iterator iterator = RECENTLYUSEDRECIPES.iterator(); iterator.hasNext(); ++index) { - IRecipe RECENTLYUSEDRECIPE = iterator.next(); + for (Iterator it = RECENTLYUSEDRECIPES.iterator(); it.hasNext();++index) { + IRecipe RECENTLYUSEDRECIPE = it.next(); if (RECENTLYUSEDRECIPE.matches(inventoryCrafting, world)) { iPossibleRecipe = Optional.of(RECENTLYUSEDRECIPE); break; @@ -90,11 +90,7 @@ public class BWCoreStaticReplacementMethodes { } if (iPossibleRecipe.isPresent()) { - if (index != 0) { - --index; - RECENTLYUSEDRECIPES.remove(iPossibleRecipe.get()); - RECENTLYUSEDRECIPES.add(index, iPossibleRecipe.get()); - } + RECENTLYUSEDRECIPES.addPrioToNode(index); return iPossibleRecipe.get().getCraftingResult(inventoryCrafting); } diff --git a/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSList.java b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSList.java new file mode 100644 index 0000000000..d320cd8316 --- /dev/null +++ b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSList.java @@ -0,0 +1,358 @@ +/* + * Copyright (c) 2018-2019 bartimaeusnek + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package com.github.bartimaeusnek.bartworks.util.selfsortinglist; + +import java.util.*; + +public class SSList implements List, Deque, Set { + + transient int size = 0; + transient SSListNode head; + transient SSListNode tail; + + public static SSList create(){ + return new SSList(); + } + + public SSList() {} + + @Override + public void addFirst(E t) { + final SSListNode first = head; + final SSListNode newNode = new SSListNode<>(null, t, first); + head = newNode; + if (first == null) + tail = newNode; + else + first.setBefore(newNode); + size++; + } + + @Override + public void addLast(E t) { + final SSListNode last = tail; + final SSListNode newNode = new SSListNode<>(last, t, null); + tail = newNode; + if (last == null) + head = newNode; + else + last.setNext(newNode); + size++; + } + + @Override + public boolean offerFirst(E e) { + return false; + } + + @Override + public boolean offerLast(E e) { + return false; + } + + @Override + public E removeFirst() { + return null; + } + + @Override + public E removeLast() { + return null; + } + + @Override + public E pollFirst() { + return null; + } + + @Override + public E pollLast() { + return null; + } + + @Override + public E getFirst() { + return peekFirst(); + } + + @Override + public E getLast() { + return peekLast(); + } + + @Override + public E peekFirst() { + return head != null ? head.getELEMENT() : null; + } + + @Override + public E peekLast() { + return tail != null ? tail.getELEMENT() : null; + } + + @Override + public boolean removeFirstOccurrence(Object o) { + return false; + } + + @Override + public boolean removeLastOccurrence(Object o) { + return false; + } + + @Override + public int size() { + return size; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public boolean contains(Object o) { + return false; + } + + @Override + public Iterator iterator() { + return new SSListIterators.SSListIterator<>(head); + } + + @Override + public Iterator descendingIterator() { + return new SSListIterators.SSListReverseIterator<>(tail); + } + + @Override + public Object[] toArray() { + Object[] ret = new Object[size]; + while (listIterator().hasNext()) + ret[listIterator().nextIndex()-1] = listIterator().next(); + return ret; + } + + @Override + public T[] toArray(T[] a) { + T[] ret = (T[]) new Object[size]; + while (listIterator().hasNext()) + ret[listIterator().nextIndex()-1] = (T) listIterator().next(); + return ret; + } + + @Override + public boolean add(E e) { + addLast(e); + return true; + } + + private void moveNodeUp(SSListNode node){ + if (node == head || node.getBefore() == null) + return; + final SSListNode before = node.getBefore(); + final SSListNode beforeBefore = before.getBefore(); + final SSListNode next = node.getNext(); + + // <0,1,2> <1,2,3> N<2,3,4> <3,4,5> + + node.setBefore(beforeBefore); + // <0,1,2> <1,2,3> N<0,3,4> <3,4,5> + + if (beforeBefore != null) + beforeBefore.setNext(node); + // <0,1,3> <1,2,3> N<0,3,4> <3,4,5> + + before.setBefore(node); + // <0,1,3> <3,2,3> N<0,3,4> <3,4,5> + + before.setNext(next); + // <0,1,3> <3,2,4> N<0,3,4> <3,4,5> + + if (next != null) + next.setBefore(before); + // <0,1,3> N<0,3,4> <3,2,4> <2,4,5> + + node.setNext(before); + // <0,1,3> N<0,3,2> <3,2,4> <2,4,5> + } + + private SSListNode getNode(int index) { + if (index <= (size / 2)) { + SSListNode x = head; + for (int i = 0; i < index; i++) + x = x.getNext(); + return x; + } else { + SSListNode x = tail; + for (int i = size - 1; i > index; i--) + x = x.getBefore(); + return x; + } + } + + @Override + public boolean offer(E e) { + return false; + } + + private boolean isValidIndex(int index) { + return index >= 0 && index < size; + } + + @Override + public E remove() { + return null; + } + + @Override + public E poll() { + return null; + } + + @Override + public E element() { + return null; + } + + @Override + public E peek() { + return null; + } + + @Override + public void push(E e) { + addFirst(e); + } + + @Override + public E pop() { + return null; + } + + @Override + public boolean remove(Object o) { + return false; + } + + @Override + public boolean containsAll(Collection c) { + return false; + } + + @Override + public boolean addAll(Collection c) { + for (E e : c) { + this.addLast(e); + } + return true; + } + + @Override + public boolean addAll(int index, Collection c) { + return false; + } + + @Override + public boolean removeAll(Collection c) { + return false; + } + + @Override + public boolean retainAll(Collection c) { + return false; + } + + @Override + public void clear() { + + } + + public void addPrioToNode(int index, long prio){ + if (!isValidIndex(index)) + return; + SSListNode node = getNode(index); + node.setPriority(node.getPriority()+prio); + if (node.getBefore() != null) + if (node.getPriority() > node.getBefore().getPriority()){ + moveNodeUp(node); + } + } + + public void addPrioToNode(int index){ + addPrioToNode(index,1L); + } + + @Override + public E get(int index) { + if (!isValidIndex(index)) + return null; + SSListNode node = getNode(index); + return node.getELEMENT(); + } + + @Override + public E set(int index, E element) { + return null; + } + + @Override + public void add(int index, E element) { + + } + + @Override + public E remove(int index) { + return null; + } + + @Override + public int indexOf(Object o) { + return 0; + } + + @Override + public int lastIndexOf(Object o) { + return 0; + } + + @Override + public ListIterator listIterator() { + return new SSListIterators.SSListListIterator<>(head,tail); + } + + @Override + public ListIterator listIterator(int index) { + return null; + } + + @Override + public List subList(int fromIndex, int toIndex) { + return null; + } + + @Override + public Spliterator spliterator() { + return null; + } +} diff --git a/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListIterators.java b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListIterators.java new file mode 100644 index 0000000000..c3f3aba347 --- /dev/null +++ b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListIterators.java @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2018-2019 bartimaeusnek + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package com.github.bartimaeusnek.bartworks.util.selfsortinglist; + +import org.apache.commons.lang3.NotImplementedException; + +import java.util.Iterator; +import java.util.ListIterator; + +public class SSListIterators { + + + public static class SSListListIterator implements ListIterator { + final SSListNode head; + final SSListNode tail; + SSListNode current; + int counter = 0; + public SSListListIterator(SSListNode head,SSListNode tail) { + this.head = head; + this.tail = tail; + current = null; + } + + @Override + public boolean hasNext() { + return head != current; + } + + @Override + public E next() { + counter++; + E ret = current.getELEMENT(); + current = current.getNext(); + return ret; + } + + @Override + public boolean hasPrevious() { + return tail != current; + } + + @Override + public E previous() { + counter--; + E ret = current.getELEMENT(); + current = current.getBefore(); + return ret; + } + + @Override + public int nextIndex() { + return counter+1; + } + + @Override + public int previousIndex() { + return counter-1; + } + + @Override + public void remove() { + throw new NotImplementedException("Not Implemented"); + } + + @Override + public void set(E e) { + throw new NotImplementedException("Not Implemented"); + } + + @Override + public void add(E e) { + throw new NotImplementedException("Not Implemented"); + } + } + + public static class SSListIterator implements Iterator { + final SSListNode head; + SSListNode current; + public SSListIterator(SSListNode head) { + this.head = head; + current = null; + } + + @Override + public boolean hasNext() { + return current != null; + } + + @Override + public E next() { + E ret = current.getELEMENT(); + current = current.getNext(); + return ret; + } + } + + public static class SSListReverseIterator implements Iterator { + final SSListNode tail; + SSListNode current; + + public SSListReverseIterator(SSListNode head) { + this.tail = head; + current = null; + } + + @Override + public boolean hasNext() { + return current != null; + } + + @Override + public E next() { + E ret = current.getELEMENT(); + current = current.getBefore(); + return ret; + } + } + +} diff --git a/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListNode.java b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListNode.java new file mode 100644 index 0000000000..f9c509019e --- /dev/null +++ b/src/main/java/com/github/bartimaeusnek/bartworks/util/selfsortinglist/SSListNode.java @@ -0,0 +1,75 @@ +/* + * Copyright (c) 2018-2019 bartimaeusnek + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package com.github.bartimaeusnek.bartworks.util.selfsortinglist; + +public class SSListNode { + + public final static SSListNode EMPTY_NODE = new SSListNode(null); + + private final E ELEMENT; + private long priority = Long.MIN_VALUE; + private SSListNode next; + private SSListNode before; + + public SSListNode(E element) { + ELEMENT = element; + } + + public SSListNode(SSListNode before, E element, SSListNode next) { + this.ELEMENT = element; + connect(next, before); + } + + public void connect(SSListNode next, SSListNode before){ + this.setNext(next); + this.setBefore(before); + } + + public E getELEMENT() { + return ELEMENT; + } + + public long getPriority() { + return priority; + } + + public void setPriority(long priority) { + this.priority = priority; + } + + public SSListNode getNext() { + return next; + } + + public void setNext(SSListNode next) { + this.next = next; + } + + public SSListNode getBefore() { + return before; + } + + public void setBefore(SSListNode before) { + this.before = before; + } +} -- cgit