/*	Javascript topic map utility functions
	12-15-2002 Added buildSubclassAssoc_players(), suoerclass/subclass uri 
		constants. Added hierarchyTree().
	7-28-2002 Added fixData1().
	4-21-2002 T. B. Passin
*/

//===== Topic map utility functions ========

SUPERCLASS_SUBCLASS_ASSOC_URI = "http://www.topicmaps.org/xtm/1.0/core.xtm#superclass-subclass"
SUPERCLASS_ROLE_URI	          = "http://www.topicmaps.org/xtm/1.0/core.xtm#superclass"
SUBCLASS_ROLE_URI             = "http://www.topicmaps.org/xtm/1.0/core.xtm#subclass"

/* ======================================================
	Correct line feeds and escape double quotation marks 
	so they will load and round-trip correctly (used to
	round-trip javascript data in and out of textArea values
	and similar problems).
   ======================================================*/
function fixData(data){
	if (!data){return ''}
	//alert(data)
	var str,ar,i
	str=data
	str=str.replace(/\n/g,"###@@")
	str=str.replace(/\\n/g,"###@@")
	str=str.replace(/[\r]/g,"###@@")
//alert(str)
	
	// Escape double quotation marks
	// First temporarily protect any "\n" characters
	// Need to replace line feeds + continuation marks by "\n\"
	// Three cases: "\n\", the characters "\n" and actual line feeds
	// Next unescape any escaped quote marks
	ar=str.split('\\')
	str=ar.join('')
	
	ar=str.split('"')
	for (i in ar){
		if (i==ar.length-1){break}
		str=ar[i]+'\\\"'
		ar[i]=str
	}
	str=ar.join('')
	//str=str.replace(/"/g,'\'+ '"')
	str=str.replace(/###@@/g,"\\n")
return str
}

// Change handling of newlines to round-trip in/out of text areas
function fixData1(data){
	if (!data){return ''}
	
	var str,ar,i
	str=data
	str=str.replace(/\n/g,"###@@")
	str=str.replace(/\\n/g,"###@@")
	str=str.replace(/[\r]/g,"###@@")
	
	// Escape double quotation marks
	// First temporarily protect any "\n" characters
	// Need to replace line feeds + continuation marks by "\n\"
	// Three cases: "\n\", the characters "\n" and actual line feeds
	// Next unescape any escaped quote marks
	ar=str.split('\\')
	str=ar.join('')
	
	ar=str.split('"')
	for (i in ar){
		if (i==ar.length-1){break}
		str=ar[i]+'\\\"'
		ar[i]=str
	}
	str=ar.join('')
	//str=str.replace(/"/g,'\'+ '"')
	str=str.replace(/###@@/g,"\n")
return str
}

function add_topic(map,topicid,name,typ){
    var top1=new topic(topicid)
	
    top1.addBaseName(new baseName(name))
    top1.instanceOf=typ||'tt-urtype'
    map.addTopic(top1)
	return top1
}

function add_occur(map,owner_topic,occur_type,
	occur_scope,resourceRef,data){
	var oc,top1
	oc=new occur()
	oc.instanceOf=occur_type
	oc.data=data||''
	oc.resourceRef=resourceRef||''
	if (occur_scope){oc.addScope(new scope(occur_scope))}
	top1=map.getTopicById(owner_topic)
	if (top1){top1.addOccur(oc)}
	return oc
}

function add_subject_indicator(map,owner_topic,uri) {
	if (!(map && owner_topic)){return}
	var uri=uri || ''
	
	var top1=map.getTopicById(owner_topic)
	if (!top1){return}

	var subj = top1.getIdentity()
	
	if (!subj){
		subj=new subjectIdentity()
		top1.setIdentity(subj)
	}
	
	subj.addSubjectIndicatorRef(uri)
}

function add_subject_resource_ref(map,owner_topic,uri) {
	if (!(map && owner_topic)){return}
	var uri=uri || ''
	
	var top1=map.getTopicById(owner_topic)
	if (!top1){return}

	var subj = top1.getIdentity()
	
	if (!subj){
		subj=new subjectIdentity()
		top1.setIdentity(subj)
	}
	
	subj.setResourceRef(uri)
}


/* ====================================================
      Create a default topic map - useful for getting
	  a new map started.  
   ====================================================*/
function defaultTopicMap(){
    var tm
    tm=new topicMap()
    add_topic(tm,'tt-urtype','Ur-Type')
    add_topic(tm,'tt-topicmap','Topic Map Type','tt-urtype')
    add_topic(tm,'tt-assoc','Association Type','tt-urtype')
    add_topic(tm,'tt-role','Role Type','tt-urtype')
    add_topic(tm,'tt-occur','Occurrence Type','tt-urtype')
    add_topic(tm,'tt-scope','Scope Type','tt-urtype')
	add_topic(tm,"tt-class","Class","tt-urtype")
    
    // ============ Role topics ============
	add_topic(tm,"rt-superclass","superclass","tt-role")
	add_topic(tm,"rt-subclass","subclass","tt-role")
	add_subject_indicator(tm,"rt-superclass",SUPERCLASS_ROLE_URI)
	add_subject_indicator(tm,"rt-subclass",SUBCLASS_ROLE_URI)
	add_topic(tm,"rt-subtype","subtype","tt-role")
	add_topic(tm,"rt-supertype","supertype","tt-role")
    
    // ============ Occurrence topics ============
    add_topic(tm,'ot-descr','description','tt-occur')
    add_topic(tm,'ot-note','note','tt-occur')
    add_topic(tm,'ot-homepage','home page','tt-occur')
    add_topic(tm,'ot-about','about','tt-occur')
    
    // ============ Scope topics ============
    add_topic(tm,'st-unconstrained','All-scopes','tt-scope')

    // ============ Association topics ============
	add_topic(tm,"at-subclassof","SubclassOf","tt-urtype")
	add_subject_indicator(tm,"at-subclassof",SUPERCLASS_SUBCLASS_ASSOC_URI)
	add_topic(tm,"at-subtype","SubType","tt-urtype")

	return tm
}

/* ===================================================
    Load  list of topics, possibly filtered
   ===================================================*/
function loadTopicList(map,selectbox,topictype,filter){
	/* Write all the items of the list box
	 Load select box with topic names
	 Need an array of scopes for filtering
	 but we are only going to apply a single one here.

	 "topictype" is one of these strings:
		"all", "topics","scopes","occurs",'assoc','roles'

	 This controls which kind of topics will be included
	 in the select box.
	*/
    if (!map) {return}
	var TOPICS,SCOPES,OCCURS,ASSOC,ROLES,TOPICTYPE
	TOPICTYPE=(topictype||'all')
	TOPICS=((TOPICTYPE=='all') || TOPICTYPE=='topics')
	SCOPES=((TOPICTYPE=='all') || TOPICTYPE=='scopes')
	OCCURS=((TOPICTYPE=='all') || TOPICTYPE=='occurs')
	ASSOC=((TOPICTYPE=='all') || TOPICTYPE=='assoc')
	ROLES=((TOPICTYPE=='all') || TOPICTYPE=='roles')
	var filters=new Array()
	var unnamed_serial = 1

	if (!filter || !filter.length){
		filters[0]='st-unconstrained'
	}
	else {filters=filter}

	var tops=map.getTopicsFiltered(filters)
	var names ={}
	var top1,n,i,j,Name
	var usename,Type
	var showalert=false

	for (i in tops){
		usename=false
		top1=tops[i]
		if (!top1){continue}
		// Get all topic names that pass the filter
		// If more than one, use the first
		n=top1.getNamesFiltered(filters)
		Name = null
		if (n){
			Name=n[0].name
		}
		//Skip missing names and skippable types
		if (!Name){
			Name = '[un-named topic ' + unnamed_serial.toString() + ']'
			unnamed_serial++			
		}

		Type=top1.instanceOf
		//if (!Type){continue}

		if (TOPICTYPE=='all'){usename=true}
		else {
			if (TOPICS){
				usename=(Type!='tt-role')
					&&(Type!='tt-assoc')
					&&(Type!='tt-occur')
					&&(Type!='tt-scope')
			}
			if (!usename){	
				usename=((Type=='tt-occur' && OCCURS)||
					(Type=='tt-scope' && SCOPES)||
					(Type=='tt-assoc' && ASSOC)||
					(Type=='tt-role' && ROLES))

			}
		}
		
		if (usename){names[top1.id]=Name}	
	}
	names=sortArrayByValue(names)

	// Remove all the old options in the select box
	//removeOptions(document.f1.tops.options)
	removeOptions(selectbox.options)
 	// Create new options
	j=0
	for (i in names){
		// Loop over the topics
		selectbox.options[j]=new Option(names[i],i)
		j++
	}
}

/*
	Build select list of all topics which are subclasses of the topic
	Association Type.

	- get all association of type at-subclassOf
	- for list of all these whose superclass role-player is type "at-subclassof"
	- make list of the subclass role-player for each surviving association
	- sort by topic name
	- create select list
*/
function loadAssociationTypes(map,selectbox){
	if (!map) {
	    return
	}
	var assocs = map.getAssocByType('at-subtype')
	if (!assocs.length){
		return
	}

	var assoc
	var mem
	var superclass_player, subclass_player
	var topiclist=[]
	var ASSOC_TOPIC = map.getTopicById('tt-assoc')
	if (!ASSOC_TOPIC){
		return
	}

	for (var a=0; a < assocs.length;a++){
		assoc = assocs[a]
		mem = assoc.getMemberByRoleType('rt-supertype')
		if (mem){
			superclass_player = mem.getPlayers()[0]
			
			if (superclass_player != ASSOC_TOPIC){
				continue
			}
			mem = assoc.getMemberByRoleType('rt-subtype')
			subclass_player = mem.getPlayers()[0]
			if (subclass_player){
				topiclist.push(subclass_player)
			}
		}
	}

	topiclist.sort(compare_by_name)

	removeOptions(selectbox.options)

	// Create new options
	var id,Name
	var theTopic
	for (var t=0;t < topiclist.length;t++){
		theTopic = topiclist[t]
		id=theTopic.id
		Name = theTopic.getNamesFiltered()[0].getNameString()
		selectbox.options[t]=new Option(Name,id)
	}
	

	function compare_by_name(topic1,topic2){
		var name1 = topic1.getNamesFiltered()[0].getNameString()
		var name2 = topic2.getNamesFiltered()[0].getNameString()
		if (name1 < name2){
			return -1
		}
		if (name1 == name2){
			return 0
		}
		return 1
	
	}
	

}

/*=================================================
	"Print" association members in a readable format.
	The roleSpec property is a topic id, not a 
	topic.  So we need to supply the topic map
	so the actual topic can be found.  We don't 
	need to do this for the member topics, since 
	they are actual topic (references) within the
	map itself.

	"separator" is the string used to separate 
	the items.

	Returns a string.
==================================================*/
function printMember(member,topicmap, separator,indent){
	if (!(member&&topicmap)){return ''}
	var rolename, membername,i,str='',sep,ind
	sep=separator||'\n';ind=indent||'\t'
	if (member&&member.roleSpec){
		membername=topicmap.getTopicById(member.roleSpec).
			getNamesFiltered()[0].name
		str='<b>Role:</b> "'+(membername)+'"'
	}

	// Now get the names of the member topics
	var top,i
	for (i in member.rolePlayers){
		top=member.rolePlayers[i]
		if (top){
			membername=topicmap.
				getTopicById(top.id).
				getNamesFiltered()[0].name
			str+=sep+ind+membername
		}
	}
	return str
}

/*=================================================
	"Print" an association in a readable format.
	The association instanceOf and the members' 
	roleSpecs are  topic ids, not  topics.  So we 
	need to supply the topic map so the actual topic 
	can be found.

	"separator" is the string used to separate 
	the items.

	Returns a string.
==================================================*/
function printAssoc(assoc,topicmap, separator,indent){
	if (!(assoc&&topicmap)){return ''}
	var typename,i,str='',sep,ind
	sep=separator||'\n';ind=indent||'\t'

	// Get the name of the type of this association
	if (!assoc.instanceOf){
		str+='(none)'
	}
	else {
		typename=topicmap.getTopicById(assoc.instanceOf).
		getNamesFiltered()[0].name
		str+='<b>Association type:</b> '+typename
	}

	//Now get the members
	var m,member
	for (m in assoc.members){
		member=assoc.members[m];
		str+=sep+printMember(member,topicmap,separator,indent)
	}

	return str
}

/*=================================================
	"Print" an occurrence in a readable format.
	The topicRef id is printed for each scope.

	"separator" is the string used to separate 
	the items.

	Returns a string.
==================================================*/
function printOccur(Occur, separator,indent){
	if (!Occur){return ''}
	var topicid, occurtype,sep,ind
	var scopes,ref
	sep=separator||'\n';ind=indent||'\t'
	
	// Get occurrence type and id
	str='Occurrence'+sep
	str+=indent+ 'type: '+Occur.instanceOf+sep
	str+=indent+'id: ' + Occur.id+sep

	// Get scope topicRefs
	scopes=Occur.getScopes()
	if (scopes.length){
		str+=indent+'Scope: '+sep
		for (s in scopes){
			str+=indent+indent+scopes[s].topic+sep
		}
	}


	// Get resourceRef or data
	ref=Occur.resourceRef
	if (!ref){ref='Resource:'}
	else {ref='Data:'}

	str+=indent+ref + sep
	str +=indent+indent+Occur.getResourceOrData()
		+sep
	return str
}

/*=================================================
	"Print"  occurrences for a topic
	Returns a string.
==================================================*/
function printTopicOccurs(Topic,separator,indent){
	var o,occurs,str=''
	occurs=Topic.getOccursFiltered()
	for (o in occurs){
		str+=printOccur(occurs[o],separator,indent)
	}
	return str
}

/* =================================================
		Get all topic names in array of topics
   =================================================*/
function getTopicNames(topic_array){
	var n,i,str=''
	if (topic_array.length){
		for (i in topic_array){
			n=topic_array[i].getNamesFiltered()
			if (n.length){
				str+=n[0].name
				str+='<br>'}
		}
	}
	return str
}


/* =================================================
	Get all associations in a topic map involving 
	a specified topic
   =================================================*/
function getAssocForTopic(topicmap, Topic){
	var as,assoc, players, m,p, list=new Array()	
	// Get all associations
	as=topicmap.getAssociations()
	// Check each one
	for (assoc in as){
		// Get its members
		members=as[assoc].getMembers()
		// Check each member
		for (i in members){
			// Get all member's topics
			m=members[i].rolePlayers
			// Check each topic to see if it matches
			// our selected topic
			for (p in m){
				if (Topic==m[p]){
					list[list.length]=as[assoc]
					break
				}	
			}
		}
	}
	return list
}


/* ================================================
     Get the (first) baseNameString of the topic
	 pointed to by a scope.
   ================================================*/
function getScopeName(scope,map){
    var id,Topic,names,name
    if (!scope){return ''}
    id=scope.topic
    if (!id){return ''}
    Topic=map.getTopicById(id)
    if (!Topic){return ''}
    names=Topic.getNamesFiltered()
    // Use scope id if we can't find a topic name
    if (names.length){
        name=names[0]
        return name.getNameString()
    }
    else {
        name=id
        if (name=='st-unconstrained'){
            return '(Unspecified context)'
        }
    }
    return name
}

/* ================================================
     Create a dictionary of occurrences, keyed by
     the occurrence resourceRef or ResourceData.  
     Each entry contains the topic owning
     the occurrence.
   ================================================*/
function makeOccurrenceDictionary(map){
    var occurDict=Array()
    var occurList
    var t,topics,Topic
    var o,occurs,Occur,resource
    var isIndexed
    // Look through all topics
    topics=map.getTopicsFiltered()
    if (!topics.length){return occurDict}
    for (t in topics){
        Topic=topics[t]
        occurs=Topic.getOccursFiltered()
        if (occurs.length){
            for (o in occurs){
                Occur=occurs[o]
                resource=Occur.getResourceOrData()
                // See if this resource already is indexed
                isIndexed=(occurDict[resource]!=undefined)
                if (isIndexed){//add this topic to the list
                    occurList=occurDict[resource]
                    occurList[occurList.length]=Topic
                }
                else {//Start a new list for this occurrence
                    occurList=Array()
                    occurList[0]=Topic
                    occurDict[resource]=occurList
                }
            }
        }
        
    }
    return occurDict
}    

/* =======================================================
	Return the name of an association type
   ======================================================= */
function getAssocType(map,assoc){
	var theTopic,theName
	var assoc=assoc||null
	if (!assoc ||!assoc.instanceOf){return ''}
	theTopic=map.getTopicById(assoc.instanceOf)
	if (!theTopic){return ''}
	theName=theTopic.getNamesFiltered()[0]
	if (!theName){return ''}
	return theName.name
}

/* =======================================================
	Index Topics by association.  The index is an array
	keyed by topic id.  Each entry is an array containing
	all associations that contain the topic as a 
	role-player
   ======================================================= */
function indexTopicsByAssoc(map){
	var index=new Object()
	var assoclist
	var t,Topic,topics
	var assocs,a,assoc
	var isplayer
	var m,mem,members
	var p,player,players

	assocs=map.getAssociations()
	topics=map.getTopicsFiltered()
	for (t in topics){
		Topic=topics[t]
		if (!Topic){continue}
		assoclist=new Array()
		for (a in assocs){
			isplayer=false
			assoc=assocs[a]
			if (!assoc){continue}
			
			members=assoc.getMembers()
			for (m in members){
				mem=members[m]
				players=mem.getPlayers()
				for (p in players){
					player=players[p]
					isplayer=(player.id==Topic.id)
					if (isplayer){break}
				}
				if (isplayer){break}
			}
			if (isplayer){
				assoclist.push(assoc.id)
			}
		}
		if (assoclist.length){
			index[Topic.id]=assoclist
		}

	}
	return index
}

function getTopicLabelById(map,topicid){
	var Topic,name,label
	Topic=map.getTopicById(topicid)
	if (!(Topic&&Topic.getNamesFiltered)){return ''}
	
	name=Topic.getNamesFiltered()[0]
	label= name && name.getNameString()
	return label
}

function getTypeLabelForObject(map,object){
	var typeid,name,label,typetopic
	typeid=object.instanceOf
	if (!typeid) {return ''}

	typetopic=map.getTopicById(typeid)
	if (!(typetopic&&typetopic.getNamesFiltered)){return ''}
	
	name=typetopic.getNamesFiltered()[0]
	label=name.name
	return label
}

// Return the (one) topic that is a superclass for a topic
function getSuperclassForTopic(map,Topic){
    var a,assoc,assocs
	var mem,player
	var id,foundit=false
	id=Topic.id
	assocs=map.getAssocByType('at-subclassof')
	for (a in assocs) {
		assoc=assocs[a]
		mem=assoc.getMemberByRoleType('rt-subclass')
		if (!mem){continue}
		
	    player=mem.getPlayers()[0] // Assume there is only one
		if (player.id==id) {
		    foundit=true
			break
		}
	}
	if (!foundit) {
	    return false
	}

	mem=assoc.getMemberByRoleType('rt-superclass')
	player=mem.getPlayers()[0];
	return player
}

// Return a list with the topics of the superclass chain
// of a topic
function getAncestorList(map,Topic) {
	if (!Topic) {return []}

	var chain=[],nexttopic
	nexttopic=getSuperclassForTopic(map,Topic)

	while (nexttopic) {	    
		chain.push(nexttopic)
		nexttopic=getSuperclassForTopic(map,nexttopic)	    
	}
	chain.reverse()
	return chain//.reverse()
}

/* =======================================================
	Tests to see if a topic has any interesting information
	attached to it (instances, occurrences, associations).
   ========================================================*/

function hasInstance(Topic,map){
	var topicid,topics,t,Top
	var instances, i

	topicid=Topic.id
	topics=map.getTopics()
	for (t in topics){
		Top=topics[t]
		if (!Top){continue}
		if (Top.instanceOf==topicid){
			return true
		}
	}

	// See if our topic is an association type. If so, see if it
	// has any association instances
	if (Topic.instanceOf=='tt-assoc'){
		instances=map.getAssocByType(Topic.id)
		if (instances){
			// See if there really are any
			for (i in instances){return true}
		}
	}

	return false
}

function hasOccurrence(Topic){
	return (Topic.getOccursFiltered().length>0)
}

// Don't count subclass associations
function hasAssociation(Topic,map){
	var id,assocIndex,assocs,assoc,a
	id=Topic.id
	assocIndex=map.getAssocIndex()
	assocs=assocIndex[id]
	if (!assocs) {return false}
	    
	for (a in assocs){
		assoc=map.getAssocByID(assocs[a])
		if (assoc&&assoc.instanceOf!='at-subclassof') {
		    return true
		}
	}
	//return (assocIndex[id].length>0)
	return false
}



/* ==================================================
	A simple node hierarchy to be used for building
	hierarchical lists and structures from relationships
   ====================================================== */
function node(Topic){
	this.children=[]
	this.topic=Topic||null
}

node.prototype.getChildren=_get_children
node.prototype.addChild=_add_child
node.prototype.toString=_node_to_string

function _get_children(){
	return this.children
}

function _add_child(childnode){
	this.children.push(childnode)
}

function _node_to_string(){
	return "[node for topic "+this.topic.id+" with "+this.children.length+" child nodes]"
}

// Return a tree containing the subclass tree for a topic
// Let's hope there are no cycles, because we don't look for them.
function subclassTree(map,Node){
	
    var a,assoc,assocs,newassocs=[]
	var mem,player
	var k,kids
	var id

	// Get subclass associations for the topic
	id=Node.topic.id
	assocs=map.getAssocByType('at-subclassof')
	for (a in assocs) {
		assoc=assocs[a]
		mem=assoc.getMemberByRoleType('rt-superclass')
		if (!mem){continue}
		
	    player=mem.getPlayers()[0]
		if (player.id!=id) {// This topic plays the superclass role?
			continue
		}
		mem=assoc.getMemberByRoleType('rt-subclass')
		player=mem.getPlayers()[0] // Assume only one subclass per association
		Node.addChild(new node(player))
	}

	kids=Node.getChildren()
	for (k in kids){
		subclassTree(map,kids[k])
	}
}

/* 
	Add a hierarchical tree of descendents of a topic to the Node parameter.
	The association type and role types for the hierarchy are
	passed in as parameters.
	Let's hope there are no cycles, because we don't look for them.
*/
function hierarchyTree(map,Node,
	association_type,
	super_role_type,
	sub_role_type){
	
    var a,assoc,assocs,newassocs=[]
	var mem,player,players
	var k,kids,p
	var id

	if (!Node){
		return
	}
	// Get specified associations for the topic
	id=Node.topic.id
	assocs=map.getAssocByType(association_type)
	for (a in assocs) {
		assoc=assocs[a]
		mem=assoc.getMemberByRoleType(super_role_type)
		if (!mem){continue}
		
	    // Only work with this assoc. if the topic plays the ancestor role
		player=mem.getPlayers()[0]
		if (player.id!=id) {
			continue
		}

		mem=assoc.getMemberByRoleType(sub_role_type)
		players = mem.getPlayers()

		for (p=0; p<players.length;p++) {
		    player=players[p]
			Node.addChild(new node(player))
		}
	}

	kids=Node.getChildren()
	for (k in kids){
		hierarchyTree(map,kids[k],association_type,super_role_type,
			sub_role_type)
	}
}

/* 
	Return a reverse hierarchical tree of ancestors of a topic.
	The association type and role types for the hierarchy are
	passed in as parameters.  The bottom node will be the highest topic
	in the chain of associations, and conversely.
	Let's hope there are no cycles, because we don't look for them.
*/
function hierarchyAncestorTree(map,Node,	
	association_type,
	super_role_type,
	sub_role_type){
	
    var a,assoc,assocs
	var mem,player,players
	var k,kids,p
	var id

	var found_player = false

	if (!Node){
		return
	}
	id=Node.topic.id

	// Get associations of specified type
	assocs=map.getAssocByType(association_type)

	// find ancestor of current topic in the hierarchy
	for (a in assocs) {
		assoc=assocs[a]
		mem=assoc.getMemberByRoleType(sub_role_type)
		if (!mem){continue}
		
	    // Only work with this assoc if the topic plays the child role
		players=mem.getPlayers()
		for (p=0;p < players.length;p++){
			found_player = (players[p].id == id)
			if (found_player){
				break
			}
		}
		if (!found_player) {
			continue
		}

		mem=assoc.getMemberByRoleType(super_role_type)
		players = mem.getPlayers()
//alert(players.length.toString() + ' players found for ' + assoc.id)
		player=players[0] // Assume only one super per association
		Node.addChild(new node(player))

		// We have found the (or **a**) ancestor, no meed to keep looking
		break
	}

	kids=Node.getChildren()
	//for (k in kids){
		hierarchyAncestorTree(map,kids[0],association_type,super_role_type,
			sub_role_type)
	//}
}

/*	Depth-first traverse of a subtree starting at Node,
	which is a node object. At every step, 
	func(Map,Node,depth) is executed.
	Returns a string. */
function walkHierarchy(map,Node,func,depth){
	var depth=depth||0
	var k,kids
	var str=''

	kids=Node.getChildren()
	for (k in kids){
		str+=func(map,kids[k],depth)
		str+=walkHierarchy(map,kids[k],func,depth+1)
	}
	return str
}

// Sorted version
function walkHierarchySort(map,Node,func,depth){
	var depth=depth||0
	var k,kids,kid
	var Topic,names,label,n
	var namedict={},namelist=[]
	var str=''

	kids=Node.getChildren()

	// Sort kids by name; allow for duplicates
	for (k in kids) {
		kid=kids[k]
	    Topic=kid.topic
		names=Topic.getNamesFiltered()
		if (names&&names.length) {
		    label=names[0].name
		}
		else {
		    label=Topic.id
		}
		if (!namedict[label]) {
			namedict[label]=[]
		}
		namedict[label].push(kid)
	}
	
	for (n in namedict) {
	   namelist.push(n) 
	}
	namelist.sort()

	for (n in namelist) {
		kids=namedict[namelist[n]]
		for (k in kids) {
			str+=func(map,kids[k],depth)
			str+=walkHierarchySort(map,kids[k],func,depth+1)
		}
	}
	return str
}

/*	Depth-first reverse traverse of a subtree starting at Node,
	which is a node object. Node is at the top, but we need to 
	start at the bottom.

	Assumes that and mode can only have a single child - this is OK
	because the function is intended to find a chain of ancestors, for
	which this assumption will be correct.

	At every step, func(Map,Node,depth) is executed.
	Returns a string. */
function walkHierarchyReverse(map,Node,func,depth){
	var depth=depth||0
	var k,kids, kid
	var str=''
	var ancestor_collection = []

	ancestor_collection.push(Node)

	kids=Node.getChildren()
	while (kids.length){
		kid = kids[0]
		ancestor_collection.push(kid)
		kids = kid.getChildren()
	}

	ancestor_collection.reverse()
	var node
	for (var n = 0;n<ancestor_collection.length;n++){
		node=ancestor_collection[n]
		str+=func(map,node,n)
	}
	return str
}

/* ===========================================================
	Add a subclass association instance, including members 
   =========================================================== */
function buildSubclassAssoc(map,associd){
	if (!map){return}

	a1=new association(associd)
	a1.instanceOf='at-subclassof'
	mem=new member('rt-superclass')
	a1.addMember(mem)

	mem=new member('rt-subclass')
	a1.addMember(mem)

	map.addAssoc(a1)
}

/* =============================================================
	Add a subclass association instance, including role players 
   ============================================================= */
function buildSubclassAssoc_players(map,associd,superclass_topic_id,subclass_topic_id){
	if (!map){return}

	var a1=new association(associd)
	a1.instanceOf='at-subclassof'
	var mem=new member('rt-superclass')
	mem.addPlayer(map.getTopicById(superclass_topic_id))
	a1.addMember(mem)

	mem=new member('rt-subclass')
	mem.addPlayer(map.getTopicById(subclass_topic_id))
	a1.addMember(mem)

	map.addAssoc(a1)
}

function createNewSubtype(map,id_super,id_sub,id_assoc){
	var id_assoc=id_assoc||''
	var newassoc,mem
	var form=document.topics

	if (!(id_super&&id_sub)){return}

	// Check for duplicate id
	var assoc = top.tm1.getAssocByID()
	if (assoc && (id_assoc==assoc.id)){
		alert('This ID is in use - choose another')
		return
	}

	newassoc=new top.association(id_assoc)
	newassoc.instanceOf='at-subtype'

	mem=new top.member('rt-supertype')
	mem.addPlayer(top.tm1.getTopicById(id_super))
	newassoc.addMember(mem)

	mem=new top.member('rt-subtype')
	mem.addPlayer(top.tm1.getTopicById(id_sub))
	newassoc.addMember(mem)

	map.addAssoc(newassoc)
}

function createNewSubclass(map,id_super,id_sub,id_assoc){
	var id_assoc=id_assoc||''
	var newassoc,mem
	var form=document.topics

	if (!(id_super&&id_sub)){return}

	// Check for duplicate id
	if (id_assoc==top.tm1.getAssocByID.id){
		alert('This ID is in use - choose another')
		return
	}

	newassoc=new top.association(id_assoc)
	newassoc.instanceOf='at-subclassof'

	mem=new top.member('rt-superclass')
	mem.addPlayer(top.tm1.getTopicById(id_super))
	newassoc.addMember(mem)

	mem=new top.member('rt-subclass')
	mem.addPlayer(top.tm1.getTopicById(id_sub))
	newassoc.addMember(mem)

	map.addAssoc(newassoc)
}

// Compare function for sorting list of topic objects by basename
function compare_topics(a,b){
	var nameA,nameB
	var labelA, labelB

	nameA = a.getNamesFiltered()
	nameA = nameA && nameA[0]
	labelA = nameA && nameA.getNameString()
	if (!labelA) {return 0}

	nameB = b.getNamesFiltered()
	nameB = nameB && nameB[0]
	labelB = nameA && nameB.getNameString()
	if (!labelB) {return 0}

	labelA = labelA.toLowerCase()
	labelB = labelB.toLowerCase()

	if (labelA < labelB) {return -1}
	if (labelA > labelB) {return 1}
	return 0
}

/*
	Return the nameString of the first baseName of the given topic object.
*/
function getTopicLabel(topic) {
	if (!topic) {return ''}

	var name
	var label

	name = topic.getNamesFiltered()
	name = name && name[0]
	label = name && name.getNameString()
	label = label ||('[' + topic.id + ']')
	return label
}

/*
	Create an index of topic ids keyed by the topic namestring.
	May optionally be filtered by a topic type id.
*/
function buildTopicIdIndex(map, topic_type_id) {
	if (!map){ return {}}

	var topic_type = topic_type_id
	if (!topic_type){
		topic_type = ''
	}
	var index = {}
	var topics
	var topic
	var label

	if (topic_type){
		topics = map.getTopicsByType(topic_type)
		for (var t = 0; t < topics.length; t++) {
			topic = topics[t]
			label = getTopicLabel(topic)
			index[label] = topic.id
		}
	}
	else {
		topics = map.getTopics()
		for (t in topics) {
			topic = topics[t]
			label = getTopicLabel(topic)
			if (label) {
				index[label] = t
			}
		}
	}

	return index
}

/*
	Create an index of topic objects keyed by the topic namestring.
	May optionally be filtered by a topic type id.
*/
function buildTopicIndex(map, topic_type_id) {
	if (!map){ return {}}

	var topic_type = topic_type_id
	if (!topic_type){
		topic_type = ''
	}
	var index = {}
	var topics
	var topic
	var label

	if (topic_type){
		topics = map.getTopicsByType(topic_type)
		for (var t = 0; t < topics.length; t++) {
			topic = topics[t]
			label = getTopicLabel(topic)
			index[label] = topic
		}
	}
	else {
		topics = map.getTopics()
		for (t in topics) {
			topic = topics[t]
			label = getTopicLabel(topic)
			if (label) {
				index[label] = topic
			}
		}
	}

	return index
}

function getAssocsForTopicByAssoctype(map, topicid, assoc_type) {
	var assoclist = map.getAssocByType(assoc_type)
	var associndex = map.getAssocIndex()
	var topicassocs = associndex[topicid]

	// topicassocs contains association ids
	// assoclist contains associations - make a list of ids
	var assoc_ids = []
	for (var a in assoclist) {
		assoc_ids.push(assoclist[a].id)
	}

	return intersection(topicassocs,assoc_ids)
}

/* Create a new topic map that is the equivalent of Patric Stickler's
   "Concise Bounded Description".  Given a topic id, the new map contains:
      1. The topic for that id, including its base names and occurrences.
	  2. The topic types for all occurrences.
	  3. All associations in which our topic plays a role.
	  4. All other topics that play a role in those associations.
	  5. All scoping topics that scope basenames, associations, or
	     occurrences that we have included.

	Basically, this includes everything related to the topic of interest
	to a depth of one.

	Collecting the scoping topics is TBD.

	Input parameters -
	   tm = a topic map object
       id = id of the topic of interest.
*/
function conciseBoundedDescription(tm, id) {
	if (!tm){ return }
	var theTopic = tm.getTopicById(id)
		  
	// Get topic of this topic's type
	var type_id
	type_id = theTopic.instanceOf
	var parent_type = type_id && tm.getTopicById(type_id)

	// Get all associations in which this topic plays a role
	var assoc_index = tm.getAssocIndex(id)
	var assocs = assoc_index[id]

	// Get the role type topics for each role in every association
	var roleid
	var assoc
	var members
	var member_id
	var role_id_list = []
	var role_topic_ids = {}
	var role_id
	for (var a in assocs) {
		assoc = tm.getAssocByID(assocs[a])
		members = assoc.getMembers()
		for (var m in members) {
			role_id = members[m].roleSpec || 'tt-urtype'
			role_topic_ids[role_id] = true
			role_id_list.push(role_id)
		}
	}

	// Get all occurrence types for our topic
	var occurs = theTopic.getOccursFiltered()
	var occur_type_id
	var occur_type
	var occur_list = []
	for (var o in occurs) {
		occur_type_id = occurs[o].instanceOf
		occur_type = tm.getTopicById(occur_type_id)
		occur_list.push(occur_type)
	}

	// Get all scoping topics in names, occurrences, and associations
	// ....

	// Create new topic map with just these topics and associations
	var map = new Home.topicMap('extracted')
	if (parent_type) {map.addTopic(parent_type)}
	map.addTopic(theTopic)

	var assoc_type
	var added_players = {}
	var member
	var players
	var player
	var player_id
	for (var a in assocs) {
		assoc = tm.getAssocByID(assocs[a])
		map.addAssoc(assoc)
		assoc_type = tm.getTopicById(assoc.instanceOf)
		if (assoc_type) {map.addTopic(assoc_type)}
		var members = assoc.getMembers()
		for (var m in members){
			member = members[m]
			players = member.getPlayers()
			for (var p in players) {
				player = players[p]
				if (player.id != theTopic.id  && !added_players[player.id]) {
					map.addTopic(player)
					added_players[player.id] = true
				}
			}
		}
	}

	var role
	for (var r in role_topic_ids) {
		role = tm.getTopicById(r)
		map.addTopic(role)
	}

	for (var o in occur_list) {
		occur_type = occur_list[o]
		map.addTopic(occur_type)
	}

	return map
}