001/**
002 * Java Web Archive Toolkit - Software to read and validate ARC, WARC
003 * and GZip files. (http://jwat.org/)
004 * Copyright 2011-2012 Netarkivet.dk (http://netarkivet.dk/)
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 */
018package org.jwat.common;
019
020import java.util.ArrayDeque;
021import java.util.Deque;
022import java.util.Iterator;
023import java.util.LinkedList;
024import java.util.List;
025
026public class TreeOfIntMapper<T> {
027
028    protected static class IntItem<T> {
029        protected int key;
030        protected List<IntItem<T>> itemList;
031        protected T value;
032    }
033
034    protected IntItem<T> rootItem = new IntItem<>();
035
036    protected int size = 0;
037
038    public int size() {
039        return size;
040    }
041
042    public void add(T value, int[] arr) {
043        int arrIdx = 0;
044        int arrLen = arr.length;
045        int arrKey;
046        IntItem<T> item = rootItem;
047        List<IntItem<T>> itemList;
048        int listIdx;
049        int listLen;
050        while (arrIdx < arrLen) {
051            itemList = item.itemList;
052            if (itemList == null) {
053                itemList = new LinkedList<>();
054                item.itemList = itemList;
055            }
056            arrKey = arr[arrIdx++];
057            listIdx = 0;
058            listLen = itemList.size();
059            item = null;
060            while (listIdx < listLen && (item = itemList.get(listIdx)).key < arrKey) {
061                ++listIdx;
062            }
063            if (item == null || item.key != arrKey) {
064                item = new IntItem<>();
065                item.key = arrKey;
066                itemList.add(listIdx, item);
067            }
068        }
069        item.value = value;
070        ++size;
071    }
072
073    public T lookup(int[] arr) {
074        int arrIdx = 0;
075        int arrLen = arr.length;
076        int arrKey;
077        IntItem<T> item = rootItem;
078        List<IntItem<T>> itemList;
079        int listIdx;
080        int listLen;
081        T value = null;
082        while (item != null && arrIdx < arrLen) {
083            itemList = item.itemList;
084            item = null;
085            if (itemList != null) {
086                arrKey = arr[arrIdx++];
087                listIdx = 0;
088                listLen = itemList.size();
089                while (listIdx < listLen && (item = itemList.get(listIdx)).key < arrKey) {
090                    ++listIdx;
091                }
092                if (item != null && item.key != arrKey) {
093                    item = null;
094                }
095            }
096        }
097        if (item != null) {
098            value = item.value;
099        }
100        return value;
101    }
102
103    @Override
104    public String toString() {
105        StringBuilder sb = new StringBuilder();
106        Iterator<IntItem<T>> iter = rootItem.itemList.iterator();
107        IntItem<T> tmpListItem;
108        List<IntItem<T>> itemList;
109        Deque<Iterator<IntItem<T>>> queue = new ArrayDeque<>();
110        queue.push(iter);
111        String indent = "  ";
112        while (queue.size() > 0) {
113            iter = queue.pop();
114            indent = indent.substring(2);
115            while (iter.hasNext()) {
116                tmpListItem = iter.next();
117                if (tmpListItem.value == null) {
118                    sb.append(indent + tmpListItem.key);
119                }
120                else {
121                    sb.append(indent + tmpListItem.key + " " + tmpListItem.value);
122                }
123                sb.append("\n");
124                itemList = tmpListItem.itemList;
125                if (itemList != null) {
126                    queue.push(iter);
127                    iter = itemList.iterator();
128                    indent = indent + "  ";
129                }
130            }
131        }
132        return sb.toString();
133    }
134
135}