[ https://issues.apache.org/jira/browse/GOSSIP-59?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15884743#comment-15884743 ]
ASF GitHub Bot commented on GOSSIP-59: -------------------------------------- Github user makrusak commented on a diff in the pull request: https://github.com/apache/incubator-gossip/pull/36#discussion_r103104210 --- Diff: src/main/java/org/apache/gossip/crdt/OrSet.java --- @@ -0,0 +1,295 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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. + */ +package org.apache.gossip.crdt; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.UUID; + +import org.apache.gossip.crdt.OrSet.Builder.Operation; + +public class OrSet<E> implements Crdt<Set<E>, OrSet<E>> { + + private final Map<E, Set<UUID>> elements = new HashMap<>(); + private final Map<E, Set<UUID>> tombstones = new HashMap<>(); + private final transient Set<E> val; + + public OrSet(){ + val = computeValue(); + } + + OrSet(Map<E, Set<UUID>> elements, Map<E, Set<UUID>> tombstones){ + this.elements.putAll(elements); + this.tombstones.putAll(tombstones); + val = computeValue(); + } + + @SafeVarargs + public OrSet(E ... elements){ + for (E e: elements){ + internalAdd(e); + } + val = computeValue(); + } + + public OrSet(Builder<E>builder){ + for (Builder<E>.OrSetElement<E> e: builder.elements){ + if (e.operation == Operation.ADD){ + internalAdd(e.element); + } else { + internalRemove(e.element); + } + } + val = computeValue(); + } + + public OrSet(OrSet<E> set, Builder<E> builder){ + elements.putAll(set.elements); + tombstones.putAll(set.tombstones); + for (Builder<E>.OrSetElement<E> e: builder.elements){ + if (e.operation == Operation.ADD){ + internalAdd(e.element); + } else { + internalRemove(e.element); + } + } + val = computeValue(); + } + + public OrSet(OrSet<E> left, OrSet<E> right){ + elements.putAll(left.elements); + elements.putAll(right.elements); + tombstones.putAll(left.tombstones); + tombstones.putAll(right.tombstones); + val = computeValue(); + } + + public OrSet.Builder<E> builder(){ + return new OrSet.Builder<>(); + } + + @Override + public OrSet<E> merge(OrSet<E> other) { + return new OrSet<E>(this, other); + } + + private void internalAdd(E element){ + Set<UUID> l = elements.get(element); + if (l == null){ + Set<UUID> d = new HashSet<UUID>(); + d.add(UUID.randomUUID()); + elements.put(element, d); + } else { + l.add(UUID.randomUUID()); + } + } + + private void internalRemove(E element){ + Set<UUID> elementIds = elements.get(element); + if (elementIds == null){ + //deleting elements not in the list + return; + } + Set<UUID> current = tombstones.get(element); + if (current != null){ + current.addAll(elementIds); + } else { + tombstones.put(element, elementIds); + } + } + + private Set<E> computeValue(){ + Set<E> values = new HashSet<>(); + for(E e: elements.keySet()){ + Set<UUID> deleteIds = tombstones.get(e); + if (deleteIds == null){ + values.add(e); + } else { + if (deleteIds.containsAll(elements.get(e))){ --- End diff -- Little strange if > Implement CRDT OrSet > -------------------- > > Key: GOSSIP-59 > URL: https://issues.apache.org/jira/browse/GOSSIP-59 > Project: Gossip > Issue Type: New Feature > Reporter: Edward Capriolo > Assignee: Edward Capriolo > > Currently we have a implementation of GrowOnlySet which is not a very > flexible type. The OrSet allows additional and deletions and having that will > be a nice building block. -- This message was sent by Atlassian JIRA (v6.3.15#6346)