tree.cc

对ns2软件进行UMTS扩展

/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */

/* By Pablo Martin and Paula Ballester,
 * Strathclyde University, Glasgow.
 * June, 2003.
*/

/* Copyright (c) 2003 Strathclyde University of Glasgow, Scotland.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code and binary code must contain
 * the above copyright notice, this list of conditions and the following
 * disclaimer.
 *
 * 2. All advertising materials mentioning features or use of this software
 * must display the following acknowledgement:
 * This product includes software developed at Strathclyde University of
 * Glasgow, Scotland.
 *
 * 3. The name of the University may not be used to endorse or promote
 * products derived from this software without specific prior written
 * permission.
 * STRATHCLYDE UNIVERSITY OF GLASGOW, MAKES NO REPRESENTATIONS
 * CONCERNING EITHER THE MERCHANTABILITY OF THIS SOFTWARE OR THE
 * SUITABILITY OF THIS SOFTWARE FOR ANY PARTICULAR PURPOSE.  The software
 * is provided "as is" without express or implied warranty of any kind.
*/

#include <stdlib.h>
#include <stdio.h>
#include "tree.h"

tree::tree()
{
  root=NULL;
  left=NULL;
  right=NULL;
  up=NULL;
  next=NULL;
}

tree::tree(int maxsf)
{
  root=NULL;
  left=NULL;
  right=NULL;
  up=NULL;
  next=NULL;
  build_tree(maxsf);
}


int tree::check(void)
{
  if (root->source_ == -1) {
	if (right != NULL) {
		if ((right->check()) && (left->check()))
			return(1);
		else
			return(0);
	} else
		return(1);
  } else
  	return (0);
}


int tree::insert_sf(int source, int sf)
{
  int temp = 0;
  return (insert(source, sf, temp));
}

int tree::insert(int source, int sf, int &temp)
{
  // comprobamos temp
  if (root->sf_ < temp) {
	temp = root->sf_;
	if (next != NULL) {
		return(next->insert(source, sf, temp));
	} else if (up != NULL) {
		return(up->insert(source, sf, temp));
	} else {
		return(0);
	}
  } else {
	// bajar hasta sf comprobando que el camino esta libre
	// nosotros
	if (root->source_ != -1) {
		if (next != NULL) {
			return(next->insert(source, sf, temp));
		} else if (up != NULL) {
			temp = root->sf_;
			return(up->insert(source, sf, temp));
		}
	} else {
		if (sf == root->sf_) {
			if (check()) {
				root->source_ = source;
				return(1);
			} else {
				// movernos hacia la izquierda y si no se puede, hacia arriba ?????
				if (next != NULL) {
					return(next->insert(source, sf, temp));
				} else if (up != NULL) {
					temp = root->sf_;
					return(up->insert(source, sf, temp));
				}else {
					return(0);
				}
			}
		} else {
			// hacia abajo
			if (right != NULL) {
				temp = root->sf_;
				return(right->insert(source, sf, temp));
			} else {
				return (0);
			}
		}
	}
  }


}

node *tree::search(int source, int sf, int &temp)
{
  if (sf == root->sf_) {
  	if (source == root->source_) {
		return(root);
	} else {
		temp = root->sf_;
		if (next != NULL) {
			return(next->search(source, sf, temp));
		} else if (up != NULL) {
			return(up->search(source, sf, temp));
		} else {
			return(NULL);
		}
	}
  } else if (sf > root->sf_) {
	if (temp < root->sf_){
		if (right != NULL) {
			temp = root->sf_;
			return(right->search(source, sf, temp));
		}
	} else {
		temp = root->sf_;
		if (next != NULL) {
			return(next->search(source, sf, temp));
		} else if (up != NULL) {
			return(up->search(source, sf, temp));
		} else {
			return(NULL);
		}
	}
  }

}

int tree::remove_sf(int source, int sf)
{
  int temp = 0;
  node *leaf = search(source, sf, temp);
  if (leaf != NULL) {
	leaf->source_ = -1;
	return (1);
  }
  return (0);
}

void tree::build_nodes(int sf, int k, int deep, int maxsf)
{
  if(root==NULL) {
  	root=new node;
  }
  root->source_=-1;
  root->sf_=sf;
  root->k_=k;
  root->deep_=deep;

  // hacia abajo
  if (root->sf_ < maxsf) {
    right = new tree();
    right->up = this;
    right->build_nodes(sf*2, (2*k), (deep + 1), maxsf);
    left = new tree();
    right->next = left;
    left->up = this;
    left->build_nodes(sf*2, (2*k + 1), (deep + 1), maxsf);
  }

  // hacia la izquierda
  if ((k < sf - 1) && (sf == 4)) {
    next = new tree;
    next->build_nodes(sf, (k + 1), deep, maxsf);
  }
  return;
}

void tree::build_tree(int maxsf)
{
  build_nodes(4, 0, 0, maxsf);
  return;
}