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 }