62: }
63: }
64:
65: /*
66: * Pointer to the head of the VList, which contains the final elements of
67: * the list.
68: */
69: private VListCell
70:
71: /* Cached total number of elements in the array. */
72: private int mSize;
73:
74: /**
75: * Adds a new element to the end of the array.
76: *
77: * @param elem
78: * The element to add.
79: * @return true
80: */
81: @Override
82: public boolean add(T elem) {
83: /* If no free space exists, add a new element to the list. */
84: if (mHead == null || mHead.mFreeSpace == 0)
85: mHead = new VListCell
86: : mHead.mElems.length * 2, mHead);
87:
88: /* Prepend this element to the current cell. */
89: mHead.mElems[(mHead.mFreeSpace--) - 1] = elem;
90: ++mSize;
91:
92: /* Success! */
93: return true;
94: }
95:
96: /**
97: * Given an absolute offset into the VList, returns an object describing
98: * where that object is in the VList.
99: *
100: * @param index
101: * The index into the VList.
102: * @return A VListLocation object holding information about where that
103: * element can be found.
104: */
105: private VListLocation
106: /* Bounds-check. */
107: if (index >= size() || index < 0)
109: + size());
110:
111: /*
112: * Because the list is stored with new elements in front and old
113: * elements in back, we'll invert the index so that 0 refers to the
114: * final element of the array and size() - 1 refers to the first
115: * element.
116: */
117: index = size() - 1 - index;
118:
119: /*
120: * Scan across the cells, looking for the first one that can hold our
121: * entry. We do this by continuously skipping cells until we find one
122: * that can be sure to hold this element.
123: *
124: * Note that each cell has mElems.length elements, of which mFreeSpace
125: * is used. This means that the total number of used elements in each
126: * cell is mElems.length - mFreeSpace.
127: */
128: VListCell
129: while (index >= curr.mElems.length - curr.mFreeSpace) {
130: /* Skip past all these elements. */
131: index -= curr.mElems.length - curr.mFreeSpace;
132: curr = curr.mNext;
133: }
134:
135: /*
136: * We're now in the correct location for what we need to do. The element
137: * we want can be found by indexing the proper amount beyond the free
138: * space.
139: */
140: return new VListLocation
141: }
142:
143: /**
144: * Scans for the proper location in the cell list for the element, then
145: * returns the element at that position.
146: *
147: * @param index
148: * The index at which to look up the element.
149: * @return The element at that position.
150: */
151: @Override
152: public T get(int index) {
153: VListLocation