001/**
002 * Copyright (C) 2006-2024 Talend Inc. - www.talend.com
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016package org.talend.sdk.component.api.record;
017
018import java.util.Collections;
019import java.util.HashMap;
020import java.util.Iterator;
021import java.util.Map;
022import java.util.NoSuchElementException;
023import java.util.Optional;
024import java.util.function.Consumer;
025import java.util.function.Function;
026import java.util.stream.Stream;
027import java.util.stream.StreamSupport;
028
029import lombok.AllArgsConstructor;
030import lombok.Getter;
031
032/**
033 * On TCK Record, we have to control order of elements with keeping efficient access.
034 * LinkedHashMap has efficient access, but order of element is only the order of insertions.
035 * List (ArrayList, LinkedList) allow to fine control order but have inefficent access.
036 * This class aims to control element order with keeping efficient access.
037 * 
038 * @param <T> : type of element.
039 */
040public class OrderedMap<T> {
041
042    private static final String NOT_IN_SCHEMA = "%s not in schema";
043
044    @AllArgsConstructor
045    static class Node<T> implements Iterable<Node<T>> {
046
047        @Getter
048        public T value;
049
050        public Node<T> next;
051
052        public Node<T> prec;
053
054        public Node<T> insert(final T newValue) {
055            final Node<T> newNode = new Node<>(newValue, this.next, this);
056            return this.insert(newNode);
057        }
058
059        public Node<T> insert(final Node<T> newNode) {
060            if (newNode == this) {
061                return newNode;
062            }
063            if (this.next != null) {
064                this.next.prec = newNode;
065            }
066            newNode.prec = this;
067            newNode.next = this.next;
068            this.next = newNode;
069
070            return newNode;
071        }
072
073        public void remove() {
074            if (next != null) {
075                this.next.prec = this.prec;
076            }
077            if (this.prec != null) {
078                this.prec.next = this.next;
079            }
080            this.next = null;
081            this.prec = null;
082        }
083
084        public void swapWith(final Node<T> other) {
085            if (this.next == other) { // case this -> other direct
086                this.swapWithNext();
087            } else if (other.next == this) { // case other -> this direct
088                other.swapWithNext();
089            } else { // general case
090                this.swapWithOther(other);
091            }
092        }
093
094        /**
095         * switch current node with its next
096         * For example : 1 <=> 2(this) <=> 3 <=> 4
097         * will be transformed to : 1 <=> 3 <=> 2(this) <=> 4
098         */
099        void swapWithNext() {
100            final Node<T> nextNode = this.next;
101            if (nextNode == null) {
102                return;
103            }
104            // save what will be changed
105            final Node<T> firstPrec = this.prec;
106            final Node<T> nextNext = nextNode.next;
107
108            // change next node
109            nextNode.next = this;
110            nextNode.prec = this.prec;
111
112            // change prec.next to new next
113            if (firstPrec != null) {
114                firstPrec.next = nextNode;
115            }
116            this.prec = nextNode;
117            this.next = nextNext;
118            if (nextNext != null) {
119                nextNext.prec = this;
120            }
121        }
122
123        void swapWithOther(final Node<T> other) {
124            // save prec & next
125            final Node<T> firstPrec = this.prec;
126            final Node<T> firstNext = this.next;
127
128            final Node<T> secondPrec = other.prec;
129            final Node<T> secondNext = other.next;
130
131            // Put this node at other node place
132            this.prec = secondPrec;
133            if (secondPrec != null) {
134                secondPrec.next = this;
135            }
136            this.next = secondNext;
137            if (secondNext != null) {
138                secondNext.prec = this;
139            }
140
141            // Put other node at this node place
142            other.prec = firstPrec;
143            if (firstPrec != null) {
144                firstPrec.next = other;
145            }
146            other.next = firstNext;
147            if (firstNext != null) {
148                firstNext.prec = other;
149            }
150        }
151
152        @Override
153        public Iterator<Node<T>> iterator() {
154            return new NodeIterator<>(this);
155        }
156
157        @AllArgsConstructor
158        static class NodeIterator<T> implements Iterator<Node<T>> {
159
160            private Node<T> current;
161
162            @Override
163            public boolean hasNext() {
164                return current != null;
165            }
166
167            @Override
168            public Node<T> next() {
169                if (!this.hasNext()) {
170                    throw new NoSuchElementException("no further node");
171                }
172                final Node<T> next = this.current;
173                this.current = next.next;
174                return next;
175            }
176        }
177    }
178
179    private Node<T> first;
180
181    private Node<T> last;
182
183    private final Map<String, Node<T>> values = new HashMap<>();
184
185    private final Function<T, String> identifierGetter;
186
187    public OrderedMap(final Function<T, String> identifierGetter) {
188        this(identifierGetter, Collections.emptyList());
189    }
190
191    public OrderedMap(final Function<T, String> identifierGetter,
192            final Iterable<T> inputValues) {
193        this.identifierGetter = identifierGetter;
194        inputValues.forEach(this::addValue);
195    }
196
197    public Stream<T> streams() {
198        if (this.first == null) {
199            return Stream.empty();
200        }
201        return StreamSupport.stream(this.first.spliterator(), false)
202                .map(Node<T>::getValue);
203    }
204
205    public void forEachValue(final Consumer<T> valueConsumer) {
206        if (this.first != null) {
207            this.first.forEach((Node<T> node) -> valueConsumer.accept(node.getValue()));
208        }
209    }
210
211    public void removeValue(final T value) {
212        final String identifier = this.identifierGetter.apply(value);
213        final Node<T> node = this.values.remove(identifier);
214        if (node == null) {
215            throw new IllegalArgumentException(
216                    "No node '" + identifier + "' expected in values");
217        }
218        this.removeFromChain(node);
219    }
220
221    private void removeFromChain(final Node<T> node) {
222        if (this.first == node) {
223            this.first = node.next;
224        }
225        if (this.last == node) {
226            this.last = node.prec;
227        }
228        node.remove();
229    }
230
231    public T getValue(final String identifier) {
232        return Optional.ofNullable(this.values.get(identifier)) //
233                .map(Node::getValue) //
234                .orElse(null);
235    }
236
237    public void replace(final String identifier, final T newValue) {
238        final Node<T> node = this.values.remove(identifier);
239        if (node != null) {
240            node.value = newValue;
241            final String newIdentifier = this.identifierGetter.apply(newValue);
242            this.values.put(newIdentifier, node);
243        }
244    }
245
246    public void addValue(final T value) {
247        final String name = this.identifierGetter.apply(value);
248        if (this.values.containsKey(name)) {
249            return;
250        }
251        if (this.first == null) {
252            this.first = new Node<>(value, null, null);
253            this.last = this.first;
254            this.values.put(name, this.first);
255        } else {
256            final Node<T> newNode = this.last.insert(value);
257            this.values.put(name, newNode);
258            this.last = newNode;
259        }
260    }
261
262    public void moveAfter(final String pivotIdentifier, final T valueToMove) {
263        final Node<T> pivotNode = this.values.get(pivotIdentifier);
264        if (pivotNode == null) {
265            throw new IllegalArgumentException(String.format(NOT_IN_SCHEMA, pivotIdentifier));
266        }
267        final String identifier = this.identifierGetter.apply(valueToMove);
268        final Node<T> nodeToMove = this.values.get(identifier);
269
270        this.removeFromChain(nodeToMove);
271        pivotNode.insert(nodeToMove);
272        if (pivotNode == this.last) {
273            this.last = nodeToMove;
274        }
275    }
276
277    /**
278     * New Value should take place before 'pivotIdentifier' value
279     *
280     * @param pivotIdentifier : value pivotIdentifier to move before (pivot).
281     * @param valueToMove : value to move.
282     */
283    public void moveBefore(final String pivotIdentifier, final T valueToMove) {
284        final Node<T> nodePivot = this.values.get(pivotIdentifier);
285        if (nodePivot == null) {
286            throw new IllegalArgumentException(String.format(NOT_IN_SCHEMA, pivotIdentifier));
287        }
288        final String newValueName = this.identifierGetter.apply(valueToMove);
289        final Node<T> nodeToMove = this.values.get(newValueName);
290
291        this.removeFromChain(nodeToMove);
292        if (nodePivot == this.first) {
293            nodeToMove.next = nodePivot;
294            nodePivot.prec = nodeToMove;
295            this.first = nodeToMove;
296        } else {
297            nodePivot.prec.insert(nodeToMove);
298        }
299    }
300
301    public void swap(final String first, final String second) {
302        if (first == null || second == null || first.equals(second)) {
303            return;
304        }
305        final Node<T> firstNode = this.values.get(first);
306        if (firstNode == null) {
307            throw new IllegalArgumentException(String.format(NOT_IN_SCHEMA, first));
308        }
309        final Node<T> secondNode = this.values.get(second);
310        if (secondNode == null) {
311            throw new IllegalArgumentException(String.format(NOT_IN_SCHEMA, secondNode));
312        }
313
314        firstNode.swapWith(secondNode);
315
316        if (this.first == firstNode) {
317            this.first = secondNode;
318        } else if (this.first == secondNode) {
319            this.first = firstNode;
320        }
321        if (this.last == firstNode) {
322            this.last = secondNode;
323        } else if (this.last == secondNode) {
324            this.last = firstNode;
325        }
326    }
327
328}