/**
 * Returns the successors of a given node.
 *
 * @param node a node (say, corresponding to the pair [<code>index</code>,
 *            <code>LID</code>])
 * @return the list of all successors; these are obtained as follows: for
 *         every successor <code>x</code> of <code>node</code> in the call
 *         graph
 *         <ul>
 *         <li>if <code>x</code> is internal, [<code>index</code>,
 *         <code>LID</code>] is a successor
 *         <li>if <code>x</code> is external and it corresponds to the GID
 *         <code>g</code> (which in turn corresponds to a generic
 *         {@link FastenURI}), we look at every index
 *         <code>otherIndex</code> where <code>g</code> appears, and let
 *         <code>otherLID</code> be the corresponding LID: then
 *         [<code>otherIndex</code>, <code>otherLID</code>] is a successor.
 *         </ul>
 */
public ObjectList<Node> successors(final Node node) {
	final long gid = node.gid;
	final long index = node.index;
	final CallGraph callGraph = callGraphs.get(index);
	assert callGraph != null;

	final CallGraphData callGraphData = callGraph.callGraphData();
	final LongList successors = callGraphData.successors(gid);

	final ObjectList<Node> result = new ObjectArrayList<>();

	/* In the successor case, internal nodes can be added directly... */
	for (final long x: successors)
		if (callGraphData.isExternal(x))
			for (final LongIterator revisions = GIDAppearsIn.get(x).iterator(); revisions.hasNext();)
				result.add(new Node(x, revisions.nextLong()));
		else result.add(new Node(x, index));

	return result;
}
 

/**
 * Returns a list of partitions of the posting list.
 * @param partSize the size of the partitions.
 * @return a list of word vectors.
 */
public ObjectList<ObjectList<Object2IntMap<String>>> partition(int partSize){

	ObjectList<ObjectList<Object2IntMap<String>>> resList= new ObjectArrayList<ObjectList<Object2IntMap<String>>>();

	// if the partition size is larger than the posting list, then put the whole list into one partition
	// if partsize is less or equal than zero we create one single partition too, which is equivalent to the full
	// tweet centroid model
	if(partSize>=this.postingList.size() || partSize <=0){
		resList.add(this.postingList);
	}
	else{
		int i=0;
		while(i+partSize<=this.postingList.size()){
			resList.add(this.postingList.subList(i, i+partSize));
			i+=partSize;				
		}
		if(i<this.postingList.size()&& i+partSize>this.postingList.size() ){
			resList.add(this.postingList.subList(i, this.postingList.size()));
		}

	}

	return resList;

}
 

/** Creates a trie from a set of elements.
 * 
 * @param elements a set of elements
 * @param transformationStrategy a transformation strategy that must turn <code>elements</code> into a list of
 * distinct, lexicographically increasing (in iteration order) binary words.
 */

public ImmutableBinaryTrie( final Iterable<? extends T> elements, final TransformationStrategy<? super T> transformationStrategy ) {
	this.transformationStrategy = transformationStrategy;
	defRetValue = -1;
	// Check order
	final Iterator<? extends T> iterator = elements.iterator();
	final ObjectList<LongArrayBitVector> words = new ObjectArrayList<LongArrayBitVector>();
	int cmp;
	if ( iterator.hasNext() ) {
		final LongArrayBitVector prev = LongArrayBitVector.copy( transformationStrategy.toBitVector( iterator.next() ) );
		words.add( prev.copy() );
		BitVector curr;

		while( iterator.hasNext() ) {
			curr = transformationStrategy.toBitVector( iterator.next() );
			cmp = prev.compareTo( curr );
			if ( cmp == 0 ) throw new IllegalArgumentException( "The trie elements are not unique" );
			if ( cmp > 0 ) throw new IllegalArgumentException( "The trie elements are not sorted" );
			prev.replace( curr );
			words.add( prev.copy() );
		}
	}
	root = buildTrie( words, 0 );
}
 

