class ProjectedDatabase {

	public Set<FrequentSequenceItem> getBackwardExtensionItems() {
		Set<FrequentSequenceItem> backwardExtensionItems = new HashSet<FrequentSequenceItem>();
		if (projectedInfo.size() == 0) {
			return backwardExtensionItems;
		}

		//record what the first sequence has at each ditted position
		Map<Integer, String> positionsToSymbols = new HashMap<Integer, String>();
		int dittedPosition = 0;
		List<Sequence> sequences = database.getSequences();
		Sequence firstSequence = sequences.get(projectedInfo.get(0).getSequenceIndex());
		for (SequenceItem currentItem : prefixSequence) {
			int fixedPosition = currentItem.getIndex();
			while (dittedPosition < fixedPosition) {
				String symbol = firstSequence.getSequenceAsString().substring(dittedPosition,
					dittedPosition + 1);
				//System.out.println("adding " + symbol + " at position " + dittedPosition);
				positionsToSymbols.put(new Integer(dittedPosition), symbol);
				dittedPosition++;
			}
			dittedPosition++;//advance past fixedPosition
		}

		//if all of the preceeding positions are filled, there can't be any backward
		//extension items
		if (positionsToSymbols.isEmpty()) {
			return backwardExtensionItems;
		}

		//check the other projected sequences for consistency with the first sequence
		//if there is an inconsistency, that position can't be a backward extension item
		int numSequences = projectedInfo.size();
		for (int i = 1; i < numSequences; ++i) {
			Set<Integer> positionsToRemove = new HashSet<Integer>();
			for (Entry<Integer, String> entry : positionsToSymbols.entrySet()) {
				Integer key = entry.getKey();
				String storedValue = entry.getValue();
				Sequence testSequence = sequences.get(projectedInfo.get(i).getSequenceIndex());
				String testValue = testSequence.getSequenceAsString().substring(key, key + 1);
				if (!storedValue.equals(testValue)) {
					positionsToRemove.add(key);
				}
			}
			for (Integer position : positionsToRemove) {
				positionsToSymbols.remove(position);
			}
			//exit early if we find that there are conflicting choices for all ditted positions
			if (positionsToSymbols.isEmpty()) {
				return backwardExtensionItems;
			}
		}

		//return the set FrequentItems corresponding to all positions which are not specified
		//in the prefix but which nonetheless have the same value for all projected sequences
		for (Entry<Integer, String> entry : positionsToSymbols.entrySet()) {
			int position = entry.getKey();
			String symbol = entry.getValue();
			SequenceItem item = new SequenceItem(symbol, position);
			FrequentSequenceItem fItem = new FrequentSequenceItem(support, item);
			backwardExtensionItems.add(fItem);
		}
		return backwardExtensionItems;
	}

	public  ProjectedDatabase(SequenceDatabase database, List<SequenceItem> prefixSequence);
	public  ProjectedDatabase(ProjectedDatabase projDatabase, SequenceItem extendingItem);

}