You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

266 lines
4.7 KiB

//
// node.cpp
// 234Tree
//
// Created by Minseok Choi on 21/10/2017.
// Copyright © 2017 Minseok Choi. All rights reserved.
//
#include "node.h"
queue<node*> node::q;
node::node(){}
node::node(int ele){
elements[1] = ele;
elements[SIZE]++;
}
node::node(int* eles, node** cd){
elements[SIZE] = eles[SIZE];
if(cd[0]!=NULL){
children[0] = cd[0];
children[0]->parent = this;
}
for (int i=1; i<=elements[SIZE]; i++) {
elements[i] = eles[i];
if(cd[i]){
children[i] = cd[i];
children[i]->parent = this;
}
}
}
string node::getStringAllElements(){
if (elements[SIZE]==0) {
return "elements not found";
}
string e = "(";
int i=1;
for (; i<elements[SIZE]; i++) {
e += to_string(elements[i]) + " ";
}
e += to_string(elements[i]) + ")";
return e;
}
node* node::getParent(){
return parent;
}
void node::setParent(node* n){
parent = n;
}
node* node::getChild(int idx){
return children[idx];
}
node* node::addChild(int idx, node* child){
int i = elements[SIZE];
for (; i>=idx; i--) {
children[i+1] = children[i];
children[i] = NULL;
}
children[idx] = child;
if(child!=NULL) children[idx]->parent = this;
return 0;
}
int* node::getElementsAll(){
return elements;
}
node** node::getChildrenAll(){
return children;
}
int node::getIdxOnParent(){
int myidx = 0;
while (1) {
if(parent->getChild(myidx)==this) break;
myidx++;
}
return myidx;
}
int node::getSize(){
return elements[SIZE];
}
int node::getSiblingNum(){
return parent->getSize()+1;
}
int node::getFirstElement(){
return elements[1];
}
node* node::getSibling(){
int myidx = getIdxOnParent();
if(myidx==0) return parent->getChild(myidx+1);
if (myidx==parent->getSize()) return parent->getChild(myidx-1);
int siblingOffset = parent->getChild(myidx+1)->getSize() > parent->getChild(myidx-1)->getSize() ? 1 : -1;
return parent->getChild(myidx+siblingOffset);
}
int node::addElement(int ele){
if(elements[SIZE]==4) return -1;
int i = elements[SIZE];
for (; i>SIZE; i--) {
if (elements[i] >= ele) {
elements[i+1] = elements[i];
if(children[i] != NULL) {
children[i+1] = children[i];
children[i] = NULL;
}
continue;
}
else break;
}
elements[i+1] = ele;
elements[SIZE]++;
return 0;
}
int node::addElementByIdx(int ele, int idx){
int i = elements[SIZE];
for (; i>idx; i--) {
if (elements[i] >= ele) {
elements[i+1] = elements[i];
children[i+1] = children[i];
children[i] = NULL;
continue;
}
else break;
}
elements[i+1] = ele;
elements[SIZE]++;
return 0;
}
int node::eliminateElement(int ele){
int size = elements[SIZE];
if(size==0) return -1;
int i=1;
for (; i<size; i++) {
if (elements[i]<ele) continue;
elements[i] = elements[i+1];
children[i] = children[i+1];
children[i+1] = NULL;
}
elements[SIZE]--;
return 0;
}
int node::eliminateElementByIdx(int idx, int direc){
int size = elements[SIZE];
int dltedEle = elements[idx];
for (int i=idx; i<size+1; i++) {
elements[i] = elements[i+1];
if (direc==FOR_FUSION) {
children[i] = children[i+1];
children[i+1] = NULL;
} else {
if (i==size && direc==FOR_TRANSFER_RIGHT) break;
children[i-1] = children[i];
children[i] = NULL;
}
}
elements[SIZE]--;
return dltedEle;
}
int node::changeElement(int ori, int src){
int size = elements[SIZE];
for (int i=1; i<size+1; i++) {
if (elements[i] == ori) {
elements[i] = src;
break;
}
}
return 0;
}
int node::changeElementByIdx(int oriIdx, int src){
int oriEle = elements[oriIdx];
elements[oriIdx] = src;
return oriEle;
}
int node::split(){
int ele1[3], ele2[2];
node* cd1[3], *cd2[2];
ele1[SIZE] = 2;
cd1[0] = children[0];
for (int i=1; i<3; i++) {
ele1[i] = elements[i];
cd1[i] = children[i];
}
node* child1 = new node(ele1, cd1);
q.push(child1);
ele2[SIZE] = 1;
ele2[1] = elements[4];
cd2[0] = children[3];
cd2[1] = children[4];
node* child2 = new node(ele2, cd2);
q.push(child2);
return elements[3];
}
int node::addChildFromQueue(node* n){
if (q.empty()) return -1;
int idxFirstNull = 0;
while(1){
if (n->children[idxFirstNull] == NULL) break;
else idxFirstNull++;
}
if(idxFirstNull==0){
n->children[idxFirstNull] = q.front(); q.pop();
n->children[idxFirstNull]->setParent(n);
n->children[idxFirstNull+1] = q.front(); q.pop();
n->children[idxFirstNull+1]->setParent(n);
} else {
n->children[idxFirstNull-1] = q.front(); q.pop();
n->children[idxFirstNull-1]->setParent(n);
n->children[idxFirstNull] = q.front(); q.pop();
n->children[idxFirstNull]->setParent(n);
}
return 0;
}