/**
 * Returns the predecessors of a given node.
 *
 * @param node a node (for the form [<code>index</code>, <code>LID</code>])
 * @return the list of all predecessors; these are obtained as follows:
 *         <ul>
 *         <li>for every predecessor <code>x</code> of <code>node</code> in the call graph,
 *         [<code>index</code>, <code>LID</code>] is a predecessor
 *         <li>let <code>g</code> be the GID of <code>node</code>: for every index
 *         <code>otherIndex</code> that calls <code>g</code> (i.e., where <code>g</code> is the GID
 *         of an external node), and for all the predecessors <code>x</code> of the node with GID
 *         <code>g</code> in <code>otherIndex</code>, [<code>otherIndex</code>, <code>x</code>] is a
 *         predecessor.
 *         </ul>
 */
public ObjectList<Node> predecessors(final Node node) {
	final long gid = node.gid;
	final long index = node.index;
	final CallGraph callGraph = callGraphs.get(index);
	assert callGraph != null;

	final CallGraphData callGraphData = callGraph.callGraphData();
	final LongList predecessors = callGraphData.predecessors(gid);

	final ObjectList<Node> result = new ObjectArrayList<>();

	/* In the successor case, internal nodes can be added directly... */
	for (final long x: predecessors) {
		assert callGraphData.isInternal(x);
		result.add(new Node(x, index));
	}

	/*
	 * To move backward in the call graph, we use GIDCalledBy to find
	 * revisions that might contain external nodes of the form <gid, index>.
	 */
	for (final LongIterator revisions = GIDCalledBy.get(gid).iterator(); revisions.hasNext();) {
		final long revIndex = revisions.nextLong();
		final CallGraphData precCallGraphData = callGraphs.get(revIndex).callGraphData();
		for (final long y: precCallGraphData.predecessors(gid)) result.add(new Node(y, revIndex));
	}

	return result;
}
 

/**
 * Given a generic URI (one without a version), returns all the matching
 * non-generic URIs.
 *
 * @param genericURI a generic URI.
 * @return the list of all non-generic URIs matching
 *         <code>genericURI</code>.
 */
public ObjectList<FastenURI> genericURI2URIs(final FastenURI genericURI) {
	if (genericURI.getVersion() != null || genericURI.getScheme() != null) throw new IllegalArgumentException("The FASTEN URI must be generic and schemeless");
	final long gid = uri2GID(genericURI);
	if (gid == -1) return null;
	final ObjectArrayList<FastenURI> result = new ObjectArrayList<>();
	for (final long index : GIDAppearsIn.get(gid))
		result.add(FastenURI.createSchemeless(genericURI.getRawForge(), genericURI.getRawProduct(), callGraphs.get(index).version, genericURI.getRawNamespace(), genericURI.getRawEntity()));
	return result;
}
 

/**
 * Given a fast util object list of indexed words, return object array list of the same object list
 * @param: oWordList: list of indexed word (object list)
 * @return: an object array list object of oWordList
 */
public static ObjectArrayList<IndexedWord> objectListToObjectArrayList(ObjectList<IndexedWord> oWordList){
    ObjectArrayList<IndexedWord> oaWordList = new ObjectArrayList<>();
    for (IndexedWord w: oWordList){
        oaWordList.add(w);
    }
    return oaWordList.clone();
}
 

public synchronized ObjectList<? extends S> list() {
	if ( list == null ) {
		list = stringMap.list();
		if( list != null ) list = ObjectLists.synchronize( list, this ); 
	}
	return list;
}
 

public ObjectList<MutableString> list() {
	if ( list == null ) list = new AbstractObjectList<MutableString>() {
		public int size() {
			return AbstractPrefixMap.this.size();
		}
		public MutableString get( int index ) {
			return getTerm( index, new MutableString() );
		}
	};
	
	return list;
}
 

