KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > micronova > util > SparseList


1 /*
2
3 Copyright 2003-2007 MicroNova (R)
4 All rights reserved.
5
6 Redistribution and use in source and binary forms, with or
7 without modification, are permitted provided that the following
8 conditions are met:
9
10     * Redistributions of source code must retain the above copyright
11     notice, this list of conditions and the following disclaimer.
12
13     * Redistributions in binary form must reproduce the above copyright
14     notice, this list of conditions and the following disclaimer in the
15     documentation and/or other materials provided with the distribution.
16
17     * Neither the name of MicroNova nor the names of its contributors
18     may be used to endorse or promote products derived from this
19     software without specific prior written permission.
20
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
25 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 POSSIBILITY OF SUCH DAMAGE.
32
33 */
34
35
36 package com.micronova.util;
37
38 import java.util.*;
39
40 /** Sparse list implemented using TreeMap */
41
42 public class SparseList extends AbstractList implements SparseObject
43 {
44     protected TreeMap treeMap;
45     protected int _size;
46
47     public SparseList()
48     {
49         super();
50
51         treeMap = new TreeMap();
52         _size = 0;
53     }
54
55     public Object JavaDoc get(int index)
56     {
57         Integer JavaDoc integerIndex = new Integer JavaDoc(index);
58
59         SortedMap tailMap = treeMap.tailMap(integerIndex);
60
61         if ((tailMap != null) && (!tailMap.isEmpty()))
62         {
63             Object JavaDoc firstKey = tailMap.firstKey();
64
65             if (integerIndex.equals(firstKey))
66             {
67                 return tailMap.get(firstKey);
68             }
69         }
70
71         return null;
72     }
73
74     public int size()
75     {
76         return _size;
77     }
78
79     public Object JavaDoc set(int index, Object JavaDoc element)
80     {
81         Object JavaDoc previous = get(index);
82
83         treeMap.put(new Integer JavaDoc(index), element);
84
85         if (index >= _size)
86         {
87             _size = index + 1;
88         }
89
90         return previous;
91     }
92
93     public void add(int index, Object JavaDoc element)
94     {
95         SortedMap tailMap = treeMap.tailMap(new Integer JavaDoc(index));
96
97         if ((tailMap != null) && (!tailMap.isEmpty()))
98         {
99             ArrayList keyList = new ArrayList();
100             ArrayList valueList = new ArrayList();
101
102             Iterator iterator = tailMap.entrySet().iterator();
103
104             while (iterator.hasNext())
105             {
106                 Map.Entry entry = (Map.Entry)iterator.next();
107                 
108                 keyList.add(entry.getKey());
109                 valueList.add(entry.getValue());
110             }
111
112             for (int i = keyList.size(); --i >=0;)
113             {
114                 Integer JavaDoc key = (Integer JavaDoc)keyList.get(i);
115                 
116                 treeMap.remove(key);
117                 
118                 treeMap.put(new Integer JavaDoc(key.intValue() + 1), valueList.get(i));
119             }
120
121             _size ++;
122         }
123
124         set(index, element);
125     }
126
127     public Object JavaDoc remove(int index)
128     {
129         Object JavaDoc currentValue = get(index);
130
131         int size = _size;
132
133         if (index == size - 1)
134         {
135             treeMap.remove(new Integer JavaDoc(index));
136             _size = size - 1;
137         }
138         else if (index < size)
139         {
140             SortedMap tailMap = treeMap.tailMap(new Integer JavaDoc(index + 1));
141
142             if ((tailMap != null) && (!tailMap.isEmpty()))
143             {
144                 ArrayList keyList = new ArrayList();
145                 ArrayList valueList = new ArrayList();
146                 
147                 Iterator iterator = tailMap.entrySet().iterator();
148                 
149                 while (iterator.hasNext())
150                 {
151                     Map.Entry entry = (Map.Entry)iterator.next();
152                     
153                     keyList.add(entry.getKey());
154                     valueList.add(entry.getValue());
155                 }
156
157                 for (int i = 0; i < keyList.size(); i ++)
158                 {
159                     Integer JavaDoc key = (Integer JavaDoc)keyList.get(i);
160                     
161                     treeMap.remove(key);
162                     
163                     treeMap.put(new Integer JavaDoc(key.intValue() - 1), valueList.get(i));
164                 }
165             }
166
167             _size = size - 1;
168         }
169
170         return currentValue;
171     }
172
173     /** actual size */
174
175     public int getActualSize()
176     {
177         return treeMap.size();
178     }
179 }
180
Popular Tags