001: package org.drools.util;
002:
003: /*
004: * Copyright 2005 JBoss Inc
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: */
018:
019: import java.io.Serializable;
020:
021: public class PrimitiveLongStack implements Serializable {
022: /**
023: *
024: */
025: private static final long serialVersionUID = 400L;
026: private final int tableSize;
027: private int currentPageId;
028: private Page currentPage;
029:
030: public PrimitiveLongStack() {
031: this (256);
032: }
033:
034: public PrimitiveLongStack(final int tableSize) {
035: this .tableSize = tableSize;
036: this .currentPageId = 0;
037:
038: // instantiate the first node
039: // previous sibling of first node is null
040: // next sibling of last node is null
041: this .currentPage = new Page(null, this .currentPageId,
042: this .tableSize);
043: }
044:
045: public void push(final long value) {
046: if (this .currentPage.getPosition() == this .tableSize - 1) {
047:
048: final Page node = new Page(this .currentPage,
049: ++this .currentPageId, this .tableSize);
050: this .currentPage = node;
051: }
052:
053: this .currentPage.push(value);
054: }
055:
056: public long pop() {
057: if (this .currentPage.getPosition() == -1) {
058: if (this .currentPageId == 0) {
059: throw new RuntimeException("Unable to pop");
060: }
061:
062: final Page node = this .currentPage;
063: this .currentPage = node.getPreviousSibling();
064: this .currentPageId--;
065: node.remove();
066:
067: }
068:
069: return this .currentPage.pop();
070: }
071:
072: public boolean isEmpty() {
073: return this .currentPageId == 0
074: && this .currentPage.getPosition() == -1;
075: }
076:
077: private static final class Page implements Serializable {
078: /**
079: *
080: */
081: private static final long serialVersionUID = 400L;
082: private final int pageId;
083: private Page nextSibling;
084: private Page previousSibling;
085: private long[] table;
086: private int lastKey;
087:
088: Page(final Page previousSibling, final int nodeId,
089: final int tableSize) {
090: // create bi-directional link
091: this .previousSibling = previousSibling;
092: if (this .previousSibling != null) {
093: this .previousSibling.setNextSibling(this );
094: }
095: this .pageId = nodeId;
096: this .lastKey = -1;
097:
098: // initiate tree;
099: this .table = new long[tableSize];
100: }
101:
102: public int getNodeId() {
103: return this .pageId;
104: }
105:
106: void setNextSibling(final Page nextSibling) {
107: this .nextSibling = nextSibling;
108: }
109:
110: public Page getNextSibling() {
111: return this .nextSibling;
112: }
113:
114: public Page getPreviousSibling() {
115: return this .previousSibling;
116: }
117:
118: public long pop() {
119: return this .table[this .lastKey--];
120: }
121:
122: public void push(final long value) {
123: this .table[++this .lastKey] = value;
124: }
125:
126: public int getPosition() {
127: return this .lastKey;
128: }
129:
130: void remove() {
131: this.previousSibling.setNextSibling(null);
132: this.previousSibling = null;
133: this.table = null;
134: }
135: }
136: }
|