/** Creates a new shift-add-xor signed string map using a given hash map.
 * 
 * @param function a function mapping each string in <code>list</code> to its ordinal position.
 * @param list a list of strings.
 */

public LiterallySignedStringMap( final Object2LongFunction<? extends CharSequence> function, final ObjectList<? extends MutableString> list ) {
	this.function = function;
	this.list = list;
	size = list.size();
	for( int i = 0; i < size; i++ ) if ( function.getLong( list.get( i ) ) != i ) throw new IllegalArgumentException( "Function and list do not agree" );
	defRetValue = -1;
}
 

@SuppressWarnings("unchecked")
public static void main( final String[] arg ) throws IOException, JSAPException, ClassNotFoundException, SecurityException, NoSuchMethodException {

	final SimpleJSAP jsap = new SimpleJSAP( LiterallySignedStringMap.class.getName(), "Builds a shift-add-xor signed string map by reading a newline-separated list of strings and a function built on the same list of strings.",
			new Parameter[] {
		new FlaggedOption( "encoding", ForNameStringParser.getParser( Charset.class ), "UTF-8", JSAP.NOT_REQUIRED, 'e', "encoding", "The string file encoding." ),
		new Switch( "zipped", 'z', "zipped", "The string list is compressed in gzip format." ),
		new Switch( "text", 't', "text", "The string list actually a text file, with one string per line." ),
		new UnflaggedOption( "function", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The filename of the function to be signed." ),
		new UnflaggedOption( "list", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The filename of the serialised list of strings, or of a text file containing a list of strings, if -t is specified." ),
		new UnflaggedOption( "map", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The filename of the resulting map." ),
	});

	JSAPResult jsapResult = jsap.parse( arg );
	if ( jsap.messagePrinted() ) return;

	final String functionName = jsapResult.getString( "function" );
	final String listName = jsapResult.getString( "list" );
	final String mapName = jsapResult.getString( "map" );

	
	final Charset encoding = (Charset)jsapResult.getObject( "encoding" );
	final boolean zipped = jsapResult.getBoolean( "zipped" );
	final boolean text = jsapResult.getBoolean( "text" );
	
	ObjectList<MutableString> list = text ? new FileLinesCollection( listName, encoding.toString(), zipped ).allLines() : (ObjectList)BinIO.loadObject( listName );
	
	LOGGER.info( "Signing..." );
	BinIO.storeObject( new LiterallySignedStringMap( (Object2LongFunction)BinIO.loadObject( functionName ), list ), mapName );
	LOGGER.info( "Completed." );
}
 

/** Returns all lines of the file wrapped by this file-lines collection.
 * 
 * @return all lines of the file wrapped by this file-lines collection.
 */

public ObjectList<MutableString> allLines() {
	final ObjectArrayList<MutableString> result = new ObjectArrayList<MutableString>();
	for( Iterator<MutableString> i = iterator(); i.hasNext(); ) result.add( i.next().copy() );
	return result;
}
 

public ObjectList<CharSequence> list() {
	return null;
}
 

/** Builds a trie recursively. 
 * 
 * <p>The trie will contain the suffixes of words in <code>words</code> starting at <code>pos</code>.
 * 
 * @param elements a list of elements.
 * @param pos a starting position.
 * @return a trie containing the suffixes of words in <code>words</code> starting at <code>pos</code>.
 */
	
protected Node buildTrie( final ObjectList<LongArrayBitVector> elements, final int pos ) {
	// TODO: on-the-fly check for lexicographical order
	
	if ( elements.size() == 0 ) return null;

	BitVector first = elements.get( 0 ), curr;
	int prefix = first.size(), change = -1, j;

	// We rule out the case of a single word (it would work anyway, but it's faster)
	if ( elements.size() == 1 ) return new Node( pos < prefix ? LongArrayBitVector.copy( first.subVector( pos, prefix ) ) : null, size++ );
	
	// 	Find maximum common prefix. change records the point of change (for splitting the word set).
	for( ListIterator<LongArrayBitVector> i = elements.listIterator( 1 ); i.hasNext(); ) {
		curr = i.next();
		
		if ( curr.size() < prefix ) prefix = curr.size(); 
		for( j = pos; j < prefix; j++ ) if ( first.get( j ) != curr.get( j ) ) break;
		if ( j < prefix ) {
			change = i.previousIndex();
			prefix = j;
		}
	}
	
	final Node n;
	if ( prefix == first.size() ) {
		// Special case: the first word is the common prefix. We must store it in the node,
		// and explicitly search for the actual change point, which is the first
		// word with prefix-th bit true.
		change = 1;
		for( ListIterator<LongArrayBitVector> i = elements.listIterator( 1 ); i.hasNext(); ) {
			curr = i.next();
			if ( curr.getBoolean( prefix ) ) break;
			change++;
		}
			
		n = new Node( prefix > pos ? LongArrayBitVector.copy( first.subVector( pos, prefix ) ) : null, size++ );
		n.left = buildTrie( elements.subList( 1, change ), prefix + 1 );
		n.right = buildTrie( elements.subList( change, elements.size() ), prefix + 1 );
	}
	else {
		n = new Node( prefix > pos ? LongArrayBitVector.copy( first.subVector( pos, prefix ) ) : null ); // There's some common prefix
		n.left = buildTrie( elements.subList( 0, change ), prefix + 1 );
		n.right = buildTrie( elements.subList( change, elements.size() ), prefix + 1 );
	}
	return n;
}
 

public ObjectList<? extends MutableString> list() {
	return list;
}
 

@Override
protected Instances process(Instances instances) throws Exception {



	Instances result;


	// The first batch creates de labelled data		
	if(!this.isFirstBatchDone()){
		result = getOutputFormat();

		for(String word:this.wordInfo.keySet()){
			// get the word vector
			WordRep wordRep=this.wordInfo.get(word);

			// We just consider valid words
			if(wordRep.numDoc>=this.minInstDocs){

				// a list of lists of tweet vectors
				ObjectList<ObjectList<Object2IntMap<String>>> partitions=wordRep.partition(this.getPartNumber());

				// traverse the partitions
				for(ObjectList<Object2IntMap<String>> tweetPartition:partitions){
					// create one instance per partition	
					double[] values = new double[result.numAttributes()];

					// average the vectors of the tweets in the partition
					// traverse each feature space in the partition
					for(Object2IntMap<String> wordSpace:tweetPartition){

						for(String innerWord:wordSpace.keySet()){
							// only include valid words
							if(this.m_Dictionary.containsKey(innerWord)){
								int attIndex=this.m_Dictionary.getInt(innerWord);
								// we normalize the value by the number of documents
								values[attIndex]+=((double)wordSpace.getInt(innerWord))/tweetPartition.size();					
							}
						}
					}



					String wordPol=this.lex.getNomDict().get(word).get(this.polarityAttName);
					if(wordPol.equals(this.polarityAttNegValName))
						values[result.numAttributes()-1]=0;
					else if(wordPol.equals(this.polarityAttPosValName))
						values[result.numAttributes()-1]=1;
					else
						values[result.numAttributes()-1]= Utils.missingValue();					



					Instance inst=new SparseInstance(1, values);


					inst.setDataset(result);

					result.add(inst);



				}
			}
		}
	}

	// Second batch maps tweets into the original feature space
	else{
		result=this.mapTargetInstance(instances);

	}

	return result;

}
 

/** Returns a list view of the domain of this string map (optional operation). 
 * 
 * <p>Note that the list view acts as an inverse of the mapping implemented by this map.
 * 
 * @return a list view of the domain of this string map, or <code>null</code> if this map does
 * not support this operation.
 */

public ObjectList<? extends S> list();