001    /**
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.fusesource.hawtdb.util.list;
018    
019    import java.util.ArrayList;
020    import java.util.Map.Entry;
021    
022    import org.fusesource.hawtdb.util.Comparators;
023    import org.fusesource.hawtdb.util.TreeMap;
024    
025    public class SortedLinkedList<T extends SortedLinkedListNode<T>> {
026    
027        protected final TreeMap<Long, T> index;
028        T head;
029        int size;
030       
031        public SortedLinkedList() {
032            index = new TreeMap<Long, T>(Comparators.LONG_COMPARATOR);
033        }
034    
035        public boolean isEmpty() {
036            return head == null;
037        }
038    
039        public void add(T node) {
040            T prev = null;
041            if (head != null) {
042                // Optimize for case where this is at tail:
043                if (head.prev.getSequence() < node.getSequence()) {
044                    prev = head.prev;
045                } else {
046                    Entry<Long, T> entry = index.lowerEntry(node.getSequence());
047                    if (entry != null) {
048                        prev = entry.getValue();
049                    }
050                }
051            }
052            // T prev = index.lower(node);
053            // If this the lowest then the new head is this.
054            if (prev == null) {
055                node.linkToHead(this);
056            } else {
057                prev.linkAfter(node);
058            }
059        }
060        
061        /**
062         * @param sequence The sequence number of the element to get.
063         */
064        public T get(long sequence) {
065            return index.get(sequence);
066        }
067    
068        public T lower(long sequence, boolean inclusive) {
069            Entry<Long, T> lower = index.floorEntry(sequence);
070            if (lower == null) {
071                return null;
072            }
073    
074            if (inclusive) {
075                return lower.getValue();
076            }
077    
078            if (lower.getKey() == sequence) {
079                return lower.getValue().prev;
080            } else {
081                return lower.getValue();
082            }
083    
084        }
085    
086        public T upper(long sequence, boolean inclusive) {
087            if (head == null || head.prev.getSequence() < sequence) {
088                return null;
089            }
090    
091            Entry<Long, T> upper = index.ceilingEntry(sequence);
092            if (upper == null) {
093                return null;
094            }
095    
096            if (inclusive) {
097                return upper.getValue();
098            }
099    
100            if (upper.getKey() == sequence) {
101                return upper.getValue().next;
102            } else {
103                return upper.getValue();
104            }
105        }
106    
107        public void remove(T node) {
108            if (node.list == this) {
109                node.unlink();
110            }
111        }
112    
113        public T getHead() {
114            return head;
115        }
116    
117        public T getTail() {
118            return head.prev;
119        }
120    
121        public void clear() {
122            while (head != null) {
123                head.unlink();
124            }
125            index.clear();
126        }
127    
128        public int size() {
129            return size;
130        }
131    
132        @Override
133        public String toString() {
134            StringBuilder sb = new StringBuilder();
135            sb.append("[");
136            boolean first = true;
137            T cur = getHead();
138            while (cur != null) {
139                if (!first) {
140                    sb.append(", ");
141                }
142                sb.append(cur);
143                first = false;
144                cur = cur.getNext();
145            }
146            sb.append("]");
147            return sb.toString();
148        }
149    
150        /**
151         * Copies the nodes of the LinkedNodeList to an ArrayList.
152         * 
153         * @return
154         */
155        public ArrayList<T> toArrayList() {
156            ArrayList<T> rc = new ArrayList<T>(size);
157            T cur = head;
158            while (cur != null) {
159                rc.add(cur);
160                cur = cur.getNext();
161            }
162            return rc;
163        }
164    
165        
166    }