Créer une SkipList nommée en Java qui ressemble à un ensemble trié redis

https://github.com/q-ikawa/skiplist-java

Comme Redis avec ʻO (log (N)) ・ Ajouter / supprimer par nom ・ Se référer à par index ・ Se référer au score (plage de score) ・ Référence par nom (Ceci est ʻO (1)(est un mensonge et est vraiment l'accès à la table de hachage)) Je voulais faire quelque chose que je pourrais faire.

Beaucoup d'autres implémentations de SkipList ne supportaient pas l'accès par nom / index (la théorie que je n'ai pas étudiée correctement), donc l'index peut être pris avec ʻO (log (N)) comme Redis. Et je l'ai rendu accessible par ʻO (1) même par son nom. L'index est mis à jour lors de l'ajout / suppression d'éléments de la même manière qu'une arborescence de segments. (Je pense que c'est une partie gênante lorsque l'on pense correctement et que l'on l'implémente. Donc, si cela devient un code de référence dans un tel cas.)

Comme les éléments et les gardes réels sont partagés sur Inteface, il y a beaucoup de Getters et Setters, et il semble que la quantité de code a augmenté pour le rendre facultatif, donc le style d'écriture plus classique est meilleur. C'est peut-être mieux. J'ai essayé d'obtenir la plage de score avec un itérateur. Il devrait être possible de le supprimer avec une plage, d'incrémenter le score d'une valeur spécifique, etc. en le combinant, et pour le moment, il n'y a pas d'utilisation spécifique pour le moment, donc je ne l'ai pas implémenté.

Ce n'est pas thread-safe. Cependant, je pense que Spliterator peut être facilement créé si la référence est divisée dans la hiérarchie au-dessus de SkipList, donc si elle est implémentée, cela se sentira bien en fonction de la situation (un flux parallèle peut être retourné). Je vais.

import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Optional;
import java.util.Random;
import java.util.StringJoiner;

import javax.management.RuntimeErrorException;

public class SkipList<K, E> {

	private final int MAX_HEIGHT;
	private Elements.Row<E> topRow;
	private final Map<K, IElement<E>> map;
	private final Random r;

	int size;

	public SkipList() {
		this(0x1000);
	}

	/**
	 * @param size
	 *            The depth of the skip list depends on parameter {@code size}.
	 */
	public SkipList(int size) {
		this.MAX_HEIGHT = Math.max(5, (int) Math.log(size));
		topRow = Elements.createInitialRow();
		map = new HashMap<K, IElement<E>>(size);
		r = new Random(System.currentTimeMillis());
	}

	/**
	 * insert or overwrite by given element
	 * @param key
	 * @param value
	 * @param score
	 */
	public void put(K key, E value, double score) {
		if (map.containsKey(key)) {
			remove(key);
		}
		insert(key, value, score);
	}

	/**
	 * remove element by key
	 * @param key
	 */
	public void remove(K key) {
		IElement<E> elem = map.get(key);

		IElement<E> cursol = elem;
		for (;;) {
			IElement<E> prevRight = cursol.getRight().orElseThrow(() -> SkipListError.ElementMustHaveRightElement);
			IElement<E> prevLeft = cursol.getLeft().orElseThrow(() -> SkipListError.ElementMustHaveLeftElement);

			prevLeft.setRight(prevRight);
			prevRight.setLeft(prevLeft);

			int skipNum = cursol.getSkipNum();
			prevRight.incrementSkipNum(skipNum - 1);

			if (cursol.getDown().isPresent()) {
				cursol = cursol.getDown().get();
			} else {
				break;
			}
		}

		cursol = elem;
		for (;;) {
			if (!cursol.getUp().isPresent() && !cursol.getRight().isPresent()) {
				break;
			}
			if (cursol.getUp().isPresent()) {
				cursol = cursol.getUp().get();
				cursol.incrementSkipNum(-1);
				continue;
			}
			if (cursol.getRight().isPresent()) {
				cursol = cursol.getRight().get();
			}
		}

		size--;
		map.remove(key);
	}

	private void insert(K key, E value, double score) {

		int height = randomHeight();

		IElement<E> newRight = getInertPointByScore(score);
		IElement<E> newLeft = newRight.getLeft().orElseThrow(() -> SkipListError.ElementMustHaveLeftElement);
		IElement<E> nextBottom;
		{
			IElement<E> newElem = new Element<E>(value, score);
			newElem.setLeft(newLeft);
			newElem.setRight(newRight);
			newElem.incrementSkipNum(1);
			newRight.setLeft(newElem);
			newLeft.setRight(newElem);
			nextBottom = newElem;
		}
		for (int i = 0; i < height; i++) {
			int distanceToLeft = nextBottom.getSkipNum();
			for (; !newRight.getUp().isPresent();) {
				if (!newRight.getRight().isPresent()) {
					topRow = Elements.createTopRow(topRow);
					topRow.mostRight.incrementSkipNum(size + 1);
					break;
				}
				newRight = newRight.getRight().get();
			}
			newRight = newRight.getUp().get();
			for (; !newLeft.getUp().isPresent();) {
				distanceToLeft += newLeft.getSkipNum();
				newLeft = newLeft.getLeft().orElseThrow(() -> SkipListError.ElementMustHaveLeftElement);
			}
			newLeft = newLeft.getUp().get();

			IElement<E> newElem = new Element<E>(value, score);
			newElem.setLeft(newLeft);
			newElem.setRight(newRight);
			newElem.setDown(nextBottom);
			nextBottom.setUp(newElem);
			newElem.incrementSkipNum(distanceToLeft);
			newRight.setLeft(newElem);
			newRight.incrementSkipNum(-distanceToLeft + 1);
			newLeft.setRight(newElem);
			nextBottom = newElem;
		}

		for (;;) {
			if (!newRight.getUp().isPresent() && !newRight.getRight().isPresent()) {
				break;
			}
			if (newRight.getUp().isPresent()) {
				newRight = newRight.getUp().get();
				newRight.incrementSkipNum(1);
				continue;
			}
			if (newRight.getRight().isPresent()) {
				newRight = newRight.getRight().get();
			}
		}
		size++;
		map.put(key, nextBottom);
	}

	/**
	 * get element by key
	 * @param key
	 * @return
	 */
	public Optional<E> get(K key) {
		return _get(key).flatMap(elem -> elem.value());
	}

	/**
	 * get element by index
	 * @param i
	 * @return
	 */
	public Optional<E> at(int i) {
		return _at(i).flatMap(elem -> elem.value());
	}

	/**
	 * get index by score
	 * @param score
	 * @return element witch has minimum score bigger than {@code score} 
	 */
	public int getIndexByScore(double score) {
		IElement<E> current = topRow.mostLeft;
		int currentPos = 0;
		for (;;) {
			IElement<E> next = current.getRight().orElseThrow(() -> SkipListError.ElementMustHaveRightElement);
			if (next.getScore() < score) {
				current = next;
				currentPos += next.getSkipNum();
				continue;
			}
			if (!current.getDown().isPresent()) {
				return currentPos;
			}
			current = current.getDown().get();
		}
	}
	/**
	 * get iterator by score range
	 * @param minScoreInclusive
	 * @param maxScoreExclusive
	 * @return
	 */
	public Iterable<E> getIterableByRange(double minScoreInclusive, double maxScoreExclusive){
		int start = getIndexByScore(minScoreInclusive);
		
		Optional<IElement<E>> elem = _at(start);
		if(!elem.isPresent()){
			return new Iterable<E>(){
				@Override
				public Iterator<E> iterator() {
					return 	Collections.emptyIterator();
				}
			};
		}
		for(;elem.get().getDown().isPresent();){
			elem = elem.get().getDown();
		}
		
		final Optional<IElement<E>> initialElement = elem;
		return new Iterable<E>(){
			public Iterator<E> iterator(){
				return new Iterator<E>() {
					Optional<IElement<E>> next = initialElement; 
					@Override
					public boolean hasNext() {
						return next.isPresent() && next.get().value().isPresent() && next.get().getScore() < maxScoreExclusive;
					}

					@Override
					public E next() {
						if(!hasNext()){
							throw new IllegalStateException("Illiegal access for an iterator happened."+this.toString());
						}
						E result = next.get().value().get();
						next = next.get().getRight();
						return result;
					}
				};
			}
		};
	}

	private Optional<IElement<E>> _at(int i) {
 		if (i < 0 || i >= size) {
			return Optional.empty();
		}
		int currentPos = -1;
		IElement<E> current = topRow.mostLeft;
		for (;;) {
			IElement<E> next = current.getRight().orElseThrow(() -> SkipListError.ElementMustHaveRightElement);
			for (;;) {
				if (currentPos + next.getSkipNum() <= i) {
					break;
				}
				current = current.getDown().orElseThrow(() -> SkipListError.ElementMustHaveDownElement);
				next = current.getRight().orElseThrow(() -> SkipListError.ElementMustHaveRightElement);
			}

			if (currentPos + next.getSkipNum() == i) {
				return Optional.of(next);
			}
			currentPos = currentPos + next.getSkipNum();
			current = next;
		}
	}

	private IElement<E> getInertPointByScore(double score) {
		IElement<E> current = topRow.mostLeft;
		for (;;) {
			IElement<E> next = current.getRight().orElseThrow(() -> SkipListError.ElementMustHaveRightElement);
			if (next.getScore() < score) {
				current = next;
				continue;
			}
			if (!current.getDown().isPresent()) {
				return next;
			}
			current = current.getDown().get();
		}
	}

	private Optional<IElement<E>> _get(K key) {
		if (map.containsKey(key)) {
			return Optional.of(map.get(key));
		} else {
			return Optional.empty();
		}
	}

	// return 0 with probability 1/2,
	// 1 with probability 1/4,
	// 2 with probability 1/8,
	// 3 with probability 1/16,
	// 4 with probability 1/32,
	// …
	// MAX_HEIGHT with probability 2^(-MAX_HEIGHT)
	private int randomHeight() {
		int bound = 1 << (MAX_HEIGHT - 1);
		int random = r.nextInt(bound);
		int count = 0;
		for (; (random & 1) == 1; count++) {
			random = random >> 1;
		}
		return count + 1;
	}

	String deepToString() {
		StringJoiner lines = new StringJoiner("\n", "{\n", "\n}");
		for (IElement<E> mostLeft = topRow.mostLeft;;) {
			StringJoiner sj = new StringJoiner(", ");

			for (IElement<E> current = mostLeft;;) {
				sj.add(current.deepToString());
				if (!current.getRight().isPresent()) {
					break;
				}
				current = current.getRight().get();
			}
			lines.add(sj.toString());

			if (!mostLeft.getDown().isPresent()) {
				break;
			}
			mostLeft = mostLeft.getDown().get();
		}
		return lines.toString();
	}

}

class SkipListError extends RuntimeErrorException {
	private static final long serialVersionUID = -9054212978445616068L;

	public SkipListError(Error e) {
		super(e);
	}

	public final static SkipListError ElementMustHaveRightElement = new SkipListError(
			new Error("ElementMustHaveRightElement"));
	public final static SkipListError ElementMustHaveLeftElement = new SkipListError(
			new Error("ElementMustHaveLeftElement"));
	public final static SkipListError ElementMustHaveDownElement = new SkipListError(
			new Error("ElementMustHaveDownElement"));
	public final static SkipListError IncrementSkipNumOfLeftSentinelMustNotBeCalled = new SkipListError(
			new Error("IncrementSkipNumOfLeftSentinelMustNotBeCalled"));
}

interface IElement<E> {
	Optional<IElement<E>> getUp();

	Optional<IElement<E>> getDown();

	Optional<IElement<E>> getLeft();

	Optional<IElement<E>> getRight();

	void setUp(IElement<E> upper);

	void setDown(IElement<E> bottom);

	void setLeft(IElement<E> left);

	void setRight(IElement<E> right);

	Optional<E> value();

	double getScore();

	int getSkipNum();

	void incrementSkipNum(int i);

	String deepToString();
}

class Element<E> implements IElement<E> {
	IElement<E> upper;
	IElement<E> bottom;
	IElement<E> left;
	IElement<E> right;

	final E _value;
	final double score;

	int skipNum;

	public Element(E _value, double score) {
		this._value = _value;
		this.score = score;
	}

	@Override
	public Optional<IElement<E>> getUp() {
		return Optional.ofNullable(upper);
	}

	@Override
	public Optional<IElement<E>> getDown() {
		return Optional.ofNullable(bottom);
	}

	@Override
	public Optional<IElement<E>> getLeft() {
		return Optional.of(left);
	}

	@Override
	public Optional<IElement<E>> getRight() {
		return Optional.of(right);
	}

	@Override
	public Optional<E> value() {
		return Optional.of(_value);
	}

	@Override
	public void setUp(IElement<E> upper) {
		this.upper = upper;
	}

	@Override
	public void setDown(IElement<E> bottom) {
		this.bottom = bottom;
	}

	@Override
	public void setLeft(IElement<E> left) {
		this.left = left;
	}

	@Override
	public void setRight(IElement<E> right) {
		this.right = right;
	}

	@Override
	public double getScore() {
		return score;
	}

	@Override
	public int getSkipNum() {
		return skipNum;
	}

	@Override
	public void incrementSkipNum(int i) {
		skipNum += i;
	}

	@Override
	public String deepToString() {
		return String.format("[val: %s. score: %g, skip: %d]", value(), getScore(), getSkipNum());
	}

}

abstract class SentinelElement<E> implements IElement<E> {
	IElement<E> upper;
	IElement<E> bottom;
	IElement<E> left;
	IElement<E> right;

	@Override
	public Optional<IElement<E>> getUp() {
		return Optional.ofNullable(upper);
	}

	@Override
	public Optional<IElement<E>> getDown() {
		return Optional.ofNullable(bottom);
	}

	@Override
	public Optional<IElement<E>> getLeft() {
		return Optional.ofNullable(left);
	}

	@Override
	public Optional<IElement<E>> getRight() {
		return Optional.ofNullable(right);
	}

	@Override
	public Optional<E> value() {
		return Optional.empty();
	}

	@Override
	public void setUp(IElement<E> upper) {
		this.upper = upper;
	}

	@Override
	public void setDown(IElement<E> bottom) {
		this.bottom = bottom;
	}

	@Override
	public void setLeft(IElement<E> left) {
		this.left = left;
	}

	@Override
	public void setRight(IElement<E> right) {
		this.right = right;
	}

	static class Left<E> extends SentinelElement<E> {
		@Override
		public double getScore() {
			return -Double.MAX_VALUE;
		}

		@Override
		public int getSkipNum() {
			return 0;
		}

		@Override
		public void incrementSkipNum(int i) {
			throw SkipListError.IncrementSkipNumOfLeftSentinelMustNotBeCalled;
		}

		@Override
		public String deepToString() {
			return String.format("[LEFT. score: %g, skip: %d]", getScore(), getSkipNum());
		}

	}

	static class Right<E> extends SentinelElement<E> {
		@Override
		public double getScore() {
			return Double.MAX_VALUE;
		}

		int skipNum;

		@Override
		public int getSkipNum() {
			return skipNum;
		}

		@Override
		public void incrementSkipNum(int i) {
			skipNum += i;
		}

		@Override
		public String deepToString() {
			return String.format("[RIGHT. score: %g, skip: %d]", getScore(), getSkipNum());
		}
	}

}

class Elements {

	static class Row<E> {
		final IElement<E> mostLeft;
		final IElement<E> mostRight;

		public Row(IElement<E> mostLeft, IElement<E> mostRight) {
			this.mostLeft = mostLeft;
			this.mostRight = mostRight;
		}

	}

	static <A> Row<A> createTopRow(Row<A> currentTopRow) {
		SentinelElement<A> left = new SentinelElement.Left<A>();
		left.bottom = currentTopRow.mostLeft;
		SentinelElement<A> right = new SentinelElement.Right<A>();
		right.bottom = currentTopRow.mostRight;
		left.right = right;
		right.left = left;

		left.bottom.setUp(left);
		right.bottom.setUp(right);

		return new Row<A>(left, right);
	}

	static <A> Row<A> createInitialRow() {
		SentinelElement<A> left = new SentinelElement.Left<A>();
		SentinelElement<A> right = new SentinelElement.Right<A>();
		left.right = right;
		right.left = left;

		return new Row<A>(left, right);
	}

}

   	SkipList<PersonId, Person> list = new SkipList<PersonId,Person>();
   	Person alice = new Person(new PersonName("Alice"),new Priority(10));
   	Person bob = new Person(new PersonName("Bob"),new Priority(20));
   	Person chuck = new Person(new PersonName("Chuck"),new Priority(30));
   	Person dan = new Person(new PersonName("Dan"),new Priority(40));
   	Person erin = new Person(new PersonName("Erin"),new Priority(50));
   	
   	list.put(new PersonId(1),alice,alice.priority.value);
   	list.put(new PersonId(2),bob,bob.priority.value);
   	list.put(new PersonId(3),chuck,chuck.priority.value);
   	list.put(new PersonId(4),dan,dan.priority.value);
   	list.put(new PersonId(5),erin,erin.priority.value);
   			
   	assertEquals(alice, list.at(0).get());
   	assertEquals(bob, list.at(1).get());
   	assertEquals(chuck, list.at(2).get());
   	assertEquals(dan, list.at(3).get());
   	assertEquals(erin, list.at(4).get());

   	Person franc = new Person(new PersonName("Franc"),new Priority(35));
   	// overwrite alice
   	list.put(new PersonId(1),franc,franc.priority.value);
   	
   	assertEquals(bob, list.at(0).get());
   	assertEquals(chuck, list.at(1).get());
   	assertEquals(franc, list.at(2).get());
   	assertEquals(dan, list.at(3).get());
   	assertEquals(erin, list.at(4).get());

J'ai pu obtenir une liste triée en toute sécurité. C'était plus facile que d'écrire une bifurcation équilibrée. C'est un sentiment intéressant que je puisse mettre un Spliterator, donc je voulais l'utiliser un jour.